Set Theory And Foundations Of Mathematics: An Introduction To Mathematical Logic - Volume I: Set Theory. Douglas Cenzer
(⊆): Suppose that (x, y) ∈ R ◦ (S ◦ T). Then, for some z ∈ C, (x, z) ∈ S ◦ T and (z, y) ∈ R. The first statement implies that, for some v ∈ B, (x, v) ∈ T and (v, z) ∈ S. Since (v, z) ∈ S and (z, y) ∈ R, it follows that (v, y) ∈ R ◦ S. Since (x, v) ∈ T, it follows that (x, y) ∈ (R ◦ S) ◦ T.
The steps above can be reversed to obtain the other inclusion.
Proposition 2.2.20. If R ⊆ B×C and S ⊆ A×B are relations, then (R ◦ S)−1 = S−1 ◦ R−1.
Proof. (⊆): Suppose (x, y) ∈ (R ◦ S)−1. Then (y, x) ∈ R ◦ S. This means that, for some z ∈ B, (y, z) ∈ S and (z, x) ∈ R. It follows that (z, y) ∈ S−1 and (x, z) ∈ R−1. This implies that (x, y) ∈ S−1 ◦ R−1.
(⊇): Suppose that (x, y) ∈ S−1 ◦ R−1. Then, for some z ∈ B, (z, y) ∈ S−1 and (x, z) ∈ R−1. Thus (y, z) ∈ S and (z, x) ∈ R. It follows that (y, x) ∈ R ◦ S. This implies that (x, y) ∈ (R ◦ S)−1.
For our discussion of equivalence relations and orderings, we will need the following basic concepts about relations.
Definition 2.2.21. For any binary relation R on a set A,
(1) R is reflexive if, for any x ∈ A, xRx.
(2) R is irreflexive if, for any x ∈ A, ¬xRx.
(3) R is transitive if, for any x, y, z ∈ A, if both xRy and yRz, then xRz.
(4) R is symmetric if, for any x, y ∈ A, xRy if and only if yRx.
(5) R is antisymmetric if, for any x, y ∈ A, if both xRy and yRx, then x = y.
Example 2.2.22. Returning to the examples above, we have the following conditions:
(1) From Example 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 =