The Role of True Finiteness in the Admissible Recursively Enumerable Degrees
Seiten
2006
American Mathematical Society (Verlag)
978-0-8218-3885-3 (ISBN)
American Mathematical Society (Verlag)
978-0-8218-3885-3 (ISBN)
- Titel ist leider vergriffen;
keine Neuauflage - Artikel merken
Discusses both codings of models of arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees. This title shows that if an admissible ordinal $/alpha$ is effectively close to $/omega$ then such constructions may be performed in the $/alpha$-r.e. degrees, but otherwise they fail.
When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of $/alpha$-finiteness. As examples we discuss both codings of models of arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees.We show that if an admissible ordinal $/alpha$ is effectively close to $/omega$ (where this closeness can be measured by size or by confinality) then such constructions may be performed in the $/alpha$-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natural elementary differences between the structures of $/alpha$-r.e. degrees for various classes of admissible ordinals $/alpha$. Together with coding work which shows that for some $/alpha$, the theory of the $/alpha$-r.e. degrees is complicated, we get that for every admissible ordinal $/alpha$, the $/alpha$-r.e. degrees and the classical r.e. degrees are not elementarily equivalent.
When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of $/alpha$-finiteness. As examples we discuss both codings of models of arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees.We show that if an admissible ordinal $/alpha$ is effectively close to $/omega$ (where this closeness can be measured by size or by confinality) then such constructions may be performed in the $/alpha$-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natural elementary differences between the structures of $/alpha$-r.e. degrees for various classes of admissible ordinals $/alpha$. Together with coding work which shows that for some $/alpha$, the theory of the $/alpha$-r.e. degrees is complicated, we get that for every admissible ordinal $/alpha$, the $/alpha$-r.e. degrees and the classical r.e. degrees are not elementarily equivalent.
Introduction Coding into the R. E. degrees Coding effective successor models A negative result concerning effective successor models A nonembedding result Embedding the 1-3-1 lattice Appendix A. Basics Appendix B. The jump Appendix C. The projectum Appendix D. The admissible collapse Appendix E. Prompt permission Appendix. Bibliography.
Erscheint lt. Verlag | 1.5.2006 |
---|---|
Reihe/Serie | Memoirs of the American Mathematical Society |
Verlagsort | Providence |
Sprache | englisch |
Gewicht | 227 g |
Themenwelt | Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre |
ISBN-10 | 0-8218-3885-7 / 0821838857 |
ISBN-13 | 978-0-8218-3885-3 / 9780821838853 |
Zustand | Neuware |
Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
Buch | Softcover (2024)
World Scientific Publishing Co Pte Ltd (Verlag)
31,15 €
what we have that machines don't
Buch | Softcover (2024)
Profile Books Ltd (Verlag)
13,70 €
how simple questions lead us to mathematics’ deepest truths
Buch | Softcover (2024)
Profile Books Ltd (Verlag)
13,70 €