A note on computable embeddings for ordinals and their reverses. (English) Zbl 07633492
Anselmo, Marcella (ed.) et al., Beyond the horizon of computability. 16th conference on computability in Europe, CiE 2020, Fisciano, Italy, June 29 – July 3, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12098, 1-13 (2020).
Summary: We continue the study of computable embeddings for pairs of structures, i.e. for classes containing precisely two non-isomorphic structures. Surprisingly, even for some pairs of simple linear orders, computable embeddings induce a non-trivial degree structure. Our main result shows that although \(\{\omega \cdot 2, \omega^\star \cdot 2\}\) is computably embeddable in \(\{\omega^2, {(\omega^2)}^\star \}\), the class \(\{\omega \cdot k,\omega^\star \cdot k\}\) is not computably embeddable in \(\{\omega^2, {(\omega^2)}^\star \}\) for any natural number \(k \ge 3\).
For the entire collection see [Zbl 1502.68017].
For the entire collection see [Zbl 1502.68017].
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Bazhenov, N., Downey, R., Kalimullin, I., Melnikov, A.: Foundations of online structure theory. Bull. Symb. Log. 25(2), 141-181 (2019). https://doi.org/10.1017/bsl.2019.20 · Zbl 1477.03167 · doi:10.1017/bsl.2019.20 |
| [2] | Bazhenov, N., Fokina, E., San Mauro, L.: Learning families of algebraic structures from informant. Preprint, arXiv:1905.01601 (2019) · Zbl 1496.68162 |
| [3] | Bazhenov, N., Ganchev, H., Vatev, S.: Computable embeddings for pairs of linear orders. Preprint, arXiv:1901.01933 (2019) · Zbl 1515.03159 |
| [4] | Calvert, W., Cummins, D., Knight, J.F., Miller, S.: Comparing classes of finite structures. Algebra Log. 43(6), 374-392 (2004). https://doi.org/10.1023/B:ALLO.0000048827.30718.2c · Zbl 1097.03026 · doi:10.1023/B:ALLO.0000048827.30718.2c |
| [5] | Chisholm, J., Knight, J.F., Miller, S.: Computable embeddings and strongly minimal theories. J. Symb. Log. 72(3), 1031-1040 (2007). https://doi.org/10.2178/jsl/1191333854 · Zbl 1127.03030 · doi:10.2178/jsl/1191333854 |
| [6] | de Brecht, M., Yamamoto, A.: Topological properties of concept spaces (full version). Inf. Comput. 208(4), 327-340 (2010). https://doi.org/10.1016/j.ic.2009.08.001 · Zbl 1192.68428 · doi:10.1016/j.ic.2009.08.001 |
| [7] | Downey, R., Harrison-Trainor, M., Kalimullin, I., Melnikov, A., Turetsky, D.: Graphs are not universal for online computability. J. Comput. Syst. Sci. 112, 1-12 (2020). https://doi.org/10.1016/j.jcss.2020.02.004 · Zbl 1476.03046 · doi:10.1016/j.jcss.2020.02.004 |
| [8] | Ershov, Y.L., Puzarenko, V.G., Stukachev, A.I.: \(HF\)-computability. In: Cooper, S.B., Sorbi, A. (eds.) Computability in Context, pp. 169-242. Imperial College Press, London (2011). https://doi.org/10.1142/9781848162778_0006 · Zbl 1260.03086 |
| [9] | Friedman, H., Stanley, L.: A Borel reducibility theory for classes of countable structures. J. Symb. Log. 54(3), 894-914 (1989). https://doi.org/10.2307/2274750 · Zbl 0692.03022 · doi:10.2307/2274750 |
| [10] | Ganchev, H., Kalimullin, I., Vatev, S.: Computable embedding of classes of algebraic structures with congruence relation. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki 160(4), 731-737 (2018). in Russian |
| [11] | Harrison-Trainor, M., Melnikov, A., Miller, R., Montalbán, A.: Computable functors and effective interpretability. J. Symb. Log. 82(1), 77-97 (2017). https://doi.org/10.1017/jsl.2016.12 · Zbl 1390.03034 · doi:10.1017/jsl.2016.12 |
| [12] | Harrison-Trainor, M., Miller, R., Montalbán, A.: Borel functors and infinitary interpretations. J. Symb. Log. 83(4), 1434-1456 (2018). https://doi.org/10.1017/jsl.2017.81 · Zbl 1522.03171 · doi:10.1017/jsl.2017.81 |
| [13] | Hirschfeldt, D.R., Khoussainov, B., Shore, R.A., Slinko, A.M.: Degree spectra and computable dimensions in algebraic structures. Ann. Pure Appl. Logic 115(1-3), 71-113 (2002). https://doi.org/10.1016/S0168-0072(01)00087-2 · Zbl 1016.03034 · doi:10.1016/S0168-0072(01)00087-2 |
| [14] | Kalimullin, I.S.: Computable embeddings of classes of structures under enumeration and turing operators. Lobachevskii J. Math. 39(1), 84-88 (2018). https://doi.org/10.1134/S1995080218010146 · Zbl 1483.03027 · doi:10.1134/S1995080218010146 |
| [15] | Knight, J.F., Miller, S., Vanden Boom, M.: Turing computable embeddings. J. Symb. Log. 72(3), 901-918 (2007). https://doi.org/10.2178/jsl/1191333847 · Zbl 1123.03026 · doi:10.2178/jsl/1191333847 |
| [16] | Miller, R., Poonen, B., Schoutens, H., Shlapentokh, A.: A computable functor from graphs to fields. J. Symb. Log. 83(1), 326-348 (2018). https://doi.org/10.1017/jsl.2017.50 · Zbl 1447.03005 · doi:10.1017/jsl.2017.50 |
| [17] | Puzarenko, V.G.: A certain reducibility on admissible sets. Sib. Math. J. 50(2), 330-340 (2009). https://doi.org/10.1007/s11202-009-0038-z · Zbl 1224.03022 · doi:10.1007/s11202-009-0038-z |
| [18] | Rosenstein, J.G.: Linear Orderings. Pure and Applied Mathematics, vol. 98. Academic Press, New York (1982) · Zbl 0488.04002 |
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.
