The complexity of the index sets of $\aleph_0$-categorical theories and of Ehrenfeucht theories

Details The complexity of the index sets of $\aleph_0$-categorical theories and of Ehrenfeucht theories The complexity of the index sets of $\aleph_0$-categorical theories and of Ehrenfeucht theories

2006-10-26

arxiv.org/abs/math/0610776v1

Mathematics

Logic

Scientific paper

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 $\Pi^0_3$-complete; and the property of being an Ehrenfeucht theory $\Pi^1_1$-complete. We also show that the property of having continuum many models is $\Sigma^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 $\Pi^1_1$-complete.

Affiliated with

Also associated with

No associations

Rating

The complexity of the index sets of $\aleph_0$-categorical theories and of Ehrenfeucht theories does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The complexity of the index sets of $\aleph_0$-categorical theories and of Ehrenfeucht theories, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The complexity of the index sets of $\aleph_0$-categorical theories and of Ehrenfeucht theories will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-114556