§ 1. Ordered groups. Divisibility

The notions and results presented in this section concern the study of order relations in commutative monoids (I, p. 12, Def. 2), the most important case being that of abelian groups. Unless explicitly stated otherwise, we will use additive notation for the composition law in all groups and monoids under study. On the other hand, as we go along we will present certain important algebraic applications of the theory of ordered groups and monoids, and we will accordingly translate certain of our results into the multiplicative notation which is appropriate for these applications.

1. Definition of ordered monoids and groups

(OM) For each $z \in M$, the relation $x \leq y$ implies $x + z \leq y + z$.

A set $M$ equipped with a commutative monoid structure and an ordering which are compatible is called an ordered monoid; if its commutative monoid structure is a group structure, then it is called an ordered group.

In an analogous fashion, we can define the notion of a noncommutative ordered monoid (VI, p. 30, Ex. 1).

If an ordering is compatible with a given monoid structure, then so is the opposite ordering.

2. Pre-ordered monoids and groups

Recall that if a relation $x \leq y$ between elements of a set $E$ is reflexive and transitive, it is called a pre-order relation (Set Theory, III, p. 133). The relation « $x \leq y$ and $y \leq x$ » is an equivalence relation $S$ on $E$, compatible with the relation $x \leq y$; on passing to the quotient, the relation $\leq$ induces an order relation on $E/S$, called the order relation associated to $\leq$.

(POM) For each $z \in M$, the relation $x \leq y$ implies $x + z \leq y + z$.

A set $M$ equipped with a commutative monoid structure and a pre-order relation which are compatible is called a pre-ordered monoid.

Let $M$ be a pre-ordered monoid, and $S$ the equivalence relation « $x \leq y$ and $y \leq x$ ». By virtue of (POM) the relation $x \equiv x' \pmod{S}$ implies $x + y \leq x' + y$ and $x' + y \leq x + y$ for all $y \in M$, that is $x + y \equiv x' + y \pmod{S}$. In other words the equivalence relation $S$ is compatible with addition in $M$ (I, p. 11). Thus the quotient by $S$ of the addition law on $M$, together with the ordering associated to $\leq$, gives $M/S$ the structure of an ordered monoid. In the case where $M$ is a pre-ordered group, the group $M/S$ is the quotient of $M$ by the subgroup consisting of all elements $x$ such that $x \leq 0$ and $0 \leq x$.

3. Positive elements

Let $G$ be a pre-ordered group with pre-order relation $\leq$; if $0 \leq x$ and $0 \leq y$ then we deduce that $y \leq x + y$ by (POM), and so $0 \leq x + y$ by transitivity; this says that the set $G_+$ of elements $x \in G$ such that $0 \leq x$ is closed under addition; moreover, the relation $x \leq y$ is equivalent to $0 \leq y - x$, that is to $y - x \in G_+$. Conversely:

Note that $0$ is the only element which is both positive and negative ; any element $x$ such that $0 < x$ (resp. $x < 0$) is called strictly positive (resp. strictly negative).

4. Filtered groups

Recall (Set Theory, III, p. 145) that an ordered set $G$ is right (resp. left) filtered\footnote{1} if for each pair $(x, y)$ of elements of $G$ there exists $z \in G$ such that $x \leq z$ and $y \leq z$ (resp. $z \leq x$ and $z \leq y$). Every right filtered ordered group $G$ is also left filtered and conversely : indeed, since there exists $z \in G$ such that $-x \leq z$ and $-y \leq z$, we have $-z \leq x$ and $-z \leq y$ (VI, p. 3, Cor.). We will therefore speak simply of filtered groups.

5. Divisibility relations in a field

Here we will define certain ordered groups which play an important part in algebra. The notation usually used for these groups is multiplicative; the application of results previously obtained in additive notation to these groups thus presupposes the translation to multiplicative notation — which should present no difficulty to the reader. Throughout this section, the letter A will denote an integral domain and K its field of fractions (l, p. 116).

In the multiplicative group $\mathbf{K}^*$ of nonzero elements of $\mathbf{K}$, the set P of nonzero elements of A is closed under multiplication, since A is a ring. Hence it defines a pre-order relation on $\mathbf{K}^*$ by $x^{-1}y \in P$, that is « there exists $z \in P$ such that $y = zx$ », which makes $\mathbf{K}^*$ apre-ordered group (written multiplicatively) (VI, p. 3, Prop. 3). Extending the terminology relating to elements of A (I, p. 97) to $\mathbf{K}^*$, the relation $x^{-1}y \in P$ can also be expressed as : x divides y, or x is a divisor of y, or y is a multiple of x (relative to the ring A); and we will call the relation $x^{-1}y \in P$ the divisibility relation in $\mathbf{K}^*$ relative to the ring A. The relation « x 'divides y » is denoted $x \mid y$, and its negation $x \nmid y$. The elements of P are none other than the multiples of 1.

6. Elementary operations on ordered groups

Let H be a subgroup of an ordered group G; it is clear that the restriction to H of the ordering of G is compatible with the group structure of H; we will always take H to be ordered in this way, unless otherwise stated. If P is the set of positive elements of G then the set of positive elements of H is H ∩ P.

Let $(G_\alpha)$ be a family of ordered groups; according to the definition of the product of ordered sets (Set Theory, III, p. 137) the product group G = $\prod G_\alpha$ is equipped with an ordering, the relation « $(x_\alpha) \leq (y_\alpha)$ » between two elements of G being by definition the same as « $x_\alpha \leq y_\alpha$ for all α ». It is immediate that this ordering is compatible with the group structure of G; this ordering makes G an ordered group which we call the product of the ordered groups $G_\alpha$. The positive elements of G are those elements all of whose components are positive. In the case where all the factors $G_\alpha$ are identical to the same ordered group H, then G is the group H' of maps from the index set I into H, the relation « f ≤ g » between two maps from I into H being the same as « f(α) ≤ g(α) for all α ∈ I »; the positive maps are those which take only positive values. The direct sum of a family $(G_\alpha)$ of ordered groups is defined as an ordered subgroup of their product (II, p. 202).

Let $(G_i)_{i \in I}$ be a family of ordered groups whose index set I is well ordered: recall (Set Theory, III, p. 157) that an order relation, called the lexicographic ordering, is defined on the product set G = $\prod G_i$, the relation « $(x_i) < (y_i)$ » between two elements of G being by definition the same as « if β is the smallest of the indices i such that x_i ≠ y_i, then x_β < y_β ». Recall that the product of a well ordered family of totally ordered sets is totally ordered under the lexicographic ordering. In the general case, the lexicographic ordering on G is compatible with its group structure, as is immediately verified; equipped with this ordering, the group G is thus an ordered group, called the lexicographic product of the well ordered family of ordered groups $(G_i)$.

7. Increasing homomorphisms of ordered groups

Let G and G' be two ordered groups; among the homomorphisms f from the underlying additive group of G into that of G', it makes sense to consider the increasing maps, that is those such that x ≤ y implies f(x) ≤ f(y). Because of the relation $f(y - x) = f(y) - f(x)$ it follows that the increasing homomorphisms from G into G' are characterised by the fact that the image of a positive element of G under such a homomorphism is a positive element of G'; if P (resp. P') denotes the set of positive elements of G (resp. G'), this can be written $f(P) \subset P'$. It is clear that the canonical injection of a subgroup G into an ordered group G', and the projection of a product of ordered groups onto one of its factors, are increasing homomorphisms.

An isomorphism (VI, p. 2) $f$ from an ordered group G onto an ordered group G' is a bijective homomorphism from G onto G' such that both $f$ and the inverse homomorphism are increasing, in other words $f(P) = P'$.

It can happen that an isomorphism from the underlying group of G onto that of G' can be increasing without the inverse isomorphism also being increasing. This is the case, for example, if $G = G'$, if $f$ is the identity map on G, and if $P \subset P'$ but $P \neq P'$. Thus in $\mathbf{Z}$ we can take $P'$ to be the set of (ordinary) positive integers and P to be the set of even positive integers.

(DIV) Let K be the field of rational functions $F_2(X)$ over the field $F_2$ of order 2. The divisibility relations relative to the rings $F_2[X] = A'$ and $F_2[X^2, X^3] = A$ define two distinct ordered group structures on $K^*$, such that $A \subset A'$ (they are ordered group structures since 1 is the only unit in A and the only unit in A').

8. Suprema and infima in an ordered group

Recall (Set Theory, III, p. 141) that if the set of upper bounds of a subset F of an ordered set E (that is to say the set of $z \in E$ such that $x \leq z$ for all $x \in F$) has a least element a, then this element, which is then unique, is called the supremum of F. If F is the set of elements in a family $(x_i)_i$, of elements of E, its supremum, if it exists, is denoted $\sup x_i$ (or $\sup x_i$ or simply $\sup(x_i)$) ; if it is a finite family $(x_i)$ ($1 \leq i \leq n$), this supremum is also denoted $\sup_{\text{LEI}} (x_1, \ldots, x_n)$. The infimum is defined in an analogous manner and is denoted inf. The operations sup and inf are associative and commutative.

Recall (Set Theory, loc. cit.) that if F is a subset of an ordered set E, and $(x_i)$ a family of elements of F, then the existence of $\sup(x_i)$ in E (which may be denoted $\sup_E(x_i)$) does not imply the existence of a supremum of the $x_i$ in F (which may be denoted $\sup_F(x_i)$ when it does exist); if both exist we know only that $\sup_E(x_i) \leq \sup_F(x_i)$; however if $\sup_E(x_i)$ exists and belongs to F, then $\sup_F(x_i)$ exists and is equal to $\sup_E(x_i)$. For example, in the polynomial ring $A = K[X, Y]$ (K a field), the principal ideals AX and AY have the ideal $AX + AY$ as supremum (under the relation $\subset$) in the ordered set of ideals of A, but have the ideal A as supremum in the set of all principal ideals of A.

(DIV) An element d of $K^*$ is called a greatest common divisor, or gcd for short, of a family $(x_i)$ of elements of $K^*$, if the principal fractional ideal (d) is the supremum in $\mathscr{P}^*$ (under the relation $\subset$) of the family of ideals $((x_i))$, or in other words if the relation $z \mid d$ for $z \in K^*$ is equivalent to « $z \mid x_i$ for all $i$ ». In the same way we will say that $m \in K^*$ is a least common multiple or an lcm of the family $(x_i)$ if $(m)$ is the infimum in $\mathscr{P}^*$ of the family of ideals $((x_i))$, that is if m | z is equivalent to « x_i | z for all i ». It amounts to the same thing to say that $(m) = \cap_{i} (x_i)$; indeed, the condition $x_i | z$ for all $i$ is equivalent to $z \in A x$, for all $i$, that is to $z \in \cap_{i} (x_i)$, and the condition $m | z$ is equivalent to $z \in (m)^1$.

Note that if a principal fractional ideal (d) satisfies $(d) = \sum (x_i)$ then d is a gcd of the family $(x_i)$; but conversely a gcd of $(x_i)$ does not necessarily satisfy the above condition (cf. VI, p. 33, Ex. 24).

The gcd and lcm, if they exist, are well defined modulo the subgroup U of units of $K^*$, that is two gcd's (or two lcm's) of a given family are associate ; by abuse of language we will often write gcd$(x_i)$ and lcm$(x_i)$ for any of the gcd's or lcm's of the family $(x_i)$, whenever such elements exist.

(DIV) By abuse of language we sometimes extend the notion of gcd to a family $(x_i)$ of elements of K, some of which may be zero ; this gcd is again defined to be an element d such that the relation $z | d$ is equivalent to « $z | x_i$ for all $i$ »; clearly d is 0 if all the $x_i$ are zero ; otherwise d is a gcd of the nonzero $x_i$. Similarly the lcm of a family, some elements of which are zero, is 0.

In an ordered group G, an immediate consequence of the invariance under translation of the ordering (VI, p. 2, Prop. 2) is that

(1)

(2)

9. Lattice ordered groups

Recall that an ordered set in which every non empty finite subset has a supremum and an infimum is called a lattice (E, III, p. 13). It is clear that a product of lattice ordered groups, and in particular a product of totally ordered groups, is a lattice ordered group. In contrast a subgroup of a lattice ordered group is not necessarily lattice ordered.

Thus, in the product ordered group $Z \times Z$, the « antidiagonal » (set of pairs $(n, n')$ such that $n + n' = 0$) is ordered with the discrete ordering, and hence is not a lattice ordered group. The additive group of polynomials in one real variable (VI, p. 1, example 2) is a filtered group (since both $p(x)$ and $q(x)$ are less than $(p(x))^2 + (q(x))^2 + 1$) which one can show is not lattice ordered. \

10. The decomposition theorem

11. Positive and negative parts

Despite its name, the negative part $x^-$ is a positive element.

Clearly $x^- = (-x)^+$ and $|-x| = |x|$. Let us also note the following formulae, the first of which is an immediate consequence of the definitions and of the invariance of the ordering under translation, and the second of which follows from the first by Prop. 7 of VI, p. 10:

12. Coprime elements

In some cases it is natural to define two elements to be coprime if $\inf(|x|, |y|) = 0$ (cf. INT, II, § 1) or to introduce the corresponding terminology in divisibility theory. We shall not do so here.

Two coprime elements are necessarily positive. The positive and negative parts $x^+$ and $x^-$ of x are coprime (VI, p. 12, Prop. 9, a)). The elements $x_i$ of a family $(x_i)_{i \in I}$ are said to be setwise coprime if $\inf_{i \in I} x_i = 0$; if the $x_i$ are all $\geq 0$ then it is sufficient for there to exist a finite subset J of I such that the corresponding elements are setwise coprime. The elements of a family $(x_i)$ are said to be pairwise coprime if $\inf(x_i, x_j) = 0$ for every pair $(\ell, \kappa)$ of distinct indices.