Definability in the lattice of equational theories of semigroups (Q1209280)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Definability in the lattice of equational theories of semigroups |
scientific article |
Statements
Definability in the lattice of equational theories of semigroups (English)
0 references
16 May 1993
0 references
The authors study first order definability in the lattice \(L\) of equational theories of semigroups. The results are elegant and the techniques are new. Let \(X\) be a denumerably infinite set and let \(W\) be the free semigroup on \(X\). An equational theory can be identified with a fully invariant congruence on \(W\). If \(J\) is a fully invariant ideal of \(W\), then the equational theory \((J\times J)\cup \Delta\), where \(\Delta\) is the diagonal of \(W\) is called an ideal theory and will be denoted by \(I_ J\). Theorem 1: The theory of semilattices is definable in \(L\) and the set of ideal theories is definable in \(L\). The relation \(u\leq v\), defined by \(f(u)\) is a subword of \(v\) for some endomorphism of \(W\), is a quasi order and the resulting equivalence relation produces a partially ordered set: the set \(P\) of word patterns; \(u\), \(v\) are of the same pattern iff \(v = f(u)\) for some automorphism of \(W\). If \([u]\) denotes the fully invariant ideal generated by \(u\), then \(I_{[u]}\) is a code for the pattern of \(u\) in \(L\). The authors study several relations between patterns, including covering. The equational theory generated by \((a,b)\) is denoted by \(Eq(a,b)\). The mirror image of words induces an involutive automorphism of \(L\) which will be denoted by \(\partial\) and called dual. The authors call a set \(K\) of equations good if there is a first order formula \(f(X_ 1,X_ 2,X_ 3)\) in the language of lattice theory such that for any triple \(T_ 1,T_ 2,T_ 3\) in \(L\), \(f(T_ 1,T_ 2,T_ 3)\) is true in \(L\) iff either the triple \(T_ 1,T_ 2,T_ 3\) or the triple \(T_ 1^ \partial,T_ 2^ \partial,T_ 3^ \partial\) is \(I_{[xxy]},I_{[xaxb]},Eq(a,b)\) for some \((a,b)\in K\) and \(x\in X\) not occurring in \(ab\) and \(y\in X\), \(x\neq y\). Theorem 2: Let \(K\) be a good set of equations. Then: (1) The set \(\{Eq(a,b): (a,b)\in K\cup K^ \partial\}\) is definable in \(L\). (2) For every \((a,b)\in K\), the one based equational theory \(Eq(a,b)\) is an element definable up to duality in \(L\). (3) If \(\alpha\) is an automorphism of \(L\), then either \(\alpha\) is the identity on all equational theories generated by a subset of \(K\), or \(\alpha(T) = T^ \partial\) for every equational theory \(T\) generated by a subset of \(K\). The authors conjecture that the set \(W\times W\) is good. They prove that many sets of equations are good. Theorem 3: The set of equational theories of finite semigroups is definable and each theory of a finite semigroup is semi-definable. Theorem 4. The set of finitely axiomatizable locally finite theories is definable and each such theory is semi-definable. Theorem 5: The set of locally finite theories is definable. Theorem 6: The set of all finitely axiomatizable theories is definable. An equation \((a,b)\) is called 9-smooth if neither the first nor the last better of \(a\) is repeated in \(a\) but both the first and last letter of \(b\) are repeated in \(b\) and \(a,b\) contains exactly the same set of letters. The authors conjecture that the set of all 9-smooth equations is good and prove that this implies that the set of all equations is good.
0 references
lattices of equational theories of semigroups
0 references
first order definability
0 references
free semigroups
0 references
fully invariant congruences
0 references
theory of semilattices
0 references
ideal theories
0 references
partially ordered sets
0 references
word patterns
0 references
first order formula
0 references
good sets of equations
0 references
equational theories of finite semigroups
0 references
finitely axiomatizable locally finite theories
0 references