[ Pobierz całość w formacie PDF ]
For a finite set X, the unique n " N0 for which there is a bijection n -’! X is called the
cardinality of X, denoted |X|. If X is infinite then we sometimes write |X| = ", while if X is
finite we write |X|
We reformulate Theorem 4.3 without proof to give some important facts about cardinalities
of finite sets.
Theorem 4.5 (Pigeonhole Principle). Let X, Y be two finite sets.
a) If there is an injection X -’! Y then |X| |Y |.
b) If there is a surjection X -’! Y then |X| |Y |.
c) If there is a bijection X -’! Y then |X| = |Y |.
The name Pigeonhole Principle comes from the use of this when distributing m letters into
n pigeonholes. If each pigeonhole is to receive at most one letter, m n; if each pigeonhole is
to receive at least one letter, m n.
Let X be a set and P †" X. Then P is a proper subset of X if P = X, i.e., there is an
element x " X with x " P .
/
Notice that if X is a finite set and S a subset, then the inclusion function inc: S -’! X
given by inc(j) = j is an injection. So we must have |S| |X|. If P is a proper subset then
we have |P |
P -’! X. These conditions actually characterise finite sets. In the next section we investigate
how to recognise infinite sets.
3. COUNTABLE SETS 55
2. Infinite sets
Theorem 4.6. Let X be a set.
a) X is infinite if and only if there is an injection X -’! P where P †" X is a proper
subset.
b) X is infinite if and only if there is a surjection Q -’! X where Q †" X is a proper
subset.
c) X is infinite if and only if there is an injection N0 -’! X.
d) X is infinite if and only if there is a subset T †" X and an injection N0 -’! T .
Example 4.7. The set of all natural numbers N0 = {0, 1, 2, . . .} is infinite.
Solution. Let us take the subset P = {1, 2, 3, . . .} and define a function f : N0 -’! P by
f(n) = n + 1.
· · · n · · ·
0 1 2
· · · · · ·
1 2 3 n + 1
If f(m) = f(n) then m + 1 = n + 1 so m = n, hence f is injective. If k " P then k 1 and
so (k - 1) 0, implying (k - 1) " N0 whence f(k - 1) = k. Thus f is also surjective, hence
bijective.
Example 4.8. Show that there are bijections between the set of all natural numbers N0 and
each of the sets
S1 = {2n : n " N0}, S2 = {2n + 1 : n " N0}, S3 = {3n : n " N0}.
In each case find a bijection and its inverse.
Solution. For S1, let f1 : N0 -’! S1 be given by f1(n) = 2n. Then f1 is a bijection: it is
injective since 2n1 = 2n2 implies n1 = n2, and surjective since given 2m " N0, f1(m) = 2m.
-1
The inverse function is given by f1 (k) = k/2.
For S2, let f2 : N0 -’! S2 be given by f2(n) = 2n + 1. Then f2 is a bijection: it is injective
(2n1 + 1 = 2n2 + 1 implies n1 = n2) and surjective since given 2m + 1 " N0, f2(m) = 2m + 1.
-1
The inverse function is given by f2 (k) = (k - 1)/2.
For S3, let f3 : N0 -’! S3 be given by f3(n) = 3n. Then f3 is a bijection: it is injective
since 3n1 = 3n2 implies n1 = n2, and surjective since given 3m " N0, f3(m) = 3m. The inverse
-1
function is given by f3 (k) = k/3.
Notice that each of the sets S1, S2, S3 is a proper subset of N0, yet each is in 1-1 correspon-
dence with N0 itself.
3. Countable sets
Definition 4.9. A set X is countable if there is a bijection S -’! X where either S = n for
some n " N0 or S = N0. A countable infinite set is said to be countably infinite or of cardinality
5!0. An infinite set which is not countable is said to be uncountable.
Example 4.10. The following sets are countably infinite.
a) Any infinite subset S †" N0.
b) X *" Y where X, Y are countably infinite.
c) X *" Y where X is countably infinite and Y is finite.
d) The set of all ordered pairs of natural numbers
N0 × N0 = {(m, n) : m, n " N0}.
56 4. FINITE AND INFINITE SETS, CARDINALITY AND COUNTABILITY
e) The set of all positive rational numbers
a
Q+ = : a, b " N0, a, b > 0 .
b
Solution.
a) Since S is infinite it cannot be empty. Let S0 = S. By WOP, S0 has a least element s0 say.
Now consider the set S1 = S - {s0}; this is not empty since otherwise S would be finite. Again
WOP ensures that there is a least element s1 " S1. Continuing, we can construct a sequence
s0, s1, . . . , sn, . . . of elements in S with sn the least element of Sn = S - {s0, s1, . . . , sn-1} which
is never empty. Notice in particular that
s0
from which it easily follows that sn n. If s " S, then for some m " N0 must satisfy m s, so
by construction of the sn we must have s = sm0 for some m0. Hence
S = {sn : n " N0}.
Now define a function f : N0 -’! S by f(n) = n; this is easily seen to be a bijection.
b) The simplest case is where X )" Y = ". Then given bijections f : N0 -’! X and g : N0 -’! Y
we construct a function h: N0 -’! X *" Y by
ñø
ôøf n if n is even,
ôø
òø
2
h(n) =
ôøg n - 1 n is odd.
ôø
if
óø
2
Then h is a bijection.
If Z = X )" Y and Y - Z are both countably infinite, let f : N0 -’! X and g : N0 -’! Y - Z
be bijections. Then we define h: N0 -’! X *" Y by
ñø
ôøf n if n is even,
ôø
òø
2
h(n) =
ôøg n - 1 n is odd.
ôø
if
óø
2
This is again a bijection.
The case where one of X - X )" Y and Y - X )" Y is finite is easy to deal with by the method
used for (c).
c) Since Y is finite so is Y - X )" Y †" Y . Let f : N0 -’! X and g : m -’! Y - X )" Y be
bijections. Define h: N0 -’! X *" Y by
ñø
òøg(n - 1) if 1 n m,
h(n) =
óøf(n - m - 1) if m
Then h is a bijection.
d) Plot each pair (a, b) as the point in the xy-plane with coordinates (a, b); such points are all
those with natural number coordinates. Starting at (0, 0) we can now trace out a path passing
through all of these points and we can arrange to do this without ever recrossing such a point.
4. POWER SETS AND THEIR CARDINALITY 57
.
· · · · · · · · · · · ·
.
.
(0, 3) (1, 3) · · · · · · · · ·
(0, 2) (1, 2) (2, 2) · · · · · ·
(0, 1) (1, 1) (2, 1) (3, 1) · · ·
(0, 0) (1, 0) (2, 0) (3, 0) · · ·
This gives a sequence {(rn, sn)}0 n of elements of N0 × N0 which contains every natural number
exactly once. The function
f : N0 -’! N0 × N0; f(n) = (rn, sn),
is a bijection.
e) This is demonstrated in a similar way to (d) but is slightly more involved. For each a/b " Q+,
we can assume that a, b are coprime (i.e., have no common factors) and plot it as the point in the
xy-plane with coordinates (a, b). Starting at (1, 1) we can now trace out a path passing through
all of these points with coprime positive natural number coordinates and can even arrange to
do this without ever recrossing such a point.
.
· · · · · · · · · · · · · · ·
.
.
(1, 4) (2, 4) · · · · · · · · · · · ·
(1, 3) (2, 3) (3, 3) · · · · · · · · ·
(1, 2) (2, 2) (3, 2) (4, 2) · · · · · ·
(1, 1) (2, 1) (3, 1) (4, 1) (5, 1) · · ·
This gives us a sequence {rn}0 n of elements of Q+ which contains every element exactly once.
The function
f : N0 -’! Q+; f(n) = rn,
is a bijection.
4. Power sets and their cardinality
For two sets X and Y , let
X
Y = {f : f : X -’! Y is a function}.
58 4. FINITE AND INFINITE SETS, CARDINALITY AND COUNTABILITY
X
Example 4.11. Let X and Y be finite sets. Then Y is finite and has cardinality
X
|Y | = |Y ||X|.
Solution. Suppose that the distinct elements of X are x1, . . . , xm where m = |X| and
those of Y are y1, . . . , yn where n = |Y |. A function f : X -’! Y is determined by specifying
the values of the m elements f(x1), . . . , f(xm) of Y . Each f(xk) can be chosen in n ways so the
X
total number of choices is nm. Hence |Y | = nm.
A particular case of this occurs when Y has two elements, e.g., Y = {0, 1}. The set {0, 1}X
is called the power set of X, and has 2|X| elements and indeed it is often denoted 2|X|. It has
another important interpretation.
For any set X, we can consider the set of all its subsets
P(X) = {U : U †" X is a subset}.
Before stating and proving our next result we introduce the characteristic or indicator function
of a subset U †" X,
1 if x " U,
ÇU : X -’! {0, 1}; ÇU (x) =
0 if x " U.
/
Theorem 4.12. For a set X, the function
˜: P(X) -’! {0, 1}X; ˜(U) = ÇU ,
is a bijection.
Proof. The indicator function of a subset U †" X is clearly determined by U, so ˜ is well
[ Pobierz całość w formacie PDF ]