The complexity of the index sets of $\aleph_0$-categorical theories and of Ehrenfeucht theories
| dc.creator | Lempp, Steffen | |
| dc.creator | Slaman, Theodore A. | |
| dc.date | 2006-10-26 | |
| dc.date.accessioned | 2026-07-07T07:29:27Z | |
| dc.date.available | 2026-07-07T07:29:27Z | |
| dc.description | We classify the computability-theoretic complexity of two index sets of classes of first-order theories: We show that the property of being an $\aleph_0$-categorical theory is $Π^0_3$-complete; and the property of being an Ehrenfeucht theory $Π^1_1$-complete. We also show that the property of having continuum many models is $Σ^1_1$-hard. Finally, as a corollary, we note that the properties of having only decidable models, and of having only computable models, are both $Π^1_1$-complete. | |
| dc.identifier | https://arxiv.org/abs/math/0610776 | |
| dc.identifier | http://arxiv.org/abs/math/0610776 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/118113 | |
| dc.subject | Logic | |
| dc.subject | 03D80; 03D55 | |
| dc.title | The complexity of the index sets of $\aleph_0$-categorical theories and of Ehrenfeucht theories | |
| dc.type | text |