Topics in Definability
Peter G. Hinman · 2018
The Definability Theorem 4.5.2 tells us that the recursive and semi-recursive relations are definable over Ω. The theme of this section is that many more relations than these are also definable and that we can usefully classify the definable relations by looking at the complexity of the formulas needed to define them. This is again in contrast with the situation for structures like Ω+. The quantifier-elimination Theorem 2.5.16 for T+ = Th(Ω+) implies that every LΩ+ -formula is T+-equivalent to one which is a Boolean combination of existential formulas, but we shall see that relative to Th(Ω) generally formulas with more quantifiers are more expressive in the sense that they are not equivalent to formulas with fewer quantifiers.