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

n≥1

1

n

Z

=

S

n≥1

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

k−1

x

k−1

+

···

+

a

0

7→

(

a

k

, a

k−1

, ··· , 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

k≥0

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.