Chapter 0

Introduction - Sets and Functions

ed
0.1 Sets

ct
te
Definition 0.1. A set is a collection of objects called elements or members of the set.
To denote a set, we make a complete list tx1 , x2 , ¨ ¨ ¨ , xN u or use the notation
ro
␣ ( ␣ ˇ (
x : P (x) or x ˇ P (x) ,
P
where the sentence P (x) describes the property that defines the set. A set A is said to be a
ht

subset of S if every member of A is also a member of S. We write x P A (or A contains x)

if x is a member of A, and write A Ď S (or S includes A) if A is a subset of S. The empty
ig

set, denoted H, is the set with no member.

r
py

Definition 0.2. Let S be a given set, and A Ď S, B Ď S. The set A Y B, called the union
of A and B, consists of members belonging to set A or set B. Let A1 , A2 , ¨ ¨ ¨ be sets. The
Co

8
set Ai = tx | x P Ai for some iu is the union of A1 , A2 , ¨ ¨ ¨ . The set A X B, called the
Ť
i=1
intersection of A and B, consists of members belonging to both set A and set B. Let
8
A1 , A2 , ¨ ¨ ¨ be sets. The set Ai = tx | x P Ai for all iu is the intersection of A1 , A2 , ¨ ¨ ¨ .
Ş
i=1

Remark 0.3. Let F be the collection of some subsets in S. Sometimes we also write the
union of sets in F as A; that is,
Ť
APF
ď
A = x P S ˇDA P F Q x P A
␣ ˇ (
APF

A = x P S ˇ @A P F Q x P A is the intersection of sets in F .

␣ ˇ (
Similarly,
Ş
APF

i
ii CHAPTER 0. Introduction - Sets and Functions

Example 0.4. Let A = t1, 2, 3, 4, 5u, B = t1, 3, 7u, S = t1, 2, 3, ¨ ¨ ¨ u, and F = tA, Bu.
Then E ” A Y B = t1, 2, 3, 4, 5, 7u, and
Ť Ş
E ” A X B = t1, 3u.
EPF EPF

Definition 0.5. Let S be a given set, and A Ď S, B Ď S. The complement of A relative

to B, denoted BzA, is the set consisting of members of B that are not members of A. When
the universal set S under consideration is fixed, the complement of A relative to S or simply
the complement of A, is denoted by AA , or SzA.

Theorem 0.6. (De Morgan’s Law)

8 8

ed
1. Bz Ai = (BzAi ) or Bz
Ť Ş Ť Ş
A= (BzA).
i=1 i=1 APF APF

ct
8 8
2. Bz (BzAi ) or Bz
Ş Ť Ş Ť
Ai = A= (BzA).
i=1 i=1 APF APF

te
Proof. By definition, ro
8
ď 8
ď
x P Bz Ai ô x P B but x R Ai ô x P B and x R Ai for all i
P
i=1 i=1
8
č
ô x P BzAi for all i ô x P
ht

(BzAi )
i=1
ig

The proof of the second identity is similar, and is left as an exercise. ˝

r

Definition 0.7. An ordered pair (a, b) is an object formed from two objects a and b,
py

where a is called the first coordinate and b the second coordinate. Two ordered pairs
are equal whenever their corresponding coordinates are the same. An ordered n-tuples
Co

(a1 , a2 , ¨ ¨ ¨ , an ) is an object formed from n objects a1 , a2 , ¨ ¨ ¨ , an , where for each j, aj is

called the j-th coordinate. Two n-tuples (a1 , a2 , ¨ ¨ ¨ , an ), (c1 , c2 , ¨ ¨ ¨ , cn ) are equal if aj = cj
for all j P t1, ¨ ¨ ¨ , nu.

Definition 0.8. Given sets A and B, the Cartesian product A ˆ B of A and B is the
␣ ˇ (
set of all ordered pairs (a, b) with a P A and b P B, A ˆ B = (a, b) ˇ a P A and b P B . The
Cartesian of three or more sets are defined similarly.

Example 0.9. Let A = t1, 3, 5u and B = t‹, ˛u. Then

␣ (
A ˆ B = (1, ‹), (3, ‹), (5, ‹), (1, ˛), (3, ˛), (5, ˛) .
§0.2 Functions iii

Example 0.10. Let A = [2, 7] and B = [1, 4]. The Cartesian product of A and B is the
square plotted below:
y

x
O A

Figure 1: The Cartesian product [2, 7] ˆ [1, 4]

ed
0.2 Functions

ct
Definition 0.11. Let S and T be given sets. A function f : S Ñ T consists of two sets

te
S and T together with a “rule” that assigns to each x P S a special element of T denoted
ro
by f (x). One writes x ÞÑ f (x) to denote that x is mapped to the element f (x). S is called
the domain (定義域）of f , and T is called the target or co-domain of f . The range
P
␣ ˇ (
(值域）of f or the image of f , is the subset of T defined by f (S) = f (x) ˇ x P S .
ht

f
ig

T
f (x)
r

x
py

S f (S)
Co

Definition 0.12. A function f : S Ñ T is called one-to-one（一對一）, injective or

an injection if x1 ‰ x2 ñ f (x1 ) ‰ f (x2 ) (which is equivalent to that f (x1 ) = f (x2 ) ñ
x1 = x2 ). A function f : S Ñ T is called onto（映成）, surjective or an surjection
if @ y P T, D x P S, Q f (x) = y (that is, f (S) = T ). A function f : S Ñ T is called an
bijection if it is one-to-one and onto.

Remark 0.13 (映成函數的反敘述). If f : S Ñ T is not onto, then D y P T , Q @ x P S,

f (x) ‰ y. 一般來說，若有一個的數學的敘述 @ statement A, D statement B Q statement C
成立，那麼它的相反敘述的寫法為: D statement A, Q @ statement B, statement C 不成立。
簡單的記法：1. @ Ø D 2. D P Q Q Ø Q @ P ∼ Q.
iv CHAPTER 0. Introduction - Sets and Functions

␣ ˇ (
Definition 0.14. For f : S Ñ T , A Ď S, we call f (A) = f (x) ˇ x P A the image of A
␣ ˇ (
under f . For B Ď T , we call f ´1 (B) = x P S ˇ f (x) P B the pre-image of B under f .

ed
ct
Example 0.15. f : R Ñ R, f (x) = x2 , B = [´1, 4] Ď T , f ´1 (B) = [´2, 2].

te
y ro
4
P
ht

x
´2 ´1 2
r ig

Figure 2: The preimage f ´1 ([´1, 4]) is [´2, 2] if f (x) = x2

py

Proposition 0.16. Let f : S Ñ T be a function, C1 ,C2 Ď T and D1 , D2 Ď S.

Co

(a) f ´1 (C1 Y C2 ) = f ´1 (C1 ) Y f ´1 (C2 ).

(b) f (D1 Y D2 ) = f (D1 ) Y f (D2 ).

(c) f ´1 (C1 X C2 ) = f ´1 (C1 ) X f ´1 (C2 ).

(d) f (D1 X D2 ) Ď f (D1 ) X f (D2 ).

(e) f ´1 (f (D1 )) Ě D1 (“=” if f is one-to-one).

(f) f (f ´1 (C1 )) Ď C1 (“=” if C1 Ď f (S)).

§0.3 Exercises v

Proof. We only prove (c) and (d), and the proof of the other statements are left as an
exercise.

(c) We first show that f ´1 (C1 X C2 ) Ď f ´1 (C1 ) X f ´1 (C2 ). Suppose that x P f ´1 (C1 X C2 ).
Then f (x) P C1 X C2 . Therefore, f (x) P C1 and f (x) P C2 , or equivalently, x P f ´1 (C1 )
and x P f ´1 (C2 ); thus x P f ´1 (C1 ) X f ´1 (C2 ).
Next, we show that f ´1 (C1 ) X f ´1 (C2 ) Ď f ´1 (C1 X C2 ). Suppose that x P f ´1 (C1 ) X
f ´1 (C2 ). Then x P f ´1 (C1 ) and x P f ´1 (C2 ) which suggests that f (x) P C1 and
f (x) P C2 ; thus f (x) P C1 X C2 or equivalently, x P f ´1 (C1 X C2 ).

ed
(d) Suppose that y P f (D1 X D2 ). Then D x P D1 X D2 such that y = f (x). As a
consequence, y P f (D1 ) and y P f (D2 ) which implies that y P f (D1 ) X f (D2 ).

ct
˝

te
Example 0.17. We note it might happen that f (D1 X D2 ) Ĺ f (D1 ) X f (D2 ). Take D1 =
[´1, 0] and D2 = [0, 1], and define f : S = R Ñ T = R to be f (x) = x2 . Then f (D1 ) =
ro
f ([´1, 0]) = [0, 1] and f (D2 ) = f ([0, 1]) = [0, 1]. However,
P
f (D1 X D2 ) = f (t0u) = t0u Ĺ [0, 1] = f (D1 ) X f (D2 ) .
ht

0.3 Exercises
ig

§0.1 Sets
r
py

Problem 0.1. Let A, B, C be given sets. Show that

Co

1. (A Y B) X C = (A X C) Y (B X C).

2. (A X B) Y C = (A Y C) X (B Y C).

§0.2 Functions

Problem 0.2. Let S and T be given sets, A Ď S, B Ď T , and f : S Ñ T . Show that

1. f (f ´1 (B)) Ď B, and f (f ´1 (B)) = B if B Ď f (S).

2. f ´1 (f (A)) Ě A, and f ´1 (f (A)) = A if f : S Ñ T is one-to-one.

Problem 0.3. Let A and B be two non-empty sets and f : A Ñ B. Show that
vi CHAPTER 0. Introduction - Sets and Functions

1. f ´1 (D1 YD2 ) = f ´1 (D1 )Yf ´1 (D2 ), f ´1 (D1 XD2 ) = f ´1 (D1 )Xf ´1 (D2 ), f ´1 (D1 zD2 ) =
f ´1 (D1 )zf ´1 (D2 ) for all D1 , D2 Ď B.

2. f (C1 Y C2 ) = f (C1 ) Y f (C2 ), f (C1 X C2 ) Ď f (C1 ) X f (C2 ) for all C1 , C2 Ď A.

Problem 0.4. Let A and B be two non-empty sets and f : A Ñ B. Show that the following
three statements are equivalent; that is, show that each one of the following statements
implies the other four.

1. f is one-to-one.

ed
2. For every y in B, the set f ´1 (tyu) contains at most one point.

ct
3. f ´1 (f (C)) = C for all C Ď A.

te
4. f (C1 X C2 ) = f (C1 ) X f (C2 ) for all subsets C1 and C2 of A.
ro
5. f (C2 zC1 ) = f (C2 ) ´ f (C1 ) for all C1 Ď C2 Ď A.
P
ht
r ig
py
Co