×

A fixed point for the jump operator on structures. (English) Zbl 1305.03036

For a language \(L\), the jump of an \(L\)-structure \(\mathcal A\) is the structure \({\mathcal A}'\) obtained by adding all relations to \(\mathcal A\) that are definable by the computably infinitary \(\Sigma_1\) formulas in the language \(L\). The degree spectrum \(\mathrm{Sp}(\mathcal{A})\) of a structure \(\mathcal{A}\) is the set of Turing degrees that compute a copy of \(\mathcal{A}\). The main result of the paper is the following theorem proved in ZFC+“\(0^{\#}\) exists”:
Theorem 1.4. There is a structure \(\mathcal{A}\) such that \(\mathrm{Sp}({\mathcal A})=\mathrm{Sp}({\mathcal A}')\).
The corresponding structure \(\mathcal A\) is obtained using the Ehrenfeucht-Mostowski theorem. The author notes that Theorem 1.4 was independently proved by V. G. Puzarenko [Algebra Logic 50, No. 5, 418–438 (2011); translation from Algebra Logika 50, No. 5, 615–646 (2011; Zbl 1266.03052)] within ZFC by means of quite different tools. The existence of a structure \(\mathcal A\) in Theorem 1.4 can not be proved in higher-order arithmetic, which is the union of full \(n\)th-order arithmetics for all \(n\) (i.e., the theory of the structure \((\omega,{\mathcal P}(\omega),{\mathcal P}({\mathcal P}(\omega)),\ldots;0,1,+,\times,<,\in)\)). Namely, the following theorem is proved in full second-order arithmetic:
Theorem 1.5. The existence of a structure \(\mathcal A\) with \(\mathrm{Sp}({\mathcal A})=\mathrm{Sp}({\mathcal A}')\) implies the consistency of higher-order arithmetic.

MSC:

03C57 Computable structure theory, computable model theory
03F35 Second- and higher-order arithmetic and fragments

Citations:

Zbl 1266.03052
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] Effective model theory via the {\(\sigma\)}-definability approach
[2] SibirskiǏ MatematicheskiǏ Zhurnal 45 pp 211– (2004)
[3] Algebra Logika 47 pp 131– (2008)
[4] Izvestiya Vysshikh Uchebnykh ZavedeniǏ. Matematika 53 pp 71– (2009)
[5] DOI: 10.1090/S0002-9947-1968-0244049-7
[6] A note on the hyperarithmetical hierarchy 35 pp 429– (1970)
[7] DOI: 10.1090/S0002-9939-1994-1203984-4
[8] Constructibility (1984) · Zbl 0542.03029
[9] Effective model theory vs. recursive model theory 55 pp 1168– (1990)
[10] DOI: 10.1007/s00153-004-0245-z · Zbl 1089.03034
[11] Computable structures and the hyperarithmetical hierarchy 144 (2000) · Zbl 0960.03001
[12] DOI: 10.1016/0168-0072(89)90015-8 · Zbl 0678.03012
[13] Algebra Logika 46 pp 793– (2007)
[14] DOI: 10.1093/logcom/exn024 · Zbl 1165.03018
[15] Computation and logic in the real world, CiE 2007 4497 pp 716– (2007)
[16] DOI: 10.1007/s10469-011-9153-6 · Zbl 1266.03052
[17] SibirskiǏ MatematicheskiǏ Zhurnal 50 pp 415– (2009)
[18] SibirskiǏ MatematicheskiǏ Zhurnal 45 pp 634– (2004)
[19] Notre Dame Journal of Formal Logic (2010)
[20] Mathematical theory and computational practice, CiE 2009 5635 pp 372– (2009)
[21] DOI: 10.3103/S1055134410010037
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.