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

2.3.11. Show that, for any set A and any indexed family {Bi : i ∈ I}, A ∪ ⋂_i∈I Bi = ⋂_i∈I(A ∪ Bi).

       Exercise 2.3.12.

      (a) Show that, for any indexed families {Ai : i ∈ I} and {Bi : i ∈ I}, ⋃_i∈I(Ai ∩ Bi) ⊆ (⋃_i∈I Ai ∩ ⋃_i∈I Bi).

      (b) Give an example to show that equality does not always hold in part (a).

      Exercise 2.3.13. Let {Ai : i ∈ I} and Bj : j ∈ J} be indexed families of sets and suppose that Ai ⊂ Bj for all i ∈ I and all j ∈ J. Show that ⋃_i∈I Ai ⊂ ⋂_j∈J Bj.

      Exercise 2.3.14. Show that, for any indexed family {Ai : i ∈ I} of sets, (⋂_i∈I Ai)^∁ = ⋃_i∈I

.

      Exercise 2.3.15. Let {Ai : i ∈ I} be an indexed family of sets.

      (a) Show that F[⋃_i∈I Ai] = ⋃_i∈I F[Ai].

      (b) Show that F[⋂_i∈I Ai] ⊂ ⋂_i∈I F[Ai].

      (c) Show that equality does not always hold in (b).

      Exercise 2.3.16. Let {Bi : i ∈ I} be an indexed family of sets.

      (a) Show that F⁻¹[⋃_i∈I Bi] = ⋃_i∈I F⁻¹[Bi].

      (b) Show that F⁻¹[⋂_i∈I Bi] = ⋂_i∈I F⁻¹[Bi].

      

      Exercise 2.3.17. Suppose

= {Ai : i ∈ I} is an indexed family, and Ai ≠

for all i ∈ I. Show that the Rng(pi) = Ai, where pi is the ith projection function on ∏_i∈I Ai.

      Exercise 2.3.18. Let I = {0, 1}. Define a bijection between ∏_i∈I Ai and A₀ × A₁. More generally, define a bijection between

and A₁ × A₂ × · · · × An.

2.4. Equivalence Relations

      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)

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

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