Countable set

In mathematics, a set is said to be countable if its elements can be "numbered" using the natural numbers. More precisely, this means that there exists a one-to-one mapping from the set to the set of natural numbers.

A countable set is either finite or countably infinite. A set which is not countable is called uncountable.

Terminology is not uniform, however: Some authors use "countable" in the sense of "countably infinite", and "at most countable" instead of "countable". Also, sometimes "denumerable" is used for "countably infinite".
On the other hand, one must not mix up countable sets with the related, but different, concept of (recursively) enumerable sets from computability theory.

The set of natural numbers is countably infinite (of course), but there are also (only) countably many integers, rational numbers, rational algebraic numbers, and enumerable sets of integers.
On the other hand, the set of real numbers is uncountable, and there are uncountably many sets of integers.

Any subset of a countable set is countable.

The image of a countable set (under any function) is a countable set.

The countable union (i.e., the union of a countable family) of countable sets is countable.

The Cartesian product of finitely many countable sets is countable.

Examples of countably infinite sets

Perfect squares

The set of perfect squares is countably infinite, as the following correspondence shows:

$n\leftrightarrow n^{2}$

n	0	1	2	3	4	5	$\cdots$
n2	0	1	4	9	16	25	$\cdots$

This is an example of a proper subset of an infinite set that has as many elements as the set, a situation addressed by Galileo's paradox.

Integers

The set of integers is countably infinite. Indeed, the function

$f(n)=(-1)^{n}\cdot \left\lfloor {\frac {n+1}{2}}\right\rfloor$

is a one-to-one correspondence between all natural numbers and all integers:

n	0	1	2	3	4	5	$\cdots$
f(n)	0	-1	1	-2	2	-3	$\cdots$

Union of two countable sets

The union of the set of natural numbers and any finite set is countable. For instance, given the finite set

$A=\{a_{0},a_{1},\ldots ,a_{n-1}\}$

of n elements, the function

$f(i)\mapsto {\begin{cases}a_{i},&i<n\\i-n,&{\mbox{otherwise}}\end{cases}}$

shows that $A\cup \mathbb {N}$ is countable.

i	0	1	$\cdots$	n-2	n-1	n	n+1	n+2	$\cdots$
f(i)	a0	a1	$\cdots$	an-2	an-1	0	1	2	$\cdots$

More generally, consider two countably infinite sets:

$A=\{a_{0},a_{1},a_{2},\ldots \}$ and $B=\{b_{0},b_{1},\ldots \}$

then

$i\leftrightarrow {\begin{cases}a_{i/2},&i{\mbox{ is even}}\\b_{(i-1)/2},&i{\mbox{ is odd}}\end{cases}}$

is a one-to-one correspondence between $\mathbb {N}$ and $A\cup B$.

i	0	1	2	3	$\cdots$	2k	2k+1	2k+2	2k+3	$\cdots$
	a0	b0	a1	b1	$\cdots$	ak	bk	ak+1	bk+1	$\cdots$

(Note that in the example of the integers the same method has been used: Let A be the positive integers and B be the negative integers.)
This situation is illustrated by Hilbert's hotel.

Rational numbers

The set of (positive) rational numbers is the set of fractions

$\{{\tfrac {p}{q}}\mid p,q\in \mathbb {N} \}.$

In fact, the union of an enumerable number of enumerable sets is still enumerable. Suppose we have a collection of sets $A_{0}=\{a_{0,0},a_{0,1},a_{0,2},\ldots \},A_{1}=\{a_{1,0},a_{1,1},\ldots \},A_{2},A_{3},\ldots$. Then we can create a bijection between the whole numbers and all the elements of all the $A_{i}$ as follows:

$a_{i,j}\leftrightarrow {\frac {(i+j)^{2}+i+j}{2}}+j.$

Notice that this concept is used in the proof of the enumerability of the rational numbers, given below. e set of rational numbers is an enumerable set. Envision a table which contains all rational numbers (below). One can make a function that dovetails back and forth across the entire area of the table. This function enumerates all rational numbers.

Table of all rational numbers

	0	1	2	$\ldots$
1	$0 \over {1}$	$1 \over {1}$	$2 \over {1}$	$\ldots$
2	$0 \over {2}$	$1 \over {2}$	$2 \over {2}$	$\ldots$
3	$0 \over {3}$	$1 \over {3}$	$2 \over {3}$	$\ldots$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$

Rational numbers

The set of rational numbers is not countable. The proof is a proof by contradiction, an indirect proof:

Suppose that the set of rational numbers is countably infinite, then the interval of rational numbers r with $0<r<1$ is (as a subset) also countable, and the interval can be written as a sequence:

$\{r\mid 0\leq r<1,r\in \mathbb {R} \}=\{r_{i}\mid i\in \mathbb {N} \}$

Since any real number between 0 and 1 can be written as a decimal number, the sequence r_i can be written as an infinitely long list:

i	ri
0	0.32847...
1	0.48284...
2	0.89438...
3	0.00154...
4	0.32425...
...	...
	0.55544...

But this list cannot be complete:
To show this, we construct a real number r with a decimal expansion which differs from each of the decimal numbers in the list by at least one digit, using the following procedure:
If the i-th digit (after the decimal point) of the i-th number in the list is a 5, then we take 4 as the i-th digit of the num, and if not, then take 5 instead.he Thus the i-th digit of the newly constructed number differs from the i-th digit of the i-th real number in the list, and therefore the expansion of r does not appear in the list. The expansion of r uses only the digits 4 and 5 and is thus unique, therefore the real number r does not occur in the list. Since this contradicts our initial assumption, the assumption, namely, that the set or real numbers is countable, is wrong.

This is known as Cantor's diagonalization argument.