The complexity of classification problems for models of arithmetic

Bulletin of Symbolic Logic 16 (3):345-358 (2010)
  Copy   BIBTEX

Abstract

We observe that the classification problem for countable models of arithmetic is Borel complete. On the other hand, the classification problems for finitely generated models of arithmetic and for recursively saturated models of arithmetic are Borel; we investigate the precise complexity of each of these. Finally, we show that the classification problem for pairs of recursively saturated models and for automorphisms of a fixed recursively saturated model are Borel complete

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,100

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Four Problems Concerning Recursively Saturated Models of Arithmetic.Roman Kossak - 1995 - Notre Dame Journal of Formal Logic 36 (4):519-530.
Models with the ω-property.Roman Kossak - 1989 - Journal of Symbolic Logic 54 (1):177-189.
Transplendent Models: Expansions Omitting a Type.Fredrik Engström & Richard W. Kaye - 2012 - Notre Dame Journal of Formal Logic 53 (3):413-428.
Recursively saturated $\omega_1$-like models of arithmetic.Roman Kossak - 1985 - Notre Dame Journal of Formal Logic 26 (4):413-422.
Recursively saturated nonstandard models of arithmetic.C. Smoryński - 1981 - Journal of Symbolic Logic 46 (2):259-286.
On the complexity of models of arithmetic.Kenneth McAloon - 1982 - Journal of Symbolic Logic 47 (2):403-415.
Elementary Cuts in Saturated Models of Peano Arithmetic.James H. Schmerl - 2012 - Notre Dame Journal of Formal Logic 53 (1):1-13.
Elementary extensions of recursively saturated models of arithmetic.C. Smoryński - 1981 - Notre Dame Journal of Formal Logic 22 (3):193-203.
On Cofinal Submodels and Elementary Interstices.Roman Kossak & James H. Schmerl - 2012 - Notre Dame Journal of Formal Logic 53 (3):267-287.

Analytics

Added to PP
2010-10-06

Downloads
75 (#221,197)

6 months
13 (#197,285)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Roman Kossak
City University of New York

Citations of this work

Add more citations

References found in this work

Models and types of Peano's arithmetic.Haim Gaifman - 1976 - Annals of Mathematical Logic 9 (3):223-306.
The Structure of Models of Peano Arithmetic.Roman Kossak & James Schmerl - 2006 - Oxford, England: Clarendon Press.

View all 10 references / Add more references