J. Munkres. Topology (2013) Chapter 1: Set Theory and Logic. 3: Relations

Definition 1: Relation

A relation on a set \(A\) is a subset of \(A^2\).

Given a relation \(R\), we write \(xRy\) for \((x,y) \in R\).

Equivalence Relations and Partitions

Definition 2: Reflexive

A relation \(R\) on \(A\) is reflexive iff \( \forall x \in A. xRx \).

Definition 3: Symmetric

A relation \(R\) on \(A\) is symmetric iff \( \forall x,y \in A. x R y \Rightarrow y R x \).

Definition 4: Transitive

A relation \(R\) on \(A\) is transitive iff \( \forall x,y,z \in A. xRy \wedge yRz \Rightarrow xRz \).

Definition 5: Equivalence Relation

An equivalence relation on a set \(A\) is a relation on \(A\) that is reflexive, symmetric and transitive.

A side remark here. Munkres gives as an example the relation of 'blood relative', defined as \(x\) is a blood relative of \(y\) iff \(x\) and \(y\) have a common ancestor, and then says this relation is not transitive - "I am not a blood relative of my wife, although my children are". This is not correct - with this definition, any two human beings are blood relatives. (If we allow ancestors to be non-human, any two organisms on Earth are blood relatives.)

Definition 6: Equivalence Class

Given an equivalence relation \(\sim\) on a set \(A\) and an element \(x \in A\), the equivalence class determined by \(x\) is the set \(\{y \in A \mid x \sim y\}\).

Proposition 7

Two equivalence classes are either disjoint or equal.

Proof

Let \(E\) be the equivalence class of \(x\) and \(E'\) the equivalence class of \(y\). Assume \(E \cap E' \neq \emptyset\); we shall prove that \(E = E'\).

Pick \(z \in E \cap E'\). Then \(x \sim z\) and \(y \sim z\). Hence \(z \sim y\) by symmetry, and so \(x \sim y\) by transitivity.

We now prove \(E' \subseteq E\). Let \(t \in E'\). Then we have \(y \sim t\), and so \(x \sim t\) by transitivity. Thus, \(t \in E\).

We also have \(y \sim x\) (by transitivity) and so \(E \subseteq E'\) similarly. Thus, \(E = E'\) as required. \(\Box\)

Definition 8: Partition

A partition of a set \(A\) is a set of pairwise disjoint, nonempty subsets of \(A\) whose union is \(A\).

Proposition 9

Given any equivalence relation \(\sim\) on a set \(A\), the set of all equivalence classes forms a partition of \(A\). Conversely, given any partition \(\mathcal{P}\) of \(A\), there exists a unique equivalence relation on \(A\) such that \(\mathcal{P}\) is the set of all equivalence classes.

Proof

Step 1: Given any equivalence relation \(\sim\) on a set \(A\), the set of all equivalence classes forms a partition of \(A\).

Let \(\sim\) be an equivalence relation on \(A\) and let \(\mathcal{E}\) be the set of equivalence classes. We prove that \(\mathcal{E}\) is a partition of \(A\). We have that the elements of \(\mathcal{E}\) are pairwise disjoint by Proposition 7 and nonempty because, for any \(x \in A\), we have \(x\) is an element of the equivalence class determined by \(x\) by reflexivity. Their union is \(A\) because again, for any \(x \in A\), we have \(x\) is an element of the equivalence class determined by \(x\).

Step 2: Given any partition \(\mathcal{P}\) of \(A\), there exists an equivalence relation on \(A\) such that \(\mathcal{P}\) is the set of all equivalence classes.

Let \(\mathcal{P}\) be any partition of \(A\). Define \(\sim\) on \(A\) by: \(x \sim y\) iff \(\exists X \in \mathcal{P}. x \in X \wedge y \in X\). We prove \(\sim\) is an equivalence relation on \(A\) and that \(\mathcal{P}\) is the set of all equivalence classes.

Step 2a: \(\sim\) is reflexive.

Let \(x \in A\). Pick \(X \in \mathcal{P}\) such that \(x \in X\) (since the union of \(\mathcal{P}\) is \(A\)). Then \(x \in X \wedge x \in X\), and so \(x \sim x\).

Step 2b: \(\sim\) is symmetric.

Immediate from the definition of \(\sim\).

Step 2c: \(\sim\) is transitive.

Assume \(x \sim y\) and \(y \sim z\). Pick \(X, Y \in \mathcal{P}\) such that \(x \in X \wedge y \in X\) and \(y \in Y \wedge z \in Y\). Then we have \(y \in X \cap Y\) and so \(X = Y\) (since the members of \(\mathcal{P}\) are pairwise disjoint). Hence \(x \in X \wedge z \in X\), and so \(x \sim z\).

Step 2d: For all \(X \in \mathcal{P}\) and \(x \in X\), we have that \(X\) is the equivalence class determined by \(x\).

Let \(X \in \mathcal{P}\) and \(x \in X\). Let \(E\) be the equivalence class determined by \(x\). We prove that \(X = E\).

Step 2d(i): \( X \subseteq E\)

Let \(y \in X\). Then \(x \in X \wedge y \in X\) so \(x \sim y\) and hence \(y \in E\) as required.

Step 2d(ii): \(E \subseteq X\)

Let \(y \in E\). Then \(x \sim y\). Pick \(Y \in \mathcal{P}\) such that \(x \in Y \wedge y \in Y\). We have \(x \in X \cap Y\) and so \(X = Y\) (because the members of \(\mathcal{P}\) are pairwise disjoint). Hence \(y \in X\) as required.

Step 2e: Every equivalence class is in \(\mathcal{P}\)

Let \(x \in A\) and let \(E\) be the equivalence class determined by \(x\). Pick \(X \in \mathcal{P}\) such that \(x \in X\) (since \( \bigcup \mathcal{P} = A \)). Then \(X = E\) by Step 2d and therefore \(E \in \mathcal{P}\).

Step 2f: Every element of \(\mathcal{P}\) is an equivalence class of \(\sim\).

Let \(X \in \mathcal{P}\). Pick \(x \in X\) (since the members of \(\mathcal{P}\) are nonempty). Then \(X\) is the equivalence class determined by \(x\) by Step 2d.

Step 3: If two equivalence relations have the same set of equivalence classes, then they are equal.

Let \(\sim\) and \(\approx\) be equivalence relations on \(A\). Assume that every equivalence class of \(\sim\) is an equivalence class of \(\approx\) and vice versa. If \(x \sim y\), then \(y\) is in the equivalence class of \(x\) w.r.t. \(\sim\), which is the same as the equivalence class of \(x\) w.r.t. \(\approx\); hence \(x \approx y\). Similarly, if \(x \approx y\) then \(x \sim y\). So \(\sim = \approx\). \(\Box\)

Order Relations

Definition 10: Irreflexive

A relation \(R\) is irreflexive iff there is no object \(x\) such that \(xRx\).

Definition 11: Strict Partial Order

A strict partial order on a set \(A\) is a relation \(<\) on \(A\) that is irreflexive and transitive.

When we use the symbol \(<\) for a strict partial order, we write \(x \leq y\) for \(x < y \vee x = y\).

A partially ordered set is a pair \((A,<)\) such that \(A\) is a set and \(<\) is a strict partial order on \(A\).

Definition 12: Strict Linear Order

A strict linear order on a set \(A\) is a strict partial order \(<\) on \(A\) such that, for all \(x,y \in A\), either \(x = y\) or \(x < y\) or \(y < x\).

A linearly ordered set is a pair \((A,<)\) such that \(A\) is a set and \(<\) is a strict linear order on \(A\).

Proposition 13: Trichotomy

Let \(<\) be a linear order on \(A\). Then for any \(x,y \in A\), exactly one of the three possibilities \(x = y\), \(x < y\), \(y < x\) holds.

Proof

We must show that it is impossible for two of them to hold. If \(x = y\) and \(x < y\) then \(x < x\) contradicting irreflexivity. Similarly if \(x = y\) and \(y < x\). If \(x < y\) and \(y < x\) then \(x < x\) by transitivity, which again contradicts irreflexivity. \(\Box\)

Definition 14: Open Interval

Let \(<\) be a linear order on a set \(A\) and \(a, b \in A\) with \(a < b\). Then the open interval \((a,b)\) is defined to be \(\{ x \in A : a < x < b \}\).

Definition 15: Successor, Predecessor

Let \(<\) be a linear order on a set \(A\) and \(a,b \in A\). Then \(b\) is the (immediate) successor of \(a\), and \(a\) is the (immediate) predecessor of \(b\), iff \(a < b\) and there is no \(c \in A\) such that \(a < c < b\).

Definition 16: Isomorphic

Linearly ordered sets \((A, <_A)\) and \((B, <_B)\) are isomorphic iff there exists a bijection \( f : A \rightarrow B\) such that, for all \(x,y \in A\), if \(x <_A y\) then \(f(x) <_B f(y)\).

Definition 17: Dictionary Order

Let \((A, <_A)\) and \((B, <_B)\) be linearly ordered sets. The dictionary order \(<\) on \(A \times B\) is defined by \((a,b) < (a',b')\) iff \(a <_A a' \vee (a = a' \wedge b <_B b')\).

Definition 18: Largest Element

Let \((A, <)\) be a linearly ordered set, \(S \subseteq A\), and \(b \in A\). Then \(b\) is the largest element in \(S\) iff \(b \in S\) and \( \forall x \in S. x \leq b \).

Proposition 19

A set has at most one largest element.

Proof

Assume \(b\) and \(b'\) are largest elements in \(S\). Because \(b \in S\) and \(\forall x \in S. x \leq b'\), we have \(b \leq b'\). Because \(b' \in S\) and \(\forall x \in S. x \leq b\), we have \(b' \leq b\). Hence by trichotomy we have \(b = b'\). \(\Box\)

Definition 20: Smallest Element

Let \((A, <)\) be a linearly ordered set, \(S \subseteq A\), and \(b \in A\). Then \(b\) is the smallest element in \(S\) iff \(b \in S\) and \( \forall x \in S. b \leq x \).

Proposition 21

A set has at most one smallest element.

Proof

Similar to Proposition 19. \(\Box\)

Definition 22: Upper Bound

Let \((A, <)\) be a linearly ordered set, \(S \subseteq A\), and \(b \in A\). Then \(b\) is an upper bound for \(S\) iff \( \forall x \in S. x \leq b \). We say \(S\) is bounded above iff it has an upper bound.

Definition 23: Lower Bound

Let \((A, <)\) be a linearly ordered set, \(S \subseteq A\), and \(b \in A\). Then \(b\) is a lower bound for \(S\) iff \( \forall x \in S. b \leq x \). We say \(S\) is bounded below iff it has a lower bound.

Definition 24: Supremum

Let \((A, <)\) be a linearly ordered set, \(S \subseteq A\), and \(b \in A\). Then \(b\) is the least upper bound or supremum for \(S\) iff \(b\) is the least element in the set of upper bounds of \(S\).

Definition 25: Infimum

Let \((A, <)\) be a linearly ordered set, \(S \subseteq A\), and \(b \in A\). Then \(b\) is the greatest lower bound or infimum for \(S\) iff \(b\) is the greatest element in the set of lower bounds of \(S\).

Definition 26: Least Upper Bound Property

A linearly ordered set \((A, <)\) has the least upper bound property iff every nonempty subset of \(A\) bounded above has a supremum.

Definition 27: Greatest Lower Bound Property

A linearly ordered set \((A, <)\) has the greatest lower bound property iff every nonempty subset of \(A\) bounded below has an infimum.

Proposition 28

A linearly ordered set has the least upper bound property if and only if it has the greatest lower bound property.

Proof

Let \((A, <)\) be a linearly ordered set with the least upper bound property. We prove it has the greatest lower bound property.

Let \(S\) be a nonempty subset of \(A\) bounded below. Let \(S \downarrow\) be the set of lower bounds of \(S\). Then \(S \downarrow\) is nonempty and bounded above (because \(S\) is nonempty, and every element of \(S\) is an upper bound for \(S \downarrow\)).

So let \(l\) be the supremum of \(S \downarrow\). We prove \(l\) is the infimum of \(S\).

We first prove \(l\) is a lower bound for \(S\). For any \(s \in S\), we have that \(s\) is an upper bound for \(S \downarrow\), and so \(l \leq s\) because \(l\) is the least upper bound of \(S \downarrow\).

Now, let \(l'\) be any lower bound for \(S\); we must show that \(l' \leq l\). This holds because \(l' \in S \downarrow\) and \(l\) is an upper bound for \(S \downarrow\).

Thus \(A\) has the greatest lower bound property. Similarly, any linearly ordered set with the greatest lower bound property has the least upper bound property. \(\Box\)

Exercises

Equivalence Relations

Exercise 1

Define two points \((x_0, y_0)\) and \((x_1,y_1)\) of the plane to be equivalent if \(y_0 - x_0^2 = y_1 - x_1^2\) . Check that this is an equivalence relation and describe the equivalence classes.

Solution

For any point \((x_0,y_0)\), we have \(y_0 - x_0^2 = y_0 - x_0^2\). Thus the relation is reflexive.

If \(y_0 - x_0^2 = y_1 - x_1^2\) then \(y_1 - x_1^2 = y_0 - x_0^2\). Thus the relation is symmetric.

If \(y_0 - x_0^2 = y_1 - x_1^2\) and \(y_1 - x_1^2 = y_2 - x_2^2\) then \(y_0 - x_0^2 = y_2 - x_2^2\). Thus the relation is transitive.

The equivalence classes are the parabolas with equations \(y - x^2 = c\) or \(y = x^2 + c\) for any constant \(c\).

Exercise 2

Let \(C\) be a relation on \(A\). If \(A_0 \subseteq A\), define the restriction of \(C\) to \(A_0\) to be the relation \(C \cap A_0^2\). Show that the restriction of an equivalence relation is an equivalence relation.

Solution

Let \(C\) be an equivalence relation on \(A\) and \(A_0 \subseteq A\). We show that \(C \cap A_0^2\) is an equivalence relation on \(A_0\).

Let \(x \in A_0\). Then \(x \in A\) and so \((x,x) \in C\), hence \((x,x) \in C \cap A_0^2\). Thus, \(C \cap A_0^2\) is reflexive on \(A_0\).

Let \((x,y) \in C \cap A_0^2\). Then \((x,y) \in C\) so \((y,x) in C\) since \(C\) is symmetric. Therefore \((y,x) \in C \cap A_0^2\). Thus, \(C \cap A_0^2\) is symmetric.

Let \((x,y),(y,z) \in C \cap A_0^2\). Then \((x,y),(y,z) \in C\) so \((x,z) \in C\) since \(C\) is transitive. Therefore, \((x,z) \in C \cap A_0^2\). Thus, \(C \cap A_0^2\) is transitive.

Exercise 3

Here is a "proof" that every relation \(C\) that is both symmetric and transitive is also reflexive: "Since \(C\) is symmetric, \(a C b\) implies \(b C a\). Since \(C\) is transitive, \(a C b\) and \(b C a\) together imply \(a C a\), as desired." Find the flaw in this argument.

Solution

The argument shows that if \(a C b\) then \(a C a\). However, we cannot conclude that \(C\) is reflexive because, given \(a\), there may not exist \(b\) such that \(aCb\).

Exercise 4

Let \(f : A \rightarrow B\) be a surjective function. Let us define a relation on \(A\) by setting \(a_0 \sim a_1\) if

\[ f(a_0) = f(a_1) \]

(a)

Show that this is an equivalence relation.

Solution

For any \(a \in A\) we have \(f(a) = f(a)\) and so \(a \sim a\). Thus, \(\sim\) is reflexive on \(A\).

Assume \(a \sim b\). Then \(f(a) = f(b)\) so \(f(b) = f(a)\) and so \(b \sim a\). Thus \(\sim\) is symmetric.

Assume \(a \sim b\) and \(b \sim c\). Then \(f(a) = f(b)\) and \(f(b) = f(c)\) and so \(f(a) = f(c)\). Thus \(\sim\) is transitive.

(b)

Let \(A^*\) be the set of equivalence classes. Show that there is a bijective correspondence of \(A^*\) with \(B\).

Solution

Define \(g : B \rightarrow A^*\) by \(g(y) = \{x \in A \mid f(x) = y\} = f^{-1}(y)\).

We first prove that \(g(y) \in A^*\) for all \(y\). Let \(y \in B\). Pick \(x \in A\) such that \(f(x) = y\) (since \(f\) is surjective). We prove that \(g(y)\) is the equivalence class determined by \(x\). We have \(x \sim z\) iff \(f(x) = f(z)\) iff \(f(z) = y\) iff \(z \in g(y)\) as required.

We now prove \(g\) is surjective. Let \(E \in A^*\). Pick \(x \in A\) such that \(E\) is the equivalence class determined by \(x\). We have that \(g(f(x))\) is the equivalence class determined by \(x\) (by the same argument as the previous paragraph), that is, \(g(f(x)) = E\).

We now prove \(g\) is injective. Assume \(g(y) = g(y')\). Pick \(x \in A\) such that \(f(x) = y\) (since \(f\) is surjective). Then \(x \in g(y)\) so \(x \in g(y')\) so \(f(x) = y'\). Thus \(y = y'\) as required.

Exercise 5

Let \(S\) and \(S'\) be the following subsets of the plane:

\[ \begin{align} S & = \{ (x,y) \mid y = x + 1 \text{ and } 0 < x < 2 \} \\ S' & = \{ (x,y) \mid y - x \text{ is an integer} \} \end{align} \]

(a)

Show that \(S'\) is an equivalence relation on the real line and \(S' \supseteq S\). Describe the equivalence classes of \(S'\).

Solution

For any \(x \in \mathbb{R}\), we have \(x - x = 0\) which is an integer, so \(x S' x\). Thus \(S'\) is reflexive on \(\mathbb{R}\).

If \(x S' y\), i.e. \(y-x\) is an integer, then \(x-y\) is an integer, and so \(y S' x\). Thus \(S'\) is symmetric.

If \(x S' y\) and \(y S' z\), i.e. \(y-x\) and \(z-y\) are integers, then \(z - x = (z-y) + (y-x)\) is an integer, and so \(x S' z\). Thus \(S'\) is transitive.

An equivalence class under \(S'\) has the form \( \{ \cdots, -2 + \epsilon, -1 + \epsilon, \epsilon, 1 + \epsilon, 2 + \epsilon, \cdots \}\), where \(\epsilon\) is some real in \([0,1)\).

(b)

Show that given any collection of equivalence relations on a set \(A\), their intersection is an equivalence relation on \(A\).

Solution

Let \(\mathcal{E}\) be a set of equivalence relations on \(A\). We prove \(\bigcap \mathcal{E}\) is an equivalence relation on \(A\).

Let \(x \in A\). For all \(R \in \mathcal{E}\) we have \(xRx\). Therefore, \((x,x) \in \bigcap \mathcal{E}\). Thus, \(\bigcap \mathcal{E}\) is reflexive on \(A\).

Assume \((x,y) \in \bigcap \mathcal{E}\). For all \(R \in \mathcal{E}\) we have \(x R y\) and therefore \(y R x\), because \(R\) is symmetric. Thus, \((y,x) \in \bigcap \mathcal{E}\), and so \(\bigcap \mathcal{E}\) is symmetric.

Assume \((x,y),(y,z) \in \bigcap \mathcal{E}\). For all \(R \in \mathcal{E}\), we have \(xRy\) and \(yRz), and therefore \(xRz\) because \(R\) is transitive. Thus, \((x,z) \in \bigcap \mathcal{E}\), and so \(\bigcap \mathcal{E}\) is transitive.

(c)

Describe the equivalence relation on \(T\) on the real line that is the intersection of all equivalence relations on the real line that contain \(S\). Describe the equivalence classes of \(T\).

Solution

We have \(T = \{(x,y) \mid x = y \vee (0 < x,y < 3 \wedge |y-x| = 1) \vee (0 < x,y < 3 \wedge |y-x|=2)\}). The equivalence classes of \(T\) are the sets of the form \(\{\epsilon, 1 + \epsilon, 2 + \epsilon\} for \{\epsilon \in (0,1)\}, together with \(\{1, 2\}\) and \(\{r\}\) for all \(r \leq 0\) and \(r \geq 3\).

Order Relations

Exercise 6

Define a relation on the plane by setting

\[ (x_0, y_0) < (x_1, y_1) \]

if either \(y_0 - x_0^2 < y_1 - x_1^2\), or \(y_0 - x_0^2 = y_1 - x_1^2\) and \(x_0 < x_1\). Show that this is a linear order on the plane, and describe it geometrically.

Solution

We first prove \(<\) is irreflexive. For any point \((x,y)\), we cannot have \(y - x^2 < y - x^2\), and we cannot have \(x < x\). Therefore, we cannot have \((x,y) < (x,y)\).

We now prove \(<\) is transitive. Assume \((x_0,y_0) < (x_1, y_1) < (x_2, y_2)\). If \(y_0 - x_0^2 < y_1 - x_1^2\) then we have \(y_1 - x_1^2 \leq y_2 - x_2^2\) and so \(y_0 - x_0^2 < y_2 - x_2^2\). Similarly if \(y_1 - x_1^2 < y_2 - x_2^2\) then we have \(y_0 - x_0^2 < y_2 - x_2^2\). The other case is \(y_0 - x_0^2 = y_1 - x_1^2 = y_2 - x_2^2\) and \(x_0 < x_1 < x_2\), in which case \(x_0 < x_2\). Thus in every case we have \((x_0,y_0) < (x_2,y_2)\).

Now, let \((x_0,y_0),(x_1,y_1) \in \mathbb{R}^2\) and assume \((x_0,y_0) \neq (x_1,y_1)\). If \(y_0 - x_0^2 < y_1 - x_1^2\) then \((x_0,y_0) < (x_1,y_1)\). If \(y_1 - x_1^2 < y_0 - x_0^2\) then \((x_1,y_1) < (x_0,y_0)\). If \(y_0 - x_0^2 = y_1 - x_1^2\) then we must have \(x_0 < x_1\) or \(x_1 < x_0\) (because \(x_0 = x_1\) would imply \(y_0 = y_1\) and hence \((x_0,y_0) = (x_1,y_1)\)). Thus we have \((x_0,y_0) < (x_1,y_1)\) or \((x_1,y_1) < (x_0,y_0)\) in every case.

So \(<\) is a linear order on \(\mathbb{R}^2\). Geometrically, divide the plane into the parabolas \(y = x^2 + c\) for constants \(c\). Then \((x_0,y_0) < (x_1,y_1)\) iff \((x_0,y_0)\) is in a lower parabola than \((x_1,y_1)\), or the two points are in the same parabola and \((x_0,y_0)\) is to the left of \((x_1,y_1)\).

Exercise 7

Show that the restriction of a strict linear order is a strict linear order.

Solution

Let \(R\) be a strict linear order on \(A\) and \(A_0 \subseteq A\). We prove that \(R \cap A_0^2\) is a strict linear order on \(A_0\).

There is no \(x \in A_0\) such that \(xRx\). So \(R \cap A_0^2\) is irreflexive.

Let \((x,y),(y,z) \in R \cap A_0^2\). Then we have \(xRy\) and \(yRz\) and so \(xRz\). Therefore \((x,z) \in R \cap A_0^2\). Thus, \(R \cap A_0^2\) is transitive.

Now, let \(x,y \in A_0\) with \(x \neq y\). Then either \(xRy\) or \(yRx\). Hence either \((x,y) \in R \cap A_0^2\) or \((y,x) \in R \cap A_0^2\).

Exercise 8

Check that the relation defined in Example 7 is a strict linear order.

Example 7: Define \(x C y\) if \(x^2 < y^2\), or if \(x^2 = y^2\) and \(x < y\).

Solution

For any \(x \in \mathbb{R}\), we cannot have \(x^2 < x^2\), and we cannot have \(x < x\). So we cannot have \(x C x\). Thus, \(C\) is irreflexive.

We now prove \(C\) is transitive. Assume \(x C y\) and \(y C z\). If \(x^2 < y^2\) then we have \(y^2 \leq z^2\) and so \(x^2 < z^2\). Similarly if \(y^2 < z^2\) then \(x^2 < z^2\). The other case is \(x^2 = y^2 = z^2\) and \(x < y < z\), which is impossible as there can be at most two distinct reals with the same square.

Exercise 9

Check that the dictionary order is a strict linear order.

Solution

Let \((A, <_A)\) and \((B, <_B)\) be linearly ordered sets. Let \(<\) be the dictionary order on \(A \times B\).

For any \((a,b) \in A \times B\), we cannot have \(a <_A a\) or \(b <_B b\), so we cannot have \((a,b) < (a,b)\). Thus, \(<\) is irreflexive

Assume \((a_1,b_1) < (a_2, b_2) < (a_3, b_3)\). If \(a_1 <_A a_2\), then since we have \(a_2 \leq_A a_3\) we have \(a_1 <_A a_3\) and so \((a_1,b_1) < (a_3,b_3)\). Similarly, if \(a_2 <_A a_3\) then \(a_1 <_A a_3\) and so \((a_1,b_1) < (a_3, b_3)\). The only other case is \(a_1 = a_2 = a_3\) and \(b_1 <_B b_2 <_B b_3\). In this case we have \(a_1 = a_3\) and \(b_1 <_B b_3\). Thus, \(<\) is transitive.

Now, let \((a_1,b_1),(a_2,b_2) \in A \times B\). We know that one of \(a_1 <_A a_2\), \(a_2 <_A a_1\) and \(a_1 = a_2\) holds. In the first case, \((a_1,b_1) < (a_2,b_2)\). In the second case, \((a_2,b_2) < (a_1,b_1)\).

If \(a_1 = a_2\), then we also know that one of \(b_1 <_B b_2\), \(b_2 <_B b_1\), \(b_1 = b_2\) holds. If \(b_1 <_B b_2\) then \((a_1,b_1) < (a_2,b_2)\). If \(b_2 <_B b_1\) then \((a_2,b_2) < (a_1,b_1)\). If \(b_1 = b_2\) then \((a_1,b_1) = (a_2,b_2)\).

Exercise 10

(a)

Show that the map \(f : (-1,1) \rightarrow \mathbb{R}\) of Example 9 is order preserving.

\[ f(x) = \frac{x}{1-x^2} \]

Solution

Let \(x,y \in (-1,1)\), and assume \(x < y\). We have \(xy > -1\) and so \(1 + xy > 0\), hence \(x(1+xy) < y(1+xy)\). That is, \( x + x^2y < y + xy^2 \), and so \(x - xy^2 < y - x^2 y\), that is, \(x(1-y^2) < y(1-x^2)\). So \(x / 1-x^2 < y / 1-y^2 \) as required (using the fact that \(1 - x^2 > 0\) and \(1 - y^2 > 0\)).

(b)

Show that the equation \( g(y) = 2y/[1 + (1 + 4y^2)^{1/2}]\) defines a function \(g : \mathbb{R} \rightarrow (-1,1)\) that is both a left and a right inverse for \(f\).

Solution

If \(y = f(x) = \frac{x}{1-x^2}\) then

\[ \begin{align} 4y^2 & = \frac{4x^2}{1 - 2x^2 + x^4} \\ \therefore 1 + 4y^2 & = \frac{1 + 2x^2 + x^4}{1 - 2x^2 + x^4} \\ \therefore (1 + 4y^2)^{1/2} & = \frac{1 + x^2}{1 - x^2} \\ \therefore 1 + (1 + 4y^2)^{1/2} & = \frac{2}{1-x^2} \\ \therefore \frac{2y}{1 + (1 + 4y^2)^{1/2}} & = 2x / 2 \\ & = x \\ \therefore g(f(x)) & = x \end{align} \]

Thus \(g\) is a left inverse for \(f\).

Now, let \(x = g(y)\). Let \(D = 1 + (1 + 4y^2)^{1/2}\). Then we have \(D^2 = 2 + 2(1+4y^2)^{1/2} + 4y^2 = 2D+4y^2\). So

\[ \begin{align} x^2 & = \frac{4y^2}{D^2} \\ \therefore 1 - x^2 & = \frac{D^2 - 4y^2}{D^2} \\ & = \frac{2D}{D^2} \\ & = \frac{2}{D} \\ \therefore \frac{x}{1-x^2} & = \left( \frac{2y}{D} \right) / \left( \frac{2}{D} \right) \\ & = y \\ \therefore f(g(y)) & = y \end{align} \]

Exercise 11

Show that an element in a linearly ordered set has at most one immediate successor and at most one immediate predecessor. Show that a subset of a linearly ordered set has at most one smallest element and at most one largest element.

Solution

Let \((A, <)\) be a linearly ordered set.

Suppose \(b\) and \(c\) are both immediate successors of \(a\). Assume w.l.o.g. \(b \leq c\). We cannot have \(b < c\) because there is no element \(x\) such that \(a < x < c\); therefore \(b = c\). Thus, \(a\) has at most one immediate successor.

Similarly, an element can have at most one immediate predecessor.

Let \(S \subseteq A\) and suppose \(a\) and \(b\) are both smallest elements of \(S\). We have \(a \leq b\) because \(b \in S\) and \(a\) is smallest in \(S\). Similarly we have \(b \leq a\) because \(a \in S\) and \(b\) is smallest in \(S\). Therefore \(a = b\). Thus, \(S\) has at most one smallest element.

Similarly, a subset of \(A\) can have at most one greatest element.

Exercise 12

Let \(\mathbb{Z}_+\) denote the set of positive integers. Consider the following linear orders on \(\mathbb{Z}_+^2\). In these order relations, which elements have immediate predecessors? Does the set have a smallest element? Show that all three order types are different.

(i)

The dictionary order.

Solution

\((a,b)\) has an immediate predecessor iff \(b \neq 1\), in which case its immediate predecessor is \((a,b-1)\).

\((1,1)\) is the smallest element.

(ii)

\((x_0,y_0) < (x_1,y_1)\) iff either \(x_0 - y_0 < x_1 - y_1\), or \(x_0 - y_0 = x_1 - y_1\) and \(y_0 < y_1\).

Solution

\((a,b)\) has an immediate predecessor iff neither \(a\) nor \(b\) is \(1\), in which case its predecessor is \((a-1,b-1)\).

There is no smallest element.

This is not isomorphic to the dictionary order because there is no smallest element.

(iii)

\((x_0, y_0) < (x_1, y_1)\) iff either \(x_0 + y_0 < x_1 + y_1\), or \(x_0 + y_0 = x_1 + y_1\) and \(y_0 < y_1\).

Solution

\((a,b)\) has an immediate predecessor iff \((a,b) \neq (1,1)\). If \(b \neq 1\), the immediate predecessor of \((a,b)\) is \((a+1,b-1)\); otherwise, the predecessor of \((a,1)\) is \((1,a-1)\).

The smallest element is \((1,1)\).

This is not isomorphic to either of the orders in (i) or (ii) because there is only one element without a predecessor.

Exercise 13

Prove the following:

Theorem

If a linearly ordered set \(A\) has the least upper bound property, then it has the greatest lower bound property.

Solution

See Proposition 28 above.

Exercise 14

If \(C\) is a relation on a set \(A\), define a new relation \(D\) on \(A\) by letting \((b,a) \in D\) iff \((a,b) \in C\).

(a)

Show that \(C\) is symmetric if and only if \(C = D\).

Solution

\(C\) is symmetric iff, for all \(x,y \in A\), we have \((x,y) \in C\) iff \((y,x) \in C\). This is the same as saying \((x,y) \in C\) iff \((x,y) \in D\), i.e. \(C = D\).

(b)

Show that if \(C\) is a linear order, \(D\) is also a linear order.

Solution

Assume that \(C\) is a linear order.

For any \(x \in A\) we have \((x,x) \notin C\) and so \((x,x) \notin D\). So \(D\) is irreflexive.

Assume \((x,y),(y,z) \in D\). Then we have \((y,x),(z,y) \in C\), and so \((z,x) \in C\) because \(C\) is transitive. Therefore \((x,z) \in D\). And so \(D\) is transitive.

For any \(x,y \in A\), we have either \(x = y\) or \((x,y) \in C\), or \((y,x) \in C\). Therefore, either \(x = y\), or \((y,x) \in D\), or \((x,y) \in D\). This completes the proof that \(D\) is a linear order.

(c)

Prove the converse of the theorem is Exercise 13.

Solution

Assume that \((A, C)\) has the greatest lower bound property. Then \((A, D)\) has the least upper bound property. Therefore, \((A, D)\) has the greatest lower bound property by Proposition 28. Therefore \((A,C)\) has the least upper bound property.

Exercise 15

Assume that the real line has the least upper bound property.

(a)

Show that the sets

\[ \begin{align} [0,1] & = \{ x \mid 0 \leq x \leq 1 \} \\ [0,1) & = \{ x \mid 0 \leq x < 1 \} \end{align} \]

have the least upper bound property.

Solution

Let \(S \subseteq [0,1]\) be nonempty and bounded above in \([0,1]\). Let \(u\) be its supremum in \(\mathbb{R}\); we must show \(u \in [0,1]\). Since \(1\) is an upper bound for \(S\), we have \(u \leq 1\). Pick \(s \in S\) (since \(s\) is nonempty\); we have \(0 \leq s \leq u\). Thus \(u \in [0,1]\), and so \([0,1]\) satisfies the least upper bound property.

Let \(S \subseteq [0,1)\) be nonempty and bounded above in \([0,1)\). Let \(u\) be its supremum in \(\mathbb{R}\); we must show \(u \in [0,1)\). Pick an upper bound \(u'\) for \(S\) in \([0,1)\); we have \(u \leq u' < 1\). Pick \(s \in S\) (since \(s\) is nonempty\); we have \(0 \leq s \leq u\). Thus \(u \in [0,1)\), and so \([0,1)\) satisfies the least upper bound property.

(b)

Does \([0,1] \times [0,1]\) in the dictionary order have the least upper bound property? What about \([0,1] \times [0,1)\)? What about \([0,1) \times [0,1]\)?

Solution

\([0,1] \times [0,1]\) does have the least upper bound property. Let \(S \subseteq [0,1] \times [0,1]\) be nonempty. Let \(s\) be the least upper bound of \(\pi_1(S)\). We have two cases:

Case one: there exists \(y\) such that \((s,y) \in S\). In this case, let \(t\) be the least upper bound of \(\{y \mid (s,y) \in S\}\). Then \((s,t)\) is the least upper bound of \(S\).

Case two: there is no \(y\) such that \((s,y) \in S\). Then \((s,0)\) is the least upper bound of \(S\).

\([0,1] \times [0,1)\) and \([0,1) \times [0,1]\) have the least upper bound property similarly.