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 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.
- 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
Integers
The set of integers is countable (countably infinite). Indeed, the function
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cdots } |
| f(n) | 0 | -1 | 1 | -2 | 2 | -3 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cdots} |
Union of to countable sets
The union of the set of natural numbers and any finite set is countable. For instance, given the finite set
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = \{ a_0, a_1, \ldots, a_{n-1} \} }
of n elements, the function
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \mapsto \begin{cases} a_i, & i < n \\ i-n, & \mbox{otherwise} \end{cases}}
shows that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \cup \mathbb{N} } is countable.
More generally, consider two countably infinite sets:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = \{a_0, a_1, a_2, \ldots \} } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B = \{b_0, b_1, \ldots \} }
then
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \mapsto \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb N }
and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \cup B }
.
(Note that this is the same method as in the example of the integers:
Let A be the positive integers and B be the negative integers.)
This situation is addressed in the example of Hilbert's hotel.
Rational numbers
In fact, the union of an enumerable number of enumerable sets is still enumerable. Suppose we have a collection of sets Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_i} as follows:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.
| 0 | 1 | 2 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ldots} | |
|---|---|---|---|---|
| 1 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\over{1}} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\over{1}} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\over{1}} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ldots} |
| 2 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\over{2}} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\over{2}} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\over{2}} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ldots} |
| 3 | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\over{3}} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\over{3}} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\over{3}} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ldots} |
| Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vdots} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vdots} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vdots} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vdots} | Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 < r < 1 } is (as a subset) also countable, and the interval can be written as a sequence:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ r \mid 0 \le 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 ri can be written as an infinitely long list:
| Order | Real Number |
|---|---|
| 0 | 0.32847... |
| 1 | 0.48284... |
| 2 | 0.89438... |
| 3 | 0.00154... |
| 4 | 0.32425... |
| ... | ... |
Specifically, we construct a number which differs from each real number by at least one digit, using this procedure: If the ith digit after the decimal place in the ith number in the list is a five, then our constructed number will have a four in the ith place, otherwise a five. From our example list, we would construct the number 0.55544... By construction, this number is a real number, but not in our list. As a result, the enumeration function is not onto.
This is known as Cantor's diagonalization argument. It is important to note that this argument assumes that two different decimal notations represent two different numbers. This is generally true, with one notable exception. Any digit followed by an infinite series of nines is equivalent to the same digit, increased by one, followed by an infinite series of zeros. For example, 0.3999… is equivalent to 0.4000…. This argument converts individual digits to either fours or fives, thereby avoiding any complications that could arise from this detail.