§ 3. Relations¶
Definition 3.1 : Relation
A relation on a set \(A\) is a subset \(C\) of the cartesian product \(A \times A\).
If \(C\) is a relation on \(A\), we use the notation \(x C y\) to mean the same thing as \((x, y) \in\) \(C\). We read it "\(x\) is in the relation \(C\) to \(y\)".
Definition 3.2 : Equivalence Relation
An equivalence relation on a set \(A\) is a relation \(\sim\) on \(A\) having the following three properties:
- (Reflexivity) \(x \sim x\) for every \(x\) in \(A\).
- (Symmetry) If \(x \sim y\), then \(y \sim x\).
- (Transitivity) If \(x \sim y\) and \(y \sim z\), then \(x \sim z\).
Definition 3.3 : Equivalence Class
Given an equivalence relation \(\sim\) on a set \(A\) and an element \(x\) of \(A\), we define a certain subset \(E\) of \(A\), called the equivalence class determined by \(x\), by the equation
Lemma 3.1
Two equivalence classes \(E\) and \(E^{\prime}\) are either disjoint or equal.
Proof
Let \(E\) be the equivalence class determined by \(x\), and let \(E^{\prime}\) be the equivalence class determined by \(x^{\prime}\). Suppose that \(E \cap E^{\prime}\) is not empty; let \(y\) be a point of \(E \cap E^{\prime}\). We show that \(E=E^{\prime}\).
By definition, we have \(y \sim x\) and \(y \sim x^{\prime}\). Symmetry allows us to conclude that \(x \sim y\) and \(y \sim x^{\prime}\); from transitivity it follows that \(x \sim x^{\prime}\). If now \(w\) is any point of \(E\), we have \(w \sim x\) by definition; it follows from another application of transitivity that \(w \sim x^{\prime}\). We conclude that \(E \subset E^{\prime}\).
The symmetry of the situation allows us to conclude that \(E^{\prime} \subset E\) as well, so that \(E=E^{\prime}\).
Definition 3.4 : Partition
A partition of a set \(A\) is a collection of disjoint nonempty subsets of \(A\) whose union is all of \(A\).
Theorem 3.2
Given any partition \(\mathcal{D}\) of \(A\), there is exactly one equivalence relation on \(A\) from which it is derived.
Proof
To show that the partition \(\mathcal{D}\) comes from some equivalence relation, let us define a relation \(C\) on \(A\) by setting \(x C y\) if \(x\) and \(y\) belong to the same element of \(\mathcal{D}\). Symmetry of \(C\) is obvious; reflexivity follows from the fact that the union of the elements of \(\mathcal{D}\) equals all of \(A\); transitivity follows from the fact that distinct elements of \(\mathcal{D}\) are disjoint. It is simple to check that the collection of equivalence classes determined by \(C\) is precisely the collection \(\mathcal{D}\).
To show there is only one such equivalence relation, suppose that \(C_{1}\) and \(C_{2}\) are two equivalence relations on \(A\) that give rise to the same collection of equivalence classes \(\mathcal{D}\). Given \(x \in A\), we show that \(y C_{1} x\) if and only if \(y C_{2} x\), from which we conclude that \(C_{1}=C_{2}\). Let \(E_{1}\) be the equivalence class determined by \(x\) relative to the relation \(C_{1}\); let \(E_{2}\) be the equivalence class determined by \(x\) relative to the relation \(C_{2}\). Then \(E_{1}\) is an element of \(\mathcal{D}\), so that it must equal the unique element \(D\) of \(\mathcal{D}\) that contains \(x\). Similarly, \(E_{2}\) must equal \(D\). Now by definition, \(E_{1}\) consists of all \(y\) such that \(y C_{1} x\); and \(E_{2}\) consists of all \(y\) such that \(y C_{2} x\). Since \(E_{1}=D=E_{2}\), our result is proved.
Definition 3.5 : Order Relation
A relation \(<\) on a set \(A\) is called an order relation (or a simple order, or a linear order) if it has the following properties:
- (Comparability) For every \(x\) and \(y\) in \(A\) for which \(x \neq y\), either \(x < y\) or \(y < x\).
- (Nonreflexivity) For no \(x\) in \(A\) does the relation \(x < x\) hold.
- (Transitivity) If \(x < y\) and \(y < z\), then \(x < z\).
By (2) and (3), for some pair of elements \(x\) and \(y\) of \(A\), only one of \(x < y\) or \(y < x\) hold.
We shall use the notation \(x \leq y\) to stand for the statement "either \(x<y\) or \(x=y\)"; and we shall use the notation \(y>x\) to stand for the statement "\(x<y\). We write \(x<y<z\) to mean "\(x<y\) and \(y<z\)."
Definition 3.6 : Open Interval / Immediate Predecessor / Immediate Successor
If \(X\) is a set and \(<\) is an order relation on \(X\), and if \(a<b\), we use the notation \((a, b)\) to denote the set
it is called an open interval in \(X\).
If this set is empty, we call \(a\) the immediate predecessor of \(b\), and we call \(b\) the immediate successor of \(a\).
Definition 3.7 : Order Type
Suppose that \(A\) and \(B\) are two sets with order relations \(<_{A}\) and \(<_{B}\) respectively. We say that \(A\) and \(B\) have the same order type if there is a bijective correspondence between them that preserves order; that is, if there exists a bijective function \(f: A \rightarrow B\) such that
Definition 3.8 : Dictionary Order Relation
Suppose that \(A\) and \(B\) are two sets with order relations \(<_{A}\) and \(<_{B}\) respectively. Define an order relation \(<\) on \(A \times B\) by defining
if \(a_{1}<_{A} a_{2}\), or if \(a_{1}=a_{2}\) and \(b_{1}<_{B} b_{2}\). It is called the dictionary order relation on \(A \times B\).
Definition 3.9 : Largest Element / Smallest Element
Suppose that \(A\) is a set ordered by the relation \(<\). Let \(A_{0}\) be a subset of \(A\). We say that the element \(b\) is the largest element of \(A_{0}\) if \(b \in A_{0}\) and if \(x \leq b\) for every \(x \in A_{0}\).
Similarly, we say that \(a\) is the smallest element of \(A_{0}\) if \(a \in A_{0}\) and if \(a \leq x\) for every \(x \in A_{0}\).
It is easy to see that a set has at most one largest element and at most one smallest element.
Definition 3.10 : Bounded Above / Upper Bound / Supremum (Least Upper Bound)
Suppose that \(A\) is a set ordered by the relation \(<\). Let \(A_{0}\) be a subset of \(A\).
We say that the subset \(A_{0}\) of \(A\) is bounded above if there is an element \(b\) of \(A\) such that \(x \leq b\) for every \(x \in A_{0}\); the element \(b\) is called an upper bound for \(A_{0}\).
If the set of all upper bounds for \(A_{0}\) has a smallest element, that element is called the least upper bound, or the supremum, of \(A_{0}\). It is denoted by \(\sup A_{0}\); it may or may not belong to \(A_{0}\). If it does, it is the largest element of \(A_{0}\).
Definition 3.11 : Bounded Below / Lower Bound / Infimum (Greatest Lower Bound)
Suppose that \(A\) is a set ordered by the relation \(<\). Let \(A_{0}\) be a subset of \(A\).
We say that the subset \(A_{0}\) of \(A\) is bounded below if there is an element \(a\) of \(A\) such that \(a \leq x\) for every \(x \in A_{0}\); the element \(a\) is called an lower bound for \(A_{0}\).
If the set of all lower bounds for \(A_{0}\) has a largest element, that element is called the greatest lower bound, or the infimum, of \(A_{0}\). It is denoted by \(\inf A_{0}\); it may or may not belong to \(A_{0}\). If it does, it is the smallest element of \(A_{0}\).
Definition 3.12 : Least Upper Bound Property / Greatest Lower Bound Property
An ordered set \(A\) is said to have the least upper bound property if every nonempty subset \(A_{0}\) of \(A\) that is bounded above has a least upper bound.
Analogously, the set \(A\) is said to have the greatest lower bound property if every nonempty subset \(A_{0}\) of \(A\) that is bounded below has a greatest lower bound.