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

⋃_i∈I Bi).

      (2) (⋂_i∈I Ai ∪ ⋂_i∈I Bi) ⊆ ⋂_i∈I(Ai ∪ Bi).

      Proof. Part (1) is left to the exercises. Here is a proof of part (2). Let x ∈ ⋂_i∈I Ai ∪ ⋂_i∈I Bi. Then either x ∈ ⋂_i∈I Ai or x ∈ ⋂_i∈I Bi. Without loss of generality, suppose that x ∈ ⋂_i∈I Ai. This means that (∀i ∈ I) x ∈ Ai. Now let i ∈ I be arbitrary. Then x ∈ Ai, so that x ∈ Ai ∨ x ∈ Bi and hence x ∈ Ai ∪ Bi. Since i was arbitrary, it follows that (∀i ∈ I) x ∈ Ai ∪ x ∈ Bi. Thus x ∈ ⋂_i∈I(Ai ∪ Bi).

      

      Here is an example to show that equality does not always hold for the second inclusion. Let I =

, let Ai be the interval (−∞, i), and let Bi = [i, ∞). Then ⋂_i∈I Ai =

= ⋂i Bi, so that ⋂_i∈I Ai ∪ ⋂_i∈I Bi =

. But Ai ∪ Bi = (−∞, ∞) for every i, so that ⋂_i∈I(Ai ∪ Bi) = (−∞, ∞).

      Finally, here is a version of DeMorgan’s laws for indexed families.

      Proposition 2.3.11. Let (Ai)_i∈I be an indexed family of sets.

      (1) (⋃_i∈I Ai)^∁ = ⋂_i∈I

.

      (2) (⋂_i∈I Ai)^∁ = ⋃_i∈I

.

      Proof. (1) x ∈ (⋃_i∈I Ai)^∁ if and only if x ∉ ⋃_i∈I Ai, which holds if and only if ¬(∃i) x ∈ Ai. It follows from predicate logic that this is true if and only if (∀i) ¬x ∈ Ai, which holds if and only if (∀i) x ∈

, which is true if and only if x ∈ ⋂_i∈I

.

      Part (2) is left to the exercises.

      One can also define a doubly indexed family {Bi,j : i ∈ I, j ∈ J}. For example, let Ai,j be the open interval (i − j, i + j) of reals for i ∈

and j ∈

. Then we have

      whereas

      On the other hand, we do have the following proposition.

      Proposition 2.3.12. For any doubly indexed family {Ai,j : i ∈ I, j ∈ J}, ⋃_j∈J ⋂_i∈I Ai,j ⊆ ⋂_i∈I ⋃_j∈J Ai,j.

      Proof. Suppose x ∈ ⋃_j∈J ⋂_i∈I Ai,j and let i ∈ I be arbitrary. Then (∃j ∈ J) x ∈ ⋂_i∈I Ai,j. Fix k ∈ J such that x ∈ ⋂_i∈I Ai,k. This means that (∀i ∈ I) x ∈ Ai,k. Now let i ∈ I be arbitrary. Then we have immediately x ∈ Ai,k. Hence (∃j) x ∈ Ai,j, so that x ∈ ⋃_j∈J Ai,j. Since i was arbitrary, it follows that (∀i ∈ I) x ∈ ⋃_j∈J Ai,j. This means that x ∈ ⋂_i∈I ⋃_j∈J Ai,j, as desired.

       Exercises for Section 2.3

      Exercise 2.3.1. Show that, for any function F : C → D and any subsets A, B of D, F⁻¹[A \ B] = F⁻¹[A] \ F⁻¹[B].

      Exercise 2.3.2. Show that, for any two functions F : B → C and G : A → B, F ◦ G is a function.

      Exercise 2.3.3. Show that, for any functions F and G, Dmn(F ◦ G) = G⁻¹[Dmn(F)] ⊆ Dmn(G).

      Exercise 2.3.4. Show that, for any two functions F and G, Rng(F ◦ G) = F[Rng(G)] ⊆ Rng(F).

      Exercise 2.3.5. Show that, for any function F : A → B, F is surjective if and only if, for all C and all G : B → C and H : B → C, G ◦ F = H ◦ F implies G = H.

      Exercise 2.3.6. For a function F : A → B, show that

      (1) F is surjective if and only if there exists G : B → A such that F ◦ G = IB;

      (2) F is injective if and only if there exists G : B → A such that G ◦ F = IA;

      (3) F is bijective if and only if there exists G : B → A such that F ◦ G = IB and G ◦ F = IA.

      Exercise 2.3.7. Let A, B, and C be sets.

      (a) Show that (A ∩ B)C = AC ∩ BC.

      (b) Show that AC ∪ BC ⊆ (A ∪ B)C.

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

      Exercise 2.3.8. Let A ⊆ B.

      (a) Show that AC ⊆ BC.

      (b) Define a map from CB onto CA.

      Exercise 2.3.9. Let An = {k/n : k ∈

} = {0, 1/n, −1/n, 2/n, . . . } for each n ∈

⁺. Determine the resulting sets ⋃_n∈I An and ⋂_n∈I An.

      Exercise 2.3.10. Show that, for any indexed families {Ai