Partially Ordered Algebraic Systems

CHAPTER I

INTRODUCTION

1. Partially ordered sets

It will be convenient to collect here the fundamental concepts and terminology we shall need.

If a binary relation is defined on a set A with the properties

then A is called a partially ordered set (abbreviated: p. o. set) and is called a partial order on A. The dual of A is the p. o. set A′ with the same elements and with the partial order ′ defined as follows: a ′ b (in A′) if, and only if, b a (in A).¹

As usual, one may write b a for a b, and a < b (or b > a) to mean that a b and a ≠ b. If neither a b nor b a, then a and b are called incomparable, in sign: a | | b.

It may happen that a relation satisfies only P1 and P3; in this case we say is a preorder.² A preorder induces an equivalence relation ~ on A, namely, a ~ b if, and only if, simultaneously a b and b a. The set of classes a*, c*, … of this equivalence can be partially ordered in the natural way : a* c* if for some (and hence for all) a in a* and for some (and so for all) c in c* we have a c. The set A* of the classes a*, c*, ... is a p. o. set.

A partial order on A induces in the natural way a partial order on any non-void subset B of A) namely, for a, b ∈ B one puts a b in B if, and only if, a b in the original partial order of A. This induced partial order of B will be denoted by the same symbol .

A (closed) interval³ [a, b] of A (where a b) consists of all c ∈ A satisfying a c b; a and b are called the endpoints of [a, b], The subsets Ia = [x ∈ A | x a], defined for each a ∈ A, and their duals Ja = [x ∈ A | x a] are also considered as (closed) intervals. A subset of A is called convex if it contains the whole interval [a, b] whenever it contains the endpoints a, b. If we replace by < we obtain the definition of open intervals (a, b), . . ..

Let A and A′ be p. o. sets. A mapping a → a′ from A into A′ is called isotone if it is single-valued and order-preserving in the sense that a b implies a′ b′. A mapping which is one-to-one and isotone in both directions is said to be an isomorphism (or order-isomorphism) of A onto A′; A and A′ are then called isomorphic (order-isomorphic). If a one-to-one mapping between A and A′ reverses order (i. e. a b if, and only if, a′ b′), then it is a dual isomorphism.

Assume that two partial orders, 1 and 2, are defined on the same set A. Then 2 is an extension of 1 if, for all a, b ∈ A, a 1 b implies a 2 b.

A has the trivial order if, for all a, b ∈ A, a b implies a = b (i. e. a < b never holds). The order relation is called a full (or linear or simple or total) order on A and A a fully ordered (etc.) set (f. o. set) or a chain, if, in addition to P1 — 3, also

P4. for all a, b ∈ A, either a < b or a = b or a > b

holds. The subsets of a f. o. set are again f. o. sets under the induced partial order.

For a subset B of a p. o. set A, an upper (lower) bound of B in A is an element u ∈ A (v ∈ A) such that b u (b v) for every b ∈ B. B is called bounded (in A) if A contains both upper and lower bounds of B. The set of all upper (lower) bounds of B will be denoted by U(B) (L(B)). If B consists of the elements x, y, … , then we shall often write U(B) = = U(x, y, . . .) and L(B) = L(x, y, . . .). If B is the void set, then U(B) = L(B) = A, while if B has no upper bound in A, then U(B) = Ø.

Note that B ⊆ C implies U(B) ⊇ U(C) and L(B) ⊇ L(C). Furthermore

thus

A p. o. set A satisfying

P5. for any a, b ∈ A, the set U(a, b) is not void,

and the dual law

P6. for any a, b ∈ A, the set L(a, b) is not void,

is called u- and l-directed, respectively. Obviously, P5 implies that U(B) is never void if B is a finite subset of A. A is said to be directed (or to have the Moore-Smith-property) if it satisfies both P5 and P6.

A p. o. set A is a ∨-semilattice or a ∧-semilattice according as

P7. to all a, b ∈ A there exists a c ∈ A such that U (a, b) = U(c),

or

P8. to all a, b ∈ A there exists a d ∈ A such that L(a, b) = L(d) is satisfied. Then the elements

are uniquely determined elements of A (if they exist) and are called the join (or union or least upper bound) and the meet (or intersection or greatest lower bound)⁴ of a and b.

If P7 and P8 are both satisfied, then A is called a lattice.⁵ A lattice may alternatively be defined as an algebraic system in which two operations, ∨ and ∧, are defined such that

L1. a ∨ a = a and a ∧ a = a,

L2. a ∨ b = b ∨ a and a ∧ b = b ∧ a,

L3. (a ∨ b) ∨ c = a ∨ (b ∨ c) and (a ∧ b) ∧ c = a ∧ (b ∧ c),

L4. (a ∨ b) ∧ a = a and (a ∧ b) ∨ a = a

for all a, b, c ∈ A. In fact, the join a ∨ b and the meet a ∧ b of a, b satisfy Ll — 4, and if in some set A the operations ∨ and ∧ possess properties Ll — 4, then putting a b if, and only if, a ∨ b = b (or equivalently, a ∧ b = a), A becomes a p. o. set in which P7 — 8 hold.

A f. o. set W is said to be well-ordered if every non-void subset V of W contains a smallest element, i. e. a u such that u v for every v ∈ V. The Axiom of Choice will be assumed for all sets. Then by a theorem of ZERMELO, every set can be well-ordered. An equivalent statement is ZORN’S lemma: if every subset of a p. o. set A which is a chain (in the induced partial order) has an upper bound in A, then A contains a maximal element, say x, in the sense that if y ∈ A and x y, then y = x.

2. Partial order in algebraic systems

As usual, by an algebraic system (or algebraic structure) we understand a set A in which operations fα are defined satisfying certain rules.⁶ Thus each fα is a single-valued function from a product set A × … ×A (say, with n = n(α) components) into A. The notions of isomorphism, homomorphism, etc. of two algebraic systems with the same operations will be understood in the ordinary sense.

A function g(x) from a p. o. set A into a p. o. set A′ is called isotone if x y in A implies g(x) g(y) in A′ and antitone if x y in A implies g(x) g(y) in A′. A function g(x1, … , xn) of more than one variable can be isotone in some of its variables, antitone in others and both in yet others,⁷ and it can, of course, be none of these things in further variables.

The following formulation of monotony is sufficiently general and suitable for all cases to be considered here.

We shall say that an operation f of an algebraic system A satisfies a monotony law with the monotony domain⁸ C if

1. f(x1, … , xn) ∈ C whenever x1, … , xn ∈ C,

2. for each i (i = 1, … , n), f is either isotone or antitone or both in the variable xi ∈ C.

According as which of these three alternatives occurs, f will be called of type ↑ , ↓ or ↕ in the variable xi. We shall say that f(x1, … , xn) is of type (γ1, … , yn) in the domain C if γi (= ↑, ↓ or ↕) denotes the type of f in xi. If no γi equals ↕ , then f is non-degenerate in C.

By a partially ordered algebraic system we shall mean a set A satisfying

(i) A is an algebraic system,

(ii) A is a p. o. set,

(iii) every operation f α of A fulfils a monotony law.

Our main interest lies in groups, rings and semigroups, therefore we shall now derive some consequences of the definition for binary operations.

a) An associative operation f(x, y) for which g(x, y, z) = = f(f(x, y), z) (considered as a ternary operation) is non-degenerate must be of type ( ↑ , ↑ ) in any monotony domain C. For assume, on the contrary, that f(x, y) is of type ↓ in x. Then g(x, y, z) is of type ↑ in x, while f(x, f(y, z)) is obviously of type ↓ in x. The same argument applies for y.

b) Every operation f(x, y) with a neutral element e (i. e. f(e, x) = f(x, e) = x for all x ∈ A) is of type ( ↑ , ↑ ) in any monotony domain C containing e. In fact, x1 < x2 implies f(e, x1) < < f(e, x2) and f(x1, e) < f(x2, e).

c) If f(x, y) is of type ( ↑ , ↑ ) and g(x) is a right-inverse operation in the sense that f(x, g(x)) is a fixed element e of A for every x ∈ A, then g(x) is of type ↓ in any C.

Hence we see that in a loop, group, semigroup (with some uninteresting exceptions), and (not necessarily associative) ring with unit element, the multiplication and addition are of type ( ↑ , ↑ ) in every monotony domain; while inversion is of type ↓ and subtraction is of type ( ↑ , ↓ ). Thus in the cases mentioned the definition of partial order to be given here is the onl, reasonable one in view of our general definition of partially ordered algebraic systems. However, in quasigroups—and a fortiori in groupoids—the operation may be of type ( ↑ , ↓ ) or of type (↓ , ↓), as shown by the example of integers if the operation ∘ is defined by x ∘ y = x — y and x ∘ y = — x — y, respectively.

¹ We shall often speak of the dual of an assertion; thereby we mean that the signs and are to be interchanged throughout.

² It is also called quasiorder; cf. BIRKHOFF [3].

³ Generalized intervals have been considered by BURGESS [1].

⁴ We shall use the customary abbreviations l.u.b. and g.l.b.

⁵ We shall need several results of lattice theory; the reader is referred to BIRKHOFF [3] for them.

⁶ We may content ourselves with this naive definition of algebraic systems, since for our purposes we do not need a more precise one.

⁷ If A is u- directed or l-directed, then this third alternative means that the function is independent of the variables now considered.

⁸ A monotony domain is always a non-void subset of A.

FIRST PART

PARTIALLY ORDERED GROUPS

CHAPTER II

PRELIMINARIES ON PARTIALLY ORDERED GROUPS

1. Definitions

A partially ordered group (p. o. group) is a set G such that

Gl. G is a group under multiplication,¹

G2. G is a p. o. set under a relation ,

G3. the monotony law² holds with the whole of G as monotony domain:

Since a group contains a neutral element³ e and the cancellation laws hold, either one of the following conditions is equivalent to G3:

(1) a b implies cad cbd for all c, d ∈ G.

(2) a < b implies ca < cb and ac < bc for all c ∈ G (that is to say, x → cx and x → xc are, for any c ∈ G, one-to-one and isotone mappings).

(3) a < b implies cad < cbd for all c, d ∈ G.

On using the transitivity of , it follows readily that further equivalent conditions are the laws:

(4) a b and a′ b′ imply aa′ bb′.

(5) a b and a′ < b′ imply aa′ < bb′ and a′a < b′b

Let us note the following immediate consequences of the definition:

(6) a b implies a–1 b–1 [a < b implies a–1 > b–1]

(7) For all a, b ∈ G the sets U(a) and U(b) are, regarded as p. o. sets, isomorphic, say, under x → ba–1 x.

(8) For all a ∈ G, the sets U(a) and L(a) are, again as p. o. sets, dually isomorphic, say, under x → ax–1 a.

(9) If G is a p. o. group, then it remains so if the partial order is replaced by its dual.

The following generalizations of the concept of p. o. groups deserve mention.

MATSUSHITA [1] and ZAǏCEVA [2] considered the case when only the half of the monotony law G3 is assumed. Cf. also CONRAD [10] and COHN [1].

A somewhat more general notion than p. o. group has been studied by BRITTON and SHEPPERD [1] under the name almost ordered groups.

If condition G2 is weakened to the requirement that G is a pre-ordered set, then G3 implies that

and that

Hence one obtains at once that the equivalence class containing e is a normal subgroup N of G and the other classes are just the cosets of N. The p. o. set of the equivalence classes is nothing else than the factor group G/N which is now a p. o. group.

If a, b ∈ G have an upper (lower) bound c ∈ G, then their inverses, a–1 and b–1, have a lower (upper) bound. Hence a p. o. group which is u-directed (l-directed) is necessarily l-directed (u-directed), and thus directed. If this is the case, we call G a directed group.

Moreover, if we assume merely that in the p. o. group G, for some fixed a0∈ G and for every b ∈ G, an upper (lower) bound of a0 and b exists, then G is directed. In fact, if a1 and b1 are arbitrary and c is an upper (lower) bound for a0 and , then c is an upper (lower) bound for a1 and b1.

Proposition 1. (CLIFFORD [1].) If a p. o. group G contains an element a e such that U(a) generates G, then G is directed.

Conversely, if G is a directed group, then for every a ∈ G each element b of G may be written in the form⁴

It suffices to verify the first part for a = e, since U(e) = = a–1 U(a) is contained in the subgroup generated by U(a). Assuming {U(e)} = G, any b ∈ G has the form b = x1 … xr with xi or . Since the product of two elements of U (e) and the conjugates of every element of U(e) also belong to U(e), b may be written as b = yz–1 with y, z ∈ U(e). Then y e and y b, that is, e and each b have an upper bound, and so G is directed. Conversely, if G is a directed group, then e, b ∈ G have an upper bound c ∈ G. Let y = ca and z = = (b–1 c)a. Then y, z ∈ U(a) and b = yz–1 has the indicated form. Q.E.D.

If a, b ∈ G have a 1. u. b. a ∨ b in G, then the inverses a–1 and b–1 have a g. 1. b. a–1 ∧ b–1 in G. In fact, (a ∨ b)–1 a–1 and b–1, because a ∨ b a, b, and if x a–1, b–1, then x-1 a, b, whence x-1 a ∨ b, x (a ∨ b)–1 and (a ∨ b)–1 is the g. 1. b. of a–1 and b–1. Hence a p. o. group G which is a ∨-semilattice (∧-semilattice) is at the same time a ∧-semi-lattice (∨-semilattice) and thus a lattice where

A p. o. group which is a lattice under its partial order will be called a lattice-ordered group (I. o. group⁵).

If the order of G is full, we say G is a fully ordered group (f. o. group).

We list some elementary and useful rules on the sets⁶ U(. . . , aa, . . .) and L(. . . , aa, . . .):

(i)

(ii) xU (. . . , a a , . . .) y = U (. . . , xa a y . . .),

(iii) the multiplication ⁷ of the U(. . . , aa, . . .) is associative,

(iv)

,

(v) L ( a, b ) = a U ( a, b ) – ¹ b ,

(vi) U (. . . , a a , . . .) U (. .., b β ,...) ⊆ U (. . . , a a b β , . . .),

(vii) U ( x ) U (. . . , a a , . . .) = U (. . . , xa a , . . .),

and the dual laws for all aa, bβ, x, y ∈ G. The proofs are obvious and may be left to the reader.

If the p. o. group is at the same time an operator group with an operator domain Ω, then it is assumed that the operators ω ∈ Ω preserve order, i. e.

A p. o. group G is said to be Archimedean if

that is, if {e} is the only subgroup having an upper bound in G.⁸

A p. o. group is called completely integrally closed if

Any completely integrally closed p. o. group is Archimedean. For, if an < b (n = 0, ±1, ±2, . . .), then an < b and (a–1)" < < b (n = 1, 2, . . .) whence a e and a–1 e by complete integral closure; thus a = e. The converse implication does not hold in general (see EVERETT and ULAM [1]), but it does in 1. o. groups (see Chapter V, 1).

2. The positive cone

In a p. o. group G, an element a is called positive (integral) if a e, strictly positive (strictly integral) if a > e, and negative if a e. If the group operation is written as addition and 0 denotes the neutral element, then positivity has the usual meaning a 0.

The set P = P(G) = G+ of positive (integral) elements of G, i. e. P = U(e), is said to be the positive cone (or the integral part) of G. This concept is a natural tool for studying partial orders. Its precise significance will become fully apparent from Chapter III.

A partial order is already uniquely determined by the corresponding positive cone P, for

In view of this, instead of "the partial order with the positive cone P, we may say briefly the partial order P".

It is readily seen that the reflexivity of is equivalent to e ∈ P, its antisymmetry to the fact that P ∩ P–1 contains no element ≠ e, transitivity to the inclusion PP ⊆ P, while the monotony law is equivalent to the fact that ba–¹ ∈ P implies (cbd) (cad)–¹ = c(ba–1)c–1 ∈ P, i. e. to cPc–1 ⊆ P. We may use (1) to define from P if P is given.

Theorem 2. A subset P of a group G is the positive cone of some partial order of G if, and only if, it satisfies the following three conditions:

a. P ∩ P–1 = e,

β. PP ⊆ P,

y. xPx–1 ⊆ P for all x ∈ G.⁹

In other words, P is a normal subsemigroup of G containing e, but no other element along with its inverse.

This result may be completed by

Proposition 3.¹⁰ (a) G is a directed group if, and only if, P generates G;

(b) G is a l. o. group if, and only if, P generates G and P is a lattice under the induced order ;

(c) G is a f. o. group if, and only if,

Statement (a) is contained in Proposition 1, while (c) follows at once from the fact that G is f. o. exactly if, for each a ∈ G, either a e or a–1 e. The only if part of (b) is obtained from (a) and from the obvious sublattice property of P. Finally, its if" part may be shown by verifying that (ac–1 ∧ bc–1)c is a g. 1. b. for a, b ∈ G where c is a lower bound for a, b (note that ac–1, bc–1 and ac–1 ∧ bc–1 ∈ P).

Observe that the partial order on G is trivial if, and only if, P consists of e alone.

BRUCK [1] observes that in a f. o. loop G the sets P and N = = [x ∈ G | x e] have the following characterizing properties: P ∩ N = = e, P U N = G; PP ⊆ P; NN ⊆ N;P (and hence N) is normal in G.

We turn to an intrinsic characterization of the positive cones. In Theorem 2, P was assumed to be embedded in a group G. We get rid of this assumption in the next

Theorem 4. (BIRKHOFF [1].)¹¹ An arbitrary semigroup P is the positive cone of some p. o. group G if, and only if,

(i) the cancellation laws hold in P ;

(ii) P contains a neutral element e ;

(iii) ab = e ( a, b ∈ P ) implies a = b = e ;

(iv) Pa = aP for all a ∈ P .

We may restrict ourselves to the proof of sufficiency. We embed a semigroup P with properties (i)—(iv) in a group G as follows. If given a, x ∈ P, by (iv) and (i) there exists exactly one xa ∈ P such that xa = axa. The correspondence x → xa (with a fixed a) is