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 - Douglas Cenzer


Скачать книгу
interesting results about the composition of functions.

      Proposition 2.3.5. Let F : AB be a function.

      (1) F : AB is one-to-one if and only if, for all C and all G : CA and H : CA, FG = FH implies G = H.

      (2) F : AB is onto if and only if, for all C and all G : BC and H : BC, GF = HF implies G = H.

      Proof. (1) Let F : AB. Suppose that F is one-to-one and let G : CA and H : CA. Suppose also that FG = FH. Then, for any xC, F(G(x)) = F(H(x)). Since F is one-to-one, this implies that G(x) = H(x). Thus G = H.

      Next suppose that F : AB is not one-to-one and choose a1a2A and bB such that F(a1) = F(a2) = b. Let C = {c} and define G(c) = a1 and H(c) = a2, so that FG(c) = b = FH(c) and hence FG = FH. However, GH.

      Part (2) is left as an exercise.

      Next we consider indexed families of sets. This will be an important topic later in connection with the Axiom of Choice. An indexed family {Ai : iI} of sets may be viewed as a function from I to ⋃i∈I Ai.

      Definition 2.3.6. Suppose

= {Ai : iI} is an indexed family of sets.

      

      (1) The union of this family is ⋃i∈I Ai := {u : (∃iI) uAi}.

      (2) The intersection of this family is ⋂i∈I Ai := {u : (∀iI) uAi}.

      (3) The Cartesian product of this family is ∏i∈I Ai = {f : I → ⋃i∈I Ai : (∀i)[f(i) ∈ Ai]}.

      (4) For each iI, the ith projection function, pi : ∏i∈I AiAi, is defined by pi(f) = f(i) for all f ∈ ∏i∈I Ai.

       Example 2.3.7.

      (1) Let I be the set of prime numbers and let Ap = {n

: p | n}. Then ⋃p∈I Ap = {n
: n ≠ 1} and ⋂p∈I Ap = {0}.

      (2) Let I =

+ = {1, 2, . . . } and let An = (−1/n, 1/n). Then ⋃n∈I An = (−1, 1) and ⋂n∈I An = {0}.

      (3) Let I =

and let Ai =
. Then ∏i∈ Ai is the set of infinite sequences of real numbers, which plays a very important role in the study of calculus.

      (4) The Cantor space is defined to be ∏i∈{0, 1}, the set of infinite sequences of 0’s and 1’s. This is one of the fundamental spaces of topology.

      Now we can examine unions and intersections of infinitely many sets. The following is a generalization of the associative laws.

      Proposition 2.3.8. Let (Ai)i∈I and (Bi)i∈I be indexed families of sets.

      (1) ⋃i∈I(AiBi) = (⋃i∈I Ai) ∪ (⋃i∈I Bi).

      (2) ⋂i∈I(AiBi) = (⋂i∈I Ai) ∩ (⋂i∈I Bi).

      Proof. (1) (⊆): Suppose that x ∈ ⋃i∈I(AiBi). Then (∃i) xAiBi. Choose some k such that xAkBk. Now either xAk or xBk. Without loss of generality suppose that xAk. Then (∃i) xAi, and therefore x ∈ ⋃i Ai. It follows that x ∈ (⋃i∈I Ai) ∪ (⋃i∈I Bi).

      Note: When we say here “without loss of generality”, we mean that a similar argument will work in the other case that xBk.

      (⊇): Suppose now that 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 Bi). Then (∃i) xBi. Choose some k such that xBk. Then xAkBk. Hence (∃i) xAiBi. It follows that x ∈ ⋃i∈I(AiBi).

      Part (2) is left to the exercises.

      Here are some versions of the distributive law.

      Proposition 2.3.9. Let (Ai)i∈I and (Bi)i∈I be indexed families of sets.

      (1) A ∩ ⋃i∈I Bi = ⋃i∈I(ABi).

      (2) A ∪ ⋂i∈I Bi = ⋂i∈I(ABi).

      Proof. (1) (⊆): Let xA ∩ ⋃i∈I Bi. Then xA and x ∈ ⋃i∈I Bi. Now (∃i) xBi, so we can choose j such that xBj. It follows that xAxBj, so that xABj. Thus (∃i) xABi. Hence x ∈ ⋃i∈I ABi.

      (⊇): Let x ∈ ⋃i∈I ABi. Then (∃i) x ∈ ⋃i∈I ABi, so we can choose j such that xABj. Then xAxBj. Now (∃i) xBi, so that x ∈ ⋃i∈I Bi. Thus xAx ∈ ⋃i∈I Bi, so that xA ∩ ⋃i∈I Bi.

      Part (2) is left to the exercises.

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