Читать книгу Set Theory And Foundations Of Mathematics: An Introduction To Mathematical Logic - Volume I: Set Theory - Douglas Cenzer - Страница 12

Functions are of fundamental importance in mathematics. The integers come equipped with binary addition and multiplication functions. In algebra and trigonometry, we learn about the exponential function and the sine, cosine, and tangent functions on real numbers. Just as relations may be viewed as sets, functions may be viewed as relations and hence also as sets.

Definition 2.3.1. A relation F on A × B is a function if, for every x ∈ Dmn(F), there is a unique y ∈ Rng(F) such that xFy. We write y = F(x) for xFy. If Dmn(F) = A and Rng(F) ⊆ B, we say that F maps A into B, written F : A → B. F is one-toone, or injective, if F⁻¹ is also function. F maps A onto B, or is surjective, if Rng(F) = B. F is bijective, or is a set isomorphism from A to B, if F is injective and surjective.

Definition 2.3.2. For any sets A and B, BA is the set of functions mapping A into B.

A function F is said to be binary, or in general n-ary, if Dmn(F) ⊆ A×A (in general An) for some set A. Most commonly studied functions are either 1-ary (unary) or binary.

In the calculus, we studied how to determine whether functions were one-to-one and how to find their domain and range. For example, the function f(x) = x³ is both injective and surjective. The exponential function f(x) = ex is injective but not surjective. The function f(x) = x³ − x is surjective, but it is not injective, since f(0) = f(1) = 0.

In any group G, the function mapping x to its inverse x⁻¹ is a set isomorphism.

Equality of functions may be characterized as follows.

Proposition 2.3.3. Let F and G be two functions mapping set A to set B. Then F = G if and only if F(x) = G(x) for all x ∈ A.

Proof. Suppose first that F = G and let x ∈ A. Since F and G are functions, there are unique elements b and c of B such that F(x) = a and G(x) = c. Then (x, a) ∈ F and (x, c) ∈ G. Since F = G, it follows that both (x, a) and (x, c) are in F. Since F is a function, it follows that b = c, so that F(x) = G(x).

Suppose next that F(x) = G(x) for all x ∈ A. Then, for any a ∈ A and b ∈ B, we have (a, b) ∈ F if and only if F(a) = b, if and only if G(a) = b, if and only if (a, b) ∈ G. Thus F = G.

All the results about relations also apply to functions, but there are some additional nice properties of functions. Note that, for a function F : A → B and C ⊆ B, the inverse image of C under F, F⁻¹[C], is defined by taking the inverse of F as a relation, that is,

Proposition 2.3.4. For any function F : C → D and any subsets A, B of D,

(1) F⁻¹[A ∩ B] = F⁻¹[A] ∩ F⁻¹[B];

(2) F⁻¹[A \ B] = F⁻¹[A] \ F⁻¹[B].

Proof. Let x ∈ C. Then x ∈ F⁻¹[A ∩ B] if and only if F(x) ∈ A ∩ B, if and only if F(x) ∈ A ∧ F(x) ∈ B, if and only if x∈F⁻¹[A] ∧ x ∈ F⁻¹[B], if and only if x ∈ F⁻¹[A] ∩ F⁻¹[B].

Part (2) is left to the reader.

It is not hard to see that F ◦ G is a function if F and G are functions (see the exercises). Here are some 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 = for all i ∈ . 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.

Proposition 2.3.10. 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 ∪ ⋂_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 : i ∈ I} and {Bi : i ∈ I}, ⋂_i∈I(Ai ∩ Bi) = (⋂_i∈I Ai ∩ ⋂_i∈I Bi).

Exercise 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.