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
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (1.4 MB)
Cite
EndNote(RIS) BibTeX
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.

Keywords

theory of numberingsconcept latticeindex setcomplete latticeenumerative latticeFormal Concept Analysis

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.
Google Scholar
[2]

S. C. Kleene, On notation for ordinal numbers, J. Symb. Log., vol. 3, no. 4, pp. 150–155, 1938.
Crossref Google Scholar
[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.
Google Scholar
[5]

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

H. Rogers, Gödel numberings of partial recursive functions, J. Symb. Log., vol. 23, no. 3, pp. 331–341, 1958.
Crossref Google Scholar
[7]
R. I. Soare, Turing Computability : Theory and Applications. Berlin, Genmany: Springer, 2016.
Crossref
[8]

V. L. Selivanov, Two theorems on computable numberings, Algebra Logic, vol. 15, no. 4, pp. 297–306, 1976.
Crossref Google Scholar
[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.
Crossref Google Scholar
[10]

Y. L. Ershov, Rogers semilattices of finite partially ordered sets, Algebra Logic, vol. 45, no. 1, pp. 26–48, 2006.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref
[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.
Crossref Google Scholar
[22]

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

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

S. S. Goncharov and A. Sorbi, Generalized computable numerations and nontrivial Rogers semilattices, Algebra Logic, vol. 36, no. 6, pp. 359–369, 1997.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[27]

S. Yu, Podzorov, Arithmetical D-degrees, Sib. Math. J., vol. 49, no. 6, pp. 1109–1123, 2008.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[40]

W. Calvert and J. F. Knight, Classification from a computable viewpoint, Bull. Symb. Log., vol. 12, no. 2, pp. 191–218, 2006.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[45]

W. M. White, On the complexity of categoricity in computable structures, Math. Log. Q., vol. 49, no. 6, pp. 603–614, 2003.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 29 Issue 6,
December 2024
Pages 1642-1650
DOI: 10.26599/TST.2023.9010102
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

253

Views

42

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