Free lattices do not contain infinite ascending chains of three-generator copies
No free lattice contains an infinite ascending chain of copies of FL(3)
Logic in Computer Science
Summary
This paper solves a math puzzle about special structures called free lattices, focusing on the version with three starting points. The authors prove that you cannot find an endlessly growing sequence of smaller copies of this structure inside the original. They use formal proof tools to confirm their result without relying on assumptions like the infinite pigeonhole principle. The work clarifies how these complex ordered shapes behave and shows that without the ‘free’ condition, infinite sequences do appear. This advances understanding in abstract algebra and the properties of mathematical orderings.
What this means in practice
- •For developers of formal verification tools: Incorporate the paper’s methods to certify properties of free lattices in proof assistants for safer algebraic reasoning.
- •For mathematical software engineers: Improve algorithms for manipulating lattice structures by leveraging insights on self-embeddings and chain conditions described in the work.
A theory result. No direct application yet.
Authors
William DeMeo, Ralph Freese
Abstract
No free lattice contains an infinite strictly ascending chain of sublattices isomorphic to FL(3), the free lattice on three generators; this answers a question that R. A. Dean asked and the second author's 1997 notes on the problem left open. Every such chain would yield, inside FL(3), a coherent chain of proper self-embeddings $Θ_0, Θ_1, Θ_2, \dots$ with $Θ_k \circ Θ_j = Θ_j$ for $j < k$, so that each later embedding fixes the image of each earlier one pointwise. Every proper self-embedding of FL(3) whose fixed sublattice contains a free generating triple fixes one of the three generators, say $z$, because a power of it or of its dual lies above the identity, and a self-embedding that moves every generator and lies above the identity fixes at most eleven elements. Up to duality, a proper self-embedding fixing the image of such a $Θ_1$ pointwise fixes only elements above $z \wedge (x \vee y)$, where no free generating triple containing $z$ can lie. We also verify the one-step example of the 1997 notes, prove that no step toward such a chain is self-similar, and show that the configuration the argument rules out at length three does occur at length two. Without freeness the answer reverses: FL(3) contains an infinite strictly ascending chain of 3-generated sublattices, so the lattice analogue of Takahasi's chain condition for free groups fails. The theorem itself is checked by the Agda proof assistant under its safe flags, for free lattices over generators with decidable equality, and its formal proof uses no classical principle: finite searches and an induction on a finite set replace the infinite pigeonhole principle by which a chain yields a coherent chain.