Finite first-order recognition of freeness from subsemigroup lattices

Abstract

Let \(\mathcal L(S)\) be the lattice of all subsemigroups of a nonempty semigroup \(S\), including the empty subsemigroup. There are sentences \(\Phi_{\rm fr}\) and \(\Phi_{\rm ab}\) in the language \(\{\wedge,\vee\}\) such that \(\mathcal L(S)\models\Phi_{\rm fr}\) exactly when \(S\) is a free group, and \(\mathcal L(S)\models\Phi_{\rm ab}\) exactly when \(S\) is a free abelian group. The ranks are arbitrary, including zero. The abelian sentence uses a reduced positive cone with prime irreducibles. For free groups, subsemigroup cuts detect a free basis, while an unordered-product relation determines multiplication up to reversal. An oriented noncommuting pair and Beth's definability theorem eliminate the temporary multiplication relation. These finite axiomatizations give affirmative answers to both parts of Kourovka Problem 2.81.