Classifications of definable subsets

S. Boyadzhiyska ; K. Lange ; A. Raz ; R. Scanlon ; J. Wallbaum ; X. Zhang

Algebra i logika, Tome 58 (2019) no. 5, pp. 574-608

Résumé

Given a structure $\mathcal{M}$ over $\omega$ and a syntactic complexity class $\mathfrak{C}$, we say that a subset $A$ is $\mathfrak{C}$-definable in $\mathcal{M}$ if there exists a $\mathfrak{C}$-formula $\Theta(x)$ in the language of $\mathcal{M}$ such that for all $x\in\omega$, we have $x \in A$ iff $\Theta(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{C}$-classification of $\mathcal{M}$: a computable list of $\mathfrak{C}$-formulas such that every $\mathfrak{C}$-definable subset is defined by a unique formula in the list. We study the connections among $\Sigma_1^0$-, $d$-$\Sigma_1^0$-, and $\Sigma_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 $\Sigma_1^0$-classification, a $d$-$\Sigma_1^0$-classification, and a $\Sigma_2^0$-classification. In equivalence structures, on the other hand, we find a richer variety of possibilities.

Détail

Keywords: $\Sigma_1^0$-classification, $d$-$\Sigma_1^0$-classification, $\Sigma_2^0$-classification, unbounded computable equivalence structure, unbounded computable injection structure.