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.

Theorem 7.3.12   The set of all algebraic numbers is countable.

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.

Theorem 7.3.13 (Cantor's diagonal argument)   is uncountable.

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