Section 7: Countable and Uncountable Sets

An infinite set $A$ is the one which is not finite. It is countably infinite if there is a bijective correspondence of $A$ with $\mathbb{Z}_{+}$ .

A set $A$ is countable if it is finite or countably infinite. Otherwise, the set is uncountable.

Countable sets and the Principle of Recursive Definition

Let $A$ be nonempty. $A$ is countable iff there is a surjective function $f:\mathbb{Z}_{+}\rightarrow A$ iff there is an injective function $g:A\rightarrow\mathbb{Z}_{+}$ .

The proof uses the following\begin_inset Separator latexpar\end_inset
An infinite subset $A$ of $\mathbb{Z}_{+}$ is countably infinite.

which is proved by constructing

$\begin{eqnarray*} h(1)=\inf A & \mbox{ and } & h(n+1)=\inf\{A-h(\{1,\ldots,n\})\}. \end{eqnarray*}$

There is a point in the preceding proof where we stretched the principles of logic a bit. It occurred at the point where we said that "using the induction principle" we had defined the function h for all positive integers n... But there is a problem here... To use the principle to prove a theorem "by induction", one begins the proof with the statement "Let A be the set of all positive integers n for which the theorem is true"... In the preceding theorem, however, we were not really proving a theorem by induction, but defining something by induction. How then should we start the proof?.. the symbol h has no meaning at the outset of the proof... So something more is needed. What is needed is another principle, which we call

The Principle of Recursive Definition: if a formula defines uniquely $h(1)$ , and for $i>1$ , $h(i)$ in terms of the values $h(1),...,h(i-1)$ , then it defines a unique function $h:\mathbb{Z}_{+}\rightarrow A$ . See Section 8.

A countable union of countable sets is countable.
A finite product of countable sets is countable.
A countable product of countable sets may be uncountable.\begin_inset Separator latexpar\end_inset
- $\{0,1\}^{\omega}$ is uncountable.
The set of all functions from a countable set to a countable set may be uncountable.\begin_inset Separator latexpar\end_inset
- The set of all functions from a countably infinite set to a countable set that are eventually constant is countable.

Cardinality

Two sets $A$ and $B$ have the same cardinality if there is a bijection of $A$ with $B$ .

(Schroeder-Bernstein). If there are injections $f:A\rightarrow C$ and $g:C\rightarrow A$ , then $A$ and $C$ have the same cardinality.

For any set $A$ , there is no injection $f:\mathcal{P}(A)\rightarrow A$ , and there is no surjection $g:A\rightarrow\mathcal{P}(A)$ .

The set of all finite subsets of a countable set is countable.
The set of all countable subsets of a continuum has the same cardinality as the set.

Subpages

Section 7: Countable and Uncountable Sets

Section 7: Countable and Uncountable Sets

Countable sets and the Principle of Recursive Definition

Cardinality