AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (1.4 MB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

On Concept Lattices for Numberings

Laboratory of Computability Theory and Applied Logic, Sobolev Institute of Mathematics, Novosibirsk 630090, Russia
Department of Mathematics, School of Sciences and Humanities, Nazarbayev University, Astana 010000, Kazakhstan
Institute of Mathematics, National Academy of Sciences, Bishkek 720071, Kyrgyzstan
Show Author Information

Abstract

The theory of numberings studies uniform computations for families of mathematical objects. In this area, computability-theoretic properties of at most countable families of sets S are typically classified via the corresponding Rogers upper semilattices. In most cases, a Rogers semilattice cannot be a lattice. Working within the framework of Formal Concept Analysis, we develop two new approaches to the classification of families S. Similarly to the classical theory of numberings, each of the approaches assigns to a family S its own concept lattice. The first approach captures the cardinality of a family S: if S contains more than 2 elements, then the corresponding concept lattice FC1(S) is a modular lattice of height 3, such that the number of its atoms to the cardinality of S. Our second approach gives a much richer environment. We prove that for any countable poset P, there exists a family S such that the induced concept lattice FC2(S) is isomorphic to the Dedekind-MacNeille completion of P. We also establish connections with the class of enumerative lattices introduced by Hoyrup and Rojas in their studies of algorithmic randomness. We show that every lattice FC2(S) is anti-isomorphic to an enumerative lattice. In addition, every enumerative lattice is anti-isomorphic to a sublattice of the lattice FC2(S) for some family S.

References

[1]

K. Gödel, On formally undecidable propositions of Principia Mathematica and related systems I, Monatsh. Math. Phys., vol. 38, no. 1, pp. 173–198, 1931.

[2]

S. C. Kleene, On notation for ordinal numbers, J. Symb. Log., vol. 3, no. 4, pp. 150–155, 1938.

[3]
S. C. Kleene, Introduction to Metamathematics. New York, NY, USA: Van Nostrand, 1952.
[4]

A. N. Kolmogorov and V. A. Uspenskii, On the definition of an algorithm, (in Russian), Uspekhi Matematicheskikh Nauk, vol. 13, no. 4, pp. 3–28, 1958.

[5]

V. A. Uspenskii, Systems of denumerable sets and their enumeration, (in Russian), Doklady Akademii Nauk SSSR, vol. 105, pp. 1155–1158, 1958.

[6]

H. Rogers, Gödel numberings of partial recursive functions, J. Symb. Log., vol. 23, no. 3, pp. 331–341, 1958.

[7]
R. I. Soare, Turing Computability : Theory and Applications. Berlin, Genmany: Springer, 2016.
[8]

V. L. Selivanov, Two theorems on computable numberings, Algebra Logic, vol. 15, no. 4, pp. 297–306, 1976.

[9]

Y. L. Ershov, Necessary isomorphism conditions for Rogers semilattices of finite partially ordered sets, Algebra Logic, vol. 42, no. 4, pp. 232–236, 2003.

[10]

Y. L. Ershov, Rogers semilattices of finite partially ordered sets, Algebra Logic, vol. 45, no. 1, pp. 26–48, 2006.

[11]
Y. L. Ershov, Theory of Numberings, (in Russian). Moscow, USSR: Nauka, 1977.
[12]
Y. L. Ershov, Theory of numberings, in Handbook of Computability Theory, E. R. Griffor, ed. Amsterdam, the Netherlands: North-Holland, 1999, pp. 473−503.
[13]
S. A. Badaev and S. S. Goncharov, The theory of numberings: Open problems, in Computability Theory and Its Applications, P. Cholak, S. Lempp, M. Lerman, and R. Shore, eds. Providence, RL, USA: American Mathematical Society, 2000, pp. 23−38.
[14]
R. Wille, Restructuring lattice theory: an approach based on hierarchies of concepts, in Ordered Sets, I. Rival, ed. Dordrecht, Netherlands: D. Reidel Publishing Company, 1982, pp. 445−470.
[15]

M. Hoyrup and C. Rojas, Computability of probability measures and Martin-Löf randomness over metric spaces, Inf. Comput., vol. 207, no. 7, pp. 830–847, 2009.

[16]
N. Bazhenov, M. Mustafa, and A. Nurakunov, On two types of concept lattices in the theory of numberings, in Proc. Theory and Applications of Models of Computation, 17th Annual Conference, Tianjin, China, 2022, pp. 79−92.
[17]
C. J. Ash and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy. Amsterdam, the Netherlands: Elsevier Science B.V., 2000.
[18]
B. Ganter and R. Wille, Formal Concept Analysis : Mathematical Foundations. Berlin, Germany: Springer, 1999.
[19]
B. A. Davey and H. A. Pristley, Introduction to Lattices and Order, Second Edition. Cambridge, UK: Cambridge University Press, 2002.
[20]
R. Balbes and P. Dwinger, Distributive lattices. Columbia, MO, USA: University of Missouri Press, 1974.
[21]

A. B. Khutoretskii, On the cardinality of the upper semilattice of computable enumerations, Algebra Logic, vol. 10, no. 5, pp. 348–352, 1971.

[22]

Y. L. Ershov and I. A. Lavrov, The upper semilattice L (γ ), Algebra Logic, vol. 12, no. 2, pp. 93–106, 1973.

[23]

V. V. V’yugin, On some examples of upper semilattices of computable enumerations, Algebra Logic, vol. 12, no. 5, pp. 287–296, 1973.

[24]

S. S. Goncharov and A. Sorbi, Generalized computable numerations and nontrivial Rogers semilattices, Algebra Logic, vol. 36, no. 6, pp. 359–369, 1997.

[25]

S. A. Badaev, S. S. Goncharov, and A. Sorbi, Elementary theories for Rogers semilattices, Algebra Logic, vol. 44, no. 3, pp. 143–147, 2005.

[26]

S. A. Badaev, S. S. Goncharov, and A. Sorbi, Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy, Algebra Logic, vol. 45, no. 6, pp. 361–370, 2006.

[27]

S. Yu, Podzorov, Arithmetical D-degrees, Sib. Math. J., vol. 49, no. 6, pp. 1109–1123, 2008.

[28]
S. Badaev and S. Goncharov, Computability and numberings, in New Computational Paradigms, S. B. Cooper, B. Löwe, and A. Sorbi, eds. New York, NY, USA: Springer, 2008, pp. 19−34.
[29]

N. Bazhenov, M. Mustafa, and M. Yamaleev, Elementary theories and hereditary undecidability for semilattices of numberings, Arch. Math. Logic, vol. 58, nos. 3&4, pp. 485–500, 2019.

[30]

S. S. Goncharov, S. Lempp, and D. R. Solomon, Friedberg numberings of families of n-computably enumerable sets, Algebra Logic, vol. 41, no. 2, pp. 81–86, 2002.

[31]

S. A. Badaev and S. Lempp, A decomposition of the Rogers semilattice of a family of d.c.e. sets, J. Symb. Log., vol. 74, no. 2, pp. 618–640, 2009.

[32]
I. Herbert, S. Jain, S. Lempp, M. Mustafa, and F. Stephan, Reductions between types of numberings, Ann. Pure Appl. Logic, vol. 170, no. 12, p. 102716, 2019.
[33]
N. Bazhenov, S. Ospichev, and M. Yamaleev, Isomorphism types of Rogers semilattices in the analytical hierarchy, arXiv preprint arXiv: 1912.05226, 2019.
[34]

N. A. Bazhenov, M. Mustafa, S. S. Ospichev, and M. M. Yamaleev, Numberings in the analytical hierarchy, Algebra Logic, vol. 59, no. 5, pp. 404–407, 2020.

[35]

N. A. Bazhenov, M. Mustafa, and Z. Tleuliyeva, Theories of Rogers semilattices of analytical numberings, Lobachevskii J. Math., vol. 42, no. 4, pp. 701–708, 2021.

[36]
M. Hoyrup, Computability, randomness and ergodic theory on metric spaces, PhD dissertation, Université Paris Diderot, Paris, France, 2008.
[37]

B. Balcar and T. Jech, Weak distributivity, a problem of von Neumann and the mystery of measurability, Bull. Symb. Log., vol. 12, no. 2, pp. 241–266, 2006.

[38]
T. Jech, Set Theory, The Third Millennium Edition. Berlin, Germany: Springer, 2003.
[39]

N. Bazhenov, M. Harrison-Trainor, I. Kalimullin, A. Melnikov, and K. M. Ng, Automatic and polynomial-time algebraic structures, J. Symb. Log., vol. 84, no. 4, pp. 1630–1669, 2019.

[40]

W. Calvert and J. F. Knight, Classification from a computable viewpoint, Bull. Symb. Log., vol. 12, no. 2, pp. 191–218, 2006.

[41]
E. B. Fokina, V. Harizanov, and A. Melnikov, Computable model theory, in Turing’s Legacy : Developments from Turing’s Ideas in Logic, R. Downey, ed. Cambridge, UK: Cambridge University Press, 2014, pp. 124−194.
[42]

T. G. McLaughlin, The family of all recursively enumerable classes of finite sets, Trans. Am. Math. Soc., vol. 155, no. 1, pp. 127–136, 1971.

[43]
S. Wehner, Computable enumeration and the problem of repetition, PhD dissertation, Simon Fraser University, Burnaby, Canada, 1995.
[44]

J. Harrison, Recursive pseudo well-orderings, Trans. Am. Math. Soc., vol. 131, no. 2, pp. 526–543, 1968.

[45]

W. M. White, On the complexity of categoricity in computable structures, Math. Log. Q., vol. 49, no. 6, pp. 603–614, 2003.

Tsinghua Science and Technology
Pages 1642-1650
Cite this article:
Bazhenov N, Mustafa M, Nurakunov A. On Concept Lattices for Numberings. Tsinghua Science and Technology, 2024, 29(6): 1642-1650. https://doi.org/10.26599/TST.2023.9010102

115

Views

16

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics

Received: 24 January 2023
Revised: 17 July 2023
Accepted: 08 September 2023
Published: 20 June 2024
© The Author(s) 2024.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return