## 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

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'}}

Powered by AMiner. Clicking this button will take you away from SciOpen.

About Us

Discover the SciOpen Platform and Achieve Your Research Goals with Ease.

Show Outline

Outline

Outline

Open Access

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

[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
Metrics & Citations

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/).