1. Order relations. Ordered sets

1. Definition of an order relation

Let $R\{x, y\}$ be a relation, $x$ and $y$ being distinct letters. R is said to be an order relation with respect to the letters x and y (or between x and y) if

The first of the above relations says that R is transitive with respect to the letters $x$ and $y$ (Chapter II, § 6, no. 1).

Examples

(1) The relation of equality, $x = y$, is an order relation.

(2) The relation $X \subset Y$ is an order relation between X and Y (Chapter II, § 1, no. 2, Propositions 1 and 2 and axiom A1) which is often called the inclusion relation.

(3) Let $R\{x, y\}$ be an order relation between $x$ and $y$. The relation $R\{\, y,\, x\}$ is then an order relation between x and y, called the opposite of the order relation $R\{x,\, y\}$.

An order relation on a set E is an order relation $R\{x,\, y\}$ with respect to two distinct letters $x$, $y$ such that the relation $R\{x,\, x\}$ is equivalent to $x \in E$ (in other words, is such that $R\{x,\, y\}$ is reflexive on E (Chapter II, § 6, no. 1)). Then the relation $R\{x,\, y\}$ implies "$x \in E$ and $y \in E$" and the relation $(R\{x,\, y\}$ and $R\{\, y,\, x\})$ is equivalent to "$x \in E$ and $y \in E$ and $x = y$".

Examples

2. Preorder relations

Let $R\{x, y\}$ be a relation, $x$ and $y$ being distinct letters. If $R$ is transitive and if we have $R\{x, y\} \Rightarrow (R\{x, x\}$ and $R\{y, y\})$, it does not necessarily follow that $R$ is an order relation because the relation

does not necessarily imply $x = y$. $R\{x, y\}$ is said to be a preorder relation between $x$ and $y$; $R\{y, x\}$ is then also a preorder relation between $x$ and $y$, called the opposite of the relation $R\{x, y\}$.

For example, let $\mathfrak{R}$ be the set of subsets of $\mathfrak{P}(E)$ which are coverings of E (Chapter II, § 4, no. 6). The relation "$\mathfrak{R}$ is coarser than $\mathfrak{R}'$" between elements $\mathfrak{R}$, $\mathfrak{R}'$ of $\mathfrak{R}$ (Chapter II, § 4, no. 6) is transitive and reflexive. But two distinct coverings can be such that each is coarser than the other; for example, this is the case when $\mathfrak{R}'$ is the union (in $\mathfrak{P}(E)$) of $\mathfrak{R}$ and a subset of E contained in a set of $\mathfrak{R}$ but not belonging to $\mathfrak{R}$.

But in any case the relation $(R\{x, y\}$ and $R\{y, x\})$ is an equivalence relation $S\{x, y\}$ with respect to $x$ and $y$. Let $x'$, $y'$ be letters distinct from $x$, $y$ which do not appear in R. Then $R\{x, y\}$ is compatible (with respect to $x$ and $y$) with the equivalence relations $S\{x, x'\}$ and $S\{y, y'\}$; in other words (Chapter II, § 6, no. 8), the relation

implies $R\{x', y'\}$.

¶ A preorder relation on a set E is a preorder relation $R\{x, y\}$ such that the relation $R\{x, x\}$ is equivalent to $x \in E$. The relation $R\{x, y\}$ then implies "$x \in E$ and $y \in E$".

¶ If $R\{x, y\}$ is a preorder relation on a set E, then the relation $S\{x, y\}$ defined above is an equivalence relation on E. Let $R'\{X, Y\}$ denote the relation

that is to say, the relation induced by R on passing to the quotient (with respect to $x$ and $y$); we saw in Chapter II, § 6, no. 3, that it is equivalent to the relation

¶ Let us show that $R'\{X, Y\}$ is an order relation between elements of E/S. The relation $(R'\{X, Y\}$ and $R'\{Y, Z\})$ is equivalent to

(Chapter I, § 4, criteria C40, C41). Since $R\{x, y\}$ is transitive and $Y \in E/S \Rightarrow Y \neq \emptyset$ (Chapter II, § 6, no. 2), it follows immediately that $R'\{X, Y\}$ is transitive. Next, $(R'\{X, Y\}$ and $R'\{Y, X\})$ is equivalent to

and hence equivalent to

and therefore implies

Moreover, $R\{x, y\}$ implies $R\{x, x\}$ and $R\{y, y\}$, and hence $R'\{X, Y\}$ implies each of the relations

whence $R'\{X, Y\}$ implies $(R'\{X, X\}$ and $R'\{Y, Y\})$. Finally, since $x \in E$ implies $R\{x, x\}$, $X \in E/S$ implies $R'\{X, X\}$, and the proof of our assertion is complete. $R'\{X, Y\}$ is said to be the order relation associated with $R\{x, y\}$.

¶ A preordering on a set E is a correspondence $\Gamma = (G, E, E)$ with E as source and as target, and such that $(x, y) \in G$ is a preorder relation on E. By abuse of language we refer sometimes to the graph G of $\Gamma$ as a preordering on E. For this to be so it is necessary and sufficient that $\Delta \subset G$ and $G \circ G \subset G$ (which implies $G \circ G = G$). The equivalence relation S corresponding to the preorder relation $(x, y) \in G$ then has $G \cap \overset{-1}{G}$ as its graph; the order relation associated with $(x, y) \in G$ has as graph the subset G' of $(E/S) \times (E/S)$ which corresponds (Chapter II, § 6, no. 8) to the image of G under the canonical mapping of $E \times E$ onto

3. Notation and terminology

The definitions to be given in the remainder of this section apply to an arbitrary order (or preorder) relation $\mathrm{R}\{x, y\}$ between $x$ and $y$, but will be used mainly in the case where $\mathrm{R}\{x, y\}$ is written $x \leqslant y$ \*(by analogy with the usual order relation between integers or real numbers)\* (or $x \subset y$, or by means of some analogous sign); we shall therefore state them only for the notation $x \leqslant y$, and leave to the reader the task of transcribing them into other notations. When $\mathrm{R}\{x, y\}$ is written $x \leqslant y$, then $y \geqslant x$ is synonymous with $x \leqslant y$, and these relations are read "$x$ is smaller than $y$", or "$x$ is less than $y$", or "$y$ is larger than $x$" or "$y$ is greater than $x$". The relation $x \geqslant y$ is then the preorder relation (between $x$ and $y$) opposite to $x \leqslant y$.

By abuse of language, we shall often speak of "the relation $\leqslant$" instead of "the relation $x \leqslant y$"; in this case "the relation $\geqslant$" is the opposite of "the relation $\leqslant$". We remark also that, in the same proof, we may often use the same sign $\leqslant$ to denote several different order relations when there is no risk of confusion.

The conditions for a relation written $x \leqslant y$ to be an order relation on a set E are as follows :

(RO$_{\mathrm{I}}$) The relation "$x \leqslant y$ and $y \leqslant z$" implies $x \leqslant z$. (RO$_{\mathrm{II}}$) The relation "$x \leqslant y$ and $y \leqslant x$" implies $x = y$. (RO$_{\mathrm{III}}$) The relation $x \leqslant y$ implies "$x \leqslant x$ and $y \leqslant y$". (RO$_{\mathrm{IV}}$) The relation $x \leqslant x$ is equivalent to $x \in \mathrm{E}$.

If we leave out condition (RO$_{\mathrm{II}}$), we have the conditions for $x \leqslant y$ to be a preorder relation on E. ¶ When an order relation is written $x \leqslant y$ we shall write $x < y$ (or $y > x$) for the relation "$x \leqslant y$ and $x \neq y$"; these relations are read "$x$ is strictly smaller than $y$", or "$x$ is strictly less than $y$", or "$y$ is strictly larger than $x$", or "$y$ is strictly greater than $x$".

The example of the inclusion relation shows that the negation of $x \leqslant y$ (sometimes denoted by $x \nleqslant y$) is not necessarily equivalent to $y < x$ (cf. no. 12).

C58. Let $\leqslant$ be an order relation, and let $x$, $y$ be two distinct letters. The relation $x \leqslant y$ is equivalent to "$x < y$ or $x = y$". Each of the relations "$x \leqslant y$ and $y < z$", "$x < y$ and $y \leqslant z$" implies $x < z$.

The first assertion follows from the criterion $A \Rightarrow ((A$ and (not $B$)) or $B$) (Chapter I, § 3, criterion C24). To prove the second assertion, we remark that each of the hypotheses implies $x \leqslant z$, by transitivity; and the relation ($x = z$ and $x \leqslant y$ and $y \leqslant z$) would imply $x = y = z$, contrary to the hypothesis.

¶ In order to make matters easier and to replace metamathematical criteria by mathematical theorems we shall usually consider a theory $\mathscr{T}$ which contains the axioms and axiom schemes of the theory of sets, and in addition, two constants E and $\Gamma$ satisfying the axiom

"$\Gamma$ is an ordering on the set E" (no. 1).

We shall denote by $x \leqslant y$ the relation $y \in \Gamma\langle x \rangle$, and we shall say that the set E is ordered by the ordering $\Gamma$ (or by the order relation $y \in \Gamma\langle x \rangle$) (cf. Chapter IV, § 1).

¶ Whenever, in $\mathscr{T}$, $\Gamma$ is a preordering on E, we say likewise that E is preordered by the preordering $\Gamma$.

In some situations (for example in the following definition) the theories which we shall consider are a little more complicated. We shall leave it to the reader to make explicit the constants and axioms of such theories.

Let E, E$'$ be two sets ordered by orderings $\Gamma$, $\Gamma'$. An isomorphism of E onto E$'$ (for the orderings $\Gamma$ and $\Gamma'$) is a bijection $f$ of E onto E$'$ such that the relations $x \leqslant y$ and $f(x) \leqslant f(y)$ are equivalent (cf. Chapter IV, § 1).

4. Ordered subsets. Product of ordered sets

Let E be a set ordered by an ordering $\Gamma$, with graph G. For each subset A of E, $G \cap (A \times A)$ is an ordering on A; the corresponding order relation is equivalent to "$x \leqslant y$ and $x \in A$ and $y \in A$", and we shall denote it simply by $x \leqslant y$ (by abuse of language). The ordering and the order relation thus defined on A are said to be induced by the ordering and order relation given on E; and the ordering and order relation on E are said to be extensions of the ordering and order relation which they induce on A. Whenever we consider A as an ordered set we have in mind the ordering induced on A by that on E, unless the contrary is expressly stated.

Examples. The relations induced by the inclusion relation $X \subset Y$ on various sets of subsets are of considerable importance. Here are some examples :

5. Increasing mappings

An increasing mapping of E into F becomes decreasing (and vice versa) when we replace one of the preorderings on E or on F by the opposite preordering. Every constant function is both increasing and decreasing; the converse of this statement is usually not true.

For example, if a set E is ordered by the equality relation, the identity mapping of E onto itself is both increasing and decreasing, but not constant if E has more than one element (cf. Exercise 7).

Examples

6. Maximal and minimal elements

7. Greatest element and least element

If there exists an element $a$ in an ordered set E such that $a \leqslant x$ for all $x \in E$, then $a$ is the only element of E with this property; for if also $b \leqslant x$ for all $x \in E$, then we should have $a \leqslant b$ and $b \leqslant a$, and consequently $a = b$.

8. Upper and lower bounds

Every upper bound of $X$ is a lower bound of $X$ with respect to the opposite ordering, and vice versa.

¶ If $x$ is a lower bound of $X$, every element $z\leq x$ is also a lower bound of $X$. A lower bound of $X$ is also a lower bound of every subset of $X$. An ordered set $X$ has a least element if and only if there exists a lower bound of $X$ which belongs to $X$.

¶ The set of lower bounds of a subset $X$ of a preordered set $E$ may be empty : this is the case when $X=E$ and $E$ is an ordered set which has no least element.

¶ A subset $X$ of $E$ whose set of lower (resp. upper) bounds is not empty is said to be bounded below (resp. bounded above). A subset which is bounded both below and above is said to be bounded. If $X$ is bounded below (resp. bounded above, bounded), the same is true of every subset of $X$.

Every subset consisting of a single element is bounded. But a subset consisting of two elements need not be bounded either above or below (no. 10).

Let $E$ be a preordered set and let $f$ be a mapping of an arbitrary set $A$ into $E$. The mapping $f$ is said (by abuse of language) to be bounded below (resp. bounded above, bounded) if the set $f(A)$ is bounded below (resp. bounded above, bounded) in $E$.

9. Least upper bound and greatest lower bound

Given a subset $X$ of an ordered set $E$, the least upper bound (resp. greatest lower bound) of $X$ in $E$, when it exists, is denoted by

or by sup X (resp. inf X) if there is no risk of ambiguity. The least upper bound (resp. greatest lower bound) of a set $\{x, y\}$ of two elements, when it exists, is denoted by sup $(x, y)$ (resp. inf $(x, y)$). Similarly for the least upper bound and greatest lower bound of a set of three elements, etc.

¶ If a subset X of E has a greatest element $a$, then $a$ is the least upper bound of X in E.

¶ If X has a greatest lower bound $a$ in E, then $a$ is the least upper bound of X with respect to the opposite ordering on E. For this reason we may restrict ourselves for the most part, in what follows, to consideration of the properties of least upper bounds.

Examples

(1) The set of upper bounds of the empty set $\emptyset$ in an ordered set E is evidently E itself; hence $\emptyset$ has a supremum in E if and only if E has a least element, which is then the least upper bound of $\emptyset$.

(2) In the set $\mathfrak{P}(E)$ of subsets of a set E, ordered by inclusion, every subset $\mathfrak{S}$ of $\mathfrak{P}(E)$ has a least upper bound, namely the union of the sets of $\mathfrak{S}$, and a greatest lower bound, namely the intersection of the sets of $\mathfrak{S}$.

(3) Let E, F be two sets and let $\Theta$ be a subset of the $\Phi(E, F)$ of mappings of subsets of E into F, ordered by extension of mappings (no. 1, Example 3). For each $u \in \Phi(E, F)$ let $D(u)$ be the domain of $u$. The condition for the existence of a common extension of a family of mappings belonging to $\Phi(E, F)$ (Chapter II, § 4, no. 6, Proposition 7) shows that $\Theta$ has a least upper bound in $\Phi(E, F)$ if and only if for each pair $(u, v)$ of elements of $\Theta$ we have $u(x) = v(x)$ whenever $x \in D(u) \cap D(v)$.

A mapping $f$ of a set A into an ordered set E is said to have a least upper bound if the image $f(A)$ has a least upper bound in E; this bound is then called the least upper bound of f and is written $\sup_{x \in A} f(x)$. Similarly for the greatest lower bound.

In particular, if a subset A of E has a least upper bound in E, this bound is the least upper bound of the canonical injection of A into E, and may therefore be written as $\sup_{x \in A} x$.