Loading...
Please wait, while we are loading the content...
Similar Documents
COMPUTABILITY IN UNCOUNTABLE BINARY TREES
| Content Provider | Scilit |
|---|---|
| Author | Johnston, Reese |
| Copyright Year | 2019 |
| Description | Computability, while usually performed within the context of ω, may be extended to larger ordinals by means of α-recursion. In this article, we concentrate on the particular case of $ω_{1}$-recursion, and study the differences in the behavior of ${\rm{\Pi }}_1^0$ -classes between this case and the standard one.Of particular interest are the ${\rm{\Pi }}_1^0$ -classes corresponding to computable trees of countable width. Classically, it is well-known that the analog to König’s Lemma—“every tree of countable width and uncountable height has an uncountable branch”—fails; we demonstrate that not only does it fail effectively, but also that the failure is as drastic as possible. This is proven by showing that the $ω_{1}$-Turing degrees of even isolated paths in computable trees of countable width are cofinal in the ${\rm{\Delta }}_1^1\,{\omega _1}$ -Turing degrees.Finally, we consider questions of nonisolated paths, and demonstrate that the degrees realizable as isolated paths and the degrees realizable as nonisolated ones are very distinct; in particular, we show that there exists a computable tree of countable width so that every branch can only be $ω_{1}$-Turing equivalent to branches of trees with ${\aleph _2}$ -many branches. |
| Related Links | http://pdfs.semanticscholar.org/0d97/b5b7ff71910dc5ea9d7df0bcfe2b9b08d7e3.pdf https://www.cambridge.org/core/services/aop-cambridge-core/content/view/B8CCE51CE8497B45A0CFB7A06CCAA4DB/S0022481219000057a.pdf/div-class-title-computability-in-uncountable-binary-trees-div.pdf |
| Ending Page | 1098 |
| Page Count | 50 |
| Starting Page | 1049 |
| ISSN | 00224812 |
| e-ISSN | 19435886 |
| DOI | 10.1017/jsl.2019.5 |
| Journal | The Journal of Symbolic Logic |
| Issue Number | 3 |
| Volume Number | 84 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2019-09-01 |
| Access Restriction | Open |
| Subject Keyword | The Journal of Symbolic Logic Admissible Recursion Theory |
| Content Type | Text |
| Resource Type | Article |
| Subject | Philosophy Logic |
