Countable Sets, Analysis I, Fall 2003

This document gives basic definitions, theorems and examples dealing with countable sets. We shall go over some of it in class, and some of the problems are left as exercises.

Let ${\bf N}=\{1,2,3,\dots\}$ be the set of all natural numbers.

Axioms

• The Well Ordering Principle Every non-empty subset of ${\bf N}$ has a least element.
• Mathematical Induction Suppose P(1),P(2),... is a sequence of statements. If P(1) is true and for all $k \in {\bf N}$ we have ``P(k) implies P(k+1)'' is true, then P(n) is true for all n.

Definitions

• Definition 1 A set X is countably infinite if there exists a 1-1 onto function $f:{\bf N}\to X.$ Equivalently, we could say that a set X is countably infinite if there exists a 1-1 onto function $g:X \to N.$
• Definition 2 A set X is countable if it is countably infinite or finite.
• Definition 3 A set X is uncountable if it is not countable.

Theorems

• Theorem 1 Every infinite subset of ${\bf N}$ is countably infinite.
• Theorem 2 If I is a non-empty countable index set and for each $i \in I$ the set X_i is countable then $\bigcup_{i\in I} X_i$ is countable. This is often phrased as saying the countable union of countable sets is countable.
• Theorem 3 The set of all infinite sequences of elements of the set $\{-1,1\}$ is uncountable.
• Theorem 4 Let Y be the set of all subsets of a countably infinite set X. Then Y is uncountable.

Examples

• Example 1 The empty set is finite, hence countable.
• Example 2 The set of all integers ${\bf Z}$ is countably infinite.
• Example 3 If X and Y are countable sets the Cartesian product ${\bf X} \times {\bf Y}$ is countable.
• Example 4 The rational numbers are countably infinite.
• Example 5 The set of real numbers is uncountable.

Exercises: Use the previous Theorems, Definitions and preceding Exercises to prove these.

• Exercise 1 If there exists a function $f:{\bf N}\rightarrow X$ that is onto, then X is countable .
• Exercise 2 If X is countable and $f:X \to Y$ is onto then Y countable.
• Exercise 3 Any subset of a countable set is countable.
• Exercise 4 If A is uncountable and $A \subset X$ then X is uncountable.
• Exercise 5 If X is uncountable and $f:X \to Y$ is a one-to-one function then Y is uncountable.