Finite first-order recognition of $F(X)$ and $\mathbb Z^{(X)}$ from subsemigroup lattices

Proof. Suppose $\mathsf T(S)$ holds and write $E=\{e\}$. If $x\in S$ has repeated powers, then $\langle x\rangle_+$ is finite and contains an idempotent, necessarily $e$. Unless $x=e$, the interval

contradicts $\mathsf P(E,S)$. Hence every $x\neq e$ has distinct powers.

Fix an interval satisfying $\mathsf Z(E,H)$ and write $A=\langle a\rangle_+$, $B=\langle b\rangle_+$. The preceding observation and (9b) imply

We first show $ab=ba=e$. If neither cross product equals $e$, both belong to $A\cup B$. Whenever $ab=a^k$, induction gives

and whenever $ab=b^k$ it gives $a^m b^n=b^{n+m(k-1)}$. The corresponding formulas for $ba$ show that $A\cup B$ is a subsemigroup. This contradicts $e\in A\vee B$. By symmetry, take $ab=e$. If $ba=a^k$, then $ea=a^{k+1}$, and $e^2=e$ gives

contrary to injectivity of powers. The case $ba=b^k$ is identical with the roles reversed. Thus $ba=e$.

Associativity now gives $ea=ae$ and $eb=be$. If $ea=a^k$, then idempotence implies $a^{k^2}=a^k$, hence $k=1$. If $ea=b^k$, multiplying by $b$ gives $b^{k+1}=e$, which is impossible. Therefore $ea$ is either $a$ or $e$, and similarly $eb$ is either $b$ or $e$. The identities $ab=ba=e$ exclude mixed choices. If $e$ absorbs both rays, then

is a proper subsemigroup of $H$ containing $A$ and $V$, contrary to (9a). Consequently $e$ is the identity on $H$, and $a,b$ are mutual inverses. Every element of $H$ is a positive power of one of them or is $e$.

Every $x\neq e$ lies in such an interval. All these cyclic groups have the same identity $e$. It follows that $e$ is an identity on $S$ and every element of $S$ has an inverse in $S$. The injectivity of powers already proved gives torsion-freeness.

Conversely, in a torsion-free group the only idempotent is $1$. Every subsemigroup properly containing $\{1\}$ contains a nonidentity element and hence an infinite monogenic subsemigroup. Set

The two rays are disjoint, $V<B$, and $a(a^{-2})=a^{-1}$ gives $A\vee V=H$. Every nonidentity element of $H$ lies on one ray, so every infinite monogenic subsemigroup of $H$ lies on one ray. Thus all the required conditions hold. The trivial group satisfies the same formula, with the conditions involving infinite codes vacuous. ◻

Proof. Here $D=\{a^n:n\geq2\}=X_{a^2}\vee X_{a^3}$. If $X_b\vee Z=D$, write $b=a^m$ and let $a^n$ generate $Z$, where $m,n\geq2$. Representing $a^2,a^3$ in the join forces

For $m=2$, choose $U=X_{a^5}$. The join has exponent set $\{2\}\cup\{n:n\geq4\}$, so adding its only missing element $a^3$ gives $D$.

Suppose $m=3$ and $X_b\vee U\prec D$. The generator of $U$ is $a^k$ with $k\geq3$, since $k=2$ would make the join equal to $D$. This join lies in $T=\{a^n:n\geq3\}$, and $T<D$. The covering relation forces the join to equal $T$. But representing both $a^4$ and $a^5$ with the exponents $3,k$ forces respectively $k=4$ and $k=5$. This is impossible. ◻

Proof. For soundness, symmetry and (24) allow the unique special product to be $p=ab$. Suppose $ab\neq ba$. Then $ba\notin X_a\cup X_b$, since either membership would imply commutativity. The third condition and (24) give

The case $k=l=1$ contradicts uniqueness of $p$. The second equality gives

contrary to the first condition. In the first case,

If this square lies in neither original ray, condition 4 gives $a^{k+1}=a^2$, $b^{l+1}=b^2$, and hence $k=l=1$, another contradiction. The square therefore lies in $X_a$ or $X_b$. Conjugation gives

Using the expression appropriate to that ray gives $(ba)^2=(ab)^2$. Condition 5 now puts $ba$ in an original ray, the final contradiction.

For necessity, work in an abelian group. The first condition gives

It also gives

A zero exponent in (31) would put one generator in the other positive ray, or make it the identity. With both exponents positive, cancellation reduces the equality to the preceding positive identity relation.

To check $\mathsf{SP}(a,b;ab)$, write $z=a^m b^n$ and $ab=a^r z^s$. Equation (31) gives

Thus $n=s=1$. If $z\neq ab$, then $m=0$, so $z=b$. The other defining implication is symmetric. Uniqueness follows from (24).

For a mixed element $q=a^m b^n$, both exponents are positive. Neither $a^m$ nor $b^n$ is a positive power of the other, since that would put $q$ in an original ray. The same argument gives the required special product.

For condition 4, write $u=a^m$, $v=b^n$ with $m,n\geq2$. A representation

has $r,s>0$ because the square lies in neither ray. Cancellation gives

so $mr=ns=2$ and $m=n=2$. Finally, squaring is injective in a torsion-free abelian group: $q^2=p^2$ gives $(qp^{-1})^2=1$, hence $q=p$. Thus condition 5 holds. ◻

Proof. Use additive notation. If $a,b$ are independent over $\mathbb Z$, independent integer coordinates prove $\mathsf{SP}(a,b;a+b)$ by counting the two letters in a positive word. The identity cases are immediate.

Suppose $a,b\neq0$ are dependent. Choose $z$ independent of $a$; such a $z$ exists because the rank is at least two. A nonzero relation $ma+nb=0$ has $n\neq0$, and it shows that

are independent whenever their first entries are nonzero. For example, from $ka+l(b+z)=0$ one obtains

so $l=0$ and then $k=0$. Taking $u=b+z$ and $v=a+b+z$ proves the second disjunct of (39). If $a+b=0$, its last partial product is an identity case. ◻

Proof. A divisor in $I(M)$ of another element of $I(M)$ equals that element: the remaining factor must be a unit, hence $1$ by (44a). Primality therefore implies that an irreducible dividing a finite product of irreducibles occurs among its factors. Cancelling that factor and inducting on the number of factors proves that the product map

is injective. It is surjective by (44b). The induced group homomorphism

is injective: split a finitely supported integer vector into its positive and negative parts, and apply injectivity of the positive product map. Its image contains $M$, so it is surjective by the second part of (44b).

For $G=\mathbb Z^{(X)}$, take $M=\mathbb N^{(X)}$. Its only unit is $0$, its irreducibles are the standard basis vectors, and each is prime by the corresponding nonnegative coordinate. These vectors generate $M$ and generate $G$ as a group. ◻

Proof. If $\Phi_{\rm ab}$ holds, (18) reconstructs a torsion-free group with the given multiplication, and (37) makes it abelian. The cyclic alternative is free abelian of rank zero or one. Otherwise (40) and $\mathsf{Tot}$ identify the multiplication used in $\mathsf{Cone}$ with the group multiplication, and Lemma 6 applies.

Conversely, a free abelian group satisfies $\mathsf{TF}$ and $\mathsf{AB}$. In rank zero or one it satisfies $\mathsf{Cyc}$. In every other rank, Lemma 5 supplies $\mathsf{Tot}$ and the nonnegative cone supplies $\mathsf{Cone}$. A semigroup isomorphism induces an isomorphism of subsemigroup lattices and preserves the sentence. ◻

Proof. If $x,y$ commute, (24) gives at most one special product. Thus (51a) implies $\mathsf{CP}(x,y)$. The reverse implication always holds. Consequently the subgroup $H$ in (51b) is exactly $C_G(x)$.

In a free group, $C_G(x)\cong\mathbb Z$ for $x\ne1$, so commuting pairs satisfy $\mathsf{CP}$. If $[x,y]\ne1$, the subgroup theorem for free groups gives

Indeed, the rank is at most two by generation and is not at most one by noncommutativity. The images of $x,y$ generate $\mathbb Z^2$ and form an integer basis. Every positive word equal to $xy$ or $yx$ has exactly one occurrence of each generator. The defining implications for $\mathsf{SP}$ follow by substituting a positive word for the intermediate element and counting the two letters. Hence

which establish (51a). The centralizer itself supplies (51b). ◻

Proof. Elements commuting with the same nonidentity element lie in a cyclic group and commute with each other. Thus

Conjugation by $g$ preserves $C_G(x)=\langle r\rangle$. Its effect on $r$ is therefore $r\mapsto r$ or $r\mapsto r^{-1}$. In the first case $g$ commutes with $r$ and hence with $x$.

In the second case $g\neq1$, and $g^2\neq1$ by torsion-freeness. Both $g$ and $r$ commute with $g^2$, so they belong to its cyclic centralizer and commute. This contradicts $grg^{-1}=r^{-1}\neq r$. Finally, if $a,gag^{-1}\in C_G(x)$ and $a\neq1$, the first assertion puts $g$ in the cyclic group $C_G(x)$, giving $gag^{-1}=a$. The case $a=1$ is immediate. ◻

Proof. The first two alternatives follow from (24). In (56c), let $C=C_G(x)$. Then $x,y,p\in C$, $x,y\neq1$, and $z\notin C$. The partial-product witnesses give

Since $xy=yx$, the first and last possibilities are $xyz$ and $zxy$. Equality $xyz=pz$ or $zxy=zp$ gives $p=xy$ by cancellation. Equality $xyz=zp$ or $zxy=pz$ makes $p$ conjugate to $xy$ inside $C$, so Lemma 9 gives the same conclusion, including $xy=1$.

Each remaining equality contradicts malnormality. More explicitly,

In all four cases a nonidentity element of $C$ is conjugated into $C$ by $z$ or $z^{-1}$, contrary to $z\notin C$.

For completeness in a noncyclic free group, identity pairs and noncommuting pairs were treated in Lemma 8. Suppose $x,y\neq1$ commute and $p=xy=yx$. Choose $z\notin C_G(x)$; otherwise $G=C_G(x)$ would be cyclic. Cyclic centralizers imply that $y$ does not commute with $z$, and that $x$ does not commute with $yz$. If $xy\neq1$, then $xy$ also does not commute with $z$. Therefore

satisfy all three partial products in (56c), using the special products for these noncommuting pairs. When $xy=1$, the final partial product is an identity case. This proves completeness. ◻

Proof. Let $\widehat t,\widehat b_i$ be the free generators. We prove the stronger statement: whenever a finite signed word $w$ evaluates in $G$ to $t^n$, its value in the free group is $\widehat t^{n}$. Induct on the number of letters of $w$. For the empty word, the infinite order of $t$ gives $n=0$. If the first letter is $t^\varepsilon$, $\varepsilon\in\{1,-1\}$, the remaining word evaluates to $t^{n-\varepsilon}$, so induction applies.

Suppose the first letter is $b_i$. The path described by the remaining letters starts at $b_i\notin D_i$ and ends at $t^n\in D_i$. Choose its first crossing into $D_i$. By (61b), the crossing is not a $t$-letter. By (61c), the only possible crossing from outside to inside is the step $b_i\to1$ labelled $b_i^{-1}$. Thus

Both $u$ and $v$ are shorter than $w$. Their free values are respectively $1$ and $\widehat t^{n}$, so the asserted equality follows. If the first letter is $b_i^{-1}$, the remaining word runs from $1\in D_i$ to $b_it^n\notin D_i$. Its first crossing out of $D_i$ is $1\to b_i$, giving

with the same values for $u,v$, and the same argument applies.

Taking $n=0$ proves that every word in the kernel is the identity in the free group. Generation gives surjectivity. ◻

Proof. In the reduced-word model, let $D_i$ consist of the elements whose reduced word does not begin with the positive letter $b_i$. Right multiplication by a basis generator changes this property only on the edge $1\to b_i$. To see this, cancellation at the right end cannot change the first letter unless the whole word cancels; in that case the two endpoints are precisely $1,b_i$. This proves (61c), and applying it repeatedly to $t,t^{-1}$ proves (61b).

Let $\chi:F(\{t\}\sqcup I)\to\mathbb Z$ count the exponent sum of $t$, and put

Every displayed generator has $\chi$-value $1$. Therefore a conjugate $hth^{-1}$ belonging to $U_i$ must be a single generator, rather than a product of two or more. If

then $h^{-1}k\in C_G(t)=\langle t\rangle$. Consequently $k=ht^n$ for some $n\in\mathbb Z$, and (61b) gives $h\in D_i$ if and only if $k\in D_i$. We conclude that