Recursion Theory

3.6.3 Coding ω- and wellfounded models

We now work in the language of set theory and use “E” in place of the symbol ̂∈. The best models of set theory are of course those that are wellfounded.

Proposition 3.6.2. {E |〈ω, E〉 codes a wellfounded model} is .

Proof. 〈ω, E〉 codes a wellfounded model if and only if there is no function f : ω → ω such that for any pair (i, j), i < j if and only if 〈ω, E〉 ⊨ f(j)Ef(i).

Coding wellfounded models is a complicated matter, though such models are the “bona fide models” of set theory. The next best thing is to code ω-models. The reason for studying ω-models is that in considering reals or sets of reals in such ...