Tabla de Contenidos
A set of numbers is uncountable when it is not possible to assign a unique natural number to all its elements . In other words, uncountable sets are those that do not have a one-to-one correspondence with the natural numbers.
We usually use natural numbers intuitively to count, and we do this by assigning a natural number to each element of the group that we want to count, sequentially. For example, when counting the number of fingers we have on a hand, we assign each of the fingers a unique natural number starting with 1 and ending with 5. We then know that there are 5 fingers on the hands because that is the highest value we assign to fingers. In other words, we count the fingers.
This idea cannot be applied to some sets of numbers. In some cases, the sets are so large that even using infinite natural numbers would not be enough to number all the elements of the set. Since the set of natural numbers is infinite, the idea that there are uncountable sets suggests the idea that there are some infinities that are larger than others, and only those sets that have an infinity of the same “size” as the set of natural numbers are countable. the natural numbers. The number of elements in a set is called cardinal, so uncountable sets are those whose cardinal is greater than that of the natural numbers.
Some properties of countable and uncountable sets
To understand why some sets are countable and some are not, it helps to know some properties of sets:
- If A is a subset of B and A is uncountable, then B is also uncountable. In other words, any set that contains an uncountable set must itself be uncountable.
- If A is uncountable and B is any set (countable or not), then the union AUB is also uncountable.
- If A is uncountable and B is any set, then the Cartesian product A x B is also uncountable.
- If A is infinite (even countably infinite), then the power set of A is uncountable.
Examples of the most common uncountable sets
The set of real numbers (R)
The set of real numbers is the first example of an uncountable set. But how do we know that they are uncountable if they have infinite elements and we also have infinite natural numbers to assign? We do this thanks to Cantor’s diagonal argument.
Cantor’s Diagonal
Cantor’s diagonal argument allows us to show that the subset of real numbers that lie between two well-defined limits, for example, between 0 and 1, is an uncountable set. As a consequence, by the already mentioned properties of uncountable sets, the complete set of all real numbers must also be uncountable.
Suppose we create an infinite list of real numbers between 0 and 1. It is completely irrelevant how this list is constructed. The only thing that matters is that all numbers are unique. Now, we are going to assign each of these numbers a unique natural number, starting at 1 and working sequentially. An example of this list is presented in the following table:
| No. | R. | ||||||||
| 1 | 0, | 2 | 2 | 4 | 5 | 8 | 7 | 9 | 6… |
| 2 | 0, | 5 | 2 | 1 | 3 | 2 | 4 | 0 | 2… |
| 3 | 0, | 6 | 4 | 0 | 5 | 7 | 8 | 3 | 0… |
| 4 | 0, | 1 | 7 | 9 | 8 | 2 | 2 | 4 | 3… |
| 5 | 0, | 8 | 5 | 5 | 4 | 7 | 3 | 2 | 2… |
| 6 | 0, | 0 | 4 | 8 | 3 | 8 | 1 | 5 | 3… |
| 7 | 0, | 7 | 8 | 4 | 2 | 0 | 9 | 1 | 0… |
| 8 | 0, | 3 | 4 | 6 | 7 | 9 | 1 | 3 | 5… |
| … | … |
At this point, we are assigning a unique natural number to all the numbers in our list. Since this list is infinite, and each real number corresponds to a natural number, then we “spend” all the natural numbers in this table. What Canto did was show that there is at least one additional real number that is not on this list and therefore cannot be counted. This number is built by taking all the elements of the diagonal that crosses the table, then adding 1. That is, the new number will start with the first digit of the first number increased by one unit, then it will have the second digit of the second number increased by one. unit, then the third digit of the third number and so on.
In the following table, the elements on the diagonal are highlighted in bold and the number resulting from the operation is added to the last row:
| No. | R. | ||||||||
| 1 | 0, | 2 | 2 | 4 | 5 | 8 | 7 | 9 | 6… |
| 2 | 0, | 5 | 2 | 1 | 3 | 2 | 4 | 0 | 2… |
| 3 | 0, | 6 | 4 | 0 | 5 | 7 | 8 | 3 | 0… |
| 4 | 0, | 1 | 7 | 9 | 8 | 2 | 2 | 4 | 3… |
| 5 | 0, | 8 | 5 | 5 | 4 | 7 | 3 | 2 | 2… |
| 6 | 0, | 0 | 4 | 8 | 3 | 8 | 1 | 5 | 3… |
| 7 | 0, | 7 | 8 | 4 | 2 | 0 | 9 | 1 | 0… |
| 8 | 0, | 3 | 4 | 6 | 7 | 9 | 1 | 3 | 5 … |
| … | … | 2+1 | 2+1 | 0+1 | 8+1 | 7+1 | 1+1 | 1+1 | 5+1 |
| 0, | 3 | 3 | 1 | 9 | 8 | 2 | 2 | 6… |
The resulting number is 0.33198226…
As we can see, since the first digit of the new number (which is 3) is different from the first digit of the first number in the list (which is 2), then it will be a different number from the first, even if all the other numbers numbers are exactly the same. Since the second digit (3) is different from the second digit of the second number (2), then it will be different from the second number as well.
This same argument can be continued indefinitely by advancing along the diagonal, ensuring that the resulting number will be different by at least one digit from all the infinite numbers in the table.
However, since we already “spend” or assigned all the natural numbers before creating this new number, then we have no unique natural number left to assign to it, so we conclude that the set of real numbers between 0 and 1, and therefore extension of all real numbers, is an uncountable set.
The set of transcendental numbers
The transcendental numbers are those that belong to the set of real numbers, but are not algebraic numbers. This means that they are not roots of a polynomial equation of the form:
where all the coefficients are integers. Let us call A the set of all algebraic real numbers and T the rest of the real numbers, that is, the transcendental ones. It is easy to see that the total set of real numbers, R , is the union of the sets A and T , that is:
It can be shown that the set of algebraic numbers is countable. Also, we already proved that the real numbers are uncountable. Since R is uncountable, it cannot be formed by the union of two countable sets. Knowing that A is countable, we conclude that T is uncountable.
The set of binary number sequences
A sequence of binary numbers is simply a string of 0’s and 1’s of any length. If we unite all possible sequences of binary numbers, we get the set of sequences of binary numbers. This is nothing more than a subset of the real numbers in which the only digits are 0 and 1.
It is very easy to show that this set of numbers is uncountable using the same Cantor argument with which we show that R is uncountable. The only caveat is that instead of adding 1 to the numbers on the diagonal, we simply reverse their value, replacing 0 with 1 and vice versa.
As before, the resulting binary sequence will be unlike any infinite set of sequences we may have included in the original list, so it is an uncountable set.
Other sequences of numbers with different bases
The argument from sequences of binary numbers and from real numbers can be extended to any sequence of numbers of any base. In this sense, the set of all sequences of hexadecimal numbers will be uncountable; so will be the set of sequences of ternary, quaternary numbers, etc.
References
Common examples of uncountable sets . (2020, March 16). PeoplePerProject. https://en.peopleperproject.com/posts/9312-common-examples-of-uncountable-sets
Ivorra Castillo, C. (sf). SET THEORY . UV.es. https://www.uv.es/ivorra/Libros/TC.pdf
Libretexts. (2021, July 7). 1.4: Countable and Uncountable Sets . Mathematics LibreTexts. https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/An_Introduction_to_Number_Theory_(Veerman)/01%3A_A_Quick_Tour_of_Number_Theory/1.04%3A_Countable_and_Uncountable_Sets
Schwartz, R. (2007, November 12). Countable and Uncountable Sets . Brown Math. https://www.math.brown.edu/reschwar/MFS/handout8.pdf
Uncountable Sets | Examples of Uncountable Sets . (2020, September 21). Cuemath. https://www.cuemath.com/learn/Mathematics/uncountable-sets/
