The Class of Orderable Groups Is a Quasi-Variety with Undecidable Theory

Benjamin Fine¹, Anthony Gaglione², Gerhard Rosenberger³, Dennis Spellman⁴

¹Department of Mathematics, Fairfield University, Fairfield, Connecticut, USA.
²Department of Mathematics, United States Naval Academy, Annapolis, Maryland, USA.
³Fachbereich Mathematik, University of Hamburg, Bundestrasse, Hamburg, Germany.
⁴Department of Statistics, Temple University, Philadelphia, Pennsylvania, USA.

DOI: 10.4236/apm.2021.113013                

Abstract

Let G be a group. G is right-orderable provided it admits a total order ≤ satisfying hg₁ ≤ hg₂ whenever g₁ ≤ g₂. G is orderable provided it admits a total order ≤ satisfying both: hg₁ ≤ hg₂ whenever g₁ ≤ g₂ and g₁h ≤ g₂h whenever g₁ ≤ g₂. A classical result shows that free groups are orderable. In this paper, we prove that left-orderable groups and orderable groups are quasivarieties of groups both with undecidable theory. For orderable groups, we find an explicit set of universal axioms.

Keywords

Orderable Group, Left Orderable Group, Quasi-Variety

1. Introduction

In [1] (see also [2] ), J. Howie shows that the classes of locally indicable groups and right orderable groups are quasivarieties and he also asserts that the class of locally indicable groups is a subclass of the class of right orderable groups. He posed the question of whether or not these two classes coincide. It turns out that the answer is No, indeed, the class of locally indicable groups is a proper subclass of the class of right orderable groups. The first examples of this were given by George Bergman in [3]. There he shows that the universal covering group of SL(2, R) is right-orderable but not locally indicable. It has been shown that the braid groups are right-orderable but that braid groups on more than 4 strings are not locally indicable (see [4] ).

Howie does not find an explicit set of quasi-identities determining the class of right orderable groups but instead deduces the result rather quickly from the fact that the class is closed under ultraproducts. Clearly, a similar argument shows that the class of orderable groups is a quasi-variety. It would be of interest to find explicit quasi-identities determining the class right orderable group. In this paper, we find explicit sets of universal sentences determining these quasi-varieties. Furthermore, we show that each of the quasi-varieties of orderable groups and right-orderable groups has undecidable theory. Since the paper of Howie, there has been a significnat amount of work on orderable groups (See [2] [3] [4] and the references there).

We note the classic result that free groups are orderable. It follows that every universally free group is orderable since orderability is captured by universal sentences, We remark that, in the finitely generated case, universally free groups are precisely, in the terminology of Sela, the non-abelian limit groups.

2. Preliminaries from Group Theory

Definition 2.1. Let G be a group. G is locally indicable provided every finitely generated subgroup H, $\left\{1\right\}\ne H\le G$ ; admits a surjective homomorphism $G\to \langle a\mathrm{<mo>\; :\; </mo>}\rangle$ onto the infinite cyclic group.

Definition 2.2. Let G be a group. G is right-orderable provided it admits a total order ≤ satisfying $h{g}_1\le h{g}_2$ whenever $g_1\le g_2$ . G is orderable provided it admits a total order ≤ satisfying both

$h{g}_1\le h{g}_2\text{whenever}{g}_1\le g_2\text{and}{g}_{1}h\le g_{2}h\text{whenever}{g}_1\le g_2\mathrm{.}$

Clearly, both right-orderability and orderability are inherited by subgroups.

If G is a group and H and K are (not necessarily distinct) subgroups in G, then $\left[H\mathrm{,}K\right]$ shall be the subgroup of G generated by all commutators $\left[h,k\right]=h^{-1}{k}^{-1}hk$ as h and k vary independently over H and K respectively. The lower central series of G is defined recursively by ${\gamma }_1\left(G\right)=G$ and, if $n>1$ and ${\gamma }_{n-1}\left(G\right)$ has already been defined, then ${\gamma }_n\left(G\right)=\left[{\gamma }_{n-1}\left(G\right)\mathrm{,}G\right]$.

Theorem 2.3. (Iwasawa [5], B. H. Neumann [6] ) Suppose G is a group such that

${\displaystyle \underset{0\le n<\omega }{\cap }}{\gamma }_{n+1}\left(G\right)=\left\{1\right\}$

and, for each n, $0\le n<\omega$, $G/{\gamma }_{n+1}\left(G\right)$ is torsion free. Then G is orderable.

Since, by a classical result of Magnus [7], the hypotheses of Theorem 2.3 are satisfied by free groups, we have the immediate.

Corollary 1. Every free group is orderable.

3. Preliminaries from Logic

A standard reference for the material in this section is the book of Fine, Gaglione, Mysanikov, Spellman and Rosneberger [8]. [Let L₀ be the first-order language with equality containing a binary operation symbol • (suppressed notationally in favor of juxtaposition), a unary operation symbol⁻¹ and a constant symbol 1. Thus, an L₀-structure is a set G provided with a binary operation $G^2\to G\mathrm{,\; <mtext>\; \hspace{0.17em}\; </mtext>}\left(g\mathrm{,}h\right)\mapsto gh$, a unary operation $G\to G\mathrm{,\; <mtext>\; \hspace{0.17em}\; </mtext>}g\mapsto g^{-1}$ and a distinguished element $1\in G$.

A group is then an L₀-structure which is a model of the axioms

· $\forall x_1\mathrm{,}{x}_2\mathrm{,}{x}_3\left(\left(x_1{x}_2\right)x_3=x_1\left(x_2{x}_3\right)\right)$

· $\forall x\left(x1=x\right)$

· $\forall x\left(x{x}^{-1}=1\right)$

Suppose $X=\left\{x_n:n<\omega \right\}$ is the set of variables of L₀. The set of terms of L₀ is defined recursively as follows:

Every variable $x_n$ is a term; moreover, the constant symbol 1 is a term. If t is a term already defined, then ${\left(t\right)}^{-1}$ is a term. If $\left(t_1\mathrm{,}{t}_2\right)$ is an ordered pair of terms already defined, then $\left(t_1\right)\left(t_2\right)$ is a term. Modulo the group axioms, every term is equal to a word on the variables and their formal inverses. Here, 1 is identified with the empty word.

An identity or law of L₀ is a universal sentence of the form $\forall \bar{x}\left(T\left(\bar{x}\right)=t\left(\bar{x}\right)\right)$ where $\bar{x}$ is a tuple of distinct variables and $T\left(\bar{x}\right)$ and $t\left(\bar{x}\right)$ are terms of L₀ involving at most the variables in $\bar{x}$. Thus, for example, the group axioms are identities of L₀.

A quasi-identity of L₀ is a universal sentence of the form

$\forall \bar{x}\left(\underset{i}{{\displaystyle \wedge }}\left(S_i\left(\bar{x}\right)=s_i\left(\bar{x}\right)\right)\to \left(T\left(\bar{x}\right)=t\left(\bar{x}\right)\right)\right)$

where $\bar{x}$ is a tuple of distinct variables and $S_i\left(\bar{x}\right)\mathrm{,}{s}_i\left(\bar{x}\right)\mathrm{,}T\left(\bar{x}\right)$ and $t\left(\bar{x}\right)$ are terms of L₀ involving at most the variables in $\bar{x}$. Note that the identity $\forall \bar{x}\left(T\left(\bar{x}\right)=t\left(\bar{x}\right)\right)$ is equivalent to the quasi-identity $\forall \bar{x}\left(\left(1=1\right)\to \left(T\left(\bar{x}\right)=t\left(\bar{x}\right)\right)\right)$ so that identities may be considered as special cases of quasi-identities. Note also that, modulo the group axioms, the quasi-identity

$\forall \bar{x}\left(\underset{i}{{\displaystyle \wedge }}\left(S_i\left(\bar{x}\right)=s_i\left(\bar{x}\right)\right)\to \left(T\left(\bar{x}\right)=t\left(\bar{x}\right)\right)\right)$

is equivalent to one of the form

$\forall \bar{x}\left(\underset{i}{{\displaystyle \wedge }}\left(u_i\left(\bar{x}\right)=1\right)\to \left(w\left(\bar{x}\right)=1\right)\right)$

where the $u_i\left(\bar{x}\right)$ and $w\mathrm{<mo\; stretchy="false">\; (\; </mo>}\bar{x}\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ are words in at most the variables in $\bar{x}$ and their formal inverses. A quasi-variety of groups is the model class of a set of quasi-identities of L₀ together with the group axioms. Following Chang and Keisler [9] let us call a class of L₀-structures elementary provided it is the model class of at least one set of sentences of L₀. A theorem of Mal’cev [10] asserts that a nonempty elementary class of groups is a quasi-variety of groups if and only if it is closed under taking subgroups and (unrestricted) direct products.

Two (not necessarily distinct) L₀-structures G and H are elementarily equivalent, in symbols $G\equiv H$, provided they satisfy precisely the same sentences of L₀. (In particular, if $G\equiv H$, then H is a group if and only if G is a group.) The next theorem gives an algebraic characterization of elementary equivalence. It was initially proven by Keisler assuming the Generalized Continuum Hypothesis and subsequently proven by Shelah without need of that assumption.

Theorem 3.1. (Keisler-Shelah [11] ) Two L₀-structures are elementarily equivalent if and only if they have isomorphic ultrapowers.

(For a discussion of ultraproducts, see, for example, [CK]).

Theorem 3.2. (Chang and Keisler [9] ) A class of L₀-structures is an elementary class if and only if it is closed under both elementary equivalence and ultraproducts.

To show undecidbability, we will need the following result.

Theorem 3.3. Let $\mathcal{X}$ be an elementary class of groups. If $\mathcal{X}$ contains a finitely presented group with unsolvable word problem, then the theory of $\mathcal{X}$ is undecidable.

Proof. Suppose G is a group in the class $\mathcal{X}$ and suppose that G has finite presentation

$\langle a_1,\cdots ,a_m;\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>}{R}_1\left(a_1,\cdots ,a_m\right)=\cdots =R_n\left(a_1,\cdots ,a_m\right)=1\rangle$

Suppose further that G has unsolvable word problem. For each word $w\left(x_1\mathrm{,}\cdots \mathrm{,}{x}_m\right)$ on the distinct variables $x_1\mathrm{,}\cdots \mathrm{,}{x}_m$ and their formal inverses let ${\sigma }_w$ be the sentence

$\forall x_1,\cdots ,x_m\left(\underset{i=1}{\overset{n}{{\displaystyle \wedge }}}\left(R_i\left(x_1,\cdots ,x_m\right)=1\right)\to \left(w\left(x_1,\cdots ,x_m\right)=1\right)\right).$

If there were a recursive algorithm to decide whether or not each ${\sigma }_w$ is true in every group in $\mathcal{X}$, then we would have an algorithm to solve the word problem for G. The contradiction shows the theory of $\mathcal{X}$ is undecidable. +

Finally in this section, we explicitly mention the positive solution to the Tarski question.

Theorem 3.4. (Kharlampovich and Myasnikov [12], Sela [13] ) Every non-abelian free group is elementarily equivalent to the free group $F=\langle a_1\mathrm{,}{a}_2\mathrm{<mo>\; ;\; </mo>}\rangle$ .

4. The Main Results

In this section, we show that the class of orderable groups forms a quasi-variety and further the theory of the orderable groups is undecidable.

Let G be a group and S be a subsemigroup of G. We call S normal in G provided it is invariant under conjugation by arbitrary elements in G. If n is a positive integer and $\left(b_1\mathrm{,}\cdots \mathrm{,}{b}_n\right)\in G^n$ we let $SG\left(b_1\mathrm{,}\cdots \mathrm{,}{b}_n\right)$ be the least normal subsemigroup of G containing $\left\{b_1\mathrm{,}\cdots \mathrm{,}{b}_n\right\}$ as a subset and $S\left(b_1\mathrm{,}\cdots \mathrm{,}{b}_n\right)$ the least subsemigroup of G containing $\left\{b_1\mathrm{,}\cdots \mathrm{,}{b}_n\right\}$ as a subset.

Let $\mathbb{Z}$ be the ring of integers, $\mathbb{N}=\left\{\mathrm{1,2,3,}\cdots \right\}$ be the class of posiitve integers and $U=\left\{1,-1\right\}$ be its group of units.

Theorem 4.1. (See Passman [14] ) (a) A necessary and sufficient condition for a group G to be left orderable is that, for every finite subset $\left\{a_1\mathrm{,}\cdots \mathrm{,}{a}_n\right\}\subseteq G\backslash \left\{1\right\}$ , the intersection of the 2ⁿ semigroups $S\left(a_1^{{\epsilon }_1}\mathrm{,}\cdots \mathrm{,}{a}_n^{{\epsilon }_n}\right)$ is empty as $\left({\epsilon }_1\mathrm{,}\cdots \mathrm{,}{\epsilon }_n\right)$ varies over $U^n$ .

(b) A necessary and sufficient condition for a group G to be orderable is that, for every finite subset $\left\{a_1\mathrm{,}\cdots \mathrm{,}{a}_n\right\}\subseteq G\backslash \left\{1\right\}$, the intersection of the 2ⁿ normal subsemigroups $SG\left(a_1^{{\epsilon }_1}\mathrm{,}\cdots \mathrm{,}{a}_n^{{\epsilon }_n}\right)$ is empty as $\left({\epsilon }_1\mathrm{,}\cdots \mathrm{,}{\epsilon }_n\right)$ varies over $U^n$.

Theorem 4.2. The class of orderable groups is elementary.

Proof. For each $n\in \mathbb{N}$, $\bar{\epsilon }=\left({\epsilon }_1\mathrm{,}\cdots \mathrm{,}{\epsilon }_n\right)\in U^n$ and each $\bar{N}=\left(N_0\mathrm{,}{N}_1\mathrm{,}\cdots \mathrm{,}{N}_n\right)\in {\mathbb{N}}^{n+1}$ let $w\left(\bar{\epsilon }\mathrm{,}\bar{N}\right)$ be a word of positive length at most $N_0$ on the free semigroup generators (regarded as compound symbols; so, no formal cancellation is permitted) $z_{i\mathrm{,}j}^{-1}{y}_i^{{\epsilon }_i}{z}_{i\mathrm{,}j}$, $1\le i\le n\mathrm{,\; <mtext>\; \hspace{0.17em}\; </mtext>1}\le j\le N_i$. In view of Lorenzen’s Theorem (see [14] ), the class of orderable groups is axiomatized by the group axioms together with the sentences

$\forall x,y_1,\cdots ,y_n,z_{1,1},\cdots ,z_{n,N_n}\left(\left(\underset{1\le i<j\le n}{{\displaystyle \wedge }}\left(y_i\ne y_j\right)\wedge \underset{\bar{\epsilon }\in U^n}{{\displaystyle \wedge }}\left(x=w\left(\bar{\epsilon }\mathrm{,}\bar{N}\right)\right)\right)\to \underset{i=1}{\overset{n}{{\displaystyle \vee }}}\left(y_i=1\right)\right)$

as n varies over $\mathbb{N}$, and the $\bar{N}$ vary over ${\mathbb{N}}^{n+1}$ and as the $w\left(\bar{\epsilon }\mathrm{,}\bar{N}\right)$ vary over all possible choices. (Note: $a_i\ne 1$ so $y_i\ne 1$ ). +

Corollary 2. Any elementary free group and more generally any universally free group is orderable.

Theorem 4.3. The class of left-orderable groups is elementary.

Proof. To prove this we shall utilize the characterization of elementary classes given in Theorem 3.2. Suppose ${\left(G_i\right)}_{i\in I}$ is a family of left-orderable groups indexed by a nonempty set I. For each $i\in I$, let ${\le }_i$ be a left order on $G_i$. Let D be an ultrafilter on I and let G be the ultraproduct of the family ${\left(G_i\right)}_{i\in I}$ with respect to the ultrafilter D on I.

Then ${\left[g\right]}_D\le {\left[h\right]}_D$ is well-defined on G by insisting $\left\{i\in I\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>\; <mo>\; :\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>}{g}_i{\le }_i{h}_i\right\}\in D$ and it is easily seen to be a left order on G. Thus, the class of left-orderable groups is closed under taking ultraproducts. Now suppose H is a left-orderable group and $K\equiv H$. By the Keisler-Shelah characterization of elementary equivalence ( [10] ), H and K have isomorphic ultrapowers ${}^{\ast }H$ and ${}^{\ast }K$. The fact that the class of left-orderable groups is closed under taking ultraproducts implies that ${}^{\ast }H$ admits a left order. Then the isomorphic group ${}^{\ast }K$ admits a left order. But K embeds in ${}^{\ast }K$ and the left order is inherited by subgroups. Thus, H left-orderable and $H\equiv K$ implies K left-orderable. Hence, the class of left-orderable groups is closed under elementary equivalence as well as ultraproducts. Therefore the class of left-orderable groups is elementary. +

Theorem 4.4. The class of orderable groups is a quasi-variety of groups with an undecidable theory.

Proof. Using Mal’cev’s characterization of quasi-varieties it suffices to show that the class of orderable groups is closed under taking subgroups and unrestricted direct products. We have already noted that order is inherited by subgroups. (Alternatively, since the class has a set of universal axioms it is closed under taking substructures).

Suppose ${\le }_0$ is an order on the group $G_0$ and ${\le }_1$ is an order on the group $G_1$. Then the lexicographic order on $G_0\times G_1$ (i.e., if $\left(g_0\mathrm{,}{g}_1\right)\ne \left(h_0\mathrm{,}{h}_1\right)$, then $\left(g_0,g_1\right)<\left(h_0,h_1\right)$ provided either $g_0{<}_0{h}_0$ or $g_0=h_0$ and $g_1{<}_1{h}_1$ ) makes $G_0\times G_1$ into an ordered group. Corollary 2 of Chapter 7, Section 47, p. 292 of Grätzer [15] asserts that if an elementary class $\mathcal{X}$ is closed under the direct product of two structures, then it is closed under arbitrary direct products of nonvoid families of structures in $\mathcal{X}$.

Alternatively, we could argue as follows. We may well-order the index set of any nonvoid family of orderable groups. There is no loss of generality in taking the index set to be an ordinal $\alpha$. Suppose ${\le }_{\xi }$ is a left order on $G_{\xi }$ for all ordinals $\xi <\alpha$. Then the lexicographical order on

$G={\displaystyle \underset{\xi <\alpha }{\prod }}{G}_{\xi }$

(i.e., if ${\left(g_{\xi }\right)}_{\xi <\alpha }\ne {\left(h_{\xi }\right)}_{\xi <\alpha }$, then ${\left(g_{\xi }\right)}_{\xi <\alpha }<{\left(h_{\xi }\right)}_{\xi <\alpha }$ provided $g_{\mu }{<}_{\mu }{h}_{\mu }$ where $\mu$ is the least ordinal $\xi$ such that $g_{\xi }\ne h_{\xi }$ ) makes G into an ordered group. It follows that the class of orderable groups is a quasi-variety of groups.

+

Theorem 4.5. The class of left-orderable groups is a quasi-variety of groups.

We must now show undecidability.

Theorem 4.6. The theory of orderable groups is undecidable.

Proof. By a result of Bludov and Glass [16], there is a finitely presented orderable group with unsolvable word problem. The result then follows from the proof of Theorem 2.3. +

Exactly the same proof shows.

Theorem 4.7. The theory of left-orderable groups is undecidable.

Remark 4.8. It would be of interest to find explicit quasi-identities axiomatizing the class of left-orderable groups.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Howie, J. (1982) On Locally Indicable Groups. Mathematische Zeitschrift, 180, 445-461. https://doi.org/10.1007/BF01214717
[2]	Rhemtulla, A. and Rolfsen, D. (2002) Local Indicability in Ordered Groups: Braids and Elementary Amenable Groups. Proceedings of the American Mathematical Society, 30, 2569-2577. https://doi.org/10.1090/S0002-9939-02-06413-4
[3]	Bergman, G. (1991) Right-Orderable Groups That Are Not Locally Indicable. Pacific Journal of Mathematics, 147, 243-248. https://doi.org/10.2140/pjm.1991.147.243
[4]	Fenn, R., Greene, M.T., Rolfsen, D., Rourke, C. and Wiest, B. (1998) Ordering the Braid Groups.
[5]	Iwasawa, K. (1948) On Linearly Ordered Groups. Journal of the Mathematical Society of Japan, 1, 1-9. https://doi.org/10.2969/jmsj/00110001
[6]	Neumann, B.H. (1949) On Ordered Groups. American Journal of Mathematics, 71, 1-18. https://doi.org/10.2307/2372087
[7]	Magnus, W., Karrass, A. and Solitar, D. (1966) Combinatorial Group Theory. John Wiley-Interscience, New York.
[8]	Fine, B., Gaglione, A., Myansnikov, A., Rosenberger, G. and Spellman, D. (2018) Elementary Theory of Groups. DeGruyter, Berlin.
[9]	Chang, C.C. and Keisler, H.J. (1977) Model Theory. Second Edition, North-Holland, Amsterdam.
[10]	Mal’cev, A.I. (1966) Some Remarks on Quasi-Varieties of Algebraic Structures. Algebra Logic, 5, 3-9.
[11]	Shelah, S. (1972) Every Two Elementarily Equivalent Models Have Isomorphic Ultrapowers. Israel Journal of Mathematics, 10, 224-233. https://doi.org/10.1007/BF02771574
[12]	Kharlamapovich, O. and Myasnikov, A. (2006) Elementary Theory of Free Nonabelian Groups. Journal of Algebra, 302, 451-552. https://doi.org/10.1016/j.jalgebra.2006.03.033
[13]	Sela, Z. (2006) Diophantine Geometry over Group VI: The Elementary Theory of a Free Group. Geometric & Functional Analysis GAFA, 66, 707-730. https://doi.org/10.1007/s00039-006-0565-8
[14]	Passman, D.S. (2011) The Algebraic Structure of Group Rings. Dover, New York.
[15]	Grätzer, G. (1968) Universal Algebra. Van Nostrand, Princeton.
[16]	Bludov, V.V. and Glass, A.M.W. (2012) A Finitely Presented Orderable Group with Insoluble Word Problem. Bulletin of the London Mathematical Society, 44, 85-98. https://doi.org/10.1112/blms/bdr070