Countable set

In set theory, a set be countably infinite if it has the same power as the set of natural numbers $\mathbb {N}$ . This means that there is a bijection between and the set of natural numbers, so the elements of the setcan be "numbered".

In addition to countably infinite sets, finite sets also belong to the sets that are at most countable. The use of the term countable is not uniform. Depending on the definition, it can mean both countably infinite and at most countable.

A nonempty set that is neither finite nor countably infinite is called supermultiple.

The power of a countably infinite set is denoted - as a cardinal number - by $\aleph _{0}$ (pronounced alef null), approximately holds $\left|\N\right|=\aleph_0$ . For this term, see also Aleph function.

Examples of countably infinite sets

Natural numbers

The set of natural numbers $\mathbb {N}$ is by definition countably infinite, since it has the same power as itself.

Prime numbers

The set of primes $\mathbb{P}$ is also countably infinite, since it is a subset of the natural numbers and, by Euclid's theorem, also infinite.

	1	2	3	4	5	6	7	8	…
	2	3	5	7	11	13	17	19	…

Whole numbers

The set of integers $\mathbb {Z}$ is countably infinite, for example, a count is given by

	1	2	3	4	5	6		8	…
	0	1	−1	2	−2	3	−3	4	…

The examples of prime numbers and integers show that both real subsets and supersets can have the same power as the basic set, in contrast to the ratios for finite sets.

Pairs of natural numbers

Also, the set of all pairs $(i,j)\in\mathbb{N} \times \mathbb{N}$ of two natural numbers is countably infinite.

Infinity is again obvious. More difficult is the question of countability. For this one uses the Cantor pairing function, which (i,j) bijectively assigns a natural number each pair of numbers This allows one to uniquely number all pairs of numbers and thus count them.

	1	2	3	4	5	6	7	8	9	10	…
	1,1	1,2	2,1	1,3	2,2	3,1	1,4	2,3	3,2	4,1	…

n-tuples of natural numbers

The set of all -tuples $(i_1, i_2, \ldots, i_n)$ natural numbers $\mathbb{N}^n$ is also countably infinite. This is again shown by (n-1) -times applying Cantor's pairing function.

Rational numbers

Georg Cantor showed by the so-called first diagonal argument that the set of rational numbers is countable, as is any set of the form $\mathbb{Z}^n$ (tuples of integers).

The mapping $\mathbb{N}_0^3\rightarrow\mathbb{Q}$ , $(i,j,k)\mapsto {\frac {i-j}{1+k}}$ is surjective, so the power of $\mathbb {Q}$ at most as large as that of $\mathbb{N}_0^3$ . Since, on the one hand, there are infinitely many fractions and, on the other hand, the set $\mathbb{N}_0^3$ is countably infinite, $\mathbb {Q}$ countably infinite.

Algebraic numbers

An algebraic number is zero of a polynomial $P(x)=a_{0}+\dots +a_{n}x^{n}$ with integer coefficients. Let the height of be defined as $h(P)=|a_{0}|+\dots +|a_{n}|+n$ .

For any given height k>0 there are only finitely many polynomials, which in turn have only finitely many zeros; for each of these k, with , a_0 = k-1 the polynomial has P(x)= -a_0 + x^1 the zero $x=a_0 \in \mathbb{N}$ . If Q(k) set as the set of all such zeros, then the set $\mathbb{A}$ of algebraic numbers is the union $\bigcup_{k\in\mathbb N\setminus\{0\}} {Q(k)}$ .

As a countable union of finite sets, $\mathbb{A}$ therefore countable. Since $\mathbb{A}$ on the other hand contains $\mathbb {N}$ , $\mathbb{A}$ countably infinite.

Words above an alphabet

By applying the so-called standard numbering over the alphabet $\Sigma$ one can also count the words of a language in the sense of mathematics.

Computable number functions

The set of all computable number functions is countably infinite. One can specify a standard numbering of all conceivable tape programs. Since the set of tape programs is larger than the set of computable functions (there could be two different programs that compute the same function), the number functions are thus countably infinite.

Example of a countable infinite set

The set of real numbers, on the other hand, is overcountable. This means that there is no bijective mapping that maps each real number to one natural number each, see Cantor's second diagonal argument.