The size of sets of real numbers[1]
Laerte Ferreira Morgado [2]
Federal Senate, Brasília, DF, Brazil
https://orcid.org/0009-0006-4004-9804, http://lattes.cnpq.br/1825181346586842
Summary Cantor proved that real numbers are not denumerable, that is, they cannot be generated one by one in a linear way. In this article we propose a method for generating real numbers with the velocity QR(n) =2^n through a balanced binary tree. We also prove that real numbers can only be generated exponentially QR(n) = 2^n. As natural numbers, by essence, are generated in a linear way QN(n) = n, if we can talk about the size of infinite sets of numbers, the sizes of the sets of natural and real numbers would be, respectively, lim QN(n), n-> infinity = infinity and lim QR(n) = (2^n + 1), n-> infinity = 2^infinity. The demonstration does not depend on Cantor’s one-to-one relationship and considers numbers as essentially determined by their characteristics of order and quantity, as highlighted in Morgado (2024-a).
Key words: Cantor; Real; Size; Infinite; Measure.
Submission date: March 8, 2024.
1. Introduction
George Cantor proved that real numbers cannot be enumerated. Thus, real numbers cannot be generated one by one by any algorithm, unlike natural numbers, which can be generated, one by one, from the number 0, simply by adding one unit to the last number in the sequence. How, then, can we generate real numbers, how can we construct them? In the present work, we present a very simple way of generating them and, based on this method, we derive some important conclusions about the sets of real numbers.
2. Theoretical developments
2.1 Balanced binary tree
Let us first examine the real numbers in the interval [0,1]. Later, we can generalize the results to the entire real line. Consider Figure 1, below. Starting from the root node, which represents the entire range [0,1], the left child of the node represents the lower limit and the right child of the node represents the upper limit of the real range. The construction of this binary and balanced tree is simple: for each node, starting from the children of the root node, divide the represented interval in half and create two children for each of the nodes, the child of the left node representing the left subinterval and the child of the right node representing the right subinterval. For example, the root node represents the range [0,1] and has as children nodes 0 (lower limit of the range) and 1 (upper limit of the range). The children of the left node will be 0 and ½, representing the lower and upper limits of the subinterval [0,1/2]. The children of the right node will be ½ and 1, representing the lower and upper limits of the subinterval [1/2,1]. And so on.
Figure 1 — Representation of the interval [0,1] by binary tree
As you can see, as the subintervals represented by the nodes become smaller and smaller, this binary tree becomes a tree for the generation of real numbers in the interval [0,1]. Let us represent by “n” the height of the tree in each of the iterations of its construction. The root node has height 0. Its children are at height 1. And so on. It can verified that, at each iteration, the leaves (the lowest nodes) of the tree represent the limits of the generated subintervals. And it’s also easy to see that they are the real numbers generated up to that iteration. As we proceed in generating the tree, the numbers that are represented by the leaves become increasingly dense in the range [0,1]. That is, the subintervals of represented real numbers become increasingly narrower. As the iterations proceed, we obtain more and more real numbers that are represented by the leaves of the tree. It is seen that all real numbers in the range [0,1] can be generated as the tree construction proceeds. Some numbers will never appear as leaves on the tree and will always be within the subintervals represented by the nodes. However, they can be considered “generated” when we understand that, when constructing the tree, we will obtain the delimitations (lower and upper limits) of these numbers with any necessary degree of precision: these numbers fall within increasingly narrower intervals. If we build the tree indefinitely, with ever-increasing height, we will obtain any real number with any desired degree of precision. In short, this tree generates all real numbers in the range [0,1]. This is also easy to verify when we note that the intervals represented by the leaves of the tree cover the entire interval [0,1].
2.2 Generation velocity
As we saw, the numbers are generated by the leaves of the trees, the number of which increases with each iteration, each time we increase the height of the tree by one unit and refine our representation of the subintervals. It is easy to calculate that the number of different real numbers represented by the leaves of the tree for a height “n” is: Qr(n) = 2^(n-1) + 1. If we consider that the interior of each subinterval also represents a number, albeit with finite precision, delimited by the lower and upper limits of the subinterval, we will have that the total quantity of numbers generated up to iteration (tree height) “n” is Q (n) = 2^(n-1) + 2^(n-1) + 1 = 2^n + 1.
In other words, the quantity of real numbers in the range [0,1] generated by this method grows exponentially with the precision obtained. In the limit, when we generate numbers indefinitely, the quantity of real numbers in the interval [0,1] is lim Q(n) = (2^n + 1), n-> infinity = 2^infinity.
It can be seen, on the other hand, that it is not possible to generate real numbers in the range [0,1] in a linear way, enumerating them one by one. If this were possible, we would have a method to generate them sequentially like, for example: n1, n2, n3, …. But this is impossible according to Cantor’s diagonal method. This would correspond, as is easy to see, to a method of linear speed generation Q(n) = n, whose limit, determining the quantity of numbers, would be lim Q(n), n-> infinity = infinity. Another proof of this theorem is as follows. The interval [0,1] has a midpoint at ½. In order for us to generate all the real numbers in this interval, we must select at least one number from each of the subintervals (0,1/2) and (1/2,1). If this were not the case, one of these subintervals would not be generated. On the other hand, each of these subintervals has a midpoint, causing us to have 4 subintervals: (0,1/4), (1/4,1/2), (1/2,3/4) and (3/4,1). From each of these intervals, in order for us to be able to generate the entire interval [0,1], we must select at least one number, which increases the minimum total number to 4. Continuing in this way, considering the midpoints of the subintervals, we see that, at a minimum, to generate the entire interval [0,1], 2, 4, 8, … Q(n) = 2^n points are necessary. In other words, the generation of real numbers in the interval [0,1] can only be done exponentially and, in the limit, if we can talk about size, the size of the set of real numbers in the interval is, at least, lim (Q(n) = 2^n), n-> infinity = 2^infinity. As we have already proposed a construction method, using a binary tree, that obtains this limit, we can conclude that the real numbers in the interval can only be generated at the velocity Q(n) = 2^n and its size is 2^infinity.
What we have proven, in short, is that the set of real numbers in the interval [0,1] can only be generated, by any method, through velocity Q(n) = 2^n (exponential). We can generalize this result to the set of positive real numbers, successively adding unit intervals to the right of the initial interval and generating these unit intervals alternately. As each of these intervals can only be generated exponentially, their union can also be generated for any finite union of unitary intervals of real numbers. Continuing in this way, adding unit intervals, we can generate any subset of positive real numbers at the velocity Q(n) = 2^n. We can also generalize to negative real numbers, successively adding unit intervals of negative real numbers to the left of the interval [0,1]. Thus, in conclusion, real numbers can only be generated at the velocity Q(n) = 2^n (exponential).
Now, back to Cantor. Natural numbers, by their very essence, can only be generated using linear velocity methods QN(n) = n. We proved above that real numbers, as a whole, can only be generated by exponential velocity methods QR(n) = 2^n. If we can talk about quantities of natural and real numbers, these quantities would be, respectively, lim QN(n), n-> infinity = infinity and lim QR(n) = (2^n + 1), n-> infinity = 2^infinity. It appears that the present demonstration does not depend on Cantor’s one-to-one relationship and considers the numbers essentially determined by their order and the quantity they represent, as highlighted in Morgado (2024-a).
3. References
BENTLEY, JL Algorithms for Klee’s Rectangle Problem. Unpublished notes, Department of Computer Science, Carnegie-Mellon University, Pittsburg, 1977.
FINE, B., & ROSENBERGER, G. Number Theory. An Introduction Through the Distribution of Primes. Boston, MA: Birkhäuser, 2007. ISBN 85–7110–495–6.
HAMKINS, Joel David. Lectures on the Philosophy of Mathematics (English Edition). Boston, MA: The MIT Press, 2021. ASIN B08942KP4Q.
JORGENSEN, Estelle. On Philosophical Method. Menc Handbook of Research Methodologies . Colwell, R. (Ed.): Oxford University Press, 2006. ISBN 0–19–518945–0; 0–19–530455–1 (pbk.).
MANCOSU, Paolo. Measuring the size of collection infinites of natural numbers: Was Cantor’s theory of infinite number inevitable? The Review of Symbolic Logic , vol. 2, no. 4, 2009. IT HURTS: https://doi.org/10.1017/S1755020309990128.
MEISTERS, GH Lebesgue Measure on the real line. University of Nebraska, Lincoln , vol. 118, 1997.
MORGADO, L. The size of infinite sets of natural numbers, 2024-a . Retrieved from Medium: https://medium.com/@laertefmorgado/o-tamanho-de-conjuntos-infinitos-de-n%C3%BAmeros-naturais-97b08653b102.
NIVEN, Ivan. The asymptotic density of sequences. Bull. Amer. Math. Soc. , v. 57, p. 420–434, 1951.ISSN 1088–9485 (online).
[1] I developed this work independently. I use a version of the segment tree here, as first introduced by Bentley (1977). Initial version of 03/08/2024.
[2] Brief CV: Computer Engineer from Unicamp, Master in Electrical Engineering from Unicamp, Doctor of Business Administration from California Southern University (USA). Contact: laertefmorgado@gmail.com.
