On Concept Lattices for Numberings

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 ${\mathrm{F}\mathrm{C}}_1(\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 ${\mathrm{F}\mathrm{C}}_2(\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 ${\mathrm{F}\mathrm{C}}_2(\mathcal{S})$ is anti-isomorphic to an enumerative lattice. In addition, every enumerative lattice is anti-isomorphic to a sublattice of the lattice ${\mathrm{F}\mathrm{C}}_2(\mathcal{S})$ for some family $\mathcal{S}$.