Tsinghua Science and Technology 2024, 29(6): 1642-1650
Published: 20 June 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 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 . Similarly to the classical theory of numberings, each of the approaches assigns to a family its own concept lattice. The first approach captures the cardinality of a family : if contains more than 2 elements, then the corresponding concept lattice is a modular lattice of height , such that the number of its atoms to the cardinality of . Our second approach gives a much richer environment. We prove that for any countable poset , there exists a family such that the induced concept lattice is isomorphic to the Dedekind-MacNeille completion of . 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 is anti-isomorphic to an enumerative lattice. In addition, every enumerative lattice is anti-isomorphic to a sublattice of the lattice for some family .