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.
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 .
Examples of countably infinite sets
The set of natural numbers is countably infinite by definition , since it has the same power as itself.
The set of integers is countably infinite, a count is given by, for example
Pairs of natural numbers
The set of all pairs of two natural numbers is also countably infinite.
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.
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 .
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.
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 .
As a countable union of finite sets it is therefore countable. On the other hand , since contains is countable infinite.
Words over an alphabet
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
- 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.
- Each enumerable set is at most enumerable.