First-order separation of pro-orderable groups from a bi-orderable matrix group over Z[F₂]

Problem

Let $\mathcal O$ be the class of bi-orderable groups and $\mathcal O^*$ the class in which every bi-invariant partial order extends to a bi-invariant total order. Does the first-order theory of $\mathcal O^*$ axiomatize exactly $\mathcal O$ ?

\operatorname{Mod}\bigl(\operatorname{Th}_{\{\cdot,{}^{-1},1\}}(\mathcal O^*)\bigr) \stackrel{?}{=}\mathcal O.

The separation theorem

A partial order on a group $G$ is bi-invariant if

a\le b\quad\Longrightarrow\quad ca\le cb\text{ and }ac\le bc \qquad(a,b,c\in G).

A group is bi-orderable if it admits a bi-invariant total order, and pro-orderable if every bi-invariant partial order on it extends to a bi-invariant total order on the same group. We include the equality order among partial orders. Write $\mathcal O$ and $\mathcal O^*$ for these two classes; thus $\mathcal O^*\subseteq\mathcal O$ .

All first-order theories below use the language

L_{\mathrm{grp}}=\{\cdot,{}^{-1},1\}.

For a class $\mathcal C$ of groups, set

\operatorname{Axi}(\mathcal C)=\operatorname{Mod}\bigl(\operatorname{Th}_{L_{\mathrm{grp}}}(\mathcal C)\bigr).

This is the smallest axiomatizable class containing $\mathcal C$ . The order is not a named relation in this definition.

Theorem 1. There is a countable bi-orderable group $H$ and a parameter-free first-order group sentence $\sigma$ such that

G\models\sigma\quad(G\in\mathcal O^*),\qquad H\models\neg\sigma.

Moreover, every group in $\operatorname{Axi}(\mathcal O^*)$ is bi-orderable. Hence

\tag{5} \operatorname{Axi}(\mathcal O^*)\subsetneq\mathcal O.

Equality in (5) is asked in Kourovka Problem 3.20 and in (1, Problem 3.17). For right-invariant orders, Medvedev obtained the analogous strictness result; see (1, comment on Problem 3.17). Here all orders are bi-invariant. The sentence $\sigma$ excludes $H$ from $\operatorname{Mod}(\operatorname{Th}(\mathcal O^*))$ . We use the order-extension condition of Mal’tsev (4) and prove the required instance of Kokorin’s normal-semigroup obstruction (3).

We use

x^g=g^{-1}xg,\qquad [x,y]=x^{-1}y^{-1}xy.

An obstruction from disjoint normal subgroups

Lemma 2. Let $G\in\mathcal O^*$ and let $N,M\triangleleft G$ satisfy $N\cap M=1$ . If

xx^s\in N,\qquad xx^t\in M

for some $x,s,t\in G$ , then $x=1$ .

Proof. Suppose $x\ne1$ . Choose a bi-order on $G$ , reversing it if necessary so that $x>1$ . Conjugation preserves this order, and therefore

u:=xx^s>1,\qquad v:=xx^t>1.

The normality and disjointness assumptions give $[N,M]=1$ . Define

\tag{9} P=\{nm:n\in N,\ m\in M,\ n\ge1,\ m\le1\}.

Then $1\in P$ , $PP\subseteq P$ , and $P^g=P$ for every $g\in G$ . We also have $P\cap P^{-1}=\{1\}$ . Indeed, if

a=nm,\qquad a^{-1}=n'm',\qquad n,n'\ge1,\quad m,m'\le1,

then $nn'mm'=1$ . Thus $nn'=(mm')^{-1}\in N\cap M$ , so $nn'=mm'=1$ . The inequalities imply $n=n'=m=m'=1$ .

Consequently,

a\preccurlyeq b\quad\Longleftrightarrow\quad a^{-1}b\in P

is a bi-invariant partial order. It satisfies $1\preccurlyeq u$ and $v\preccurlyeq1$ . Extend it to a bi-order $\preccurlyeq'$ on $G$ . In every bi-order,

\tag{12} 1\le yy^g\quad\Longleftrightarrow\quad1\le y, \qquad y>1\Longrightarrow yy^g>1.

Thus $1\preccurlyeq' u$ implies $1\preccurlyeq'x$ , and $x\ne1$ implies $1\prec'x$ . Equation (12) now gives $1\prec'v$ , contradicting $v\preccurlyeq'1$ . ◻

Two disjoint left ideals

Put

F=F(a,b),\qquad R=\mathbb Z[F].

We identify $F$ with its canonical multiplicative basis in $R$ .

Lemma 3. For $p,q\in R$ ,

p(1+a)=q(1+b)\quad\Longrightarrow\quad p=q=0.

In particular, $R(1+a)\cap R(1+b)=0$ .

Proof. Let $\partial_a,\partial_b:R\to R$ be the additive Fox derivatives (2). On $F$ they are determined by

\partial_i(gh)=\partial_i(g)+g\partial_i(h),\qquad \partial_i(j)=\delta_{ij}\quad(i,j\in\{a,b\}).

One can construct them directly by mapping each free generator $j$ to $(\delta_{ij},j)$ in the semidirect product of the additive group of $R$ by $F$ , where $F$ acts by left multiplication. Extending additively gives

\partial_i(pj)=\partial_i(p)+\delta_{ij}p, \qquad \partial_i\bigl(p(1-j)\bigr)=-\delta_{ij}p.

Hence $p(1-a)=q(1-b)$ forces $p=q=0$ by applying $\partial_a$ and $\partial_b$ .

Let $\varepsilon:F\to\{\pm1\}$ send both generators to $-1$ . The additive map

\tau\left(\sum_g n_g g\right)=\sum_g n_g\varepsilon(g)g

is an involutive ring automorphism. Applying $\tau$ to $p(1+a)=q(1+b)$ reduces to the preceding case. ◻

The matrix group and its order

Define

\tag{18} H=\left\{ h(g,p,q,r)= \begin{pmatrix}g&p&r\\0&1&q\\0&0&1\end{pmatrix} :g\in F,\ p,q,r\in R \right\}.

Its operations are

\begin{align*} h(g,p,q,r)h(g',p',q',r') &=h(gg',gp'+p,q+q',gr'+pq'+r),\tag{19a}\\ h(g,p,q,r)^{-1} &=h(g^{-1},-g^{-1}p,-q,g^{-1}(pq-r)).\tag{19b} \end{align*}

All products in $R$ retain their displayed order. The group $H$ is countable because $F$ and $R$ are countable.

Lemma 4. The free group $F(a,b)$ admits a bi-order.

Proof. Let $A=M_2(\mathbb Z)$ , with any lexicographic order on its four entries, and let

U=\{f\in A[T]^\times:f(0)=I\}.

Order $U$ by the coefficient of lowest degree at which two polynomials differ. The order on the additive group of $A$ is translation-invariant. If $f$ and $g$ first differ in degree $n$ and $h(0)=I$ , then

(hf-hg)_n=f_n-g_n=(fh-gh)_n,

and both differences vanish below degree $n$ . Thus this order is invariant under multiplication on either side.

Map

a\longmapsto I+TE_{12},\qquad b\longmapsto I+TE_{21}.

For $m\in\mathbb Z$ , $(I+TE_{ij})^m=I+mTE_{ij}$ . In a nonempty reduced syllable word, the factors alternate between these two types, with nonzero exponents $m_1,\ldots,m_k$ . The coefficient of degree $k$ is a matrix unit multiplied by $m_1\cdots m_k\ne0$ . The image is therefore not $I$ , proving injectivity. Pull back the bi-order of $U$ . ◻

Fix this bi-order of $F$ . Give the additive group of $R$ the lexicographic order determined by the coefficient at the least element of the finite support of a difference. For each $g\in F$ , the map $p\mapsto gp$ preserves this order, since left multiplication permutes the basis by an order-preserving bijection.

Proposition 5. The lexicographic order on the coordinates

(g,q,p,r)

is a bi-order on $H$ .

Proof. Fix $c=h(k,u,v,w)$ . Under left multiplication by $c$ , the coordinates become

(kg,\ v+q,\ kp+u,\ kr+uq+w).

The first unequal coordinate retains its comparison. For the last coordinate, the earlier equalities include $q=q'$ , so the terms $uq+w$ agree, and multiplication by $k$ preserves the order on $R$ .

Under right multiplication by $c$ , the coordinates become

(gk,\ q+v,\ gu+p,\ gw+pv+r).

At the $p$ coordinate one already has $g=g'$ , and at the $r$ coordinate one also has $p=p'$ . The added terms therefore agree whenever they precede the first difference. This proves right invariance as well. ◻

Defining the obstruction in the group language

For elements $z,x,d,e$ of an arbitrary group, define the formula

\tag{26} D(z;x,d,e)\;:\Longleftrightarrow\; \exists y\bigl([y,x]=1\ \land\ [y,d]=1\ \land\ z=[y,e]\bigr).

Let $\operatorname{Normal}(x,d,e)$ be the following finite conjunction:

\begin{align*} &D(1;x,d,e),\notag\\ &\forall z,w\bigl(D(z;x,d,e)\land D(w;x,d,e) \Rightarrow D(zw^{-1};x,d,e)\bigr),\notag\\ &\forall z,g\bigl(D(z;x,d,e)\Rightarrow D(z^g;x,d,e)\bigr). \tag{27} \end{align*}

It asserts exactly that the set defined by $D$ is a normal subgroup.

Define $\Phi(x,d,e,f,s,t)$ by

\begin{align*} &x\ne1\ \land\ \operatorname{Normal}(x,d,e) \ \land\ \operatorname{Normal}(x,d,f)\notag\\ &\quad{}\land\ \forall z\bigl(D(z;x,d,e)\land D(z;x,d,f)\Rightarrow z=1\bigr)\notag\\ &\quad{}\land\ D(xx^s;x,d,e)\ \land\ D(xx^t;x,d,f),\tag{28} \end{align*}

and put

\tag{29} \sigma=\neg\exists x,d,e,f,s,t\;\Phi(x,d,e,f,s,t).

Every symbol in (26)–(29) is a group-language symbol or an abbreviation for a displayed formula. In particular, no subgroup or order variable occurs.

Proposition 6. Every pro-orderable group satisfies $\sigma$ , and $H$ satisfies $\neg\sigma$ .

Proof. The first assertion follows from Lemma 2, applied to the two normal subgroups defined in (28).

In $H$ , put

z(c)=h(1,0,0,c),\qquad d=h(1,1,0,0),\qquad e(c)=h(1,0,c,0),\qquad \delta(g)=h(g,0,0,0).

Equations (19a) and (19b) give

\begin{align*} [y,z(1)]=[y,d]=1 &\quad\Longleftrightarrow\quad y=h(1,p,0,r) \text{ for some }p,r\in R,\tag{31a}\\ [h(1,p,0,r),e(c)]&=z(pc),\tag{31b}\\ z(c)^{h(g,p,q,r)}&=z(g^{-1}c).\tag{31c} \end{align*}

In (31a), commuting with $z(1)$ forces $g=1$ , since distinct elements of $F$ are distinct basis elements of $R$ ; commuting also with $d$ then forces $q=0$ .

It follows that

\tag{32} \{z:D(z;z(1),d,e(c))\}=z(Rc).

This is a normal subgroup: addition and negation preserve $Rc$ , and (31c) acts on it by left multiplication. Set

N=z\bigl(R(1+a)\bigr),\qquad M=z\bigl(R(1+b)\bigr).

Lemma 3 gives $N\cap M=1$ . Finally choose

x=z(1),\qquad e=e(1+a),\qquad f=e(1+b),\qquad s=\delta(a^{-1}),\qquad t=\delta(b^{-1}).

Then $x\ne1$ and

xx^s=z(1+a)\in N,\qquad xx^t=z(1+b)\in M.

These six parameters satisfy $\Phi$ . ◻

Axiomatic closure and orderability

Lemma 7. Every group in $\operatorname{Axi}(\mathcal O^*)$ is bi-orderable.

Proof. Let $G\in\operatorname{Axi}(\mathcal O^*)$ . For each finite subset $S\subseteq G$ , let $\theta_S((X_a)_{a\in S})$ be the finite conjunction

\bigwedge_{\substack{a,b\in S\\a\ne b}}X_a\ne X_b \quad\land\quad \bigwedge_{\substack{a,b,c\in S\\ab=c}}X_aX_b=X_c.

The existential closure of $\theta_S$ holds in $G$ , witnessed by $X_a=a$ . It therefore holds in some $K_S\in\mathcal O^*$ : otherwise its negation would belong to $\operatorname{Th}(\mathcal O^*)$ and also hold in $G$ . Choose a bi-order $\le_S$ on $K_S$ and witnesses $f_S:S\to K_S$ . Extend $f_S$ to all of $G$ by setting $f_S(a)=1$ outside $S$ .

Let $\mathcal U$ be an ultrafilter on the finite subsets of $G$ containing every set $\{S:S\supseteq S_0\}$ with $S_0$ finite. Define

a\le b\quad\Longleftrightarrow\quad \{S:f_S(a)\le_S f_S(b)\}\in\mathcal U.

Reflexivity, transitivity and totality follow from the corresponding order laws and the ultrafilter property. On the cofinal set $S\supseteq\{a,b\}$ , distinct $a,b$ have distinct images, giving antisymmetry. For translation invariance, take the cofinal set

\mathcal C_{a,b,c} =\{S:S\supseteq\{a,b,c,ca,cb,ac,bc\}\}\in\mathcal U.

On this set the finite diagrams give

\begin{align*} f_S(ca)&=f_S(c)f_S(a),& f_S(cb)&=f_S(c)f_S(b),\\ f_S(ac)&=f_S(a)f_S(c),& f_S(bc)&=f_S(b)f_S(c). \end{align*}

Consequently $a\le b$ implies $ca\le cb$ and $ac\le bc$ . Thus $\le$ is a bi-order on $G$ . ◻

Proof of Theorem 1. The group $H$ is countable and bi-orderable by construction and Proposition 5. Proposition 6 gives $H\notin\operatorname{Axi}(\mathcal O^*)$ , while Lemma 7 gives $\operatorname{Axi}(\mathcal O^*)\subseteq\mathcal O$ . ◻

References

Preprint · Lean (GitHub)

V. V. Bludov, A. M. W. Glass, V. M. Kopytov and N. Ya. Medvedev, Unsolved problems in ordered and orderable groups, arXiv:0906.2621 (2009).

R. H. Fox, Free differential calculus. I. Derivation in the free group ring, Ann. of Math. (2) 57 (1953), 547–560. doi:10.2307/1969736.

A. I. Kokorin, On the theory of orderable groups, Algebra i Logika. Seminar 2, no. 6 (1963), 15–20 (Russian). Math-Net.Ru: al996.

A. I. Mal’tsev, On the completion of group order, Trudy Mat. Inst. Steklov. 38 (1951), 173–175 (Russian). Math-Net.Ru: tm1116.