Interpreting true arithmetic in the local structure of the enumeration degrees. (English) Zbl 1257.03066

In the paper the enumeration reducibility and the induced structure of the enumeration degrees are considered. It is shown that the theory of the local structure of the enumeration degrees is computably isomorphic to the theory of first-order arithmetic. The methods used to prove the main result rely on the notion of an \({\mathcal H}\)-pair introduced by Kalimullin and used to show the definability of the enumeration jump operation. Using this notion, a novel coding method is introduced to code a large class of countable relations.


03D30 Other degrees and reducibilities in computability and recursion theory
03F30 First-order arithmetic and fragments
Full Text: DOI Euclid


[1] Journal of the London Mathematical Society 24 pp 1– (1981)
[2] DOI: 10.1090/S0002-9947-1968-0220595-7
[3] DOI: 10.1007/BF00739571 · Zbl 0846.03017
[4] DOI: 10.1016/S0049-237X(08)71260-6
[5] Interpreting true arithmetic in the -enumeration degrees 75 pp 522– (2010)
[6] Annals of Mathematics 105 pp 121– (1997)
[7] DOI: 10.1142/S0219061303000285 · Zbl 1049.03030
[8] Splitting properties of n-c.e. enumeration degrees 67 pp 537– (2002)
[9] DOI: 10.1093/logcom/exq042 · Zbl 1260.03077
[10] Cupping and definability in the local structure of the enumeration degrees 77 pp 133– (2012)
[11] DOI: 10.1002/malq.19590050703 · Zbl 0108.00602
[12] Handbook of computability theory pp 121– (1999)
[13] Recursion theory week, Oberwolfach 1989 1432 pp 57– (1990)
[14] Partial degrees and the density problem. Part 2: The enumeration degrees of the 1.2 sets are dense 49 pp 503– (1984)
[15] DOI: 10.1090/conm/257/04043
[16] Complexity, logic and recursion theory pp 303– (1997)
[17] DOI: 10.1007/s001530050064 · Zbl 0906.03043
[18] DOI: 10.1112/S002461159800046X · Zbl 0904.03028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.