Proof. Define aRb if and only if a and b belong to the same set Ai of the partition. This is clearly reflexive and symmetric. Suppose now that aRb and bRc. Then, for some i, j ∈ I, a, b ∈ Ai and b, c ∈ Aj. Then b ∈ Ai ∩ Aj and therefore Ai = Aj and i = j by the definition of partition. Thus aRc.
Here is one general way to obtain an equivalence relation. The proof is left as an exercise.
Proposition 2.4.7. Let F : A → B and define a relation R such that, for all x, y ∈ A, xRy
For example, let F :
Exercises for Section 2.4
Exercise 2.4.1. Suppose we extend the equivalence relation of equality modulo k to the real numbers, meaning that x ≡ y (mod k) if x − y is an integer multiple of k. Prove that this is still an equivalence relation. Find the members of the equivalence class of the real number π, when k = 2. What can you say about the group
Exercise 2.4.2. What is the equivalence class of
Exercise 2.4.3. Let F : A → B and define a relation R so that for all x, y ∈ A, xRy
Exercise 2.4.4.
(a) Let R and S be equivalence relations on a nonempty set A, and suppose R ⊆ S. Show that S induces an equivalence relation T on A/R given by [a]RT[b]R
(b) Let R be an equivalence relation on A and let T be an equivalence relation on A/R. Show that T induces an equivalence relation S on A such that R ⊆ S given by aSb
Exercise 2.4.5. Let R be an equivalence relation on A and let B ⊆ A.
(a) Show that R ∩ (B × B) is an equivalence relation on B.
(b) Let F : B → A. Show that F induces an equivalence relation S on B, given by aSb
Exercise 2.4.6. Show that if {Ri : i ∈ I} is a family of equivalence relations on a set A, then ⋂i∈I Ri is also an equivalence relation on A.
Exercise 2.4.7. Let R and S be two equivalence relations on a set A. Show that R ⊆ S if and only if every equivalence class K of R is included in some equivalence class M of S.
2.5. Orderings
In this section, we introduce the various types of partial and total orderings.
Definition 2.5.1. A relation R on A is a preorder or quasiorder if it is reflexive and transitive. A preorder is a partial ordering if it is antisymmetric. If A is a set equipped with a partial ordering, we will refer to A as a partially ordered set, or p.o. set for short. A partial ordering R is a linear ordering if it is total, that is, for any a, b ∈ A, either aRb or bRa. An ordering R is a well-ordering if it is linear and well-founded, that is, any subset B of A has a least element. A totally ordered subset of a partially ordered set is called a chain.
Note that a preorder which is symmetric is just an equivalence relation. The relation aRb if and only if card(a) ≤ card(b) for sets a and b is an example of a preorder.
Given a set A partially ordered by ≤ and a, b ∈ A, we write a < b for a ≤ b and a ≠ b. The relation < is irreflexive antisymmetric and transitive. More generally, R is a strict partial ordering if it is irreflexive, antisymmetric, and transitive. Another way to say that a partial order is total, or linear, is by the following definition.
Definition 2.5.2. The partial order ≤ on a set A has the Trichotomy Property if, for any x, y ∈ A, exactly one of the following conditions holds:
(1) x < y;
(2) y < x;
(3) x = y.
The standard ordering ≤ of the real numbers is a linear ordering, and the corresponding strict order is given by <.
The notions of minimal and maximal elements in a partially ordered set, as well as lower and upper bounds for ordered sets, are very important.
Definition 2.5.3. Let ≤ be a partial ordering on a set A and let B ⊆ A.
(1) a is a minimal element of B if a ∈ B and there is no b ∈ B with b < a.
(2) a is a maximal element of B if a ∈ B and there is no b ∈ B with b > a.
(3) a is the minimum element of B if a ∈ B and for every b ∈ B, a ≤ b.
(4) a is a lower bound for B if a ≤ b for every b ∈ B.