A fixed point for the jump operator on structures
- 1 June 2013
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 78 (2) , 425-438
Abstract
Assuming that 0# exists, we prove that there is a structure that can effectively interpret its own jump. In particular, we get a structure such that where is the set of Turing degrees which compute a copy of More interesting than the result itself is its unexpected complexity. We prove that higher-order arithmetic, which is the union of full “nth-order arithmetic for all n, cannot prove the existence of such a structure.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Fixed points for the jump operatorAlgebra and Logic, 2011
- A jump inversion theorem for the semilattices of sigma-degreesSiberian Advances in Mathematics, 2010
- Relations between algorithmic reducibilities of algebraic systemsRussian Mathematics, 2009
- A Jump Inversion Theorem for the Degree SpectraJournal of Logic and Computation, 2008
- Degrees of presentability of structures. IIAlgebra and Logic, 2008
- On the Relation of Σ-Reducibility Between Admissible SetsSiberian Mathematical Journal, 2004
- On the Ershov Upper SemilatticeSiberian Mathematical Journal, 2004
- Every low Boolean algebra is isomorphic to a recursive oneProceedings of the American Mathematical Society, 1994
- Generic copies of countable structuresAnnals of Pure and Applied Logic, 1989
- Recursive pseudo-well-orderingsTransactions of the American Mathematical Society, 1968