Skip to main content
SpringerLink
Log in

The jump operation for structure degrees

  • Published:
Archive for Mathematical Logic Aims and scope Submit manuscript

Abstract

One of the main problems in effective model theory is to find an appropriate information complexity measure of the algebraic structures in the sense of computability. Unlike the commonly used degrees of structures, the structure degree measure is total. We introduce and study the jump operation for structure degrees. We prove that it has all natural jump properties (including jump inversion theorem, theorem of Ash), which show that our definition is relevant. We study the relation between the structure degree jump (in the sense of Soskov) and the jump degrees of a structure (in the sense of Jockusch) and give necessary and sufficient conditions for their existence in the terms of structure degrees. We show some properties, distinguishing the structure degrees from the enumeration degrees.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Angelov, I.: Enumerable relations of structure degrees coding. Master's thesis, Sofia University, 1999 (in Bulgarian)

  2. Ash, C.J.: Recursive labeling systems and stability of recursive structures in hyperarithmetical degrees. Trans. Amer. Math. Soc. 298, 497–514 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  3. Ash, C.J.: Generalizations of enumeration reducibility using recursive infinitary propositional sentences. Ann. Pure Appl. Logic 58, 173–184 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  4. Ash, C.J., Jockusch, C., Knight, J.F.: Jumps of orderings. Trans. Amer. Math. Soc. 319, 573–599 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  5. Baleva, V.: Regular enumerations for abstract structures. Ann. Univ. Sofia 93, 39–48 (1999)

    Google Scholar 

  6. Baleva, V.: Structure degree jump. PhD thesis, Sofia University, 2001 (in Bulgarian)

  7. Bouchkova, V.: Relative set genericity. To appear in Ann. Univ. Sofia, 2002

  8. Case, J.: Maximal arithmetical reducibilities. Z. Math. Logik Grundlag. Math. 20, 261–270 (1974)

    MATH  MathSciNet  Google Scholar 

  9. Coles, R., Downey, R., Slaman, T.: Every set has a least jump enumeration. Journal of London Math. Soc. 62 (2), 641–649 (2000)

    Article  MathSciNet  Google Scholar 

  10. Cooper, S.B.: Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense. J. Symbolic Logic 49, 503–513 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  11. Cooper, S.B.: Enumeration reducibilty, nondeterministic computations and relative computability of partial functions. In: Ambos-Spies, K., Muler, G., Sacks, G.E. (eds), Recursion theory week, Oberwolfach 1989, vol. 1432 of Lecture notes in mathematics, Heidelberg, Springer-Verlag, 1990, pp 57–110,

  12. Downey, R.: Computability, definability and algebraic structures. In: Decheng D., et al., (ed), Proceedings of 7th and 8th Asian logic conference. World Scientific, 2003

  13. Downey, R.G., Knight, J.F.: Orderings with α-th jump degree 0( α ). Proc. Amer. Math. Soc. 114, 545–552 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  14. Jojgov, G.: Minimal pairs of structure degrees. Master's thesis, Sofia University, 1997 (in Bulgarian)

  15. Knight, J.F.: Degrees coded in jumps of orderings. J. Symbolic Logic 51, 1034–1042 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  16. Lacombe, D.: Deux généralisations de la notion de recursivité relative. C. R. de l'Academie des Sciences de Paris 258, 3410–3413 (1964)

    MATH  MathSciNet  Google Scholar 

  17. McEvoy, K.: Jumps of quasi-minimal enumeration degrees. J. Symbolic Logic 50, 839–848 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  18. Moschovakis, Y.N.: Abstract first order computability I. Trans. Amer. Math. Soc. 138, 427–464 (1969)

    Article  MATH  MathSciNet  Google Scholar 

  19. Moschovakis, Y.N.: Abstract first order computability II. Trans. Amer. Math. Soc. 138, 465–504 (1969)

    Article  MathSciNet  Google Scholar 

  20. Odifreddi, P.G.: Classical recursion theory. volume II. North–Holland, 1999

  21. Richter, L.J.: Degrees of structures. J. Symbolic Logic 46, 723–731 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  22. Rogers, Jr. H.: Theory of recursive functions and effective computability. McGraw-Hill Book Company, New York, 1967

  23. Selman, A.L.: Arithmetical reducibilities I. Z. Math. Logik Grundlag. Math. 17, 335–350 (1971)

    MATH  MathSciNet  Google Scholar 

  24. Shoenfield, J.R.: Mathematical logic. Addison-Wesley Publishing Company, 1967

  25. Skordev, D.G.: Computability in combinatory spaces. Kluwer Academic Publishers, Dordrecht – Boston – London, 1992

  26. Soskov, I.N.: A jump inversion theorem for the enumeration jump. Arch. Math. Logic 39, 417–437 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  27. Soskov, I.N.: Abstract computability and definability. Doctor habil. thesis, Sofia University, 2001 (in Bulgarian)

  28. Soskov, I.N.: Degree spectra and co-spectra of structures. To appear in Ann. Univ. Sofia, 2003

Download references

Author information

Authors and Affiliations

  1. Sofia University, Bulgaria

    V. Baleva

  2. 6, allée Martin Luther King, 76620, Le Havre, France

    V. Baleva

Authors
  1. V. Baleva
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to V. Baleva.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Baleva, V. The jump operation for structure degrees. Arch. Math. Logic 45, 249–265 (2006). https://doi.org/10.1007/s00153-004-0245-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00153-004-0245-z

Mathematics Subject Classification (2000)

Key words and phrases

Search

Navigation