Geodesic
Classifications of definable subsets
Algebra i logika, Tome 58 (2019) no. 5, pp. 574-608.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: $\Sigma_1^0$-classification, $d$-$\Sigma_1^0$-classification, $\Sigma_2^0$-classification, unbounded computable equivalence structure, unbounded computable injection structure. 
@article{AL_2019_58_5_a1,
     author = {S. Boyadzhiyska and K. Lange and A. Raz and R. Scanlon and J. Wallbaum and X. Zhang},
     title = {Classifications of definable subsets},
     journal = {Algebra i logika},
     pages = {574--608},
     publisher = {mathdoc},
     volume = {58},
     number = {5},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2019_58_5_a1/}
}
TY  - JOUR
AU  - S. Boyadzhiyska
AU  - K. Lange
AU  - A. Raz
AU  - R. Scanlon
AU  - J. Wallbaum
AU  - X. Zhang
TI  - Classifications of definable subsets
JO  - Algebra i logika
PY  - 2019
SP  - 574
EP  - 608
VL  - 58
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2019_58_5_a1/
LA  - ru
ID  - AL_2019_58_5_a1
ER  - 
%0 Journal Article
%A S. Boyadzhiyska
%A K. Lange
%A A. Raz
%A R. Scanlon
%A J. Wallbaum
%A X. Zhang
%T Classifications of definable subsets
%J Algebra i logika
%D 2019
%P 574-608
%V 58
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2019_58_5_a1/
%G ru
%F AL_2019_58_5_a1
S. Boyadzhiyska; K. Lange; A. Raz; R. Scanlon; J. Wallbaum; X. Zhang. Classifications of definable subsets. Algebra i logika, Tome 58 (2019) no. 5, pp. 574-608. http://geodesic.mathdoc.fr/item/AL_2019_58_5_a1/

[1] R. M. Friedberg, “Three theorems on recursive enumeration. I: Decomposition. II: Maximal set. III: Enumeration without duplication”, J. Symb. Log., 23:3 (1958), 309–316 | DOI | MR

[2] S. S. Goncharov, S. Lempp, D. R. Solomon, “Fridbergovskie numeratsii semeistv $n$-vychislimo perechislimykh mnozhestv”, Algebra i logika, 41:2 (2002), 143–154 | MR | Zbl

[3] S. S. Goncharov, N. T. Kogabaev, “O $\Sigma_1^0$-klassifikatsii otnoshenii na vychislimykh strukturakh”, Vestn. NGU. Ser. Matem., mekh., inform., 8:4 (2008), 23–32 | Zbl

[4] W. Calvert, D. Cenzer, V. Harizanov, A. Morozov, “Effective categoricity of equivalence structures”, Ann. Pure Appl. Logic, 141:1/2 (2006), 61–78 | DOI | MR | Zbl

[5] D. Tsenzer, V. Kharizanov, Dzh. B. Remmel, “Teoretiko vychislitelnye svoistva struktur s vlozheniem”, Algebra i logika, 53:1 (2014), 60–108 | MR

[6] A. M. Kach, D. Turetsky, “$\Delta_2^0$-categoricity of equivalence structures”, N. Z. J. Math., 39 (2009), 143–149 | MR | Zbl

[7] R. Downey, A. G. Melnikov, K. M. Ng, “On $\Delta_2^0$-categoricity of equivalence relations”, Annals Pure Appl. Logic, 166:9 (2015), 851–880 | DOI | MR | Zbl

[8] D. Cenzer, V. Harizanov, J. B. Remmel, “$\Sigma^0_1$ and $\Pi^0_1$ equivalence structures”, Mathematical theory and computational practice, 5th conf. comput. Europe, CiE 2009 (Heidelberg, Germany, July 19–24, 2009), Lect. Notes Comput. Sci., 5635, eds. K. Ambos-Spies et al., Springer-Verlag, Berlin, 2009, 99–108 | DOI | MR | Zbl

[9] D. Kuske, J. Liu, M. Lohrey, “The isomorphism problem on classes of automatic structures with transitive relations”, Trans. Am. Math. Soc., 365:10 (2013), 5103–5151 | DOI | MR | Zbl

[10] A. Montalbán, “Computability theoretic classifications for classes of structures”, Proc. Int. Congress Math., ICM 2014 (Seoul, Korea, August 13-21, 2014), v. II, Invited lectures, eds. S. Y. Jang et al., KM Kyung Moon Sa, Seoul, 2014, 79–101 | MR | Zbl

[11] S. S. Goncharov, Dzh. Nait, “Vychislimye strukturnye i antistrukturnye teoremy”, Algebra i logika, 41:6 (2002), 639–681 | MR | Zbl

[12] R. G. Downey, A. G. Melnikov, K. M. Ng, “A Friedberg enumeration of equivalence structures”, J. Math. Log., 17:2 (2017), 1750008, 28 pp. | DOI | MR | Zbl

[13] K. Lange, R. Miller, R. Steiner, “Classifications of computable structures”, Notre Dame J. Formal Logic, 59:1 (2018), 35–59 | DOI | MR | Zbl