The complexity of classification problems for models of arithmetic

DOI10.2178/BSL/1286284557MaRDI QIDQ3163661zbMATH OpenOpenAlexFDO

Authors Samuel Coskey, Roman Kossak

Publication date 26 October 2010

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0908.1718

zbMATH Keywords

models of arithmeticcountable modelsrecursively saturated modelsBorel-completefinitely generated modelsminimal types

Mathematics Subject Classification ID

Models of arithmetic and set theory (03C62)

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.

Recommendations

• The classification of countable models of set theory
• scientific article; zbMATH DE number 32280
• Four problems concerning recursively saturated models of arithmetic
• Arithmetically saturated models of arithmetic
• Complexity of categorical theories with computable models

Cites work

• A Borel reductibility theory for classes of countable structures
• Automorphisms of models of arithmetic: a unified view
• Automorphisms of recursively saturated models of arithmetic
• Borel equivalence relations and classifications of countable models
• Full satisfaction classes: A survey
• Models and types of Peano's arithmetic
• Recursively saturated nonstandard models of arithmetic
• The Borel complexity of isomorphism for theories with many types
• The structure of models of Peano arithmetic

Cited in

(4)

• The property ``arithmetic-is-recursive on a cone
• The structural complexity of models of arithmetic
• The classification of countable models of set theory
• Working with ARMs: Complexity results on atomic representations of Herbrand models

This page was built for publication: The complexity of classification problems for models of arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3163661)