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

Скачать книгу

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. If R ⊆ C × D, S ⊆ B×C, and T ⊆ A×B are relations, then R ◦ (S ◦ T) = (R ◦ S) ◦ T .

      Proof. (⊆): 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)⁻¹ = S⁻¹ ◦ R⁻¹.

      Proof. (⊆): Suppose (x, y) ∈ (R ◦ S)⁻¹. 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⁻¹ and (x, z) ∈ R⁻¹. This implies that (x, y) ∈ S⁻¹ ◦ R⁻¹.

      

      (⊇): Suppose that (x, y) ∈ S⁻¹ ◦ R⁻¹. Then, for some z ∈ B, (z, y) ∈ S⁻¹ and (x, z) ∈ R⁻¹. Thus (y, z) ∈ S and (z, x) ∈ R. It follows that (y, x) ∈ R ◦ S. This implies that (x, y) ∈ (R ◦ S)⁻¹.

      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:

Скачать книгу