Читать книгу Set Theory And Foundations Of Mathematics: An Introduction To Mathematical Logic - Volume I: Set Theory - Douglas Cenzer - Страница 11

Relations play a fundamental role in mathematics. Of particular interest are orderings, equivalence relations, and graphs. The notion of a graph is quite general. That is, a graph G = (V, E) is simply a set V of vertices and a binary relation E. In a directed graph, a pair (u, v) is said to be an edge from u to v.

A key notion here is that of an ordered pair. Given two elements a₁, a₂ from our universe U, the ordered pair (a₁, a₂) is defined so that for any two pairs of elements (a₁, b₁) and (b₁, b₂), (a₁, a₂) = (b₁, b₂) a₁ = b₁ and a₂ = b₂. This will be defined carefully in Chapter 3, along with the notion of an n-tuple (a₁, . . . , an) of elements.

Definition 2.2.1. Let A and B be sets.

(1) The product of A and B is defined to be

(2) An = {(a₁, . . . , an) : each ai ∈ A}. Here (a₁, . . . , an) is called an n-tuple.

(3) A subset R of A×B is called a relation, specifically a binary relation.

(4) A subset R of An is said to be an n-ary relation. We sometimes write aRb for (a, b) ∈ R.

Definition 2.2.2. Let A₁, . . . , An be sets.

(1) The product A₁ × A₂ × · · · × An = {(a₁, . . . , an) : each ai ∈ Ai}.

(2) An = {(a₁, . . . , 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 of integers is defined by x | y (∃z) y = xz.

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⁻¹ 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. 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:

(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 is reflexive and transitive. On the natural numbers it is also antisymmetric.

Exercises for Section 2.2

Exercise 2.2.1. Show that, for any set A, 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)⁻¹ = B × A.

Exercise 2.2.4. Show that, for any relations R and S, (R ∩ S)⁻¹ = R⁻¹ ∩ S⁻¹.

Exercise 2.2.5. Show that, for any relation R, (R⁻¹)⁻¹ = 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⁻¹) = Rng(R) and Rng(R⁻¹) = 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 = , then (C × D) ◦ (A × B) = .

(b) If B ∩ C ≠ , then (C × D) ◦ (A × B) = A × D.

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⁻¹ and IA ⊆ R⁻¹ ◦ 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⁻¹ ◦ 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 2.2.21. Show that for any relations R and S and any A ⊆ Dmn(S), (R ◦ S)[A] = R[S[A]].

Exercise 2.2.22. Let R and S be relations.

(a) Show that Dmn(R ◦ S) = S⁻¹[Dmn(R)].

(b) Show that Rng(R ◦ S) = R[Rng(S)].

Exercise 2.2.23. Suppose R is a relation on U. Prove the following conditions:

(a) R is reflexive if and only if IU ⊆ R.

(b) R is irreflexive if and only if IU ∩ R = .

(c) R is transitive if and only if R ◦ R ⊆ R.

(d) R is symmetric if and only if R = R⁻¹.

(e) R is antisymmetric if and only if R ∩ R⁻¹ ⊆ IU.

(f) If R is transitive and reflexive, then R ◦ R = R.