2e:null 2f:["$","title",null,{"children":"Refutation of Cantor's Diagonalization | Daniel LaLiberte | Observable"}] 34:T43f,So, assuming for the moment that the Reals are countable, we need to carefully re-examine whether Cantor's argument is valid, whether the enumeration and the diagonal complement number are defined in a way that is valid, and whether there might be some other flaw in the assumptions behind Cantor's argument. There are several possible alternative explanations for the absence of the diagonal complement number from the enumeration which might explain the contradiction. 1. The enumeration might be complete, but because the diagonal complement number is not a valid number, that would explain why it could never be included, so Cantor's argument is invalid. 2. The enumeration might be complete, even including the diagonal complement number which only _appears_ to be missing from the enumeration. This would demote Cantor's argument to merely being a paradox. 3. The enumeration is not a complete enumeration even though the set of Reals is nevertheless countable, so there might be something invalid about the assumption that an enumeration in this form should always be possible.35:T5f8,// 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* generateOneRandomNumberAsDiagonal( initialDepth = 32, pregenerateXDepth, animate ) { let numNumbers = initialDepth; const numbers = []; let index = 0; // Generate root of tree. const rootNode = new BinaryTreeNode(null, "0"); const randomDigits = generateNRandomDigits(numNumbers).slice(); // db('nRandomDigits', nRandomDigits); let nextDigit = randomDigits.shift(); // Generate the number for X let x = Real.construct(rootNode, index++, "X", [nextDigit]); let xComplementDigits = []; numbers.push(x); let parentNode = rootNode; while (numbers.length < numNumbers) { nextDigit = randomDigits.shift(); // Add nextDigit to curentNum x.addDigit(nextDigit); if (xComplementDigits.length > 0) { const newDigits = [...xComplementDigits, nextDigit]; const newNum = Real.construct(rootNode, index++, null, newDigits); // console.info('newNode', newNode); numbers.push(newNum); } // Append complement of next digit. xComplementDigits.push(nextDigit == "0" ? "1" : "0"); if (animate) { yield { tree: rootNode.traverseTree(), numbers }; } } // Return list of nodes by traversing the binary tree. return yield { tree: rootNode.traverseTree(), numbers }; }36:T6cd, #### Diagonal and Diagonal Complement Digits of an Enumeration Next, we will examine a little more closely what is happening with the diagonal and diagonal complement digits relative to any enumeration generated this way. In the enumeration table, above, for depth `d`, you can see that the diagonal digits of the first `d` numbers are visible and highlighted with square brackets, the `[𝟎]`s and `[𝟏]`s. Then, if you construct the string of all those diagonal digits, you will find one number in the table that has these same diagonal digits. In fact, we arranged that, for this generator, the diagonal number would be the first number in the enumeration. In general, it could be any one of the first ${tex`2^d`} numbers, but if it is one of the first `d` numbers, then of course, its diagonal digit will be the same as the corresponding digit of the diagonal number. More importantly, we can construct another number from the _complement_ of these diagonal digits, and this prefix will also show up in the first ${tex`2^d`} numbers but only after the first `d` numbers. Since each diagonal complement digit will always be in conflict with the diagonal digit of every one of the first `d` numbers, that means any number that corresponds to the complement of the first `d` diagonal digits would have to appear after the first `d` numbers. For this generator, we arranged that the very next number after the first `d` numbers will be this diagonal complement prefix for the first `d` digits. But since _every_ number that we add to the enumeration will always conflict with the diagonal complement digit, once the diagonal digit is added, this means that the diagonal complement number can never be in the enumeration. 37:T6aa,### The Diagonal Complement Number could be in the Limit Set One possible answer to this question of what happened to the diagonal complement number is that it only shows up at the limit. Since every finite-length prefix of the diagonal complement number can be used further down in the enumeration, if we take the limit of the sequence of finite-length prefixes, we will get an infinite-length diagonal complement number. But it is not correct to assume that, because the diagonal complement number is in the limit set, then it is in the sequence itself, since it is forced to be beyond any finite position and thus it is _outside_ of the enumeration and _not in_ the enumeration itself. Even though the diagonal complement number _is_ in the _limit set_ of the enumeration, the members of the limit set of a sequence are not necessarily the same as any of the members of the sequence. As another more familiar example, if we start with the sequence of fractions, 1/2, 1/4, 1/8, etc, every number in the sequence is greater than 0, so 0 is never in the sequence even though the limit of this sequence is 0. If we want to argue that the definition of the diagonal complement number is valid and it is actually included in the enumeration, we are essentially arguing that every infinite sequence of numbers should implicitly include every number in its limit set. That would mean, for example, that we only need to enumerate the rationals between 0 and 1 to effectively enumerate all reals that are in the limit set of that enumeration (similar to the Cauchy sequence definition of the reals). Maybe we will get there, but we should not make that leap of logic just yet, so let's look elsewhere.38:T4e4,## Subdivide the Enumeration into Two Complementary Enumerations The following argument assumes that we have an enumeration of Reals between 0 and 1, but it does not assume this enumeration is complete. It only assumes that it is a countable enumeration, no matter which numbers might be missing. What would happen if we subdivide the enumeration of Reals between 0 and 1 into two complementary enumerations, one for the numbers between 0 and 1/2 (not including 1/2), all starting with a '0' digit, and the other enumeration for the numbers between 1/2 and 1, all starting with a '1' digit? Then, for every number in either enumeration, the complement of that number _should_ be in the other enumeration. And this includes the complement of the diagonal, assuming the enumerations are complete. And furthermore, this includes any possible complement of the diagonal, since every number in the 0 to 1/2 enumeration starts with a `0`, so every possible diagonal also starts with a `0`, so the complement must start with a `1`. The converse applies to the 1/2 to 1 enumeration. Thus it appears **we have avoided the conflict between all the numbers in either enumeration and any possible diagonal complement number for the same enumeration**. 39:Tcd4, But to be fair, Cantor's diagonalization argument doesn't really apply to the two complementary enumerations, since neither is an enumeration of all the numbers between 0 and 1, which is what the argument assumes. Or another way to look at it is that both enumerations fail to include their own diagonal complement numbers, so they are obviously not complete enumerations of all numbers between 0 and 1. By the way, we are not trying to modify Cantor's diagonalization argument to allow a single enumeration of all numbers between 0 and 1 to be subdivided into two enumerations as we have done here. Rather, we are considering the implications of Cantor's argument assuming his conclusion is valid. So we are starting with this single enumeration, which Cantor concludes must be incomplete, and then we subdivide it into two enumerations to find out what happens. Or equivalently, rather than starting with one enumeration that we subdivide into two, we might generate the two complementary enumerations first, and then merge them into one. Note that in merging the two enumerations into one, we can't simply append one entire enumeration to the end of the other, since then we will essentially still have two countably infinite lists; rather, we will have to interleave finite subsequences of the two enumerations into one countably infinite list. Regarding the two complementary enumerations, the result ought to be the same either way (splitting the one enumeration into two, or starting with two which we merge into one), but there are a couple problems with this idea that we will have to deal with. 1. The merged enumeration of all numbers between 0 and 1 would still have its own diagonal complement number that could be different from any number that is in either of the complementary enumerations. We are going to defer this first problem for now, and return to it after we have fully considered a second problem. 2. Even though we have avoided conflict with all possible diagonal complement numbers for either complementary enumerations, there is still a "shifted diagonal complement" number that conflicts with the numbers in the enumerations, explained next. Since the cardinality of the real numbers between 0 and 1/2 is the same as the cardinality of the real numbers between 0 and 1, it makes sense that we will have a similar conflicting diagonal complement problem. To be clear about the conflict, if we look at each number in the enumeration of numbers between 0 and 1/2, in which all numbers start with a '0' digit, and we ignore the first digit of every number, then we will have numbers that look exactly the same as the entire range of numbers between 0 and 1. So a diagonal complement constructed from the "shifted diagonal" digits of all the numbers in the 0 to 1/2 enumeration, where the diagonal is shifted one position to the right, will still be in conflict with the enumeration. That is, if we construct a "shifted diagonal complement" number by starting with either a `0` or a `1` digit, and then append the complement of the second digit of the _first_ number, the complement of the third digit of the _second_ number, etc, then we will have a number that conflicts with every number in the enumeration of numbers between 0 and 1/2. 3a:T41a,### Repeat the Subdivision Now that we have subdivided the original enumeration into two, and avoided any conflict with the first digit of all possible diagonal complements in those two subdivisions, we can repeat the process by subdividing each of these subdivisions in the same way, creating two complementary enumerations from each one, based on the first two digits. As a result, we will have four enumerations containing all numbers starting with the digits '00', '01', '10', and '11', respectively. The numbers in the '00' and '11' enumerations complement each other, and the numbers in the '01' and '10' enumerations complement each other. And here again, by subdividing the original enumeration into four complementary enumerations, **we will avoid any conflict with the first two digits of all possible diagonal complement numbers of the subdivision enumerations**. This is, again, true of the four subdivisions, but not true of the original enumeration or the first pair of subdivisions. But, again, we have made a bit more progress. 3b:T4a9,### Repeat the Subdivision Process an Infinite Number of Times We can repeat this process a countably infinite number of times, corresponding to the countably infinite number of digits of each real number, and the result will be an infinite number of subdivisions. And significantly, **we will avoid any conflict with any of the countably infinite number of digits of all possible diagonal complement numbers of the infinite number of subdivision enumerations**. This will be true of the infinite number of subdivision enumerations that result at the limit of this infinite process, but not for any of the prior enumerations they were derived from. One important difference between repeating this process a finite number of times as we did previously, versus an infinite number of times as we did here, is that, since ordinary induction only lets us generalize to any finite number of repetitions, we have to use what's called "transfinite induction" to generalize to an infinite number of repetitions. To do that, we have to define a well-ordering of the entities we are "counting", which in this case is the levels of each repetition of this subdivision process. (More on that later.) 3c:T615,

Level	Infinite Binary Tree of Subdivision Enumerations
0	0. ...
1	.0...								.1...
2	.00...				.01...				.10...				.11...
3	.000...		.001...		.010...		.011...		.100...		.101...		.110...		.111...
4	.0000...	.0001...	.0010...	.0011...	.0100...	.0101...	.0110...	.0111...	.1000...	.1001...	.1010...	.1011...	.1100...	.1101...	.1110...	.1111...
...	...

3d:T655,### The Infinite Number of Subdivision Enumerations is Countable The number of subdivisions at "level infinity" of this process would seem to obviously be a countable infinity. But is it? Since the number of subdivisions at each level doubles compared to the previous level, it might seem we will get ${tex`2^{infinity}`} subdivisions, if infinity was a number. But since the number of subdivisions at the limit is clearly the same as the number of combinations of a countable infinity of digits, and that corresponds to the number of all real numbers, we have to be careful about jumping to conclusions. An enumeration of this infinite number of subdivisions would seem to require traversing the leaf nodes of an infinite binary tree, but we can't do that since there are no leaf nodes in an infinite binary tree. However, there is a simple way of enumerating all the subdivisions by counting each subdivision as it is created, and this method will turn out to be very similar to how we can enumerate the real numbers themselves. ### Infinite Binary Tree Enumerating the Subdivisions For each subsequent level of this subdivision process, we doubled the number of enumerations. But we can do a simple variation of this to effectively count each of the infinite number of enumerations that result from repeating this process an infinite number of times. For each level of the subdivision process, we will _replace_ each enumeration with the first of the two subdivisions, and then add the other new enumeration. We will still have two subdivisions for the same set of numbers, but only one new enumeration. 3e:T534,

Level	Infinite Binary Tree Enumerating the Subdivisions
0	#0
1	#0								#1
2	#0				#2				#1				#3
3	#0		#4		#2		#5		#1		#6		#3		#7
4	#0	#8	#4	#9	#2	#10	#5	#11	#1	#12	#6	#13	#3	#14	#7	#15
...	...

3f:T462,### How Many Numbers in Each of the Countable Infinity of Subdivision Enumerations? How many numbers should we expect to find in each of the infinite number of subdivisions at the limit? Could there still be as many real numbers in each subdivision as all the reals between 0 and 1? Since we already "used up" all of the countable infinity of digits of any real number in generating these subdivisions, how could there be any more digits for any more numbers? Is there only one number in each subdivision? Another way to look at these subdivisions of the original enumeration is that each subdivision one corresponds to an interval of real numbers, and at each level of the binary tree, we subdivide each interval into two intervals which, together, cover the same interval. Since the result is a binary tree of intervals, one interval for each subdivision, we can follow any path through the tree, and at every node of the tree, we can choose either of the two subintervals. Thus any path we follow through the tree will correspond to an infinite sequence of nested intervals (which are left-closed, right-open). 40:T6ca,

Binary Tree of Enumeration Intervals

Level	Binary Tree of Enumeration Intervals
0	[0, 1)
1	[.0, .1)								[.1, 1)
2	[.00, .01)				[.01, .10)				[.10, .11)				[.11, 1)
3	[.000, .001)		[.001, .010)		[.010, .011)		[.011, .100)		[.100, .101)		[.101, .110)		[.110, .111)		[.111, 1)
4	[.0000, .0001)	[.0001, .0010)	[.0010, .0010)	[.0011, .0100)	[.0100, .0101)	[.0101, .0110)	[.0110, .0111)	[.0111, .1000)	[.1000, .1001)	[.1001, .1010)	[.1010, .1011)	[.1011, .1100)	[.1100, .1101)	[.1101, .1110)	[.1110, .1111)	[.1111, 1)
...	...

41:T753, Then, the limit of every path through the binary tree of intervals will approach a single real number, according to the ["Nested intervals](http://go/wpda/Nested_intervals)" theorem. Actually, our intervals are all half-open, closed on the left and open on the right, but the same argument applies here, so none of these sequences will result in the empty set at the limit. See [Nested sequence of half open intervals with non-empty intersection](https://math.stackexchange.com/questions/3015727/nested-sequence-of-half-open-intervals-with-non-empty-intersection). It should also be clear that, if we could enumerate every path through this binary tree, and thus every sequence of nested intervals, this would be equivalent to an enumeration of the Reals, one for each real number that is the limit of each unique sequence of nested intervals. More about that next. 42:Tb67,### Merging the Subdivisions back into One Enumeration Back to Cantor's diagonalization argument, what would it mean to construct the diagonal complement of any of these infinitely small subdivision enumerations? If there is only 1 number per subdivision, then the definition of the diagonal complement of these enumerations is not useful at best. It has become meaningless. Now that we have subdivided the original enumeration into a countably infinite number of subdivisions, resulting in enumerations for which the definition of the diagonal complement number no long has any meaning, what would happen if we try to merge these infinite subdivision enumerations back into one enumeration, to address the problem we deferred above? Could we possibly count backwards from infinity in order to back up one step before we got to the limit? If we could, then maybe the definition of the diagonal complement number would still be meaningless or maybe we can show there is no conflict, and then if we could repeat that an infinite number of times, we would arrive back at the original enumeration where the definition of the diagonal complement is still meaningless. The enumerations at the limit of this infinite binary tree of enumeration subdivision should have only one number in each enumeration, corresponding to the infinitesimally small intervals. Therefore, we _should_ be able to merge the countably infinite enumerations pairwise such that each merged enumeration will have two numbers. The two numbers in each merged enumeration will have an infinite number of digits in common followed by complementary last digits. These two numbers are not complementary of each other, however, since their complements are both in another merged enumeration; the complement numbers start with the complement of the infinite number of digits. So there is no conflict with the diagonal complement of any of these merged enumerations, no matter which order the two numbers are in. More generally, there should be no problem with any of these enumerations containing the two numbers they are supposed to contain. This pairwise merging of neighboring enumerations can be repeated any finite number of times and there with never be any conflict with the diagonal complement of any permutation of the finite number of numbers in the merged enumerations. There is in general, no problem enumerating any finite number of numbers. And we can generalize this pairwise merging of neighboring enumerations to the limit of an infinite number of steps. This requires only a countably infinity of steps, just as the subdivision process only required a countable infinity of steps. But now we can see that at every step, there is no conflict with the diagonal complement of any finite number of numbers. So why should there be a conflict at the limit where all subdivision enumerations are merged back into one enumeration? 43:T7a4, ## Breadth-first Enumeration of Countably Infinite Reals Let's review the countable enumeration of Reals that was presented previously (in [Enumeration of Countably Infinite Reals Breadth-First](https://observablehq.com/@dlaliberte/countably-infinite-random-real-numbers#cell-218)). You don't need to agree with that argument about the countable enumeration of the Reals in order to agree with the Refutation of Cantor's diagonalization presented above, since the latter doesn't depend on the former, but it will help if you at least understand it. The breadth-first enumeration and the binary tree visualization are copied below. We generate real numbers represented by number objects that are added to both the enumeration and the binary tree. The real numbers that you can see listed in the enumeration and visualized in the binary tree are expanded out to only a finite depth, though every real number is subsequently extended by an infinite number of randomly generated digits. The leaves of the binary tree show the current state of every real number generated so far, in numeric order top to bottom. Every number is also included in the enumeration table which is sorted in the order that they were generated. There are a few key points that might escape notice: 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.44:T75c,#### Every Combinations of Digits is Generated in the Enumeration and the Binary Tree Looking through all the numbers created for depth `d`, you can see on the right edge of the chart the prefix of digits of all the numbers generated so far, which have the form "0." followed by `d` binary digits corresponding to all the natural numbers between 0 and ${tex`2^d - 1`} (with '0' padding on the left of each number). E.g. for depth=6, these prefix 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, which represent prefixes of ${tex`2^d`} real numbers. This is the easy part, and it doesn't prove the Reals are countable. We argued previously (see [The Completeness of the Breadth-first Generator](https://observablehq.com/@dlaliberte/countably-infinite-random-real-numbers#cell-275) for the full proof of completeness) that the generation function for this enumeration will generate every finite combination of digits at every finite level. Furthermore, every number we generate starting with a finite prefix is a real number, not just a rational number, which you can see by noticing how each number, once created, is extended by an infinite sequence of randomly chosen binary digits. By induction, we can easily show that the argument extends indefinitely to any _finite_ depth. But that's still the easy part. To show that this generator can be extended to infinite depth, we need more than mere induction. By using transfinite induction, we can prove that we will generate every combination of digits and create a unique real number for each combination, and every number object thus generated is added to an enumeration list, even as the process is extended to infinity! 45:Tcf4,## Diagonal and Diagonal Complement Numbers are Defined Self-referentially Note that both the diagonal number and the diagonal complement number are defined using the digits that appear along the diagonal of all numbers in an enumeration. These definitions are self-referential or circular because the diagonal number and the diagonal complement number are expected to be included in the enumeration that is used to define the diagonal and diagonal complement numbers. This creates a situation where the presence of these numbers in the enumeration would necessarily affect their own definitions. While there is no obvious contradiction with including the diagonal number in the enumeration, even though it is self-referential, there is a problem with the definition of the diagonal complement number since it is not only self-referential, but it is defined in terms of the enumeration itself to necessarily be excluded from the enumeration. By the way, the diagonal number is similarly contradictory with the enumeration when it is generated in a way that guarantees it contains the complement of every number in the enumeration. (See the section on balanced enumerations for how this can be done.) And a complete enumeration of the real numbers between 0 and 1 would have to include the complement of every number in the enumeration. The diagonal complement number seems to be a valid number because it is represented by an infinitely long string of binary digits, just like any other number. However, the problem with this number is not with how it is represented independent of the enumeration, but rather with how it is defined _relative to the enumeration_. The diagonal complement number is defined using all the numbers in the enumeration itself, which means that it cannot be thought of as a separate, independent number. Moreover, this self-referential definition is contradictory since it is defined such that it is different from every number in the enumeration so that it must be excluded from the enumeration. Another famous self-referential contradictory definition is Russell's "set of all sets that don't contain themselves" (see [Russell's paradox - Wikipedia](http://go/wpda/Russell%27s_paradox)). This definition caused a crisis in mathematics, which resulted in effectively outlawing the construction of any set that contains itself, contradictory or not. We will examine other self-referential contradictory definitions in more depth later. But for now, we should begin to suspect that the self-referential contradictory nature of the diagonal complement definition, being an integral part of Cantor's Diagonalization argument, might be just as problematic as the set of all sets that don't contain themselves, and if so, Cantor's diagonalization argument which is based on this definition might not be valid. So, if the Reals are indeed countable, as shown above with the infinite complete binary tree of intervals, and with the breadth-first enumeration of the Reals, then we have a conflict with Cantor's arguments that the Reals cannot be countable. One resolution to this conflict is that, given the self-referential contradictory nature of the definition of the diagonal complement, we could agree that such definitions are at best problematic, if not universally invalid.46:T820,## Implications of the Reals being Countable Regardless whether a proof of the completeness of our enumeration was possible in Cantor's time, what would have been the implications of the Reals being countable? Would any contradictions result? It seems that the belief in the uncountability of the Reals has not resulted in anything substantial other than other proofs of uncountability or undecidability, effectively walling off huge mathematical territories that seemed otherwise impenetrable or incomprehensible. Maybe the major implication is to open up previously unexplored territory. The [Continuum Hypothesis](https://en.wikipedia.org/wiki/Continuum_hypothesis) is answered in the affirmative, by the way, since "there is no set whose cardinality is strictly between that of the integers and the real numbers" because they have the same cardinality. The contradiction that Cantor believed he had discovered regarding any possible enumeration of the Reals involves this diagonal complement number. (His first proof of the uncountability of the reals was not this Diagonalization argument but the Nested Closed Intervals argument, but it turns out they are very similar.) He defined a number that could not possibly be in the enumeration by explicitly making it self-referential and contradictory. This aspect of the definition was ignored or forgotten since it seemed like an otherwise valid definition of a number that should be in any complete enumeration. The fact that no enumeration of the Reals was available made it plausible that no such enumeration was possible, and so the apparent proof of that impossibility became acceptable without sufficient scrutiny. Actually, there was a lot of vehement criticism, but mostly on the side of denying the existence of any infinite sets at all, let alone uncountable infinite sets. No one had produced an enumeration of the Reals, or a proof that one must exist, so the vacuum was eventually filled with general consent regarding this concept of a previously inconceivable, uncountable cardinality of the Reals. 47:T10ab,### A Little more Rigour Here is how we could apply the diagonalization argument to the infinite binary tree of digits. (Adapted from an answer to: [How many paths are there in the in the full (infinite) binary tree?](https://math.stackexchange.com/questions/1977161/how-many-paths-are-there-in-the-in-the-full-infinte-binary-tree)) First assume that there exists a countably infinite number of paths and label them ${tex`P_0, P_1, P_2, ... `}. We will also use the convention that ${tex`P(d) = 0 `} indicates that the path ${tex`P`} turns left at depth ${tex`d`} and ${tex`P(d)=1`} indicates that it turns right. Now consider the path ${tex`Q(d) = 1 - P_d(d)`}. If all paths are represented by one of ${tex`P_0, P_1, P_2...`} then there must be a ${tex`P_m`} such that ${tex`P_m = Q`}. And by the definition of ${tex`Q`} it follows ${tex`P_m(d) = 1 - P_m(d)`}. We then can substitute in ${tex`m`} as the depth, so ${tex`P_m(m) = 1 - P_m(m)`}. However this leads to a contradiction if ${tex`P_m(m) = 0`} because substitution gives us ${tex`0 = 1-0 = 1`}, and alternatively, if ${tex`P_m(m) = 1`} then ${tex`1 = 1-1 = 0`}. Therefore there must exist more paths in this structure then there are countable numbers. [... Working out how to represent the infinite binary tree of intervals in math terms ... e.g. ${tex`I_{2^n}^k = [\frac{k}{2^n},\frac{k+1}{2^n})`} with ${tex`n \in \mathbb{N}`} and ${tex`k \in \mathbb{Z}`}. ] If we try to apply the analogous diagonalization argument to the infinite binary tree of left-closed intervals which correspond to the tree of enumeration subdivisions, we get a different story. All intervals here are left-closed and right-open. First assume that there exists a countably infinite enumeration of a set of infinite sequences of nested left-closed intervals derived from the infinite binary tree of intervals, and label them ${tex`I_0, I_1, I_2, ... `}. We will also use the convention that ${tex`I_k`} represents the ${tex`k`}th sequence of intervals and ${tex`I_k(d)`} represents the interval at depth ${tex`d`} (or the ${tex`d`}th member) of the sequence labeled ${tex`I_k`}. At depth `0`, ${tex`I_k(0)`} is `0` which represents the interval `[0, 1)`. At depth ${tex`d+1`}, ${tex`I_k(d+1) = 0`} indicates that the left subinterval of ${tex`I_k(d)`} is used, and ${tex`I_k(d+1)=1`} indicates that the right subinterval is used. Now consider the sequence of intervals defined by a function ${tex`Q`} of ${tex`d`} in terms of the enumeration of the set of sequences of intervals such that is different from every sequence of intervals in our list. It is defined as ${tex`Q(d) = 1 - I_d(d)`}. If all sequences of intervals are represented by one of ${tex`I_0, I_1, I_2...`} then there must be a ${tex`I_m`} such that ${tex`I_m = Q`}. And by the definition of ${tex`Q`} it follows ${tex`I_m(d) = 1 - I_m(d)`}. We then can substitute in ${tex`m`} as the depth, so ${tex`I_m(m) = 1 - I_m(m) `}. However this leads to a contradiction if ${tex`I_m(m) = 0`} because substitution gives us ${tex`0 = 1-0 = 1`}, and alternatively, if ${tex`I_m(m) = 1`} then ${tex`1 = 1-1 = 0`}. Therefore, given this argument, it appears there must exist more sequences of nested intervals than there are countable numbers. So this appears to be the same contradiction for both the binary tree of intervals and the binary tree of digits. However, we can easily see that, at every level of the binary tree of intervals, the union of all the intervals is the same as the whole interval ${tex`[0, 1)`}. Therefore no real number in the whole interval is excluded at any level of the binary tree, even at the limit, and moreover, **each real number corresponds to a unique interval at the limit**. So we have a contradiction between the argument that every real number is included in the interval and the argument that some real number(s) must have been excluded. How do we decide which argument is correct? We should be suspicious about the assumption above that we can define ${tex`Q`} in terms of a set of sequences of intervals such that it must be excluded from the set. Although it appears to be a legitimate definition, this is a self-referential contradictory definition that essentially defines nothing of any meaning. 48:T684,function generateBalancedEnumerationBreadthFirst(numNumbers = 64) { 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 += 2) { // Add one digit to every current number, and the complement digit to the complement number const currentNum = numbers[i]; const parentNode = currentNum.node; // Add a random digit to the current num. const nextDigit = currentNum.addNextDigit(); // Compute the other, complementary digit. const otherDigit = nextDigit == "0" ? "1" : "0"; // Add the other digit to the complementary num. const complementNum = numbers[i + 1]; const complementParentNode = complementNum.node; complementNum.addDigit(otherDigit); // Create a new number with the otherDigit. const newNode1 = parentNode.addDigit(otherDigit); const newNum1 = Real.construct(newNode1, index++); numbers.push(newNum1); // Create another new number with the nextDigit on the complementNum const newNode2 = complementParentNode.addDigit(nextDigit); const newNum2 = Real.construct(newNode2, index++); numbers.push(newNum2); } } // Return list of nodes by traversing the binary tree. return { tree: rootNode.traverseTree(), numbers }; }49:T59c,### The Merging of Countable Enumerations of Countable Enumerations of Reals is Countable In the following sections, we make several attempts to arrange that any possible diagonal complement number for an enumeration will either end up in the enumeration, or we will expose a contradiction. These attempts all fail in one way or another, but it is perhaps useful to understand why. Related to the well-known theorem that a countable union of countable sets is countable, we can do something analogous with enumerations. Assuming the Reals are countable, we should be able to generate a countable enumeration of countable enumerations of real numbers that collectively include all real numbers. The hard part is still making sure every real number, including every possible diagonal complement number, is in at least one of the enumerations. And if the Reals are in fact countable, this must be possible. In the following sections, each enumeration of Reals will clearly be a countable subset of the Reals, and each diagonal complement number will clearly appear in at least one of the other enumerations because we will create them that way. And there will clearly be a countable enumeration of these enumerations. When we merge these countable enumerations into one enumeration, it should contain all real numbers (between 0 and 1), despite the apparent contradiction with the diagonal complement of the merged enumeration. 4a:Te7d,#### Two Complementary Enumerations of Half the Reals between 0 and 1 We can create two complementary sets of real numbers by dividing the set of all Reals between `0` to `1` into two subsets. The first set consists of all real numbers from `0` to `1/2` (excluding `1/2`), and the second set includes the real numbers from 1/2 to 1. Both sets will have the same cardinality as the set of all real numbers, and they will be complements of each other. If we create enumerations for these sets, every number in the first enumeration will have a leading digit of `0` and therefore every possible diagonal number will also have a leading digit of `0` and the corresponding diagonal complement number will have a leading digit of `1`. Consequently, no diagonal complement of the first enumeration will be expected or present in the first enumeration, but it should be present in the second enumeration, assuming it is complete. And vice versa, no diagonal complement number of the second enumeration will be expected or present in the second enumeration, but it should be present in the first enumeration, assuming it is complete. Furthermore, we can ensure that the diagonal complement numbers for any enumeration we generate will definitely be present in the other enumeration in the following way: 1. As each digit is added to a number in one enumeration, we add its complement to the corresponding number in the other enumeration. Therefore, each enumeration will be the complement of the other. 2. Use the first number in each enumeration to generate the diagonal digits of all the rest of the numbers, as was done above (see Pre-generating One Random Number as the Diagonal). This pair of complementary enumerations might suggest there is a weakness in Cantor's diagonalization argument since no diagonal complement number of either enumeration is expected to be in that enumeration even though the cardinality of the sets being enumerated is the same as that of the set of all Reals. However, Cantor's argument only applies when the diagonal complement number is expected to be in the same enumeration, so it doesn't apply in this case. But if we ignore the first digit of all the numbers in these two complementary enumerations, a variation of Cantor's argument would still apply since a diagonal complement number could be defined for all the remaining digits. More about this later. Note what happens if we merge these two enumerations of Real numbers into a single enumeration. We must conclude that any possible diagonal complement number from either the first or second enumeration, assuming these are complete enumerations, will now be present in the merged enumeration. However, this merged enumeration will have its own diagonal complement number, which cannot be present in the merged enumeration itself. This means that the process of merging the two enumerations results in the creation of a diagonal complement number that did not exist in either the first or second enumeration, since all numbers in the merged enumeration are drawn from either the first or second enumeration. This may not be surprising to you, if you are expecting that the cardinality of the set of all possible diagonal complement numbers is the same as that of the set of all Reals. This would make sense, if the countable set of numbers in either enumeration must be missing an uncountable set of Reals that cannot be in either enumeration. However, the fact that we can generate a pair of enumerations that, together, do include diagonal complement numbers that would otherwise be assumed to be missing should at least make you wonder whether there is something else going on that is worth looking into.4b:T6db, #### An Infinite Chain of Enumerations Here is an outline of how we can generate a chain of enumerations using the breadth-first generator for each one. We will generate an infinite number of enumerations, with the first enumeration consisting of all random numbers, and each subsequent enumeration will have as its first number the diagonal complement of the previous enumeration. However, to avoid creating all of the enumerations at once, we will delay the creation of each enumeration until we have the first two digits of its first number. For every diagonal digit added to any enumeration, we will also add the complement of that digit to the first number of the next enumeration. Merging all the countable infinity of enumerations generated by this process into one enumeration could be done with a zig-zag approach across the numbers in all the enumerations, or we could have added each new number to the merged enumeration as it was created for any of the enumerations. One significant obstacle to implementing this merging process is that we don't know whether any number is distinct from all of the previously created numbers, but for this purpose, we can just add all numbers to the merged enumeration, and then, theoretically, we can just remove all the duplicates. This merged enumeration doesn't really add anything new that we don't get out of the very first enumeration or any of the subsequent enumerations, every one of which should be complete on its own, except that, with this approach, we know that every diagonal complement number constructed along the way will be in this merged enumeration. And yet, this merged enumeration will nevertheless have yet another diagonal complement that cannot be in the merged enumeration. 4c:T43e,#### An Infinite Enumeration of Complementary Enumerations We can generate another countable set of enumerations starting with one complete enumeration and use it to generate all the others. For each number in the initial enumeration, we will construct two enumerations. The first enumeration will start with that number as both the first number and the diagonal number, while the second enumeration will be the exact complement of the first. Therefore every pair of these complementary enumerations will include the diagonal complement of the other enumeration as its first number. Every one of these countable infinity of enumerations, including the initial enumeration, will be complete, assuming the proof of completeness is correct, so if we merge all these enumerations into one merged enumeration, the result will not add anything we didn't already have, except it will be clear that the diagonal complement number for every enumeration will be included in the merged enumeration. Nevertheless, this is still not enough if none of these enumerations is actually complete.4d:T6ea,#### A Countable Infinity of Enumerations of Sets of Infinitesimals In the same way we subdivided the set of Reals between 0 and 1 into two subsets with half the range of numbers but the same cardinality, we can create N subsets with ranges of numbers that have boundary values of 0, 1/N, 2/N, ..., N-1/N, and 1. Every enumeration of any one of these subsets will have a diagonal complement number that should be a member of another subset, if we use binary notation and constrain N to be a power of 2. E.g. if N is 4, we will create four subsets; all numbers in the first subset will have leading "00" digits, and the complement numbers are all in the fourth subset with leading "11" digits. As N grows larger and larger, the number of subsets increases and the range of each subset decreases, while the cardinality of each subset remains the same (as all Reals). However as N approaches infinity, the number of subsets grows to infinity, and the range of each subset shrinks to 0, but the cardinality of each subset suddenly drops all the way from infinity down to 0. But wait, does that make sense? If we consider the possibility that an infinitesimal (a value that is smaller than any real number) could be considered a real number (and thus, the smallest real number), then as N approaches infinity, the range of each subset could be not 0 but 1 infinitesimal, with 1 infinitesimal/real number in each of an infinite number of subsets. In this case, the union of the _countable_ infinity of these subsets would be all real numbers between 0 and 1. Furthermore, there is no problem with any diagonal complement number for any of these subsets since every number n between 0 and 1 has a complement which is 1 - n that is contained in another of these subsets.4e:T719,## Extension of Cantor's Diagonalization Argument to Include all Permutations of the Enumeration It is often suggested that the diagonal complement number is not the only such number that supports Cantor's diagonalization argument. After all, the diagonal complement number is only one number that happens to be more easily identifiable, and if that were the only missing number then the enumeration would still be countable just by adding one. (i.e. infinity + 1 is still infinity) But assuming Cantor's diagonalization argument is sufficient to show that the Reals are uncountable, there must be an uncountable number of other numbers not present in any countable enumeration of Reals. What other numbers might these be, and can we define them in terms of the enumeration itself, similar to how the diagonal complement number is defined? Extending Cantor's argument in various ways could allow us to find other similarly defined numbers that cannot be contained in the enumeration. Setting aside the question of whether the enumeration is complete, the enumeration is definitely countable, no matter what numbers it might be missing. (I.e. we are not trying to generate an uncountable enumeration, whatever that might be.) So one thing we can do with this countable enumeration is that we can permute the order of the numbers resulting in a different order for the very same numbers in the enumeration. For example, we could swap the first two rows of the enumeration to result in a permutation that still contains the same numbers. Technically, since an enumeration is an ordered sequence, this new ordering represents a new enumeration, but since it is derived from the numbers in the original enumeration by merely permuting its members, let's refer to this as a **permutation of the enumeration**. 4f:T576,### Every Diagonal Complement for Any Permutation *Must* be Absent from Every Permutation When we permute the elements of an enumeration, the resulting permutation will have its own diagonal and diagonal complement numbers. The new diagonal complement number must not be present in the permuted enumeration, and it must also be absent from the original enumeration. Similarly, the original diagonal complement number must not be present in the permuted enumeration because the permuted enumeration contains the same numbers as the original enumeration. We can apply this argument to every possible permutation of the enumeration. For each permutation, there will be a corresponding diagonal complement number that must not be present in any of the permutations of the same enumeration. Since some permutations may have the same diagonal complement numbers as other permutations, a natural question to ask is how many unique diagonal complement numbers will be generated for all possible permutations? It is worth emphasizing that none of the diagonal complement numbers for any of the permutations can appear in any of the other permutations. This is because the diagonal complement for each permutation will necessarily be different from every number in that permutation and in _every_ permutation of the enumeration, since all permutations contain the same numbers as the original enumeration.50:Tb36,### A Reasonable Enumeration There is an essential property of any _reasonable_ enumeration of real numbers represented in binary that we will depend on. Let's define a **reasonable enumeration** as an enumeration that, if we look in every column of digits in the enumeration, we will see an infinite number of rows with a '0' and an infinite number of rows with a '1' in that column. If this is not the case for any column, then the enumeration would clearly be missing infinitely many numbers that have '0's or '1's in that column, which would be unreasonable as a candidate for a complete enumeration. Note that we are only considering enumerations of all Reals between 0 and 1 as possibly being reasonable enumerations. So even though the set of numbers between 0 and 1/2 would have the same cardinality as all Reals, an enumeration of that set would have an infinite number of '0's in the first column, and therefore, it would not meet this definition of a _reasonable_ enumeration. We are also not considering the possibility of enumerations that might be split into two infinite lists, such that all the numbers with '0's in one column might be in one list while the rest are in the other list. Even though we could conceivably deal with a countable number of such countable lists, since they could be merged into one countable list, we are ruling that out here. A second criteria for being a reasonable enumeration is that every consecutive span of '0's in each column of a reasonable enumeration will be finite in length, and the same must be true for every consecutive span of '1's. If this were not the case, then some span of '0's or '1's must be infinitely long, and an infinitely long span of '0's would mean that there could only be a finite number of '1's, and similarly, an infinitely long span of '1's would mean there could only be a finite number of '0's. So this second criteria can actually be inferred from the first, and it turns we can also infer the first criteria from the second, and therefore, curiously enough, they are equivalent. An enumeration would not have to be a complete enumeration in order to be a reasonable enumeration. It could be missing an infinite number of numbers that we intended to be in the enumeration and it still might be a reasonable enumeration as long as it meets the criteria of the definition. But if a complete enumeration of reals between 0 and 1 is possible, it would also necessarily be a reasonable enumeration. Therefore, this property of having an infinite number of rows with both '0's and '1's and finite spans of consecutive '0's and '1's, holds for any reasonable enumeration of the real numbers between 0 and 1. And consequently, this means that we can always find either a '0' or '1' in any column starting from any row by looking through only a finite number of subsequent rows. 51:Ta6c,### Permutations with Rejections Results in a Contradiction To correctly permute an enumeration and generate a specific target number along the diagonal, we must ensure that every number in the enumeration is eventually used. However, this requirement will not be met if the diagonal number is the complement of an existing number in the enumeration, because that number can never be used in the permutation. So what would happen if we reject any such number from the permutation that is the complement of the diagonal? Since this is not the same as a normal permutation, let's call it a **permutation with rejections**. It has all the same properties as a normal permutation, but we are allowed to reject a finite number of elements relative to the list it was generated from. Let's start by generating the diagonal that is the complement of the first number in the enumeration. Since it will be incompatible with the diagonal complement, we must reject it. After we reject the first number, the remaining numbers in the permutation will have exactly the same "reasonable" property as the original enumeration. We know that is true because every swap was a finite distance, so all spans of '0's and '1's will still be finite in length. That is, the resulting enumeration without this first number is still a reasonable enumeration and therefore, we can still generate _any_ number along the diagonal using only the remaining numbers just as we could for the original enumeration. Now let's take the obvious next step of repeating this process any finite number of times. After each permutation rejects another number, no matter how many numbers we have rejected from the enumeration so far, we can still generate _any_ number along the diagonal. That is, by induction we can show that any finite number of numbers can be rejected from the enumeration this way. Let's say it again with emphasis: _no matter how many numbers we have already rejected from a reasonable enumeration, it will still be a reasonable enumeration, and that means we can keep on rejecting numbers forever and it will still be a reasonable enumeration_. When we repeat this process forever, continuing on to an infinite number of steps, the result appears to be that _every_ number would be rejected from the enumeration. So it looks like we have a problem. Since we can permute an enumeration such that _any_ number can be generated along the diagonal, including any number that is in the enumeration, as long as we reject any such number, this seems to imply that we can reject all numbers from the enumeration one at a time until, after infinite repetitions, none are left. 52:Tcea,### Permutations without Rejections Also Result in Contradictions Let's repeat this process of generating every permutation such that the diagonal complement is the same as one of the numbers in the enumeration, but start each time with the original enumeration rather than from the result of rejecting numbers from the enumeration. Since we showed that every number that is in the enumeration will be incompatible with the diagonal complement number for _some_ permutation of the enumeration that we can generate, and the diagonal complement for any permutation must be missing from every permutation, that would imply that every number in the original enumeration is incompatible with some permutation of the enumeration. But of course, we started with a countable infinity of numbers in the enumeration, so if all numbers in the enumeration conflict with the diagonal complement of some permutation, that seems to imply that either no numbers can be in the enumeration, or perhaps no permutations can be allowed. If we declare that no permutation is allowed if it results in a diagonal complement that is identical to any existing number in the enumeration, that would seem to mean that no permutations are allowed at all since the diagonal complement number for an arbitrary permutation _might_ already be in the enumeration. And we can't tell whether that might happen for any arbitrary permutation. A program that generates random permutations (limited to an infinite number of finite-distance swaps) of an enumeration doesn't have any knowledge of whether the diagonal complement of the resulting permutation will conflict with any number that is in the enumeration. It might still be the case that some permutations of the enumeration exist such that the diagonal complement numbers don't conflict with any existing number in the enumeration, and perhaps there are an uncountable number of such permutations. These are the permutations we should be concerned about, since all the permutations that conflict with numbers in the enumeration might just be ruled out as invalid. If there are a uncountable number of additional valid permutations that have no conflict with numbers in the enumeration, then all the diagonal complement numbers of those permutations would be missing from the enumeration. But unfortunately, we can't tell if that is the case at all since, for any random permutation, it _might_ have a diagonal complement that does conflict or it might not conflict. Alternatively, is it the case that a random permutation generator could always avoid the possibility of generating a conflicting permutation? How could a random permutation generator tell the difference between a permutation that does conflict with a number in the enumeration versus one that does not? For a permutation that does conflict, this conflicting number will keep getting swapped with rows further and further down the list, but it will always be only a finite distance from where it started. Only at the limit would we find out that some number was never used because it was in conflict with every digit of the diagonal complement. And that means the random permutation generator cannot avoid the possibility of generating a permutation that does conflict with a number in the enumeration. 53:T1175,## Could Cantor have found this enumeration of the Reals? Even if we have successfully refuted Cantor's diagonalization argument, that by itself doesn't mean we have proved that the Reals are countable. It only proves that Cantor's proof that they are uncountable is invalid. But we nevertheless have separately proved the completeness of the breadth-first enumeration of the reals, which constitutes proof that all Reals are countable. And we also found a contradiction in the assumption that the Reals are uncountable that is independent of Cantor's diagonalization argument. Suppose Cantor had thought of this breadth-first enumeration of the Reals when it was, at first, trying to discover such an enumeration. Would he have then been satisfied that the Reals are countable and never bothered to create his two arguments that the Reals must be uncountable? Perhaps he did think of this enumeration, but was not convinced that it was a complete enumeration. The proof would have to involve doing the equivalent of what we did and maybe he didn't have the tools to construct such a proof. Is the proof of completeness actually valid, or did we make a fundamental mistake? Or would such a proof also imply that every infinite sequence necessarily includes its limit set? Regardless whether a proof of the completeness of our enumeration was possible in Cantor's time, what would have been the implications of the Reals being countable? Would any contradictions result? It seems that the belief in the uncountability of the Reals has not resulted in anything substantial other than other proofs of uncountability or undecidability, effectively walling off huge mathematical territories that seemed otherwise impenetrable or incomprehensible. Maybe the major implication is to open up previously unexplored territory. The contradiction that Cantor believed he had discovered regarding any possible enumeration of the Reals involves this diagonal complement number. (His first proof of the uncountability of the reals was not this Diagonalization argument but the Nested Closed Intervals argument, but it turns out they are very similar.) He defined a number that could not possibly be in the enumeration by explicitly making it self-referential and contradictory. This aspect of the definition was forgotten since it seemed like the definition of this number was otherwise valid such that it should be in any complete enumeration. The fact that no enumeration of the Reals was available made it plausible that no such enumeration was possible, and so the apparent proof of that impossibility became acceptable without sufficient scrutiny. Actually, there was a lot of vehement criticism, but mostly on the side of denying the existence of any infinite sets at all, let alone uncountable infinite sets. No one had produced an enumeration of the Reals, or a proof that one must exist, so the vacuum was eventually filled with general consent regarding this concept of a previously inconceivable, uncountable cardinality of the Reals. ### If the Enumeration of Reals was Known First, Would the Diagonal Complement Number be Considered Valid? If an enumeration of the Reals was provided, such as the one shown here, would the construction of the diagonal complement number still be considered valid? Is the construction of a diagonal complement number also valid for an enumeration of rational numbers? It is assumed that the diagonal and diagonal complement numbers of an enumeration of Rationals must be irrational. But could such a diagonal complement number for an enumeration of Rationals ever be a rational number? If so, then that would seem to prove that the rational numbers must also be uncountable, except we know of other ways to show they are countable. This diagonal complement number, assuming it is a valid number, is only defined with a function that computes as many digits as requested, like other computable numbers, but in this case, it takes each successively added diagonal digit from an enumeration and complements it. Therefore, its precise value is never known until the limit is reached, so by definition, one might imagine we have to wait until the enumeration is "completed" before we can determine whether this number is in the enumeration, which will never happen except, in some sense, at the limit. But regardless what its precise value might be, we do know that it can never be present in the enumeration.54:Te86,## An Abbreviated History of this Refutation I for one didn't try to seriously find a refutation for Cantor's arguments, and didn't even imagine it was possible, until I could first see (and prove to myself) how the Reals are countable independent of Cantor's arguments, and I suspect a similar approach might help a few others who are more like myself. You'd have to be open to the possibility that the Reals could be countable, so it probably won't help people who are firm believers in the correctness of Cantor's arguments, so if that includes you, then you are probably more interested in whether the refutation is valid, and you may be assuming it can't possibly be valid. Once I could see how the Reals can be shown to be countable, I went back to Cantor's arguments to try to figure out what could be going wrong there. It is admittedly a tough puzzle, and it didn't help much to look into the many attempts by other people to refute the diagonalization argument specifically, since most are easily shot down. But it did help foment ideas, since each attempt seemed to have a kernel of a good idea, though framed in a seriously flawed argument, with a couple rare exceptions. I spent most of the last couple years trying to find a valid refutation, and was feeling rather frustrated by all the dead ends I encountered. But that didn't dissuade me from accepting the proof of countability of the Reals, though not because I was just stubbornly believing it, but because it appears valid on its own. One possible outcome of all this is more of a stalemate. If the Reals appear to be both countable and uncountable by two separate proofs, both appearing to be valid, we wouldn't be able to decide whether the Reals are countable or uncountable. It would not be the first time such a thing has happened in math, that we are left with an undecidable set of alternatives, though usually we are left with proofs of unprovability rather than conflicting proofs. And if it turned out to not be possible to refute Cantor's arguments, then people would have a hard time considering the possibility that there might also be a valid proof that the Reals are countable. But even assuming I could come up with a valid refutation, that would nevertheless leave a few questions open. What about his other arguments, the nested closed intervals, and the multi-dimensional generalization of that, which are at least closely related to the diagonalization argument though not identical? Will refuting the diagonalization argument be enough to also refute the others, or is something more going on there? Are there any other ways to prove the Reals are uncountable that don't rely on these, directly or indirectly? I suspect not, though discussion I have found on mathexchange doesn't make the answer completely clear. And assuming valid refutations could be found for all known proofs of uncountability, we are left with not knowing whether there might still be another way to prove uncountability. Given all that, and the fact that the proof of the countability of the Reals is not all that difficult to understand, if you take it seriously enough to go through the details, it seemed like a good approach to start with that first. So I cleaned up the demonstration and proof of countability, as best I could, but I still did not want to make it public without dealing with Cantor's arguments once again. Only recently did I finally I find a valid refutation of diagonalization based on some earlier ideas. It was the last article I wrote up, so the series is presented in that same order. Having done that, this refutation can stand on its own, since there is no dependence on proving the countability of the Reals.55:[] 32:{"id":"2555290b866cbe32","slug":"refutation-of-cantors-diagonalization","title":"Refutation of Cantor's Diagonalization","thumbnail":"edcdd8f0696d53396a65f61ecfbc834ad57ede1b09f8f080667c3140eece2120","access_level":"public","create_time":"$D2021-09-17T02:22:26.405Z","update_time":"$D2023-06-28T03:11:33.633Z","view_time":null,"first_public_time":"$D2022-12-16T00:27:33.218Z","has_unpublished_edits":null,"fork":false,"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":2118,"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":"Refutation of Cantor's Diagonalization","cells":[{"id":0,"value":"# Refutation of Cantor's Diagonalization\n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":775,"value":"## Abstract\n\nIn the previous post, [Countably Infinite Random Real Numbers](http://observablehq.com/@dlaliberte/countably-infinite-random-real-numbers), we showed how the real numbers could be enumerated using a breadth-first generation of random real numbers, and we presented proof of its completeness there. We also show in [Infinite Binary Tree of Intervals](https://observablehq.com/@dlaliberte/infinite-binary-tree-of-intervals) that the Reals must be countable. Here we examine Cantor's diagonalization argument regarding any possible candidate enumeration of the real numbers. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":767,"value":"This document is close to being \"finalized\". If you are interested in this subject, please read the earlier notebooks first:\n\n- [Number Objects](https://observablehq.com/@dlaliberte/number-objects)\n- [Computable Real Numbers](https://observablehq.com/@dlaliberte/computable-real-numbers)\n- [Countably Infinite Random Real Numbers](http://observablehq.com/@dlaliberte/countably-infinite-random-real-numbers)\n- [Infinite Binary Tree of Intervals](https://observablehq.com/@dlaliberte/infinite-binary-tree-of-intervals)\n\nA refutation of Cantor's nested closed intervals argument is being prepared.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":771,"value":"toc(\"h2, h3, h4, h5, h6\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"## Cantor's Diagonalization Argument\n \n[Cantor's Diagonal Argument](https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument) argument can be summarized as follows: The assumption that we can generate an enumeration of all real numbers between 0 and 1 must be false because, for _any_ such candidate enumeration, we can construct a number from the complement of the diagonal digits of each number in the enumeration such that this number, hereafter referred to as the _diagonal complement_, cannot be in the enumeration even though it ought to be, and therefore the enumeration must be incomplete, which implies the set of all real numbers must be uncountable.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"### The Diagonal Complement Number Cannot be in the Enumeration\n\nWe agree that the number defined as being composed of the diagonal complement digits of an enumeration cannot be included in the enumeration. This may be a surprising way to start a refutation of Cantor's diagonalization argument. But we cannot deny that the digits of the diagonal complement number are constrained to necessarily be different from the diagonal digit of each and every number in the enumeration, and consequently the diagonal complement number cannot be the same as any number at any finite position in the enumeration. \n\nCantor's conclusion is that, because the diagonal complement number is a valid real number that is expected to be included in a complete enumeration of the Reals, but it can never be present, this must mean the enumeration cannot be complete, which means the assumption that the Reals are countable must be wrong, and therefore, the Reals must be uncountable. \n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2116,"value":"\nBut we independently proved (in [Infinite Binary Tree of Intervals](https://observablehq.com/@dlaliberte/infinite-binary-tree-of-intervals)) that the Reals must be countable. We also showed (in [Countably Infinite Random Real Numbers](http://observablehq.com/@dlaliberte/countably-infinite-random-real-numbers)) that the enumeration generated by a breadth-first algorithm is complete, and therefore the Reals are countable. But the Reals can't be both countable and uncountable. \n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2112,"value":"$34","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":898,"value":"#### Pre-generating One Random Number as the Diagonal\n\nWe can see how the diagonal complement number is excluded from the enumeration by using a variation of the generator of one random real number. We start by adding a pre-generated random real number as the first number in the enumeration, and we also use each of its digits as the diagonal digit of each number we add to the numeration. Furthermore, every number that we add to the enumeration after the first one will have a prefix that is the complement of this diagonal number up to, but not including, the diagonal digit. Thus this enumeration will only contain the diagonal number and a countable infinity of attempts to include the diagonal complement number in the enumeration.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":907,"value":"mutable nRandomDigits = []","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":905,"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":900,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":902,"value":"diagonalComplementNumbers = generateOneRandomNumberAsDiagonal(\n 0 + diagonalComplementOptions.depth,\n diagonalComplementOptions.pregenerateX,\n false\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":921,"value":"showEnumerationTable(diagonalComplementNumbers)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1399,"value":"\nIn the enumeration table above, you can see that, while the diagonal number can be in the enumeration, the diagonal complement number can never be in the enumeration, at least not at any finite position.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":910,"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":914,"value":"viewof diagonalComplementOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":917,"value":"vlembed(\n makeTreeVegaSpec(diagonalComplementNumbers.tree, {\n title: \"Create X along Diagonal\",\n width: Math.min(850, 600 + diagonalComplementOptions.depth * 5),\n height: Math.max(300, 30 + diagonalComplementOptions.depth * 12),\n hideLabels: diagonalComplementOptions.depth > 25,\n linkShape: \"diagonal\", // diagonalComplementOptions.linkShape\n colorScheme: \"bluepurple\"\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":659,"value":"$36","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":516,"value":"### A Frequent but Flawed Refutation\n\nMany people who attempt to refute Cantor's argument point out that, because the diagonal complement digits generated from the first `d` numbers _can_ appear in the enumeration, but further down in the enumeration after the first `d` numbers, that effectively refutes Cantor's argument. But that counter-argument reflects a misunderstanding of Cantor's argument. He would certainly agree that a finite-length prefix of the diagonal complement can appear in many numbers further down the list. Nevertheless, for every one of those numbers, once its diagonal digit is added, it will conflict with the corresponding digit of the diagonal complement number. This is demonstrated in the previous example.\n\nBut furthermore, Cantor was not arguing about just a finite-length prefix of the diagonal complement number but the entire infinite length of this number generated by complementing the diagonal digits of every number in the enumeration.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":531,"value":"$37","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1578,"value":"$38","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1417,"value":"$39","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1582,"value":"\nHowever, we have accomplished one thing by subdividing the enumeration into two complementary enumerations. Specifically, **we have avoided any conflict with the first digit of all possible diagonal complement numbers of the subdivision enumerations**.\nThis is true of both subdivisions of the original enumeration, though, again, this is not true of the original enumeration or the result of merging the two complementary subdivisions into one enumeration. Still, this small step represents one bit, literally, of progress that we can leverage further.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1426,"value":"$3a","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2092,"value":"### First Three Levels of Enumeration Subdivisions\n\nHere is a table showing the first three levels of the subdivisions of the enumeration.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1517,"value":"\n\n\n\n \n \n \n \n \n\t\n \t\t\n \n\t\t\t\n\t\t\n\t\t\n \n\t\t\t\n\t\t\t\n\t\t\n\t\t\n \n\t\t\t\n\t\t\t\n\t\t\t\n\t\t\t\n\t\t\n\t\n

Level	Subdivisions of Enumeration
0	0. ... All numbers between 0 and 1: [0, 1)
1	.0... All numbers between 0 ad 1/2: [0, 1/2)	.1... All numbers between 1/2 and 1: [1/2, 1)
2	.00... [0, 1/4)	.01... [1/4, 1/2)	.10... [1/2, 3/4)	.11... [3/4, 1)

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1542,"value":"\nAnd of course, we can repeat this process `n` times, for any finite number `n`. After the `n`'th repetition, we will double the number of complementary enumerations compared to the `n-1`'th repetition, and **we will avoid any conflict with the first n digits of all possible diagonal complement numbers of the subdivision enumerations**. \n\nEven though we appear to have avoided any conflict between all possible diagonal complement numbers in any of the ${tex`2^n`} subdivision enumerations, we still have an infinite number of digits remaining, and the cardinality of the subsets of the Reals corresponding to each subdivision enumeration is still the same as for all the Reals. So in an important sense, we have made no progress at all. However, we can go much further than a finite number of steps.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1461,"value":"$3b","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2081,"value":"\n### Infinite Binary Tree of Subdivision Enumerations\n\nHere is a table showing an infinite tree of subdivisions of the enumeration, where we show the prefix of digits that all numbers in each subdivision have in common. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2087,"value":"$3c","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1557,"value":"$3d","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1600,"value":"$3e","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1598,"value":"\nThus, each enumeration, once it has been created, will be replaced an infinite number of times all the way out to the limit. And therefore, we can simply count the number of enumerations created along the way to count the total number of enumerations. At level `i` we have ${tex`2^{i}`} enumerations, half of which were created previously, and the other half of which are newly created. We repeat the process for a countable infinity of levels, so this process will result in a countable infinity of subdivision enumerations at the limit.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1830,"value":"$3f","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1727,"value":"$40","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1456,"value":"$41","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1495,"value":"$42","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2041,"value":"\nBut if there are objections, we can safely avoid this line of reasoning by directly merging all the countable infinity of subdivision enumerations. The merged enumeration of the countable infinity of subdivision enumerations will have the same numbers that we started with in the original enumeration. By Cantor's diagonalization argument, somehow, this merged enumeration will have a diagonal complement number that could not have been in any of the countable infinity of subdivision enumerations, even though the intervals associated with the subdivision enumerations cover the entire range of real numbers between 0 and 1. If the Reals are actually countable, as we saw above and more below, and this diagonal complement number is nevertheless missing from the merged enumeration, that would mean the enumeration process itself can never be complete even for a countable set. But that also doesn't make sense.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":472,"value":"$43","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":474,"value":"import {generateAllNumbersBreadthFirst} from \"@dlaliberte/countably-infinite-random-real-numbers\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":492,"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":509,"value":"showEnumerationTable(breadthFirstNumbers)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1245,"value":"The above enumeration table corresponds to the following binary tree. Every time you click Regenerate or adjust the Depth, both the enumeration table and the binary tree will be regenerated from scratch.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":494,"value":"viewof replayGenerateAllNumbersBreadthFirst = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":482,"value":"viewof breadthFirstOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":507,"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":514,"value":"$44","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1618,"value":"### Bridging between Countable Subdivision Enumerations, Nested Intervals, and all Reals\n\nThese real numbers also correspond by a bijection with all possible sequences of nested intervals described above when investigating the binary tree of subdivisions of the enumeration. The way we enumerate the reals is by creating one real number for each node of the binary tree, which is equivalent to choosing one of the infinite number of real numbers that are in the subtree of that node to be the representative of that node. This infinite set of reals associated with each node is also the same set of numbers as in the subdivision enumeration that would be in the corresponding location in the binary tree of subdivision enumerations.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":45,"value":"$45","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1658,"value":"$46","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1615,"value":"---\n\n---\n\n## ---------------------------- **Restructuring this document...** Following sections may or may not end up in the final document.\n\n---\n\n---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":2051,"value":"$47","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":970,"value":"### A Balanced Enumeration Includes the Complement of Every Number in the Enumeration\n\nIs there a way to ensure that an enumeration will necessarily include the complement of every number in the enumeration? Yes, easily. We could simply modify any generator algorithm such that, for every number it creates, a second number will also be created that is constrained to always be the complement of the first.\n\nLet's call an enumeration that necessarily includes the complement of every number in the enumeration a \"**balanced enumeration**\"\". \nAny number that is missing from a balanced enumeration implies its complement is also missing. Therefore, given a balanced enumeration, since we know all possible diagonal complement numbers must be excluded from the enumeration, we can conclude that all possible _diagonal_ numbers also must be excluded. \n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1002,"value":"In the following, we generate a balanced enumeration starting with the bounding numbers for 0 and 1.\nAs we iterate through all numbers that have been previously generated, two at a time, every pair of numbers will be complementary. We add a randomly chosen digit to the first number of each pair and the complement of that digit to the second number. Then, we create two new numbers with the same prefixes as the original pair of numbers, but with the complement of those same two digits. I.e. if `A` and `B` are two existing complementary numbers, and `r` is a random digit with complement `s`, then at the next level we will have:\n\n```\nAr\nBs\nAs\nBr\n```\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":974,"value":"$48","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":978,"value":"breadthFirstBalancedNumbers = (replayGenerateBalancedEnumerationBreadthFirst,\ngenerateBalancedEnumerationBreadthFirst(\n Math.pow(2, 1 + breadthFirstBalancedOptions.depth)\n))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":983,"value":"viewof replayGenerateBalancedEnumerationBreadthFirst = html``\n ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":981,"value":"viewof breadthFirstBalancedOptions = form(html`\n`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":986,"value":"vlembed(\n makeTreeVegaSpec(breadthFirstBalancedNumbers.tree, {\n title:\n \"Generate Countable Reals Breadth-First and Balanced to Depth \" +\n (breadthFirstBalancedOptions.depth + 1),\n width: 600 + breadthFirstBalancedOptions.depth * 10,\n height: Math.max(\n 300,\n 50 + Math.min(2000, Math.pow(2, breadthFirstBalancedOptions.depth) * 18)\n ),\n hideLabels: breadthFirstBalancedOptions.depth > 7\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1030,"value":"Compare each adjacent pair of numbers in the enumeration table below to see that they are complements of each other.\n\nThe resulting enumeration is basically the same as for the breadth-first algorithm, except for this additional constraint that for every number in the enumeration, its complement will definitely be in the enumeration. And since the diagonal complement number is always excluded from any enumeration, that means the diagonal number must also be excluded.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":991,"value":"showEnumerationTable(breadthFirstBalancedNumbers)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1046,"value":"$49","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1039,"value":"$4a","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":894,"value":"$4b","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1072,"value":"$4c","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1053,"value":"$4d","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1079,"value":"#### A Countable Infinity of Incomplete Enumerations is Still Incomplete\n\nDespite the several attempts given above to construct a countable infinity of enumerations that contain all possible diagonal complement numbers, these all fail to be convincing if the enumerations are not, in fact, complete. And it doesn't help to add a countable infinity of diagonal complement numbers if there are actually an uncountable infinity of missing numbers.\n\nWorse yet, the set of all possible diagonal complement numbers for all possible countable enumerations of real numbers, assuming they must be incomplete, might not include all the missing real numbers. So we have to ask what other ways could these alleged missing number be defined such that we have to account for them as well.\n\nThe only possibly viable solution given above involves the extension of the Reals to be the same as the Hyperreals, such that a countable infinity of infinitesimals can cover the continuum between 0 and 1.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":73,"value":"$4e","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":720,"value":"\nIt may be worth noting that we don't need to physically permute the enumeration to determine its resulting diagonal complement number. It is equivalent to simply permute the row indices of the numbers in the enumeration to generate the diagonal complement number for the permuted enumeration. \n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1308,"value":"There is an important constraint on the types of permutations we might allow. In order to permute an enumeration into another enumeration, we must do so in a way that doesn't subdivide the enumeration into more than one list. A finite permutation, which consists of only a finite number of row swaps, and an infinite tail that remains the same (called \"fixed points\"), would qualify, but that won't be enough for the purpose we have ahead. We will need infinite permutations in which an infinite number of rows can be moved but only by swapping with other rows that are a finite distance away from each other. A single permutation can be composed of an infinite number of such finite distance swaps.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":81,"value":"$4f","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":819,"value":"If we want to generate a list of all possible permutations of the original enumeration of the Reals, we might have a problem, since the number of such permutations of a set grows even faster than the number of subsets of a set. Specifically, the number of possible permutations of a set of size `n` is `n!`, while the number of elements in the power set (the set of all subsets) of a set of size `n` is ${tex`2 ^ n`}. Therefore, no matter what the cardinality of the power set of natural numbers is, the number of permutations of the natural numbers is at least as large.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":758,"value":"Fortunately, regardless what the size of the set of permutations is, we can nevertheless define it mathematically and derive from it another set containing the unique diagonal complements from each permutation. Every one of these diagonal complement numbers must be absent from all permutations of the enumeration.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1090,"value":"### We Can Choose a Permutation that Results in Any Specific Diagonal Number\n\nNow let's turn the problem around to ask: Can we select the appropriate rows of the enumeration to generate the corresponding permutation such that a specific target number appears along the diagonal? \n\nTo make this possible, for each digit of the target number, we need to be able to find a previously unused number in the enumeration. We should also try to use every number in the enumeration eventually, but this requirement turns out to be central to the problem posed by Cantor's Diagonalization argument.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1106,"value":"$50","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1304,"value":"### Generating any Number Along the Diagonal Results in a Contradiction\n\nBack to the problem of creating a permutation such that a specific target number appears along the diagonal.\nBecause we can always find a row in a reasonable enumeration that contains the next digit of the target number by looking through a finite number of rows, and because this process can be repeated for each digit of the target number, the overall process of generating the entire target number along the diagonal is countable (that is, it has a countable infinity of steps). And that means it will always be possible to construct _any_ target number along the diagonal, with one exception, noted below.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":135,"value":"\nTo build a permutation of an enumeration that generates a specific target number along the diagonal, we will compare each digit of the target number with the diagonal digit of each subsequent row. If the diagonal digit matches the target number, we can move on to the next digit and the next row. If it does not match, we need to find another row that is a finite number of rows further down to swap with this one before we can move on. This will always be possible for a reasonable enumeration.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1297,"value":"\nSince we can build a permutation with any target number along the diagonal, let's consider what happens when the target number is the complement of an existing number in the enumeration. In this case, the existing number would be incompatible with the diagonal at every digit, so as we generate the permutation, every time we try to use this number again, it will always be swapped with another number a finite number of rows further down in the enumeration. Consequently, it will _never_ be used in a row of the permutation, but will effectively be pushed out of the enumeration.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1300,"value":"$51","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":546,"value":"$52","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1358,"value":"But where did we go wrong? Is the problem with how we permuted the enumeration? Yes, actually. A permutation of all numbers in the enumeration would have diagonal complement numbers that would never conflict with any numbers in the enumeration, otherwise such a number would be rejected, and thus it is not a full permutation.\n\nSo even all this is not a correct refutation of Cantor's diagonalization argument. But stay tuned.. There is more coming.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1123,"value":"### The Cause of the Contradiction\n\nWe can re-examine each step more closely, but the most suspicious component is the self-referential contradictory definition of the diagonal complement number. Even though it seems like a valid number, the fact that it is defined in terms of an enumeration to necessarily conflict with every number in the enumeration, but it is expected to be in the enumeration, means it is a self-referential contradictory definition.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":592,"value":"$53","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1287,"value":"$54","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":502,"value":"import { toc } from \"@nebrius/indented-toc\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":329,"value":"import { Table } from \"@observablehq/table\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":487,"value":"import { form } from \"@mbostock/form-input\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":498,"value":"vlembed = require(\"vega-embed\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":500,"value":"import {\n Real,\n Rational,\n Zero,\n One,\n BinaryTreeNode,\n makeTreeVegaSpec,\n showEnumerationTable,\n digitsToNumber\n} from \"@dlaliberte/number-objects\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":912,"value":"import { button } from \"@bartok32/diy-inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1009,"value":"import { Debug } from \"@trebor/debug-tool\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1013,"value":"// viewof db = Debug();","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W55","stdlib":"1","titling":"auto"}} 33:"$32:body"

Level	Infinite Binary Tree Enumerating the Subdivisions
0	#0
1	#0								#1
2	#0				#2				#1				#3
3	#0		#4		#2		#5		#1		#6		#3		#7
4	#0	#8	#4	#9	#2	#10	#5	#11	#1	#12	#6	#13	#3	#14	#7	#15
...	...

Level	Infinite Binary Tree Enumerating the Subdivisions
0	#0
1	#0								#1
2	#0				#2				#1				#3
3	#0		#4		#2		#5		#1		#6		#3		#7
4	#0	#8	#4	#9	#2	#10	#5	#11	#1	#12	#6	#13	#3	#14	#7	#15
...	...

Level	Infinite Binary Tree Enumerating the Subdivisions
0	#0
1	#0								#1
2	#0				#2				#1				#3
3	#0		#4		#2		#5		#1		#6		#3		#7
4	#0	#8	#4	#9	#2	#10	#5	#11	#1	#12	#6	#13	#3	#14	#7	#15
...	...