The elementary theory of the recursively enumerable degrees is not \(\aleph _ 0\)-categorical (Q802550): Difference between revisions

By this paper the authors give the negative answer to the question: ''Is Th(\({\mathcal R})\), the elementary theory of the ordering of the recursively enumerable degrees, \(\aleph_ 0\)-categorical?'' For proving this result, the authors first specify a sequence of finite lattices \({\mathcal P}_ n\) (n\(\geq 0)\) generated by three elements, and then show that all these lattices \({\mathcal P}_ n\) can be embedded (as lattices) into \({\mathcal R}\), the partially ordered set of r.e. degrees. Thus, Th(\({\mathcal R})\) has infinitely many distinct 3-types, and from this the above negative answer follows. The proof of the embedding of \({\mathcal P}_ n\) into \({\mathcal R}\) is very delicate.