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

Definition 2.4.1. A relation R on a set A is an equivalence relation if it is reflexive, symmetric, and transitive. For any a ∈ A, the equivalence class of a is [a]R := {x ∈ A : aRx}, or sometimes written a/R.

A family {Pi : i ∈ I} of subsets of A is a partition of A the sets Pi are nonempty, pairwise disjoint, and ⋃_i∈I Pi = A. The last two conditions may be rephrased to say that each element of A belongs to exactly one of the sets Pi.

Here are some well-known examples.

Example 2.4.2. For any positive integer m and any integers x, y, let x ≡ y (mod m) if and only if m divides x − y. For example, if m = 3, then there are three equivalence classes, [0] = {0, 3, 6, . . . }, [1] = {1, 4, 7, . . . }, and [2] = {2, 5, 8, . . . }. The equivalence classes form the group (3) with addition take modulo 3.

Example 2.4.3. Let F ≡ G (modulo finite) for functions F, G : → if and only if {x : F(x) ≠ G(x)} is finite. For subsets A, B of , let A ≡ B (modulo finite) if and only if χA ≡ χB. Another way to phrase this is that A ≡ B (modulo finite) if and only if the symmetric difference (A \ B) ∪ (B \ A) is finite.

The following proposition gives some key properties of equivalence classes.

Proposition 2.4.4. Let R be an equivalence relation on A and let [a] denote [a]R. Then the following conditions are equivalent:

(1) aRb;

(2) [a] = [b];

(3) a ∈ [b];

(4) [a] ∩ [b] ≠ .

Proof. (1) (2): Suppose aRb and let c ∈ A be arbitrary. If c ∈ [a], then cRa. By transitivity, this implies cRb and hence c ∈ [b]. Similarly c ∈ [b] implies c ∈ [a]. This demonstrates that [a] = [b].

(2) (3): Suppose that [a] = [b]. Since a ∈ [a], this implies that a ∈ [b].

(3) (4): Suppose that a ∈ [b]. Since a ∈ [a], this implies that [a] ∩ [b] ≠ .

(4) (1): Suppose that [a] ∩ [b] ≠ and let c ∈ [a] ∩ [b]. Then c ∈ [a], so that aRc and c ∈ [b], so that cRb. It follows from transitivity that aRb.

Proposition 2.4.5. Let R be an equivalence relation on A, and A ≠ . Then the family of equivalence classes of A/R is partition of A.

Proof. Let [a] denote [a]R. Certainly each [a] is a nonempty subset of A. ⋃_a∈A[a] = A since each a ∈ [a]. Given two classes [a] ≠ [b], it follows from Proposition 2.4.4 that [a] ∩ [b] = .

Proposition 2.4.6. For any partition P = {Ai : i ∈ I} of a set A, there is an equivalence relation R on A such that P is the set of equivalence classes of R.

Proof. Define aRb if and only if a and b belong to the same set Ai of the partition. This is clearly reflexive and symmetric. Suppose now that aRb and bRc. Then, for some i, j ∈ I, a, b ∈ Ai and b, c ∈ Aj. Then b ∈ Ai ∩ Aj and therefore Ai = Aj and i = j by the definition of partition. Thus aRc.

Here is one general way to obtain an equivalence relation. The proof is left as an exercise.

Proposition 2.4.7. Let F : A → B and define a relation R such that, for all x, y ∈ A, xRy F(x) = F(y). Then R is an equivalence relation on A and there is a function G : A/R → B such that F(a) = G([a]R) for all a ∈ A.

For example, let F : () → ∪ {ω} be defined by F(A) = card(A), where card(A) is the cardinality of the set A. Here we write ω for the cardinality of . Then the resulting equivalence relation will have A ≡ B if and only if A and B have the same cardinality. For instance, the equivalence class of A = {3} is [A] = {{0}, {1}, . . . }, that is, the family of sets having exactly one element. The function G thus satisfies G([A]) = card(A).

Exercises for Section 2.4

Exercise 2.4.1. Suppose we extend the equivalence relation of equality modulo k to the real numbers, meaning that x ≡ y (mod k) if x − y is an integer multiple of k. Prove that this is still an equivalence relation. Find the members of the equivalence class of the real number π, when k = 2. What can you say about the group (mod k)?

Exercise 2.4.2. What is the equivalence class of under equivalence modulo finite?

Exercise 2.4.3. Let F : A → B and define a relation R so that for all x, y ∈ A, xRy F(x) = F(y). Show that R is an equivalence relation on A and that there is a function G : A/R → B such that F(a) = G(a/R) for all a.

Exercise 2.4.4.

(a) Let R and S be equivalence relations on a nonempty set A, and suppose R ⊆ S. Show that S induces an equivalence relation T on A/R given by [a]RT[b]R aSb.

(b) Let R be an equivalence relation on A and let T be an equivalence relation on A/R. Show that T induces an equivalence relation S on A such that R ⊆ S given by aSb [a]RT[b]R.

Exercise 2.4.5. Let R be an equivalence relation on A and let B ⊆ A.

(a) Show that R ∩ (B × B) is an equivalence relation on B.

(b) Let F : B → A. Show that F induces an equivalence relation S on B, given by aSb F(a)RF(b).

Exercise 2.4.6. Show that if {Ri : i ∈ I} is a family of equivalence relations on a set A, then ⋂_i∈I Ri is also an equivalence relation on A.

Exercise 2.4.7. Let R and S be two equivalence relations on a set A. Show that R ⊆ S if and only if every equivalence class K of R is included in some equivalence class M of S.