Classifications of Definable Subsets

Abstract

Given a structure ℳ over ω and a syntactic complexity class \( \mathfrak{E} \), we say that a subset is \( \mathfrak{E} \)-definable in ℳ if there exists a C-formula Θ(x) in the language of ℳ such that for all x ∈ ω, we have x ∈ A iff Θ(x) is true in the structure. S. S. Goncharov and N. T. Kogabaev [Vestnik NGU, Mat., Mekh., Inf., 8, No. 4, 23-32 (2008)] generalized an idea proposed by Friedberg [J. Symb. Log., 23, No. 3, 309-316 (1958)], introducing the notion of a \( \mathfrak{E} \)-classification of M: a computable list of \( \mathfrak{E} \)-formulas such that every \( \mathfrak{E} \)-definable subset is defined by a unique formula in the list. We study the connections among\( {\varSigma}_1^0- \), \( d-{\varSigma}_1^0- \), and \( {\varSigma}_2^0 \)-classifications in the context of two families of structures, unbounded computable equivalence structures and unbounded computable injection structures. It is stated that every such injection structure has a \( {\varSigma}_1^0- \)classification, a \( {\varSigma}_1^0- \)classification, and a \( {\varSigma}_2^0 \)-classification. In equivalence structures, on the other hand, we find a richer variety of possibilities.