Countable amount

In set theory , a set is called countable infinite if it has the same power as the set of natural numbers . This means that there is a bijection between and the set of natural numbers, so the elements of the set can be numbered consecutively. ${\displaystyle A}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle A}$ ${\displaystyle A}$

In addition to the countable infinite sets, the finite sets also count to the at most countable sets . The use of the term countable is not uniform. Depending on the definition, it can mean either countable infinite or at most countable .

A non-empty set that is neither finite nor countably infinite is called uncountable .

The thickness of a countably infinite set is denoted - as a cardinal number - with (spoken: alef zero), for example . For this designation see also the aleph function . ${\displaystyle \aleph _{0}}$ ${\displaystyle \left|\mathbb {N} \right|=\aleph _{0}}$

Examples of countably infinite sets

Natural numbers

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

Prime numbers

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

${\displaystyle n}$	1	2	3	4th	5	6th	7th	8th	...
${\displaystyle f(n)}$	2	3	5	7th	11	13	17th	19th	...

Whole numbers

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

${\displaystyle n}$	1	2	3	4th	5	6th	7th	8th	...
${\displaystyle f(n)}$	0	1	−1	2	−2	3	−3	4th	...

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

Pairs of natural numbers

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

Again, the infinity is evident. The question of countability is more difficult. For this one uses the Cantor pairing function , which bijectively assigns a natural number to each pair of numbers . This means that all pairs of numbers can be clearly numbered and thus counted. ${\displaystyle (i,j)}$ ${\displaystyle k}$

${\displaystyle n}$	1	2	3	4th	5	6th	7th	8th	9	10	...
${\displaystyle f(n)}$	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 of natural numbers is also countably infinite. This is shown in turn by applying the Cantor pairing function several times . ${\displaystyle n}$ ${\displaystyle (i_{1},i_{2},\ldots ,i_{n})}$ ${\displaystyle \mathbb {N} ^{n}}$ ${\displaystyle (n-1)}$

Rational numbers

Georg Cantor showed with the so-called first diagonal argument that the set of rational numbers can be counted, as well as any set of shape ( tuples of whole numbers ). ${\displaystyle \mathbb {Z} ^{n}}$

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

Algebraic numbers

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

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

As a countable union of finite sets it is therefore countable. On the other hand , since contains is countable infinite. ${\displaystyle \mathbb {A} }$ ${\displaystyle \mathbb {A} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {A} }$

Words over an alphabet

By using the so-called standard numbering via the alphabet , one can also count the words of a language in the sense of mathematics. ${\displaystyle \Sigma }$

Calculable number functions

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

Example of an uncountable infinite set

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

properties

• Every subset of a (at most) countable set is (at most) countable.
• The union of two (at most) countable sets is (at most) countable.
• More generally, every union of a countable number of (at most) countable sets is again (at most) countable.
• The Cartesian product of two (at most) countable sets is (at most) countable.
• If there is a surjection of the set of natural numbers onto the set , then at most it is countable. ${\displaystyle \mathbb {N} }$ ${\displaystyle A}$ ${\displaystyle A}$
• Each enumerable set is at most enumerable.

See also

• In topology , “small” topological spaces fulfill an axiom of countability .
• Cardinal number (math)