2004/10/25 by Fredrik Engström, Engström, Fredrik
Computer Science · Mathematics · #03C25 #03C50 #03C57 #03C62 #03C75 #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, programming, and type systems #math.LO #msc:03C25 #msc:03C50 #msc:03C57 #msc:03C62 #msc:03C75 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0410523
Doctoral thesis
arxiv created 2004/10/25 · openalex publication_date 2004/10/25 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recursive saturation and resplendence are two important notions in models of arithmetic. Kaye, Kossak, and Kotlarski introduced the notion of arithmetic saturation and argued that recursive saturation might not be as rigid as first assumed. In this thesis we give further examples of variations of recursive saturation, all of which are connected with expandability properties similar to resplendence. However, the expandability properties are stronger than resplendence and implies, in one way or another, that the expansion not only satisfies a theory, but also omits a type. We conjecture that a special version of this expandability is in fact equivalent to arithmetic saturation. We prove that another of these properties is equivalent to β-saturation. We also introduce a variant on recursive saturation which makes sense in the context of a standard predicate, and which is equivalent to a certain amount of ordinary saturation. The theory of all models which omit a certain type p(x) is also investigated. We define a proof system, which proves a sentence if and only if it is true in all models omitting the type p(x). The complexity of such proof systems are discussed and some explicit examples of theories and types with high complexity, in a special sense, are given. We end the thesis by a small comment on Scott's problem. We prove that, under the assumption of Martin's axiom, every Scott set of cardinality <2ℵ0 closed under arithmetic comprehension which has the countable chain condition is the standard system of some model of PA. However, we do not know if there exists any such uncountable Scott sets.