<p>We continue our work on the model theory of free lattices, solving two of the main open problems from our first paper on the subject. Our main result is that the universal (existential) theory of infinite free lattices is decidable. Our second main result is a proof that finitely generated free lattices are positively distinguishable, as for each <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$n \geqslant 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>⩾</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> there is a positive <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\exists \forall $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>∃</mo> <mo>∀</mo> </mrow> </math></EquationSource> </InlineEquation>-sentence true in <InlineEquation ID="IEq3"> <EquationSource Format="TEX">${\textbf{F}}_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="bold">F</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> and false in <InlineEquation ID="IEq4"> <EquationSource Format="TEX">${\textbf{F}}_{n+1}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="bold">F</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation>. Finally, we show that free lattices are first-order rigid in the class of finitely generated projective lattices, and that a projective lattice has the same existential (universal) theory of an infinite free lattice if and only if it has breadth <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$> 4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>></mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation> (i.e., a single existential sentence is sufficient).</p>

Elementary properties of free lattices II: decidability of the universal theory

期刊论文
发表日期：

2026年4月16日

查看全文

J. B. Nation,
Gianluca Paolini

摘要

We continue our work on the model theory of free lattices, solving two of the main open problems from our first paper on the subject. Our main result is that the universal (existential) theory of infinite free lattices is decidable. Our second main result is a proof that finitely generated free lattices are positively distinguishable, as for each $n \geqslant 1$ $n ⩾ 1$ there is a positive $\exists \forall $ $\exists \forall$ -sentence true in ${\textbf{F}}_n$ $F_{n}$ and false in ${\textbf{F}}_{n+1}$ $F_{n + 1}$ . Finally, we show that free lattices are first-order rigid in the class of finitely generated projective lattices, and that a projective lattice has the same existential (universal) theory of an infinite free lattice if and only if it has breadth $> 4$ $> 4$ (i.e., a single existential sentence is sufficient).