Computable Model Theory for Uncountable Structures

Using classical definitions from admissible set theory, we examine computable model theory for uncountable structures.

We begin the first chapter by recalling several classic results from α-recursion, as stated in Greenberg and Knight. We give a few examples of 'ω₂-computable' structures.

In the second chapter, we continue work of Greenberg and Knight on 'ω₂-computable' structure theory. All results in this chapter are joint with Jacob Carson, Julia Knight, Karen Lange, Charles McCoy, and John Wallbaum. We define the arithmetical hierarchy through all countable levels (not just finite levels). The definition resembles that of the hyperarithmetical hierarchy. We obtain analogues of the results of Chisholm and Ash, Knight, Manasse, and Slaman, saying that a relation is relatively intrinsically Σ⁰_α if and only if it is definable by a computable Σ_α formula.

In the third chapter, we focus on quasiminimal-excellent classes, which are important classes of structures in modern model theory. We give a definition for κ⁺-computable categoricity and give properties of classes of structures, under which the unique element of size κ⁺ has a κ⁺-computable copy and is κ⁺-Δ⁰₂-categorical. We then show that any class satisfying these properties is κ⁺-computably categorical if and only if there is no triple (N',N,M) of structures of dimension κ such that M ⊆ N ⊆ N' and M is 'closed' in N and N', but N is not 'closed' in N'. We then apply this result to some well-known examples of quasiminimal-excellent classes, showing that the pseudo-exponential field of size κ⁺ is not κ⁺-computably categorical, but the 'Zil'ber cover' is relatively κ⁺-computably categorical. We end by connecting the results of computable categoricity to axiomatizability for quasiminimal-excellent classes.