On Concept Lattices for Numberings
Nikolay A. Bazhenov, Manat Mustafa, Anvar M. Nurakunov · Tsinghua Science & Technology · 2024
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$\mathcal{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$\mathcal{S}$. Similarly to the classical theory of numberings, each of the approaches assigns to a family$\mathcal{S}$its own concept lattice. The first approach captures the cardinality of a family$\mathcal{S}$: if$\mathcal{S}$contains more than 2 elements, then the corresponding concept lattice FC1($\mathcal{S}$) is a modular lattice of height 3, such that the number of its atoms to the cardinality of$\mathcal{S}$. Our second approach gives a much richer environment. We prove that for any countable poset$P$, there exists a family$\mathcal{S}$such that the induced concept lattice FC2 ($\mathcal{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 ($\mathcal{S}$) is anti-isomorphic to an enumerative lattice. In addition, every enumerative lattice is anti-isomorphic to a sublattice of the lattice FC2 ($\mathcal{S}$) for some family$\mathcal{S}$.