Alpha recursion theory: Difference between revisions

Revision as of 05:38, 30 July 2021

Revision as of 05:39, 30 July 2021

Line 23:

Shore's density theorem: Let ''A'', ''C'' be α-regular recursively enumerable sets such that <math>\scriptstyle A <_\alpha C</math> then there exists a regular α-recursively enumerable set ''B'' such that <math>\scriptstyle A <_\alpha B <_\alpha C</math>.

Barwise has proved that the sets <math>\Sigma_1</math>-definable on <math>L_{\alpha^+}</math> are exactly the sets <math>\Pi_1^1</math>-definable on <math>L_\alpha</math>, where <math>\alpha^+</math> denotes the next admissible ordinal above <math>\alpha</math>.<ref>!--Barwise. Or T. Arai, [https://www.sciencedirect.com/science/article/pii/S0168007203000204 Proof theory for theories of ordinals - I: recursively Mahlo ordinals] (p.2). Accessed 2021-07-29.</ref>

==References==

Line 30:

* Robert Soare, ''Recursively Enumerable Sets and Degrees'', Springer Verlag, 1987 https://projecteuclid.org/euclid.bams/1183541465

* Keith J. Devlin, [https://core.ac.uk/download/pdf/30905237.pdf ''An introduction to the fine structure of the constructible hierarchy''] (p.38), North-Holland Publishing, 1974

* J. Barwise, ''Admissible Sets and Structures''. 1975

[[Category:Computability theory]]