The complexity of classification problems for models of arithmetic
Bulletin of Symbolic Logic 16 (3):345-358 (2010)
| 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 | |||||||||
| Keywords | Countable models of arithmetic, complexity of isomorphis problems, finitely generated models of PA, recursively saturated models of PA | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,711 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesRoman Kossak (1995). Four Problems Concerning Recursively Saturated Models of Arithmetic. Notre Dame Journal of Formal Logic 36 (4):519-530.
Ermek S. Nurkhaidarov & Erez Shochat (2010). Automorphisms of Saturated and Boundedly Saturated Models of Arithmetic. Notre Dame Journal of Formal Logic 52 (3):315-329.
Roman Kossak (1989). Models with the Ω-Property. Journal of Symbolic Logic 54 (1):177-189.
Fredrik Engström & Richard W. Kaye (2012). Transplendent Models: Expansions Omitting a Type. Notre Dame Journal of Formal Logic 53 (3):413-428.
Fredrik Engström & Richard W. Kaye (2012). Transplendent Models: Expansions Omitting a Type. Notre Dame Journal of Formal Logic 53 (3):413-428.
Fredrik Engström & Richard W. Kaye (2012). Transplendent Models: Expansions Omitting a Type. Notre Dame Journal of Formal Logic 53 (3):413-428.
Roman Kossak (1985). Recursively Saturated $\Omega_1$-Like Models of Arithmetic. Notre Dame Journal of Formal Logic 26 (4):413-422.
C. Smoryński (1981). Recursively Saturated Nonstandard Models of Arithmetic. Journal of Symbolic Logic 46 (2):259-286.
Kenneth McAloon (1982). On the Complexity of Models of Arithmetic. Journal of Symbolic Logic 47 (2):403-415.
C. Smoryński (1982). Recursively Saturated Nonstandard Models of Arithmetic; Addendum. Journal of Symbolic Logic 47 (3):493-494.
Victor Harnik (1986). Ω1-Like Recursively Saturated Models of Presburger's Arithmetic. Journal of Symbolic Logic 51 (2):421 - 429.
James H. Schmerl (2012). Elementary Cuts in Saturated Models of Peano Arithmetic. Notre Dame Journal of Formal Logic 53 (1):1-13.
C. Smoryński (1981). Elementary Extensions of Recursively Saturated Models of Arithmetic. Notre Dame Journal of Formal Logic 22 (3):193-203.
Roman Kossak & James H. Schmerl (2012). On Cofinal Submodels and Elementary Interstices. Notre Dame Journal of Formal Logic 53 (3):267-287.
C. Smoryński (1982). A Note on Initial Segment Constructions in Recursively Saturated Models of Arithmetic. Notre Dame Journal of Formal Logic 23 (4):393-408.
Analytics
Monthly downloads |
Added to index2010-10-06Total downloads7 ( #133,668 of 551,105 )Recent downloads (6 months)1 ( #63,341 of 551,105 )How can I increase my downloads? |
My notes
Discussion
