Combinatory logic and the ω-rule
We study the notion of computable categoricity of computable structures, comparing it especially to the notion of relative computable categoricity and its relativizations. We show that every 1 decidable computably categorical structure is relatively Δ⁰₂ categorical. We study the complexity of various index sets associated with computable categoricity and relative computable categoricity. We also introduce and study a variation of relative computable categoricity, comparing it to both computable...
The structure of definable sets and maps in dense elementary pairs of o-minimal expansions of ordered abelian groups is described. It turns out that a certain notion of "small definable set" plays a special role in this description.