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: 93,069

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.
Automorphisms of Countable Short Recursively Saturated Models of PA.Erez Shochat - 2008 - Notre Dame Journal of Formal Logic 49 (4):345-360.
Automorphisms of Countable Recursively Saturated Models of PA: A Survey.Henryk Kotlarski - 1995 - Notre Dame Journal of Formal Logic 36 (4):505-518.
Arithmetically Saturated Models of Arithmetic.Roman Kossak & James H. Schmerl - 1995 - Notre Dame Journal of Formal Logic 36 (4):531-546.

Analytics

Added to PP
2010-10-06

Downloads
76 (#223,546)

6 months
14 (#200,577)

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