TY - JOUR

T1 - On Concept Lattices for Numberings

AU - Bazhenov, Nikolay

AU - Mustafa, Manat

AU - Nurakunov, Anvar

N1 - Publisher Copyright:
© 1996-2012 Tsinghua University Press.

PY - 2024/12/1

Y1 - 2024/12/1

N2 - 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.

AB - 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.

KW - complete lattice

KW - concept lattice

KW - enumerative lattice

KW - Formal Concept Analysis

KW - index set

KW - theory of numberings

UR - http://www.scopus.com/inward/record.url?scp=85197422917&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85197422917&partnerID=8YFLogxK

U2 - 10.26599/TST.2023.9010102

DO - 10.26599/TST.2023.9010102

M3 - Article

AN - SCOPUS:85197422917

SN - 1007-0214

VL - 29

SP - 1642

EP - 1650

JO - Tsinghua Science and Technology

JF - Tsinghua Science and Technology

IS - 6

ER -