← All problems

Finite lattice representation problem

63 years old · traced to

Let AA be a set and let FF be a set of finitary operations on AA, so that A=⟨A,F⟩\mathbf{A} = \langle A, F\rangle is an algebra; A\mathbf{A} is finite if AA is finite. An equivalence relation θ\theta on AA is a congruence of A\mathbf{A} if for every nn-ary f∈Ff \in F and all a1,…,an,b1,…,bn∈Aa_1,\dots,a_n, b_1,\dots,b_n \in A with (ai,bi)∈θ(a_i,b_i) \in \theta for i=1,…,ni = 1,\dots,n, one has (f(a1,…,an),f(b1,…,bn))∈θ(f(a_1,\dots,a_n), f(b_1,\dots,b_n)) \in \theta. The set Con⁡(A)\operatorname{Con}(\mathbf{A}) of all congruences of A\mathbf{A}, ordered by inclusion, is a complete lattice, with meet given by intersection.

For every finite lattice LL there exist a finite algebra A=⟨A,F⟩\mathbf{A} = \langle A, F\rangle and a lattice isomorphism

L≅Con⁡(A).L \cong \operatorname{Con}(\mathbf{A}).

Equivalently, for every finite lattice LL there exist a finite group GG and a subgroup H≤GH \le G such that LL is isomorphic to the interval [H,G]={K:H≤K≤G}[H,G] = \{K : H \le K \le G\} in the lattice of subgroups of GG, ordered by inclusion.

References
  1. Wikipedia, Finite lattice representation problem, the article this problem comes from.

Source: Wikipedia

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 2

Claimed by OpenAI. The manuscript claims a colored-graph characterization of finite nonempty lattices that are full congruence lattices of finite algebras, undecidability of that property, and a negative answer to the page’s representation question. Restricting to finite signatures does not weaken the obstruction: on a finite underlying set, finitely many operations suffice to preserve all congruences.See full solutionHide full solution
Claimed by OpenAI. The manuscript claims a finite nonempty lattice that is not the full congruence lattice of any finite nonempty algebra of finite signature. This also obstructs the page’s arbitrary family of finitary operations: on a finite set, finitely many chosen operations suffice to preserve exactly the same congruences. The claim is a negative representation result, not merely failure of a particular construction.See full solutionHide full solution