A fixed point for the jump operator on structures

DOI10.2178/JSL.7802050MaRDI QIDQ5300071zbMATH OpenOpenAlexFDO

Authors Antonio Montalbán

Publication date 24 June 2013

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.0908, https://projecteuclid.org/euclid.jsl/1368627058

zbMATH Keywords

computable structureeffective interpretabilityEhrenfeucht-Mostowski theoremhigher-order arithmeticjump operatorordinal indiscernibles

Mathematics Subject Classification ID

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

Abstract: Assuming that $$ exists, we prove that there is a structure that can effectively interpret its own jump. In particular, we get a structure $mathcalA$ such that [ Sp({mathcal A}) = {{�f x}':{�f x}in Sp ({mathcal A})}, ] where $Sp(mathcalA)$ is the set of Turing degrees which compute a copy of $mathcalA$. It turns out that, more interesting than the result itself, is its unexpected complexity. We prove that higher-order arithmetic, which is the union of full $n$th-order arithmetic for all $n$, cannot prove the existence of such a structure.

Recommendations

• On the First Order Theory of the Arithmetical Degrees
• DIRECT AND LOCAL DEFINITIONS OF THE TURING JUMP
• scientific article; zbMATH DE number 841083
• Definability in the Recursively Enumerable Degrees
• scientific article; zbMATH DE number 1302876
• Definability issues in the -Turing degrees
• Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers
• Biinterpretability up to double jump in the degrees below \(\mathbf{0}'\)
• On a Conjecture of Kleene and Post
• Working below a \(low_ 2\) recursively enumerable degree

Cites work

• A Jump Inversion Theorem for the Degree Spectra
• Computable structures and the hyperarithmetical hierarchy
• Fixed points for the jump operator
• Generic copies of countable structures
• scientific article; zbMATH DE number 3861143 (Why is no real title available?)
• The jump operation for structure degrees

Cited in

(12)

• Finitely generated groups are universal among finitely generated structures
• Constructing decidable graphs from decidable structures
• Effectively existentially-atomic structures
• A characterization of jump operators
• BOREL FUNCTORS AND INFINITARY INTERPRETATIONS
• On the notion of jump structure
• The tree of tuples of a structure
• Another jump inversion theorem for structures
• A Jump Inversion Theorem for the Degree Spectra
• Computable functors and effective interpretability
• EXPANDING THE REALS BY CONTINUOUS FUNCTIONS ADDS NO COMPUTATIONAL POWER
• Fixed points for the jump operator

This page was built for publication: A fixed point for the jump operator on structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300071)