2.2.4, the standard ordering x ≤ y on the real numbers is reflexive, transitive, and antisymmetric. The strict order < is irreflexive, transitive, and antisymmetric (in fact, it is never true that x < y and y < x).
(2) From Example 2.2.5, the subset relation A ⊆ B is reflexive, transitive, and antisymmetric. The last is the property of extensionality. That is, if A ⊆ B and B ⊆ A, then A and B contain the same elements and are therefore equal.
(3) From Example 2.2.6, the graph G representing the lattice of integer points in the plane is irreflexive, not transitive, but it is symmetric.
(4) From Example 2.2.7, the membership relation x ∈ y is irreflexive, not transitive, and antisymmetric, that is, we can never have x ∈ y and y ∈ x. This will be explained carefully in Chapter 3.
(5) From Example 2.2.8, the identity relation IA on a set A is reflexive, transitive, and symmetric. The last two properties follows from the fact that (x, y) ∈ IA implies x = y.
(6) From Example 2.2.9, the divisibility relation on
Exercises for Section 2.2
Exercise 2.2.1. Show that, for any set A, A ×
Exercise 2.2.2. Show that, for any nonempty sets A and B, A × B is nonempty.
Exercise 2.2.3. Show that (A × B)−1 = B × A.
Exercise 2.2.4. Show that, for any relations R and S, (R ∩ S)−1 = R−1 ∩ S−1.
Exercise 2.2.5. Show that, for any relation R, (R−1)−1 = R.
Exercise 2.2.6. Show that, for any sets A, B, and C, A ×(B ∩ C) = (A × B) ∩ (A × C) and (B ∩ C) × A = (B × A) ∩ (C × A).
Exercise 2.2.7. For any sets A, B, and C, show that
(a) A × (B \ C) = (A × B) \ (A × C) and
(b) (A \ B) × C = (A × C) \ (B × C).
Exercise 2.2.8. Let a < b be real numbers. Find the image and inverse image of [a, b] and (a, b) under ≤ and under <.
Exercise 2.2.9. For any relation R, show that Dmn(R−1) = Rng(R) and Rng(R−1) = Dmn(R).
Exercise 2.2.10. For any relations R and S, show that Dmn(R ∪S) = Dmn(R) ∪Dmn(S) and Rng(R ∪S) = Rng(R) ∪ Rng(S).
Exercise 2.2.11. Let R and S be relations.
(a) Show that Dmn(R ∩ S) ⊆ Dmn(R) ∩ Dmn(S) and Rng(R ∩ S) ⊆ Rng(R) ∩ Rng(S).
(b) Show that equality does not always hold.
Exercise 2.2.12. For any relations R and S, show that
(a) Dmn(R) \ Dmn(S) ⊆ Dmn(R \ S) and
(b) Rng(R) \ Rng(S) ⊆ Rng(R \ S).
Exercise 2.2.13. Prove the following conditions:
(a) If B ∩ C =
(b) If B ∩ C ≠
Exercise 2.2.14. Show that if R ⊂ A × A, then IA ◦ R = R ◦ IA = R.
Exercise 2.2.15. Show that, for any relations R and S, Rng(R ◦ S) ⊆ Rng(R).
Exercise 2.2.16. For any relations R, S, and T, R ◦ (S ∩ T) ⊆ (R ◦ S) ∩ (R ◦ T).
Exercise 2.2.17. For any relation R ⊆ A × A, with Dmn(R) = Rng(R) = A IA ⊆ R ◦ R−1 and IA ⊆ R−1 ◦ R.
Exercise 2.2.18. For any relations R, S and T, show that
(a) (R ∪ S) ◦ T = (R ◦ T) ∪ (S ◦ T) and
(b) R ◦ (S ∪ T) = (R ◦ S) ∪ (R ◦ T).
Exercise 2.2.19. Prove that, for any relations, R, S, and T, (R ◦ S) ∩ T is empty if and only if (R−1 ◦ T) ∩ S is empty.
Exercise 2.2.20. Let R be a relation and let A, B be arbitrary subsets Dmn(R).
(a) Show that R[A ∪ B] = R[A] ∪ R[B].
(b) Show that R[A ∩ B] ⊆ R[A] ∩ R[B].
(c) Show that equality does not always hold in part (b).
Exercise
