7Countability

IA Numbers and Sets



7 Countability
After messing with numbers, we finally get back to sets. Here we are concerned
about the sizes of sets. We can count how big a set is by constructing bijections.
Two sets have the same number of things if there is a bijection between them.
In particular, a set has
n
things if we can bijection it with [
n
] =
{
1
,
2
,
3
, ··· , n}
.
First first prove a few preliminary properties about bijecting with [
n
] that
should be obviously true.
Lemma. If f : [n] [n] is injective, then f is bijective.
Proof.
Perform induction on
n
: It is true for
n
= 1. Suppose
n >
1. Let
j = f (n). Define g : [n] [n] by
g(j) = n, g(n) = j, g(i) = i otherwise.
Then
g
is a bijection. So the map
g f
is injective. It fixes
n
, i.e.
g f
(
n
) =
n
.
So the map h : [n 1] [n 1] by h(i) = g f (i) is well-defined and injective.
So h is surjective. So h is bijective. So g f is bijective. So is f.
Corollary.
If
A
is a set and
f
:
A
[
n
] and
g
:
A
[
m
] are both bijections,
then m = n.
Proof.
wlog assume
m n
. Let
h
: [
n
]
[
m
] with
h
(
i
) =
i
, which is injective.
Then the map
h f g
1
: [
m
]
[
m
] is injective. Then by the lemma this is
surjective. So h must be surjective. So n m. Hence n = m.
This shows that we cannot biject a set to two different numbers, or a set
cannot have two different sizes!
Definition
(Finite set and cardinality of set)
.
The set
A
is finite if there exists
a bijection
A
[
n
] for some
n N
0
. The cardinality or size of
A
, written as
|A|, is n. By the above corollary, this is well-defined.
Lemma. Let S N. Then either S is finite or there is a bijection g : N S.
Proof.
If
S 6
=
, by the well-ordering principle, there is a least element
s
1
S
.
If
S \ {s
1
} 6
=
, it has a least element
s
2
. If
S \ {s
1
, s
2
}
is not empty, there is a
least element
s
3
. If at some point the process stops, then
S
=
{s
1
, s
2
, ··· , s
n
}
,
which is finite. Otherwise, if it goes on forever, the map
g
:
N S
given by
g
(
i
) =
s
i
is well-defined and is an injection. It is also a surjection because if
k S
, then
k
is a natural number and there are at most
k
elements of
S
less
than k. So k will be mapped to s
i
for some i k.
Definition
(Countable set)
.
A set
A
is countable if
A
is finite or there is a
bijection between A and N. A set A is uncountable if A is not countable.
This is one possible definition of countability, but there are some (often)
more helpful definitions.
Theorem. The following are equivalent:
(i) A is countable
(ii) There is an injection from A N
(iii) A = or there is a surjection from N A
Proof.
(i)
(iii): If
A
is finite, there is a bijection
f
:
A S
for some
S N
.
For all
x N
, if
x S
, then map
x 7→ f
1
(
x
). Otherwise, map
x
to any element
of A. This is a surjection since a A, we have f(a) 7→ a.
(iii)
(ii): If
A 6
=
and
f
:
N A
is a surjection. Define a map
g
:
A N
by g(a) = min f
1
({a}), which exists by well-ordering. So g is an injection.
(ii)
(i): If there is an injection
f
:
A N
, then
f
gives a bijection between
A
and
S
=
f
(
A
)
N
. If
S
is finite, so is
A
. If
S
is infinite, there is a bijection
g
between S and N. So there is a bijection g f between A and N.
Often, the injection definition is the most helpful.
Proposition. The integers Z are countable.
Proof. The map f : Z N given by
f(n) =
(
2n n > 0
2(n) + 1 n 0
is a bijection.
Proposition. N × N is countable.
Proof.
We can map (
a, b
)
7→
2
a
3
b
injectively by the fundamental theorem of
arithmetic. So N × N is countable.
We can also have a bijection by counting diagonally: (
a, b
)
7→
a+b
2
a
+ 1:
1
1
2
2
3
3
4
4
1
3
6
10
2
5
9
14
4
8
13
19
7
12
18
25
Since
Z
is countable, we have an injection
Z N
, so there is an injection
from
Z ×N N × N N
. So
Z ×N
is countable. However, the rationals are
the equivalence classes of Z × N. So Q is countable.
Proposition.
If
A B
is injective and
B
is countable, then
A
is countable
(since we can inject B N).
Proposition. Z
k
is countable for all k N
Proof.
Proof by induction:
Z
is countable. If
Z
k
is countable,
Z
k+1
=
Z ×Z
k
.
Since we can map
Z
k
N
injectively by the induction hypothesis, we can map
injectively Z
k+1
Z × N, and we can map that to N injectively.
Theorem. A countable union of countable sets is countable.
Proof.
Let
I
be a countable index set, and for each
α I
, let
A
α
be a countable
set. We need to show that
S
αI
A
α
is countable. It is enough to construct an
injection
h
:
S
αI
A
α
N × N
because
N × N
is countable. We know that
I
is
countable. So there exists an injection
f
:
I N
. For each
α I
, there exists
an injection g
α
: A
α
N.
For
a
S
A
α
, pick
m
=
min{j N
:
a A
α
and f
(
α
) =
j}
, and let
α
be
the corresponding index such that
f
(
α
) =
m
. We then set
h
(
a
) = (
m, g
α
(
a
)),
and this is an injection.
Proposition. Q is countable.
Proof. It can be proved in two ways:
(i) Q
=
S
n1
1
n
Z
=
S
n1
m
n
: m Z
, which is a countable union of count-
able sets.
(ii) Q
can be mapped injectively to
Z × N
by
a/b 7→
(
a, b
), where
b >
0 and
(a, b) = 1.
Theorem. The set of algebraic numbers is countable.
Proof.
Let
P
k
be the set of polynomials of degree
k
with integer coefficients.
Then
a
k
x
k
+
a
k1
x
k1
+
···
+
a
0
7→
(
a
k
, a
k1
, ··· , a
0
) is an injection
P
k
Z
k+1
.
Since Z
k+1
is countable, so is P
k
.
Let
P
be the set of all polynomials with integer coefficients. Then clearly
P =
S
P
k
. This is a countable union of countable sets. So P is countable.
For each polynomial
p P
, let
R
p
be the set of its roots. Then
R
p
is
finite and thus countable. Hence
S
p∈P
R
p
, the set of all algebraic numbers, is
countable.
Theorem. The set of real numbers R is uncountable.
Proof.
(Cantor’s diagonal argument) Assume
R
is countable. Then we can list
the reals as
r
1
, r
2
, r
3
···
so that every real number is in the list. Write each
r
n
uniquely in decimal form (i.e. without infinite trailing ’9’s). List them out
vertically:
r
1
= n
1
. d
11
d
12
d
13
d
14
···
r
2
= n
2
. d
21
d
22
d
23
d
24
···
r
3
= n
3
. d
31
d
32
d
33
d
34
···
r
4
= n
4
. d
41
d
42
d
43
d
44
···
Define
r
= 0
. d
1
d
2
d
3
d
4
···
by
d
n
=
(
0 d
nn
6= 0
1 d
nn
= 0
. Then by construction, this
differs from the
n
th number in the list by the
n
th digit, and is so different
from every number in the list. Then
r
is a real number but not in the list.
Contradiction.
Corollary. There are uncountable many transcendental numbers.
Proof.
If not, then the reals, being the union of the transcendentals and algebraic
numbers, must be countable. But the reals is uncountable.
This is an easy but non-constructive proof that transcendental numbers exists.
“If we can’t find one, find lots!” (it is debatable whether this proof is constructive
or not. Some argue that we can use this to construct a transcendental number
by listing all the algebraic numbers and perform the diagonal argument to
obtain a number not in the list, i.e. a transcendental number. So this is in fact
constructive)
Example.
Let
F
k
=
{Y N
:
|Y |
=
k}
, i.e. the set of all subsets of
N
of size
k
.
We can inject
F
k
Z
k
in the obvious way, e.g.
{
1
,
3
,
7
} 7→
(1
,
3
,
7) etc. So it is
countable. So F =
S
k0
F
k
, the set of all finite subsets of N is countable.
Example.
Recall
P
(
X
) =
{Y
:
Y X}
. Now suppose
P
(
N
) is countable. Let
S
1
, S
2
, S
3
, ···
be the list of all subsets of
N
. Let
S
=
{n
:
n 6∈ S
n
}
. But then
S
is not in the list. Contradiction. So P(N) is uncountable.
Example.
Let Σ be the set of all functions
N N
(i.e. the set of all integer
sequences). If Σ were countable, we could list it as
f
1
, f
2
, f
3
···
. But then consider
f
given by
f
(
n
) =
(
1 f
n
(n) 6= 1
2 f
n
(n) = 1
. Again
f
is not in the list. Contradiction. So
Σ is uncountable.
Alternatively, there is a bijection between
P
(
N
) and the set of 0, 1 sequences
by
S 7→
the indicator function. So we can inject
P
(
N
)
Σ by
S 7→
indicator
function +1. So Σ cannot be countable (since P(N) is uncountable).
Or, we can let Σ
Σ be the set of bijections from
N N
. Let Σ
∗∗
Σ
be the bijections of the special form: for every n,
either
(
f(2n 1) = 2n 1
f(2n) = 2n
, or
(
f(2n 1) = 2n
f(2n) = 2n 1
,
i.e. for every odd-even pair, we either flip them or keep them the same.
But there is a bijection between Σ
∗∗
and 0
,
1 sequences: if the
n
th term in
the sequence = 0, don’t flip the
n
th pair in the function, vice versa. Hence Σ
∗∗
is uncountable.
Theorem. Let A be a set. Then there is no surjection from A P(A).
Proof.
Suppose
f
:
A P
(
A
) is surjective. Let
S
=
{a A
:
a 6∈ f
(
a
)
}
. Since
f
is surjective, there must exist
s A
such that
f
(
s
) =
S
. If
s S
, then
s 6∈ S
by the definition of
S
. Conversely, if
s 6∈ S
, then
s S
. Contradiction. So
f
cannot exist.
This shows that there are infinitely many different possible “infinite sizes” of
sets.
We conclude by two theorems that we will not prove.
Theorem
(Cantor-Schr¨oder-Bernstein theorem)
.
Suppose there are injections
A B and B A. Then there’s a bijection A B.
Continuum hypothesis.
There is no set whose size lies between
N
and
R
.
In 1963, Paul Cohen proved that it is impossible to prove this or disprove this
statement (in ZFC). The proof can be found in the Part III Topics in Set Theory
course.