Set Theory And Foundations Of Mathematics: An Introduction To Mathematical Logic - Volume I: Set Theory. Douglas Cenzer

⊆ A × B, we have the following properties:

      (1) The inverse R⁻¹ of R is R⁻¹ = {(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⁻¹[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⁻¹y 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

but the range is just

⁺. For the strict ordering on the real numbers, let A = {a} be the set with a single element a. Then R[A] = (a, ∞) and R⁻¹[A] = (−∞, a). If R is the subset relation ⊆ on U and A is any subset of U, then R⁻¹[A] =

(A).

      Proposition 2.2.11. For any relations R and S,

      (1) (R ∪ S)⁻¹ = R⁻¹ ∪ S⁻¹;

      (2) (R ∩ S)⁻¹ = R⁻¹ ∩ S⁻¹.

      Proof. (1) (x, y) ∈ (R ∪ S)⁻¹ 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⁻¹ ∨ (x, y) ∈ S⁻¹ if and only if (x, y) ∈ R⁻¹ ∪ S⁻¹.

      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 by R ◦ S = {(u, v) : (∃w)(uSw ∧ wRv)}.

      Example 2.2.14. Here are some illustrations from the examples above.

      (1) From Example 2.2.4, let R be the strict ordering x < y on the integers. Then (x, y) ∈ R ◦ R if and only if y − x ≥ 2.

      (2) From Example 2.2.6, the graph G of the lattice of integer points in the plane, two points are related in E ◦ E if there is a path of length two connecting them.

      (3) From Example 2.2.8, the identity relation IA acts like an identity for ◦ in that IA ◦ R = R = R ◦ IA. The proof is left as an exercise.

      Example 2.2.15. For any set A, the set of permutations of A forms a group under composition. This is demonstrated by some of the properties of composition below.

      Here are some important properties of composition.

      Proposition 2.2.16. If R ⊆ B×C and S ⊆ A×B are relations, then

      (1) Dmn(R ◦ S) ⊆ Dmn(S) and

      (2) Rng(R ◦ S) ⊆ Rng(R).

      Proof. (1) Suppose that x ∈ Dmn(R ◦ S). Then, for some y, (x, y) ∈ R◦S. This means that there is some v such that (x, v) ∈ S and (v, y) ∈ R. By the first part, we have x ∈ Dmn(S).

      Part (2) is left as an exercise.

      

      Proposition 2.2.17. For any relations R, S and T,

      (1) (R ∩ S) ◦ T ⊆ (R ◦ T) ∩ (S ◦ T);

      (2) R ◦ (S ∩ T) ⊆ (R ◦ S) ∩ (R ◦ T).

      Proof. (1) Suppose that (x, y) ∈ (R∩S)◦T. Then, for some z, (x, z) ∈ T and (z, y) ∈ R ∩ S. Then (z, y) ∈ R and (z, y) ∈ S, so that (x, y) ∈ R◦T ∧ (x, y) ∈ S◦T. Thus (x, y) ∈ (R◦T)∩(S◦T).

      Part (2) is left as an exercise.

      The following example shows that inequality does not always hold in (1) above.

      Example 2.2.18. Define relations R, S, and T on the natural numbers as follows. T = {(x, 2x), (x, 3x) : x ∈

}; R = {(2x, x) : x ∈

}, and S = {3x, x) : x ∈

}. Then R ◦ T = S ◦ T = {(x, x) : x ∈

}, so that (R ◦ T) ∩ (S ◦ T) = {(x, x) : x ∈

}. On the other hand, R ∩ S =

, so that (R ∩ S) ◦ T =

.

      The next proposition says that composition is associative.

      Proposition 2.2.19.