** Next:** Bigger sets
** Up:** Countability
** Previous:** Combinations
** Contents**

#

Countable sets

**Definition 7.3.1**
A set

is countable if there exists a bijection

.

The countable sets can be equivalently thought of as those that can be listed
on a line.

**Example 7.3.2**
- (i)
- The set
is countable.
- (ii)
- The set
of all the even natural numbers is countable.

**Lemma 7.3.3**
Any subset

is countable.

*Proof*.
For: map the smallest element of

to

, the next smallest to

and so on.

**Lemma 7.3.4**
A set

is countable iff

an injection

.

*Proof*.
This is clear for finite

. Hence assume

is infinite. If

is an injection then

is an infinite subset of

.
Hence

a bijection

. Thus

is a bijection.

The following result is obvious:

**Corollary 7.3.5**
Let

and

be two sets. If

is countable and if it exists an injection

then

is countable.

**Proposition 7.3.6**
is countable.

*Proof*.
Consider

,

This is clearly a bijection.

**Proposition 7.3.7**
is countable for any natural number

.

*Proof*.
The map

(

is the

prime) is an injection by uniqueness of prime
factorisation.

**Lemma 7.3.8**
If

are countable sets with

, then so is

.

*Proof*.
Since

is countable there exists an injection

. Hence the function

defined by

is an injection.

**Proposition 7.3.9**
is countable.

*Proof*.
Define

by

where

and

.

**Theorem 7.3.10**
A countable union of countable sets is countable. That is, if

is a
countable indexing set and

is countable

then

is countable.

*Proof*.
Identify first

with the subset

.
Define

by

where

is the smallest index

with

, and

. This
is well-defined and injective (stop to think about it for a bit).

**Definition 7.3.11**
An

*algebraic number* is a root of a polynomial, whose coefficients are rational. If a number is not algebraic, it is called

*transcendental*.

For example, is an algebraic number as it is a root of the polynomial . The number and the number (basis of the natural logarithm)
are transcendental.

*Proof*.
Let

be the set of all polynomials of degree at most

with integral
coefficients. Then the map

is an injection from

to

.
Hence each

is countable. It follows that the set of all polynomials
with integral coefficients is countable. Each polynomial has finitely
many roots, so the set of algebraic numbers is countable.

*Proof*.
Assume

is countable, then the elements can be listed as

(in decimal notation). Now define the real

by

if

and

if

. This is a real number, but it differs from

in the

decimal place. So the list is incomplete. This shows that the
set of all the reals is uncountable.

Exercise: use a similiar proof to show that
is uncountable.

**Theorem 7.3.14**
The set of all transcendental numbers is uncountable. (And therefore
at least non-empty!)

*Proof*.
Let

be the set of algebraic numbers and

the set of transcendentals.
Then

, so if

was countable then so would

be. Thus

is uncountable.

** Next:** Bigger sets
** Up:** Countability
** Previous:** Combinations
** Contents**
root
2002-06-10