×

Classifications of definable subsets. (English. Russian original) Zbl 1480.03023

Algebra Logic 58, No. 5, 383-404 (2019); translation from Algebra Logika 58, No. 5, 574-608 (2019).
Summary: Given a structure \(\mathcal{M}\) over \(\omega\) and a syntactic complexity class \(\mathfrak{C} \), we say that a subset 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 [Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform. 8, No. 4, 23–32 (2008; Zbl 1249.03058)] generalized an idea proposed by R. M. Friedberg [J. Symb. Log. 23, 309–316 (1959; Zbl 0088.01601)], introducing the notion of a \(\mathfrak{C} \)-classification of \(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 \(\Sigma_1^0\)-classification, and a \(\Sigma_2^0\)-classification. In equivalence structures, on the other hand, we find a richer variety of possibilities.

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
03C40 Interpolation, preservation, definability
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Friedberg, Rf, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symb. Log., 23, 3, 309-316 (1958) · Zbl 0088.01601 · doi:10.2307/2964290
[2] S. S. Goncharov, S. Lempp, and D. R. Solomon, “Friedberg numberings of families of ncomputably enumerable sets,” Algebra and Logic, 41, No. 2, 81-86 (2002). · Zbl 1063.03028
[3] Goncharov, Ss; Kogabaev, Nt, On \({\varSigma}_1^0 \)-classification of relations on computable structures, Vestnik NGU, Mat., Mekh., Inf., 8, 4, 23-32 (2008) · Zbl 1249.03058
[4] W. Calvert, D. Cenzer, V. Harizanov, and A. Morozov, “Effective categoricity of equivalence structures,” Ann. Pure Appl. Log., 141, Nos. 1/2, 61-78 (2006). · Zbl 1103.03037
[5] Cenzer, D.; Harizanov, V.; Remmel, Jb, Computability-theoretic properties of injection structures, Algebra and Logic, 53, 1, 39-69 (2014) · Zbl 1323.03045 · doi:10.1007/s10469-014-9270-0
[6] Kach, Am; Turetsky, D., \( {\varDelta}_2^0 \)-categoricity of equivalence structures, N. Z. J. Math., 39, 143-149 (2009) · Zbl 1234.03021
[7] Downey, R.; Melnikov, Ag; Ng, Km, On \({\varDelta}_2^0 \)-categoricity of equivalence relations, Ann. Pure Appl. Log., 166, 9, 851-880 (2015) · Zbl 1386.03050 · doi:10.1016/j.apal.2015.04.003
[8] D. Cenzer, V. Harizanov, and J. B. Remmel, “\( {\varSigma}_1^0\) and \({\varPi}_0^1\) equivalence structures,” in Lect. Notes Comp. Sci., 5635, Springer-Verlag, Berlin (2009), pp. 99-108. · Zbl 1239.03023
[9] Kuske, D.; Liu, J.; Lohrey, M., The isomorphism problem on classes of automatic structures with transitive relations, Trans. Am. Math. Soc., 365, 10, 5103-5151 (2013) · Zbl 1308.03049 · doi:10.1090/S0002-9947-2013-05766-2
[10] A. Montalbán, “Computability theoretic classifications for classes of structures” in Proc. of the Int. Congress of Math., ICM 2014 (Seoul, Korea, August 13-21, 2014), Vol. II: Invited Lectures, S. Y. Jang et al. (Eds.), KM Kyung Moon Sa, Seoul (2014), pp. 79-101. · Zbl 1373.03069
[11] Goncharov, Ss; Knight, Jf, Computable structure and non-structure theorems, Algebra and Logic, 41, 6, 351-373 (2002) · Zbl 1034.03044 · doi:10.1023/A:1021758312697
[12] Downey, Rg; Melnikov, Ag; Ng, Km, A Friedberg enumeration of equivalence structures, J. Math. Log., 17, 2, Article ID 1750008 (2017) · Zbl 1423.03153 · doi:10.1142/S0219061317500088
[13] Lange, K.; Miller, R.; Steiner, R., Classifications of computable structures, Notre Dame J. Formal Log., 59, 1, 35-59 (2018) · Zbl 1455.03044 · doi:10.1215/00294527-2017-0015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.