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

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

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−1[A \ B] = F−1[A] \ F−1[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−1[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

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