Intrinsic bounds on complexity and definability at limit levels

Abstract

Abstract We show that for every computable limit ordinal α , there is a computable structure that is categorical, but not relatively categorical (equivalently, it does not have a formally Scott family). We also show that for every computable limit ordinal α , there is a computable structure with an additional relation R that is intrinsically on , but not relatively intrinsically on (equivalently, it is not definable by a computable Σ α formula with finitely many parameters). Earlier results in [7], [10], and [8] establish the same facts for computable successor ordinals α .