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

interesting results about the composition of functions.

Proposition 2.3.5. Let F : A → B be a function.

(1) F : A → B is one-to-one if and only if, for all C and all G : C → A and H : C → A, F ◦ G = F ◦ H implies G = H.

(2) F : A → B is onto if and only if, for all C and all G : B → C and H : B → C, G ◦ F = H ◦ F implies G = H.

Proof. (1) Let F : A → B. Suppose that F is one-to-one and let G : C → A and H : C → A. Suppose also that F ◦G = F ◦H. Then, for any x ∈ C, 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 : A → B is not one-to-one and choose a₁ ≠ a₂ ∈ A and b ∈ B such that F(a₁) = F(a₂) = b. Let C = {c} and define G(c) = a₁ and H(c) = a₂, so that F ◦G(c) = b = F ◦ H(c) and hence F ◦ G = F ◦ H. However, G ≠ H.

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 : i ∈ I} of sets may be viewed as a function from I to ⋃_i∈I Ai.

Definition 2.3.6. Suppose

= {Ai : i ∈ I} is an indexed family of sets.

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

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

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

(4) For each i ∈ I, the ith projection function, pi : ∏_i∈I Ai → Ai, 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(Ai ∪ Bi) = (⋃_i∈I Ai) ∪ (⋃_i∈I Bi).

(2) ⋂_i∈I(Ai ∩ Bi) = (⋂_i∈I Ai) ∩ (⋂_i∈I Bi).

Proof. (1) (⊆): Suppose that x ∈ ⋃_i∈I(Ai ∪Bi). Then (∃i) x ∈ Ai ∪ Bi. Choose some k such that x ∈ Ak ∪ Bk. Now either x ∈ Ak or x ∈ Bk. Without loss of generality suppose that x ∈ Ak. Then (∃i) x ∈ Ai, 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 x ∈ Bk.

(⊇): 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) x ∈ Bi. Choose some k such that x ∈ Bk. Then x ∈ Ak ∪ Bk. Hence (∃i) x ∈ Ai ∪ Bi. It follows that x ∈ ⋃_i∈I(Ai ∪ Bi).

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(A ∩ Bi).

(2) A ∪ ⋂_i∈I Bi = ⋂_i∈I(A ∪ Bi).

Proof. (1) (⊆): Let x ∈ A ∩ ⋃_i∈I Bi. Then x ∈ A and x ∈ ⋃_i∈I Bi. Now (∃i) x ∈ Bi, so we can choose j such that x ∈ Bj. It follows that x ∈ A ∧ x ∈ Bj, so that x ∈ A ∩ Bj. Thus (∃i) x ∈ A ∩ Bi. Hence x ∈ ⋃_i∈I A ∩ Bi.

(⊇): Let x ∈ ⋃_i∈I A ∩ Bi. Then (∃i) x ∈ ⋃_i∈I A ∩ Bi, so we can choose j such that x ∈ A ∩ Bj. Then x ∈ A ∧ x ∈ Bj. Now (∃i) x ∈ Bi, so that x ∈ ⋃_i∈I Bi. Thus x ∈ A ∧ x ∈ ⋃_i∈I Bi, so that x ∈ A ∩ ⋃_i∈I Bi.

Part (2) is left to the exercises.

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