2e:null 2f:["$","title",null,{"children":"Enumeration of Countably Infinite Random Real Numbers | Daniel LaLiberte | Observable"}] 34:T707,// Generate one number and others that branch off all of its prefixes. function* generateOneRandomNumberDepthFirst( initialDepth = 32, pregenerateX, animate ) { let numNumbers = initialDepth; // + 2; // For Zero and One const numbers = []; let index = 0; // Generate root of tree. const rootNode = new BinaryTreeNode(null, "0"); const randomDigits = generateNRandomDigits(numNumbers).slice(); // db('nRandomDigits', nRandomDigits); let currentNum; let parentNode = rootNode; let nextDigit = randomDigits.shift(); pregenerateX = pregenerateX == "noX" ? false : pregenerateX; // Generate the number for X, which will always be currentNum currentNum = Real.construct(rootNode, index++, pregenerateX ? "X" : `X${index-1}`, [nextDigit]); numbers.push(currentNum); while (numbers.length < numNumbers) { let newNode; parentNode = currentNum.node; nextDigit = randomDigits.shift(); if (pregenerateX && pregenerateX !== "noX") { // Add nextDigit to curentNum currentNum.addDigit(nextDigit); // Add other digit to parentNode to get newNode. newNode = parentNode.addDigit(nextDigit == "0" ? "1" : "0"); } else { // Add other digit to currentNum currentNum.addDigit(nextDigit == "0" ? "1" : "0"); // Add nextDigit to get newNode. newNode = parentNode.addDigit(nextDigit); } // console.info('newNode', newNode); const newNum = Real.construct(newNode, index++, pregenerateX ? "" : `X${index-1}`); numbers.push(newNum); if (!pregenerateX) { currentNum = newNum; } if (animate) { yield { tree: rootNode.traverseTree(), numbers }; } } // Return list of nodes by traversing the binary tree. return yield { tree: rootNode.traverseTree(), numbers }; }35:T40a,## Enumeration of Random Real Numbers The function **`generateCountableNumbersRandomly`**, defined next, iterates through the generation of a countable infinity of random real numbers between 0 and 1, assuming it has unlimited space and time. The following breadth-first process is repeated until the selected Depth is reached: 1. Create the root node of the binary tree. 2. Create the special real number objects for 0 and 1\. 3. Create the next random real number, by calling `Real.generateNewRandomNumber()`, which finds a unique prefix to start with and defers the generation of remaining digits until requested. Note that this is _breadth-first algorithm_. That is, we do not generate all digits of one number before starting with the next number. Rather, we initially create each number by merely ensuring that it has a unique prefix, compared to all previously generated numbers, and then we defer the generation of all remaining digits until later when required to distinguish it from subsequently generated numbers.36:T46c,In the visualization of the binary tree below, **the numbers at the leaves of the tree, on the right, are sorted numerically in increasing order**, due to the way the binary tree is visualized. Each number object is also linked to its next and previous nearest neighbors, so this doubly-linked ordered list of numbers is in the same order as the numbers displayed in the visualization. The paths and nodes of the binary tree that have the same color indicate the creation of a single new number starting at some branch from a node and continuing out to the leaf node. The index of each number, based on the creation order, is also shown on the right (#0, #1, etc), along with all the digits computed so far. You can hover your mouse over any number or part of a path to highlight the path back to the node at which each number was created. Each time you click the Regenerate button, or change the Depth or Link Shape or Animation control, the generator starts over from scratch. The depth in this visualization corresponds to the average depth of the tree. The number of numbers that will be generated is ${tex`1 + 2^{Depth}`}37:T989,### Random Number Enumeration is Countable, but is it Complete? This enumeration is clearly countable since it is formed by the process of generating each number one after the other as the number of generated numbers grows to infinity. But just because it is a countable enumeration, that doesn't mean it is a complete enumeration of all reals between 0 and 1. Aside from Cantor's arguments that the Real numbers are uncountable and thus any attempted enumeration _must_ be incomplete, is there any other obvious gap in this enumeration? Every number that is created this way will necessarily be unique, due to the algorithm enforcing this uniqueness. So if the real numbers were actually countable, the fact that every number is unique might suggest that every number would be generated. However, that is not true either, since we might skip many numbers and still have a countable infinity of unique numbers. It is apparent that the binary tree resulting from the randomly generated numbers is unbalanced, with a wide range of depths at each leaf node corresponding to numbers with different numbers of digits. This unbalanced property is not necessarily a problem, but it suggests that some branches of the tree may never be filled out while others may grow faster than the rest. As the depth grows, however, more and more of the tree tends to fill in randomly, even as it remains unbalanced. If we were to continue this process for an infinite number of iterations, how could we be sure that all branches would eventually be filled in, and thus all numbers would have been enumerated? As the process of generating random numbers continues toward an infinite number of iterations, the probability of never expanding some branches decreases with a limit that approaches 0. This means that the probability that some branches may never be expanded always decreases to an infinitesimal as the number of iterations increases toward infinity. However, there is also a chance that any two independently created random numbers may have the same value, which would cause the attempt to create the second number to loop indefinitely. This possibility of a collision between numbers also has an infinitesimal probability of occurring, but it cannot be ignored. Regardless of how we answer these questions, it seems too easy to claim that all real numbers can be enumerated simply by generating a countable infinity of unique random numbers.38:T6d1,### Does the Generation of a Random Number have a Limit? Some might object that, because we are adding random digits to each number, we can't tell what real number might result, and therefore it has no limit. There are three responses to this objection. Basically, there is a limit even if we don't know what it is, but nevertheless, we can make the random process deterministic if the repeatability of the random process is a concern. Finally, we separately show that the reals are countable through a completely non-random process, if randomness is still a concern. 1. Clearly, the process of adding random digits results in _some_ real number, even if we don't know what it will be in advance. Each subsequently added digit narrows the range of possibilities, just as _any_ sequence of nested closed intervals, no matter how it is defined, randomly or not, narrows the possibilities until the limit of the process results in one real number. We don't need to know exactly which digits are added in order to determine that one real number will result. 2. If the objection to a random process is that we cannot repeat it from one run to the next, it is possible to make the random process deterministic using a _pseudo_-random process starting from the same "seed" that can be as purely random as required. For the argument about how this can be done, see [Deterministic Random Numbers](https://observablehq.com/@dlaliberte/computable-real-numbers#). 3. If the objection is regarding any dependence on a random process, we can also show by a completely non-random process that the Reals are countable. See [Infinite Binary Tree of Intervals](https://observablehq.com/@dlaliberte/infinite-binary-tree-of-intervals) for that argument.39:T40c,#### Algorithm to Generate Reals starting with Mirrored Natural Numbers The algorithm to generate an enumeration of real numbers starting with the mirrored natural numbers is defined in the following function, **`generateRealsByIndex`**. Given the current enumeration (initialized with an empty list), and the current state of the binary tree, we get the digits of the next mirrored natural number and search through the binary tree looking up each digit until we find a node where we can add the next new real number. If we bump into a leaf node corresponding to some previously generated number, then we first add another digit to that number, and repeat the process, either by using the next digit from the mirrored natural number, or by generating a random digit, until we find an unoccupied branch where we can add the new number. The Depth control below determines how many numbers will be generated, which is ${tex`2^d`}. The Regenerate button will start over from scratch and generate a new set of random real numbers. 3a:T653,#### No Gaps Compare the digits in the following enumeration table with the table of mirrored numbers above. If you turn off the Random option, we use the same process for generating the prefix digits of every number, but now you can see that every combination of digits is generated as a result. The interesting thing to note is that the binary tree will be balanced because every prefix is generated equally, and every combination of digits is generated. In fact, the suffix of every number is the repeating digit '0', and that means every number in this enumeration is only a rational number. The important point to emphasize is that the binary tree will be balanced because every prefix is generated equally, and thus, every combination of digits is generated. With the "Random" option re-enabled, every number generated is a real number, not just a rational number. The resulting binary tree is typically unbalanced, but the main advantage of this approach is that it guarantees that every finite-length combination of digits will eventually be generated by this process. This is because there is a bijection mapping between natural numbers and prefixes. This guarantees that the generator is complete, meaning that every finite-length combination of digits will eventually be used in the prefix of some real number, and every real number has a prefix that will eventually be used in its creation. The addition of random digits after each prefix may appear to create gaps in the unbalanced tree, but these gaps will eventually be filled in as every prefix corresponding to a mirrored natural number is used. 3b:T891,#### A Countably Infinite Sequence of Rational Numbers With the Random option turned off again, recall that each number in the enumeration is a rational number, as mentioned above. We are not claiming that the enumeration of mirrored natural numbers represents all real numbers between 0 and 1. However, as the number of digits in the mirrored natural numbers grows to infinity, the number of digits representing every combination of digits also grows to infinity. This allows us to argue that the _limit set_ of the sequence includes all real numbers between 0 and 1. Some might argue that natural numbers do not have an infinite number of digits, so the mirrored natural numbers could also never have an infinite number of digits. However, we can avoid this objection by directly generating the mirrored natural number digits. Regardless of how the digits are generated, we will never be able to generate an infinite number of them. The important thing is that we can generate as many digits as needed by following this pattern that guarantees we will generate every combination of digits. The sequence of rational numbers represented by the mirrored natural numbers contains every combination of digits of increasingly precise rational numbers that collectively converge on every real number. This is how we know that the limit set of the mirrored natural numbers is all real numbers between 0 and 1. We can also form sets from each of the infinite sequences of rational numbers that define each real number, as described in the concept of "[Cauchy sequences](https://en.wikipedia.org/wiki/Cauchy_sequence)". We can then create the union of all these sets. This union set should contain the countable infinity of every rational number, and yet it also seems to represent every real number because it contains all the rational numbers in the converging infinite sequences that define all the real numbers. However, the problem with this argument is that each of the real numbers is defined (this way) as a converging infinite _sequence_ of rational numbers, and not by the numbers in that sequence. The total number of these sequences could be more than the number of rational numbers.3c:T564,#### Each Mirrored Natural Number is _Mapped_ by a Bijection with One Real Number With the Random option turned on, each real number that we create with this algorithm starts with a prefix that is one of the mirrored natural numbers. This prefix is followed by an infinite sequence of random digits corresponding to a unique real number. So the digits of each mirrored natural number are used as a prefix to create a new number, but first we check if we can create a new number starting with that prefix. If another number has already been created with the same digits, then we add more random digits to both that number and our longer prefix, and repeat this process until we find an unoccupied branch. Finally, we can create a new number with a longer unique prefix. All the real numbers in this enumeration will be created in this way. By finding a unique prefix starting with each mirrored natural number and adding an infinite sequence of random digits to it, the effect is that we can randomly choose one of the infinite number of possible real numbers that all start with that prefix and uniquely associate it with that prefix. This means that every number generated this way will have its own unique starting point in the tree. Additionally, every number must eventually be chosen and associated with some prefix, since every number has a unique combination of digits. 3d:T569,### Breadth-First Enumeration of Countably Infinite Reals The enumeration created by **`generateAllNumbersBreadthFirst`**, described next, will generate numbers in a breadth-first order. This means that it will fill out every combination of digits at each level before proceeding to the next level. This generator avoids gaps, as we did previously when generating numbers with the mirrored natural numbers. But it also avoids any possible conflicts between two numbers by ensuring that every new number is created using a unique prefix that does not require any randomly generated digits. There are a few key points about this algorithm that tend to escape notice, so it is worth emphasizing them here: 1. Every node in the binary tree corresponds to the creation of one real number, which is only one of the infinite set of numbers that share the same finite prefix that corresponds to that node. 2. Every number, once created and added to the enumeration of all numbers thus created, is subsequently extended with an independently generated infinite sequence of random digits. 3. Other real numbers that share the same finite prefix will subsequently be created starting at their own unique nodes somewhere in the subtree below that node. 4. Finally, every possible real number will thus be created and enumerated by this process. The completeness argument is summarized below. 3e:T4ff,function generateAllNumbersBreadthFirst(numNumbers = 64, random = true) { const numbers = []; let index = 0; // Generate root of tree. const rootNode = new BinaryTreeNode(null, "0"); // Generate 0 and 1 bounds. const zero = Zero.construct(rootNode.addDigit("0"), index++, "Zero"); numbers.push(zero); const one = One.construct(rootNode.addDigit("1"), index++, "One"); numbers.push(one); while (numbers.length < numNumbers) { const currentNumbersLength = numbers.length; for (let i = 0; i < currentNumbersLength; i++) { // Add one digit to every current number. const currentNum = numbers[i]; const parentNode = currentNum.node; let nextDigit = '0'; if (random) { nextDigit = currentNum.addNextDigit(); } else { if (currentNum == one) { nextDigit = '1'; } currentNum.addDigit(nextDigit); } // Create a new number with the other digit. const otherDigit = nextDigit == "0" ? "1" : "0"; const newNode = parentNode.addDigit(otherDigit); const newNum = Real.construct(newNode, index++); numbers.push(newNum); } } // Return list of nodes by traversing the binary tree. return { tree: rootNode.traverseTree(), numbers }; }3f:T5df,Since the leaf node corresponding to every previously created number will be extended with two subtrees using the same process, this means that every subtree is similar to the whole tree since they are all filled out completely with every combination of digits. But this property of filling the whole tree with every combination of digits does not, by itself, mean that we will have enumerated all real numbers between 0 and 1. In fact, there is a subset of rational numbers that will also completely fill the binary tree with no gaps or collisions. In the above generator, you can deselect the "Random" checkbox, which causes the digit that we add to each of the known numbers to always be '0'. This means that every number, once it is created, will always have an infinite number of '0' digits appended to it, and will therefore be a rational number (a sum of a finite number of negative powers of 2, in this case). Consequently, every time you regenerate the enumeration, it will be exactly the same. The difference between an enumeration of rational numbers, with the "Random" option turned off, and an enumeration of real numbers, with the "Random" option turned on, is that every number generated with an infinite sequence of random digits is a real number, whereas every number in the enumeration of rational numbers is only a rational number. So an enumeration of all rational numbers cannot be considered an enumeration of all real numbers, even though its limit set is all real numbers.40:T7ae,#### The Union of a Countable Infinity of Countably Infinite Sets is Countable Here is a different way of looking at the breadth-first generation process that might help understand how it works. We know that the union of a countable infinity of countably infinite sets is countably infinite. This principle is essentially what we are making use of in the generation of a countable infinity of real numbers, but the difference is whether we are doing it breadth-first or depth-first. The depth-first approach might be easier to understand, though it does not provide an enumeration. Starting with one real number, since this number has a countable infinity of digits when it is represented in binary, for each digit of the number, we can choose any one of the infinite number of real numbers that matches all the digits of the first number before this digit but differs at this digit, so it "branches away" from the first number. Then we can construct a set containing all these numbers that branch away from the first number, and this set will contain a countable infinity of real numbers. But then we can repeat this process for each number in this set. We create another countably infinite set of real numbers that branch away from each number, one number corresponding to each digit. And we can form the union of all these countably infinite sets, and this set is also a countably infinite. Note that we don't need to worry about choosing numbers that have not been chosen previously, but it may be simpler to assume we are doing that. By repeatedly selecting each real number from the previously generated countable infinity of numbers, we can iterate through its digits to choose another new number for each digit and add it to the ever-growing countably infinite set in the same way. And if this process is repeated indefinitely, the result at each step will always be a set containing a countably infinite number of real numbers, even at the limit. 41:T5f0,#### A Countably Infinite Loop of Countably Infinite Loops is Countable Note that when we say "for each member of a set" in mathematics, we are effectively iterating through an infinite set with an infinite loop as if it takes no time at all, even if it involves an infinite number of infinite loops. But to make a mathematical expression like this be an enumeration, we have to linearize the process by converting an infinite number of infinite loops into only one infinite loop. To do this, we must avoid using a depth-first approach that would iterate over an infinite number of digits for any one number before continuing with any other number. Instead, we must use a breadth-first approach that repeats the process for each digit of each new number as it is chosen. This is essentially the process implemented by the algorithm above for generating all digits of all real numbers in a breadth-first order. Analogous to the preceding section, I believe there should always be a way to linearize an infinite loop of infinite loops into one countable infinite loop, provided every infinite loop is countable. That's my conjecture, if no one else has claimed it. Assuming this is true, we should be able to shortcut arguments that tediously flatten out the nested infinite loops into one loop and just declare that if every nested loop only needs to loop over countable infinities, then the whole process could be refactored into one countably infinite loop. This should apply to transfinite infinities as well. 42:T52d,#### The Completeness of the Breadth-first Generator Note that because of the uniformity of this process, for each level of the binary tree at depth, d, as we iterate through all ${tex`2^d`} known numbers with `d` digits, each number is extended to `d+1` digits, and we create ${tex`2^d`} new numbers starting with `d+1` digits. So the length of the enumeration list is doubled after we finish each level of the iteration. If you look through all the numbers created at depth `d` in the visualization or the enumeration table, you can see the digits of all the numbers generated so far. Each of these numbers has the form "0." followed by a string of `d` binary digits, and for all the numbers at each depth, the digits will consist of all the natural numbers between 0 and ${tex`2^d - 1`}. E.g. for depth=6, the numbers are: ${tex.block`[0.000000..., 0.000001..., 0.000010..., ..., 0.111110..., 0.111111...]`} Therefore, after iterating to depth `d`, each and every combination of `d` digits will have been used to create ${tex`2^d`} binary tree leaf nodes, associated with ${tex`2^d`} real numbers. For every real number not yet created, it must have one of these combinations of `d` digits as a prefix, and we will eventually create that number starting with some longer prefix in a subtree of one of these nodes. 43:T60e,##### The Generation of Every Unique Infinitely Long Combination of Digits To address the first problem, suppose that the algorithm could miss the generation of some combination of digits that corresponds to a real number `x`. In this case, there would be a prefix of the digits of `x` with a finite length, `d`, for which we did not create its binary tree node. (And if this were the case, all other numbers starting with the same prefix would also be missing.) However, we can see that for every prefix of length `d`, the generation process will create every binary tree node for all combinations of digits up to length `d`. Therefore, the assumption that we somehow missed the creation of the node for any such prefix of `x` with any _finite_ number of digits must be false. While this argument applies to any _finite_ number of digits, why should we be able to extend it to an _infinite_ number of digits? It seems to make sense to do so, but we actually need to apply a technique called "transfinite induction" to extend this argument to infinity, which we will do below. OK, we should now be able to agree, tentatively, that every combination of digits is represented in the binary tree. That still doesn't prove that all numbers will be created by this enumeration process. We might have never gotten around to the creation of the number for `x`, even though all of its digits are represented in the binary tree, because for every prefix of `x`, we might have created a different number that diverges from `x` somewhere after that point.44:T680,##### The Creation of a Number for Every Unique Combination of Digits To address the second problem, first we will show that every finite length prefix of digits is associated with a unique number in this process, and then argue that this can be extended to the case of infinitely long sequences of digits which also must be associated with unique numbers. Not only do we create every combination of digits for every prefix of any finite length, we can also prove by induction that we create a unique number for every finite length unique combination of digits. Assuming that, for every prefix of unique digits with length `d`, there is a unique number associated with the prefix (for a total of ${tex`2^d`} numbers), then for prefixes of length `d+1`, we extend each of the ${tex`2^d`} current numbers that have a prefix of length `d` by one random digit, and we also create a new number by extending the same prefix using the complement of that digit. Therefore, every prefix of length `d+1` will also have a unique number associated with it (for a total of ${tex`2^{d+1}`} numbers). So by induction, this is true for all _finite_ `d`. Since we can impose a well-ordering (see below) on the generation of incrementally longer finite length prefixes and their associated unique numbers, the same argument can be extended to infinitely long sequences of digits. For any real number expressed as a unique countable infinity of digits, the generation process will incrementally generate successively longer prefixes of the number without end. At the limit, each infinitely long sequence of digits is unique and must correspond to one and only one number. 45:T694,##### Proof by Transfinite Induction While the previous section still only provides an informal argument, we should be able to prove it using transfinite induction or (more simply) [Zorn's lemma](https://gowers.wordpress.com/2008/08/12/how-to-use-zorns-lemma/). Here is a sketch of the proof: We will define a well-ordering for the levels of the binary tree of digits corresponding to prefixes of all the numbers associated with the leaves of the tree. We define one ordinal for each level of the tree, starting with the empty tree, by creating the union of the ordinal for the previous level of the tree and the result of applying a generator function to that previous ordinal. The generator function does what was described previously, and repeated here: 1. Append random digits to the prefixes of every number associated with the previous level of the tree, and 2. Create new numbers associated with the same prefixes as for step 1, but append the complements of each corresponding random digit. The result of this generator function for level `d` is an ordinal containing the ordinal for level `d-1` and the set of all known numbers that have prefixes of length `d`. While this definition is not designed for space efficiency, it does the job of ordering the levels of the tree and all the associated numbers. Given this well-ordering of the levels of the binary tree and the associated numbers, Zorn's lemma allows us to conclude that there is a "maximal element" for the infinite ordinal, corresponding to level infinity of the binary tree, where we will find the set of all real numbers between 0 and 1, and for each number, its countably infinite sequence of digits.46:T66f,A more formal statement of this proof is possible, but would not be particularly readable. 47:T910,// Generate one number, maybe, and others that branch off all of its prefixes. // Here we can vary the pregenerateX option continuously between 0 and 1, as a probability applied at each step. // Once we switch into pregenerating mode, it stays on thereafter. function* generateOneRandomNumberMaybe( initialDepth = 32, pregenerateXDepth, animate ) { let numNumbers = initialDepth; // + 2; // For Zero and One const numbers = []; let index = 0; // Generate root of tree. const rootNode = new BinaryTreeNode(null, "0"); const randomDigits = generateNRandomDigits(numNumbers).slice(); // db('nRandomDigits', nRandomDigits); let currentNum; let parentNode = rootNode; let nextDigit = randomDigits.shift(); let pregenerateX = false; let maybePregenerateNow = () => { if (pregenerateX) return; pregenerateX = pregenerateXDepth === 0 ? true : pregenerateXDepth === 1 ? false : numbers.length > 100 * pregenerateXDepth; }; maybePregenerateNow(); // Generate the number for X, which will always be currentNum currentNum = Real.construct( rootNode, index++, pregenerateX ? "X" : `X${index - 1}`, [nextDigit] ); numbers.push(currentNum); while (numbers.length < numNumbers) { let newNode; parentNode = currentNum.node; nextDigit = randomDigits.shift(); if (pregenerateX) { // Add nextDigit to curentNum currentNum.addDigit(nextDigit); // Add other digit to parentNode to get newNode. newNode = parentNode.addDigit(nextDigit == "0" ? "1" : "0"); } else { // Add other digit to currentNum currentNum.addDigit(nextDigit == "0" ? "1" : "0"); // Add nextDigit to get newNode. newNode = parentNode.addDigit(nextDigit); } // console.info('newNode', newNode); const newNum = Real.construct( newNode, index++, pregenerateX ? "" : `X${index - 1}` ); numbers.push(newNum); if (!pregenerateX) { currentNum = newNum; } maybePregenerateNow(); if (pregenerateX) { currentNum.name = "X"; } if (animate) { yield { tree: rootNode.traverseTree(), numbers }; } } // Return list of nodes by traversing the binary tree. return yield { tree: rootNode.traverseTree(), numbers }; }48:T51b, However, if the infinitesimal chance of creating each real number is truly an immeasurable infinitesimal, then it would mean that there must be an infinite number of reals between any two normal infinitesimals. But this cannot be true because in the hyperreal number system, the first infinitesimal is defined as being smaller than any real number but greater than 0. This means that there cannot be _any_ real numbers between 0 and one infinitesimal. In the hyperreal number system, each infinitesimal is defined as the limit of a converging infinite sequence of real numbers. This means that the distance between infinitesimals must be at least as small as the distance between reals. Therefore, we can conclude that the number of reals cannot be greater than the number of infinitesimals. This definition of hyperreals in terms of infinite sequences of reals is similar to how the reals are defined in terms of infinite sequences of rational numbers. So we are back to affirming that the infinitesimal chance of creating each number is accurate, and therefore a countable infinity of infinitesimal chances must add up to certainty. By the way, this argument comparing the size of the reals and the hyperreals appears to be leading us to conclude that both the reals and hyperreals must be countable.49:Tac1,#### Enumeration of Rationals versus Reals How is this proof of completeness of the enumeration of real numbers any different if we substitute the creation of rational numbers at every step instead of the creation of real numbers? Since we only seem to be concerned with the enumeration of numbers that have certain prefixes and that we generate every combination of digits for those prefixes, and we extend all of those prefixes similarly, then why does it matter whether the numbers we create this way are merely rationals or actually reals? All combinations of digits for prefixes of any finite length will be generated either way. The main difference is that we do create actual real numbers, rather than merely rational numbers. And the way we create and extend these real numbers depends on the generation of an infinite sequence of random digits to ensure that any possible real number might be created. If we only enumerate rational numbers (for example, numbers that have a finite-length binary representation followed by an infinite number of 0s), then we haven't resolved the question of whether we can enumerate all real numbers. But if we extend the enumeration of rationals to infinitely long sequences of digits at the limit, then we have a similar situation as for the enumeration of real numbers, where every combination of digits is generated and a unique number is created corresponding to every finite prefix, which is extended to infinitely long sequences. So it would seem there is no difference between the enumeration of rationals and the enumeration of reals at the limit of infinitely long sequences of digits, at least regarding this question of whether every combination of digits is generated, and a unique number corresponds to each unique combination of digits. Does this mean that there is no difference between the rationals and the reals? Not at all, since the rationals are clearly a proper subset of the reals. However, it does seem to confirm that the cardinality of all rationals is the same as the cardinality of all reals. Furthermore, if we have an enumeration of all rationals that, at the limit of this enumeration is identical with all reals, then this enumeration must have effectively enumerated the same set of numbers (in the sense of the Cauchy sequence definition of reals). It might appear that the irrational numbers are effectively equivalent to rational numbers with infinitely long non-repeating prefixes when represented in a rational-base number system followed by a suffix of repeating digits that has zero length. But rational numbers, by definition, will always have only a finitely long prefix of non-repeating digits followed by an infinitely long suffix of repeating digits.4a:T42a,## Cantor's Counter Arguments Cantor makes two arguments that the real numbers are uncountable. These arguments correspond pretty closely to the two question raised above about whether the breadth-first enumeration of the reals can be considered complete. The first question, whether we have generated every combination of digits, is answered in the negative by Cantor's Diagonalization argument, which claims that there must be at least one combination of digits that has been missed since we can construct it from the complement of the diagonal digits of the enumeration. The second question, whether we have necessarily generated every number, is answered in the negative by Cantor's Nested Closed Intervals argument, which claims that the limit of his sequence of nested closed intervals will always exclude a number that therefore cannot be in the enumeration. Although we addressed both questions above, Cantor's arguments would seem to contradict our arguments, so we have to address why his arguments cannot be correct, which we will do in future posts.4b:[{"id":"b175a14eb9b0e1110328ed455c68686c14529c994fde30376d610cc0b13f317d90b9cd71a7d9255c92c709dc86bb54fc056b46d8d7424acc165846d8d650f2d5","href":"https://static.observableusercontent.com/files/b175a14eb9b0e1110328ed455c68686c14529c994fde30376d610cc0b13f317d90b9cd71a7d9255c92c709dc86bb54fc056b46d8d7424acc165846d8d650f2d5","name":"4096reals.png","type":"image/png","lastModified":1642803648722.206,"size":159997}] 32:{"id":"07567b6857ecba84","slug":"countably-infinite-random-real-numbers","title":"Enumeration of Countably Infinite Random Real Numbers","thumbnail":"f7e072f2b33e7bcb5c609256b43d61ca47dd95649592ffb0f21b52c16f7d4104","access_level":"public","create_time":"$D2022-01-19T22:23:32.405Z","update_time":"$D2023-10-17T02:03:29.460Z","view_time":null,"first_public_time":"$D2022-12-07T03:38:27.167Z","has_unpublished_edits":null,"fork":{"id":"662080314eb2cb2c","slug":"blog-post","title":"Blog Post","owner":{"id":"f35c755083683fe5","login":"observablehq","name":"Observable"}},"stars":1,"starred":false,"owner":{"type":"team","id":"88bca6b25e968fae","login":"dlaliberte","name":"Daniel LaLiberte","avatar_url":"https://avatars-next.observableusercontent.com/e5ca1f0f640d7d3579ea69f7316220ebcec267322399e2773f31b91bc2790b15","tier":"starter_2024"},"version":1321,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"b887ef310da1b17a","login":"dlaliberte","name":"Daniel LaLiberte","avatar_url":"https://avatars-next.observableusercontent.com/e5ca1f0f640d7d3579ea69f7316220ebcec267322399e2773f31b91bc2790b15","tier":null}],"members":[{"type":"individual","id":"b887ef310da1b17a","login":"dlaliberte","name":"Daniel LaLiberte","avatar_url":"https://avatars-next.observableusercontent.com/e5ca1f0f640d7d3579ea69f7316220ebcec267322399e2773f31b91bc2790b15","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"Enumeration of Countably Infinite Random Real Numbers","cells":[{"id":0,"value":"# Enumeration of Countably Infinite Random Real Numbers\n\n_We can easily enumerate a countable infinity of random real numbers._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":882,"value":"By Merril Jordahl, Jena Jordahl, Daniel LaLiberte","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4,"value":"FileAttachment(\"4096reals.png\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":109,"value":"## Abstract\n\nIn a previous post, [Computable Real Numbers](https://observablehq.com/@dlaliberte/computable-real-numbers), we showed how we could generate one random real number, and how it is also straightforward to generate an enumeration of an infinite number of random real numbers. However, there were questions of whether we could choose digits purely randomly, and therefore, whether this enumeration of real numbers could be considered complete. The generator also allowed the possibility of collisions between two random but identical numbers. In this post, we resolve these problems by showing how we can factor out the need for true randomness while we nevertheless generate all combinations of digits, and therefore we can ensure we miss no numbers and avoid all collisions in the enumeration.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":214,"value":"toc(\"h2, h3, h4, h5, h6\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":308,"value":"---\n## Generate Random Real Numbers\n\nA generator of numbers was first outlined in \"[Number Objects](https://observablehq.com/@dlaliberte/number-obj)\" where we focused mostly on enumerations of the Rational numbers. Here we focus attention on enumerating all the Real numbers, especially ensuring that no conflicts will occur (i.e. generating the same number more than once) and that none will be missed. \n\nAs before, the `Real` class along with the `BinaryTreeNode` class manages the creation of an enumeration of unique real number objects where the digits of all numbers are stored in a shared binary tree. The various generation functions defined here determine which numbers will be created and in what order.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":151,"value":"### Generate One Random Real Number, Depth-First\n\nWe previously showed in \"[Computable Real Numbers](https://observablehq.com/@dlaliberte/computable-real-numbers)\" how we can generate one random number by repeatedly adding enough randomly generated digits to distinguish it from all previously generated numbers. If we are only generating one random number along with the numbers that branch away from it, this task is trivially easy. \n\nThe **`generateNRandomDigits`** function, defined below, follows this generation process. Based on the Depth option, we add more digits to the random number while creating a branching number for each digit of the random number which shares the same prefix but always differs by its last digit.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":496,"value":"mutable nRandomDigits = []","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":498,"value":"function generateNRandomDigits(n) {\n // Slice off extras\n if (nRandomDigits.length > n) {\n nRandomDigits.splice(n);\n }\n // Push on new digits.\n while (nRandomDigits.length < n) {\n nRandomDigits.push(Math.random() < 0.5 ? \"0\" : \"1\");\n // db(\"nd\", nRandomDigits);\n }\n return nRandomDigits;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":504,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":158,"value":"depthFirstNumbers = generateOneRandomNumberDepthFirst(\n 0 + depthFirstOptions.depth,\n depthFirstOptions.pregenerateX,\n false\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":557,"value":"html`\n${button({\n value: \"Regenerate\",\n divStyle: {\n display: \"inline-block\"\n },\n buttonStyle: {\n background: \"#CCE9FF\"\n },\n titleStyle: {\n \"text-align\": \"center\"\n },\n onclick: ({ button }) => {\n mutable nRandomDigits = [];\n }\n})}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":161,"value":"viewof depthFirstOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":164,"value":"vlembed(\n makeTreeVegaSpec(depthFirstNumbers.tree, {\n title:\n \"Depth-first Generation\" +\n (depthFirstOptions.pregenerateX ? \" of Random X \" : \" Without X\"),\n width: 600 + depthFirstOptions.depth * 5,\n height: Math.max(300, 30 + depthFirstOptions.depth * 12),\n hideLabels: depthFirstOptions.depth > 60,\n linkShape: \"diagonal\" // depthFirstOptions.linkShape\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"$35","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"// Generate all numbers and return the list of nodes of the binary tree.\nfunction* generateCountableNumbersRandomly(randomly = true, numNumbers = 64, animate = false) {\n // First initialize the array of all numbers.\n const numbers = [];\n let index = 0;\n \n // Generate root of tree.\n const rootNode = new BinaryTreeNode(null, '0');\n \n // Generate 0 and 1 branches.\n const zero = Zero.construct(rootNode.addDigit('0'), index++);\n numbers.push(zero);\n const one = One.construct(rootNode.addDigit('1'), -1)\n numbers.push(one);\n\n for (let i = 0; i < numNumbers; i++) {\n const newNum = Real.generateNewRandomNumber(rootNode, index++);\n numbers.push(newNum);\n \n if (animate) {\n // This is an easy, but expensive, way to animate the growth of the binary tree.\n yield {tree: rootNode.traverseTree(), numbers};\n }\n }\n \n // Return list of nodes by traversing the binary tree. Also return the list of numbers.\n yield {tree: rootNode.traverseTree(), numbers};\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":322,"value":"The result of generateCountableNumbersRandomly is an object containing the binary tree and the list of real numbers that were generated. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":119,"value":"randomNumbers = (replayGenerateCountableNumbers,\ngenerateCountableNumbersRandomly(\n true,\n Math.pow(2, randomOptions.depth) - 1,\n randomOptions.depth < 7 && randomOptions.animate // only if it is not too deep\n))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":115,"value":"$36","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":123,"value":"viewof replayGenerateCountableNumbers = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":121,"value":"viewof randomOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"vlembed(\n makeTreeVegaSpec(randomNumbers.tree, {\n title: `Generate 2^${randomOptions.depth} Reals Randomly`,\n width: 800,\n height: Math.max(300, Math.pow(2, randomOptions.depth) * 12),\n linkShape: randomOptions.linkShape\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":138,"value":"\nBelow is a table that shows this countable enumeration of real numbers sorted by the index of each number, so this is the same order as they were initially created. \n\nClick the '**approximate value**' column header to sort by the approximate value of each number, and then you will see the numbers listed in the same order as shown beside the leaf nodes in the binary tree. Note that, when the table is sorted numerically, assuming we could run this generator forever, between each pair of adjacent numbers visible at this early stage there would be an infinite number of other numbers that are generated later.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":127,"value":"showEnumerationTable(randomNumbers)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":194,"value":"$37","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1304,"value":"$38","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":740,"value":"## How to Avoid Collisions and Missing Numbers\n\nTo avoid any potential question about whether we might miss some numbers or attempt to generate the same numbers more than once while we are generating an infinite list of real numbers purely randomly, we can build the enumeration other ways such that we are guaranteed to fill every branch of the tree and never have a conflict between two numbers. The following sections describe two methods that attempt to do this.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":730,"value":"### Enumeration of Reals by Mirroring the Natural Numbers\n\nWe can enumerate all real numbers (between 0 and 1) by generating each new number such that it _starts with_ the digits of successive \"mirrored\" natural numbers. For each natural number, we mirror it by reversing its digits, as shown in the following table. We will use these digits to find the starting node for each new real number that we generate. All digits added after these starting digits will be randomly generated.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":734,"value":"countingNumbers = [\n 0, 1, 2, 3, 4, 5, 6, 7, 8, 4095, 4096, 4097\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":748,"value":"Table(\n [\n ...countingNumbers.map((n) => {\n const digits = n.toString(2);\n const mirrored = `0.${n.toString(2).split(\"\").reverse().join(\"\")}`;\n return {\n number: n,\n binary: digits,\n mirrored,\n decimal: digitsToNumber(mirrored, 2)\n };\n }),\n { number: \"...\", mirrored: \"...\" },\n { number: \"Countable steps: ...\", mirrored: \"...\" },\n { number: \"Limit set: ∞\", binary: \"∞\", mirrored: \"ℝ?\" }\n ],\n {\n align: { binary: \"right\", decimal: \"left\" },\n format: { decimal: (n) => n.toString() }\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":768,"value":"$39","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":682,"value":"function generateRealsByIndex(numNumbers = 64, random = true) {\n const numbers = [];\n let index = 0;\n\n // Generate root of tree.\n const rootNode = new BinaryTreeNode(null, \"0\");\n\n // Generate 0 and 1 bounds.\n const zero = Zero.construct(rootNode.addDigit(\"0\"), index++, \"Zero\");\n numbers.push(zero);\n \n while (numbers.length < numNumbers) {\n // Convert index number to mirrored binary fraction.\n let startingDigits = index.toString(2).split(\"\").reverse();\n\n const newNum = random ? Real.construct(rootNode, index, index, startingDigits) :\n Rational.construct(rootNode, index, index, startingDigits, ['0']);\n // newNum.addNextDigit();\n \n index++;\n numbers.push(newNum);\n }\n\n // Return list of nodes by traversing the binary tree.\n return { tree: rootNode.traverseTree(), numbers };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":689,"value":"mirroredNaturalNumbers = (replayGenerateAllNumbersByIndex,\ngenerateRealsByIndex(Math.pow(2, mirroredNaturalOptions.depth), mirroredNaturalOptions.random))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":709,"value":"viewof replayGenerateAllNumbersByIndex= html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":691,"value":"viewof mirroredNaturalOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":695,"value":"vlembed(\n makeTreeVegaSpec(mirroredNaturalNumbers.tree, {\n title:\n \"Generate Countable Reals by Mirrored Counting Numbers to Depth \" +\n (mirroredNaturalOptions.depth),\n width: 600 + mirroredNaturalOptions.depth * 5,\n height: Math.max(\n 300,\n 50 + Math.min(1200, Math.pow(2, mirroredNaturalOptions.depth) * 18)\n ),\n hideLabels: mirroredNaturalOptions.depth > 7\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":812,"value":"$3a","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":704,"value":"showEnumerationTable(mirroredNaturalNumbers)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":760,"value":"$3b","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":762,"value":"Nevertheless, it is worth emphasizing that the enumeration of natural numbers goes to infinity, which results in a countable limit set of the natural numbers (if we collect every natural number into a single limit set). In contrast, the enumeration of mirrored natural numbers, which is also countable, results in a limit set of all real numbers between 0 and 1, and this limit set is believed to be uncountable in cardinality. This means that one countable enumeration results in a countable limit set, while another countable enumeration results in an uncountable limit set. This paradox is understood and accepted by the math community.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":765,"value":"$3c","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":789,"value":"While this algorithm avoids gaps by generating all possible prefixes, it still allows for the possibility of a conflict when adding a new number. This can happen if the new number and an existing number have exactly the same infinitely long sequence of randomly generated digits. Although this collision has only an infinitesimally small chance of occurring, we still need to find an algorithm that avoids it completely. We will do this in the next section.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":218,"value":"$3d","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1281,"value":"\n#### Outline of the algorithm\n\nWe repeatedly iterate through all the currently known (previously created) numbers and add one random digit ('0' or '1') to each of them. The added digit is determined independently by the number itself, which by default for Real numbers is a random choice. After adding a digit to each currently known number, we also create a new number starting with the same prefix as the known number, but extending it with the other digit ('1' or '0', respectively). \n\nIn other words, the current digits of each known number will be used as the prefix for two branches of the tree:\n\n1. One branch, adding a randomly chosen '0' or '1', will extend a known, previously created number.\n2. The other branch, adding a '1' or '0', respectively, will correspond to the creation of a new number.\n\nNote that the bounding numbers for Zero and One, are exceptions to this rule since they are always extended with '0' and '1' respectively.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":228,"value":"$3e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":232,"value":"breadthFirstNumbers = (replayGenerateAllNumbersBreadthFirst,\ngenerateAllNumbersBreadthFirst(Math.pow(2, 1 + breadthFirstOptions.depth), breadthFirstOptions.random))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":251,"value":"showEnumerationTable(breadthFirstNumbers)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"Above is the enumeration table of all numbers generated by this algorithm, in the order they were generated. Below is the corresponding binary tree of all digits of the numbers generated so far. \n\nEach time you click the \"Regenerate\" button, or change the \"Depth\" slider, the numbers will be regenerated from scratch, but the balanced binary tree structure will be exactly the same because the resulting prefixes of the set of numbers will be exactly the same. The order of the index numbers and the colors of the branches are different each time due to the random digit generation for existing numbers.\n\nThe \"Random\" option is explained below.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":234,"value":"viewof replayGenerateAllNumbersBreadthFirst = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":238,"value":"viewof breadthFirstOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":246,"value":"vlembed(\n makeTreeVegaSpec(breadthFirstNumbers.tree, {\n title:\n \"Generate Countable Reals Breadth-First to Depth \" +\n (breadthFirstOptions.depth + 1),\n width: 600 + breadthFirstOptions.depth * 10,\n height: Math.max(\n 300,\n 50 + Math.min(2000, Math.pow(2, breadthFirstOptions.depth) * 18)\n ),\n hideLabels: breadthFirstOptions.depth > 7\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":263,"value":"#### All Gaps and Collisions are Avoided\n\nSo for this generator, the quality of the randomness doesn't matter at all regarding the question of whether any prefix of digits will be missed. Since every combination of prefixes will be generated at every depth, no prefix will be missed. There is also no risk of collision between any two numbers (i.e. where two numbers accidentally have the exact same infinitely long sequence of digits), since each new number is only created by branching away non-randomly from a previously created number at some finite depth.\n\nPart of the process that we use here to generate numbers is not random, because we will always see the same prefixes at each depth in every enumeration generated this way, but the order of the numbers and the eventually complete value of each number varies randomly from one enumeration to the next.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":850,"value":"$3f","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":846,"value":"But even though every number in this breadth-first enumeration of Reals is a real number, and every combination of digits is generated, this does not quite prove that the enumeration is complete. There are three remaining problems:\n\n1. Once each number is created, we need to ensure that _any_ possible random sequence of digits might follow. This appears to require the \"pure\" randomness discussed previously, or the equivalent in the form of a true random number generator.\n2. Even with the generation of any possible random sequence of digits, we still have to show that _every_ real number is necessarily enumerated.\n3. We must refute Cantor's arguments that claim the Real numbers cannot be enumerated.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":799,"value":"$40","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1153,"value":"\nThis explanation of how the algorithm works might help you gain an intuitive understanding of what we are doing, but this is not a proof of the completeness of the process such that we can be sure every real number will be encountered and added to the one countably infinite set. For that proof, we need to look more closely at how we are constructing the set of real numbers, which we will do next.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1209,"value":"$41","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":275,"value":"$42","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":290,"value":"The completeness of this breadth-first generation process may seem fairly self-evident, since every unique combination of finitely many digits is created at each depth, and the process is repeated forever to the limit of infinitely long strings of digits. Since every number has a unique combination of digits corresponding to an infinitely long path in the binary tree from the root out toward a leaf node, and every unique combination of digits will be generated at some finite step in this process, that should mean that every number will eventually be enumerated.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":662,"value":"But that same intuitive argument would apply to an enumeration of rational numbers, so we have to be a little more careful here. Let's see if there is a more rigorous argument. We can divide up the problem into two parts:\n\n1. The generation of every unique infinitely long combination of digits.\n2. The creation of a number for every unique combination of digits.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":467,"value":"$43","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":629,"value":"$44","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1021,"value":"$45","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":915,"value":"$46","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":931,"value":"But perhaps this proof will not be quite enough since we still need to deal with the probabilistic aspect of the generation of random digits. While the random generation of all combinations of digits is easy enough to prove as we did above, the creation of a number corresponding to every unique combination of digits is a separate problem. This problem is explored in more detail in the next section.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":933,"value":"##### Create Random X at Some Finite Depth\n\nWe saw above in [Generate One Random Real Number, Depth-first](https://observablehq.com/@dlaliberte/countably-infinite-random-real-numbers#cell-151) that it is conceivable that we could generate all the digits of one number and yet somehow never get around to creating the number for it. If you toggle the \"Pregenerate X\" option on and off, you can see that the very same digits of the number can be generated in the non-pregenerated mode and yet we will never create the number.\n\nBut this toggle for the \"Pregenerate X\" option is a boolean switch, and we programmatically force the outcome to be at one extreme or the other. However, it is possible to, instead, vary the depth that we create the number for X continuously between those extremes. This means that at every step of the iteration, we decide whether to create the number at that step. This is shown in the following visualization.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":940,"value":"$47","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":942,"value":"maybeNumbers = generateOneRandomNumberMaybe(\n 0 + maybeOptions.depth,\n maybeOptions.pregenerateX,\n false\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":956,"value":"html`\n${button({\n value: \"Regenerate\",\n divStyle: {\n display: \"inline-block\"\n },\n buttonStyle: {\n background: \"#CCE9FF\"\n },\n titleStyle: {\n \"text-align\": \"center\"\n },\n onclick: ({ button }) => {\n mutable nRandomDigits = [];\n }\n})}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":944,"value":"viewof maybeOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":947,"value":"vlembed(\n makeTreeVegaSpec(maybeNumbers.tree, {\n title: \"Create X at Depth \" + Math.round(maybeOptions.pregenerateX * 100),\n width: Math.min(850, 600 + maybeOptions.depth * 5),\n height: Math.max(300, 30 + maybeOptions.depth * 12),\n hideLabels: maybeOptions.depth > 60,\n linkShape: \"diagonal\", // maybeOptions.linkShape\n colorScheme: \"bluepurple\"\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":977,"value":"When you adjust the \"Create X at Depth\" option, you will see the color of the X path change based on the depth at which the number is created. Also note that, up to the step where X is created, the number labels will be 'Xi' for the number created on the ith step, and once X is created, the 'X' label will be shown for the number X.\n\nWhat would happen if, instead of specifying exactly what depth the number will be created, we only used this depth probabilistically (by some appropriate function)? The number for 'X' might be generated at any step of the process, or it seems possible that it might never be generated. If we could extend this depth all the way to infinity, the chance of creating the number at each depth would be in the neighborhood of 1 infinitesimal.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1130,"value":"##### An Infinite Number of Infinitesimal Chances to Create Each Number\n\nThis visualization shows that we can control the depth at which the number for `X` is created. When we are not controlling that creation explicitly, then there is only an infinitesimal chance of creating any specific number object. And while we are generating the infinite sequence of digits for the number `X`, in which the number `X` may or may not be created at each finite step, then we have an infinite number of infinitesimal chances of creating the number for `X`. \n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1133,"value":"The way we should think about whether the number object for `X`, for any arbitrary infinite sequence of digits, is created (and thus enumerated by this system) is that there is an infinitesimal chance of creating the number object `X` for each of the infinite number of digits in the sequence. The calculation of this probability is an infinitesimal times an infinite number, which if they are of the same magnitude (i.e. ${tex`epsilon^1`} and ${tex`omega^1`}) then the result is 1. In other words, the arbitrary number object for `X` will be certainly be created this way since an infinite number of infinitesimal chances is equal to 1. And since this argument is stated in terms of an arbitrary number, this means that each and every real number will be generated this same way.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1136,"value":"\nIt is essential to note that this argument relies on the assumption that the infinitesimal chance of creating each number is accurate. If the real numbers are truly uncountable, then this infinitesimal chance must actually be way too large. If so, we would really need an \"immeasurable\" infinitesimal, which is still greater than 0, but infinitely smaller than an infinitesimal (to an uncountably infinite power?). If we multiply this immeasurable infinitesimal probability by a countable infinity, the result would never be as large as a normal infinitesimal.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":989,"value":"$48","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1235,"value":"### A Bijection between Naturals and Reals","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1239,"value":"To be considered \"countable\", we must define the bijection mapping between the natural numbers and the real numbers. \n\nThe mapping from natural numbers to real numbers in the enumeration is self-evident, since the enumeration itself provides this mapping. Each of the generation algorithms presented here results in a \"numbers\" array, which represents this enumeration and we can define a function to return the corresponding unique real number object given any natural number. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1231,"value":"function getNumber(numbers, i) {\n return numbers[i];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1233,"value":"Given two natural numbers, i and j, we could test that, if they map to the same real number, then the two natural numbers must be the same. This is a test that our mapping from natural numbers to real numbers is an _injection_. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1237,"value":"function testInjection(numbers, i, j) {\n let r = getNumber(numbers, i);\n let s = getNumber(numbers, j); \n if (r == s) { \n if (i != j) {\n throw new Error('Broken');\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1241,"value":"Each number object also stores its index, such that we can map any real number object back to its corresponding natural number index. So we can define a function to get the index for any number from the number object used to represent it.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1244,"value":"function getIndex(r) {\n return r.index;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1246,"value":"Given any real number object, `r`, we can test that `getNumber(numbers, getIndex(r)) == r`. This is a test that our mapping from natural numbers to real numbers is a _surjection_ or _onto_, **assuming we can find the number object that corresponds to any real number**.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1251,"value":"function testSurjection(numbers, r) {\n let i = getIndex(r);\n if (getNumber(numbers, i) != r) {\n throw new Error('Broken');\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1253,"value":"By the way, an injective mapping is also sometimes referred to as _one-to-one_, but that term is confusing since it suggests there is a bidirectional symmetry that does not necessarily exist. Each natural number is mapped by an injection to a unique real number, but that by itself doesn't mean the reverse is true, that each real number is mapped to a unique natural number. A surjective mapping goes in the opposite direction, since each real number is mapped to a unique natural number, but again, that by itself doesn't mean the reverse is true, that each natural number is mapped to a unique real number. Both mappings together are required to define a _bijection_.\n\nAssuming these two tests are always true, and that therefore our we have an _injective_ (or _one-to-one_) mapping and a _surjective_ (or _onto_) mapping, this is equivalent to finding a _bijection_ between the naturals numbers and the real numbers. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":664,"value":"$49","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":345,"value":"$4a","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1211,"value":"## Follow up Notebooks\n \n1. It should be fairly straightforward to prove: \"A Countably Infinite Loop of Countably Infinite Loops is Countable\"\n2. [Refutation of Cantor's Diagonalization](https://observablehq.com/@dlaliberte/refutation-of-cantors-diagonalization)\n3. Cantor's Nested Closed Intervals argument\n4. [Infinite Binary Tree of Intervals](https://observablehq.com/@dlaliberte/infinite-binary-tree-of-intervals)\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":409,"value":"## References\n\n* [To Infinity and Beyond](https://acko.net/blog/to-infinity-and-beyond/)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":84,"value":"vlembed = require(\"vega-embed\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"import {\n Real,\n Rational,\n Zero,\n One,\n BinaryTreeNode,\n makeTreeVegaSpec,\n showEnumerationTable, digitsToNumber\n} from \"@dlaliberte/number-objects\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"import {toc} from \"@nebrius/indented-toc\"\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":88,"value":"import { form } from \"@mbostock/form-input\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":752,"value":"import {Table} from \"@observablehq/table\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":512,"value":"import { Debug } from \"@trebor/debug-tool\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":570,"value":"// viewof db = Debug()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":560,"value":"import { button } from \"@bartok32/diy-inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4b","stdlib":"1","titling":"auto"}} 33:"$32:body"