2.2.2. Let A1, . . . , An be sets.
(1) The product A1 × A2 × · · · × An = {(a1, . . . , an) : each ai ∈ Ai}.
(2) An = {(a1, . . . , an) : each ai ∈ A}.
Proposition 2.2.3. For any sets A, B, and C,
(1) A × (B ∪ C) = (A × B) ∪ (A × C) and (B ∪ C) × A = (B × A) ∪ (C × A);
(2) A × (B ∩ C) = (A × B) ∩ (A × C) and (B ∩ C) × A = (B × A) ∩ (C × A);
(3) A × (B \ C) = (A × B) \ (A × C) and (A \ B) × C = (A × C) \ (B × C).
Proof. (1) (x, y) ∈ A × (B ∪ C) if and only if x ∈ A ∧ y ∈ B ∪ C, if and only if x ∈ A ∧ (y ∈ B ∨ y ∈ C), if and only if (x ∈ A ∧ y ∈ B) ∨ (x ∈ A ∧ y ∈ C), if and only if (x, y) ∈ A×B ∨ (x, y) ∈ A×C, if and only if (x, y) ∈ (A×B)∪(A×C). The proof of the second statement in (1) is similar.
The proof of parts (2) and (3) are left to the exercises.
Here are some important examples of binary relations that we will return to frequently in what follows.
Example 2.2.4. The standard ordering x ≤ y (as well as the strict order <) on the real numbers is a binary relation, which also applies to the rational numbers, integers, and natural numbers.
Example 2.2.5. The subset relation A ⊆ B on sets, read “A is a subset of B”, or “A is included in B”, is a binary relation.
Example 2.2.6. Let the graph G have vertices (i, j) for integers i, j; this is the lattice of integer points in the plane. Let there be horizontal and vertical edges between adjacent vertices. That is, each (i, j) has four edges, going to (i − 1, j), (i + 1, j), (i, j − 1), and (i, j + 1) which means that, for example, (1, 2)E(1, 3).
Example 2.2.7. The fundamental relation of axiomatic set theory is membership, that is the relation x ∈ y, for sets x and y. Note that when we study higher set theory, we do not distinguish between points and sets.
Example 2.2.8. For any set A, let IA = {(a, a) ∈ A × A : a ∈ A} be the identity relation on A.
Example 2.2.9. The divisibility relation on the set
Here are some useful concepts associated with relations.
Definition 2.2.10. For any sets A and B, and any relation R ⊆ A × B, we have the following properties:
(1) The inverse R−1 of R is R−1 = {(u, v) : vRu}.
(2) The domain of R is Dmn(R) = {x : (∃y) xRy} and for any set D ⊆ B, the inverse image of D is R−1[D] = {x ∈ A : (∃y ∈ D) xRy}.
(3) The range of R is Rng(R) = {y : (∃x) xRy} and for any C ⊆ A, the image R[C] = {y ∈ B : (∃x ∈ A) xRy}.
For example, if xRy is the ordering x ≤ y, then xR−1y is the ordering x ≥ y. The inverse of the identity relation is again the identity. On the natural numbers, the domain of strict inequality is
Proposition 2.2.11. For any relations R and S,
(1) (R ∪ S)−1 = R−1 ∪ S−1;
(2) (R ∩ S)−1 = R−1 ∩ S−1.
Proof. (1) (x, y) ∈ (R ∪ S)−1 if and only if (y, x) ∈ R ∪ S if and only if (y, x) ∈ R ∨ (y, x) ∈ S if and only if (x, y) ∈ R−1 ∨ (x, y) ∈ S−1 if and only if (x, y) ∈ R−1 ∪ S−1.
Part (2) is left to the exercise.
Proposition 2.2.12. For any relations R and S,
(1) Dmn(R ∩ S) = Dmn(R) ∩ Dmn(S);
(2) Rng(R ∩ S) = Rng(R) ∩ Rng(S).
Proof. (⊆): Suppose x ∈ Dmn(R ∩ S). Then, for some y, (x, y) ∈ R ∩ S. Choose some b so that (x, b) ∈ R ∩ S. Then (x, b) ∈ R and (x, b) ∈ S. It follows that (∃y)(x, y) ∈ R and (∃y)(x, y) ∈ S. Thus x ∈ Dmn(R) ∧ x ∈ Dmn(S), and therefore x ∈ Dmn(R) ∩ Dmn(S). The above steps can be reversed to obtain the other inclusion. The proof of (2) is left to the reader.
Definition 2.2.13. If R ⊆ B × C and S ⊆ A × B are relations, then the composition R ◦ S is defined
