[A] tortoise and [a] hare are about to begin a 10-mile race along a “stretch” of road. The tortoise is driving a car that travels 60 miles per hour, while the hare is driving a car that travels 75 miles per hour. [Assume both cars instantly attain those speeds during movement.]
The hare[, wanting to end at the same time as the tortoise,] realizes if it [were to wait] until two minutes have passed, they’ll cross the finish line at the exact same moment. And so, when the race begins, the tortoise drives off while the hare patiently waits.
But one minute into the race, after the tortoise has driven 1 mile, something extraordinary happens. The road turns out to be magical and instantaneously stretches by 10 miles! [The road stretches linearly, taking whatever is on the road with it, including the hare, tortoise, and finish line.] As a result of this stretching, the tortoise is now 2 miles ahead of the hare, who remains at the starting line.
At the end of every subsequent minute, the road stretches by [an additional] 10 miles [in a similar fashion]. With this in mind[, how] long after the race has begun should the hare wait so that both the tortoise and the hare will cross the finish line at the same exact moment?
----------------------------------------------------------
Hint: You don't actually need to find how long it takes for the tortoise to finish the race to answer this problem.
I'll provide the answer I came up with. I find it interesting that the harmonic series (1 + 1/2 + 1/3 + ...) is involved in this question.
Notice that, because of the speeds, the hare should always wait until the tortoise is 20% into the race, regardless of how far the road has stretched. (The road stretches uniformly at all times, so the positions will always remain in proportion.) This means that we do not need to know how long it takes for the race to finish, only how long it takes for the tortoise to get to 20%.
To make things simpler, we can consider the road rescaled to 10 miles at all times, in order to rewrite the problem. So instead of the road stretching by 10 miles every minute, we consider the tortoise slowing down every minute, in a harmonic series-like fashion:
- The tortoise drives 1 mile in the first minute, then 1/2 mile in the next, then 1/3 mile in the next, ... How long then will it take the tortoise to get to 2 miles?
Which is a much simpler question:
- After 1 minute, tortoise is at 1 mi
- After 2 minutes, tortoise is at 1 + 1/2 = 3/2
- After 3 minutes, tortoise is at 3/2 + 1/3 = 11/6 = 22/12
- After 4 minutes, tortoise is at 22/12 + 1/4 = 25/12 > 2
So the tortoise reaches the 2-mile mark somewhere between 3 and 4 minutes. Linear interpolation shows that the tortoise reaches 24/12 at two thirds of a minute (40 seconds) after the 3-minute mark. So if the hare wants to finish the race at the exact same time as the tortoise, the hare should begin the race 3m 40s after the tortoise begins.
Note: How do we know the tortoise is able to finish the race, and it won't go on forever? Simple, 1+1/2+1/3+... diverges. So in fact the race could be a million miles long (stretching a million miles each time) and the tortoise will still eventually finish. Though, even for 10 miles it takes a long time (8.588 days, to be precise), and the amount of time required will increase exponentially based on the distance.
An image of the 8.588-day race is shown in the following solver's twitter post (sorry, the "GIF" (if it is even an actual .gif) is embedded so I can't extract it):
https://twitter.com/ali_geeee8/status/1285183324596535298
Thinking about infinite sets, a question rose to mind.
The continuum hypothesis famously posits that there is no set whose cardinality is strictly between that of the integers and the real numbers.
This got me thinking: It seems to be kind of taken for granted that the set of integers is the "smallest" possible infinite set. Why?
Would the question "is there an infinite set whose cardinality is strictly smaller than that of the integers?" be something completely ridiculous to ask? Is the answer self-evidently "no"? Would it be as ridiculous as asking if there's a smaller non-negative number than zero?
I tried reading about cardinality and aleph numbers, but I didn't really find something that would definitely state that there cannot be an infinite set which cardinality is strictly smaller than that of the integers. Maybe because it's such a self-evident thing that it isn't even worth mentioning? But is it?
This got me thinking: It seems to be kind of taken for granted that the set of integers is the "smallest" possible infinite set. Why?
Would the question "is there an infinite set whose cardinality is strictly smaller than that of the integers?" be something completely ridiculous to ask? Is the answer self-evidently "no"? Would it be as ridiculous as asking if there's a smaller non-negative number than zero?
I tried reading about cardinality and aleph numbers, but I didn't really find something that would definitely state that there cannot be an infinite set which cardinality is strictly smaller than that of the integers. Maybe because it's such a self-evident thing that it isn't even worth mentioning? But is it?
"Taken for granted" is not the right word, it is proven.
Suppose there is a set A whose cardinality is smaller than N. That means one can find a function f: A -> N such that f is injective. Now, look at its image, clearly there is a bijection between A and Im(f), so they have the same cardinality.
If Im(f) is finite, then A is also finite. If Im(f) is infinite, because it's a non-empty subset of the natural numbers, then by the well-ordering principle, it has a least element. So, we can define recursively a function g: N -> Im(f) such that:
g(0) is the least element of A
g(1) is the least element of A - {g(0)}
g(2) is the least element of A - {g(0),g(1)}
...
Notice that this function is well-defined, since if A is infinite, subtracting any finite set from A results in a non-empty set. It's also easy to prove it's a bijection. So there is a bijection between Im(f) and N, and thus also from A to N. Because of this, we have proved that if a set has the cardinality at most that of N, then it's either finite or has the same cardinality as N.
If you neglect the axiom of choice, it's possible to construct a set S whose cardinality is not comparable to that of N (there's neither an injection from S to N or from N to S), but it's still true that N is the smallest infinite cardinal.
I suppose it makes intuitive sense that if there's an infinite set of numbers that's "smaller" than the natural numbers, it must be a countable set (because if it were uncountable, then it would pretty much by definition be larger than the natural numbers, not smaller, I think.)
And if it's countable, it means that every element can be assigned an index number. Which, all in itself, provides a 1-to-1 mapping, ie. bijection, between this set and the natural numbers.
But I was thinking that, perhaps, it could be possible to construct a set of size aleph-0 or "smaller" (if that's even possible) where it's not possible to index the elements because there's no "least element" that can be chosen or pointed out.
(But, then, perhaps it's not possible to construct such a set. Maybe it's a bit like the rational numbers: At first it looks like the rational numbers would be this kind of set: You can't eg. decide that 0 is the "first" rational number and then choose the next one to be "the smallest rational number that's larger than 0" because such a number doesn't exist. However, there are other ways to unambiguously assign unique indices to each distinct rational number.)
But I was thinking that, perhaps, it could be possible to construct a set of size aleph-0 or "smaller" (if that's even possible) where it's not possible to index the elements because there's no "least element" that can be chosen or pointed out.
If the axiom of countable choice (a weaker version of the axiom of choice) holds, then it is possible to index a countably infinite subset of any infinite set just by invoking the axiom, so there cannot be any smaller infinite cardinality than aleph-0.
If we are not allowed to assume any choice axioms, then I think it's up in the air.
Warp wrote:
At first it looks like the rational numbers would be this kind of set: You can't eg. decide that 0 is the "first" rational number and then choose the next one to be "the smallest rational number that's larger than 0" because such a number doesn't exist. However, there are other ways to unambiguously assign unique indices to each distinct rational number.
The Calkin-Wilf sequence is one well-known way to order the positive rationals. It is defined by the breath-first traversal (level-order traversal) of an infinite binary tree whose root is 1/1 and the children of each node are defined as:
- left child of a/b is a/(a+b),
- right child of a/b is (a+b)/b.
The order of the positive rationals here is 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...
Thinking about Cantor's diagonal argument, I realized that I don't actually understand how it proves anything about there existing uncountable sets.
Any countable set can be "indexed", ie. every element in the set can be assigned a unique natural number. Thus we can represent any countable set as simply the list of natural numbers, in order. So we list them eg. in binary, with the least-significant digit first:
0 = 0000000...
1 = 1000000...
2 = 0100000...
3 = 1100000...
4 = 0010000...
5 = 1010000...
etc.
Cantor's diagonal argument takes the first digit of the first number, the second digit of the second number and so on and so forth, and inverts them, and constructs a new number that "doesn't exist in the set":
X = 1111111...
But this is just a number with infinitely many 1-digits in it. Which technically speaking is infinity. But one could argue whether this is an actual number at all. Sure this number with an infinite number of 1-digits doesn't exist in the set of natural numbers... but that isn't very surprising nor telling, because this number is just "infinity". Infinity isn't actually a number (not a natural number, not a real number).
So I don't really understand how this proves anything. It's just essentially saying that infinity is not part of the set of natural numbers. Which is true by definition. It doesn't say anything about uncountable sets.
As I understand it, a countable set of infinite numbers has a method that eventually, given infinite time, maps the set to the sequence 1 to infinity. Cantor's diagonal argument (applied to the set of Real numbers at the very least) is a method that proves that whatever your method of indexing R, there is always a number not on your list.
Your example is different. You give the set N in binary but inverted, but that is obviously still a set of numbers mappable to N: it is a countable set. The diagonal argument does indeed not apply in this case, but then again, it never was supposed to.
But this is just a number with infinitely many 1-digits in it. Which technically speaking is infinity. But one could argue whether this is an actual number at all. Sure this number with an infinite number of 1-digits doesn't exist in the set of natural numbers... but that isn't very surprising nor telling, because this number is just "infinity". Infinity isn't actually a number (not a natural number, not a real number).
Its basic usage is poof that real numbers from 0 to 1 are uncountable.
So, your mistake is that you state numbers as if they are integers, and in the end you get 11111.... <- not actually integer.
Instead of that, in basic example you have:
0.100101010... <- representation of any real number as infinite binary fraction representation.
In this case no matter how many digits, it's still between 0 and 1. And cantor diagonal argument says that no matter which list of infinite sequence you pick, it can not list all real numbers. Because any real number is uniquely represented into binary number, for example sqrt(2)/2 has infinite binary number representation: 0.10110101000... And for any list of real numbers you can construct another real number which is not in the list, because result of construction is binary representation, and any binary representation is possible to translate into convergent series to the value of real number.
Its basic usage is poof that real numbers from 0 to 1 are uncountable.
I think there's a contradiction in the argument, then.
That's because the argument starts with the assumption that you can list all the numbers between 0 and 1 in some order (because if you couldn't, then it would be impossible to "choose the first digit of the first number, the second digit of the second number, and so on".)
If you can list all the numbers in the set as a list, that means that you can assign a natural number to it: Its position on the list.
I don't see any reason why you couldn't list the numbers in their base-2 increasing order... which then results in the "diagonal" number being 1111111... (or 0.111111... which would just be 1), which doesn't really tell us anything.
(Most particularly, if you were to list the numbers in the order 0.000..., 0.100... 0.010..., 0.110... and so on, and you included 1.000... in the list, the "diagonal number" would give you 0.111111... which is just 1.0. A number that's already in the list. Thus the diagonal argument actually fails to give a new number in this case.)
(Most particularly, if you were to list the numbers in the order 0.000..., 0.100... 0.010..., 0.110... and so on, and you included 1.000... in the list, the "diagonal number" would give you 0.111111... which is just 1.0. A number that's already in the list. Thus the diagonal argument actually fails to give a new number in this case.)
First, for some reason you stick with this way of ordering. But it doesn't list all real numbers, because as I said initial statement allows to list any real number. And many real numbers has inifinite binary digits. For example 1/5 is 0.110011001100 (period 1100) but it's not in your list. None of your numbers has infinity representation. For each of them there is position from which all digits are zero.
Second. 0.111111111.... which is 1 - indeed is not in your list.
Third:
Warp wrote:
Cantor's diagonal argument takes the first digit of the first number, the second digit of the second number and so on and so forth, and inverts them, and constructs a new number that "doesn't exist in the set":
Cantor's diagonal argument invert digits at positions, so it's not always construct 0.1111111....
And, lastly, I should have mentioned straight away that trailing infinity ones is edge case, so they should be treated carefully. Any number can be represented in two ways: 0.101111111111.... or 0.1100000... for example. So, we should pick one of ways, and then it's indeed unique representation. I just didn't want to make too much text in first place.
Edit: I see now that you said you add 1 in the list, and if you put it in front, by simple same process you get 0.111111... again. So, I looked up into wikipedia, and instead of just binary representation they first show that infinite sequences of 1 and 0 are uncountable using Cantor's argument it's straight forward, because 11111111... is infinite series - so it is element of set what we want to know is it countable or not. Also, if you list in order as you did before, then your list will not contain 11111111.... sequence. So set of all infinite sequences of 1 and 0 is uncountable. And then, in wikipedia described how you may construct bijection from infinite sequence of 1 and 0 into interval of real numbers. Bijection is one to one correspondance. And this corner cases described. I didn't verify though.
Its basic usage is poof that real numbers from 0 to 1 are uncountable.
I think there's a contradiction in the argument, then.
That's because the argument starts with the assumption that you can list all the numbers between 0 and 1 in some order (because if you couldn't, then it would be impossible to "choose the first digit of the first number, the second digit of the second number, and so on".)
If you can list all the numbers in the set as a list, that means that you can assign a natural number to it: Its position on the list.
I don't see any reason why you couldn't list the numbers in their base-2 increasing order... which then results in the "diagonal" number being 1111111... (or 0.111111... which would just be 1), which doesn't really tell us anything.
(Most particularly, if you were to list the numbers in the order 0.000..., 0.100... 0.010..., 0.110... and so on, and you included 1.000... in the list, the "diagonal number" would give you 0.111111... which is just 1.0. A number that's already in the list. Thus the diagonal argument actually fails to give a new number in this case.)
There is no contradiction in the argument at all. The problem you allude to arises from the fact that the standard way to interpret a string of 0's and 1's as a real number between 0 and 1 is not a bijection, because some numbers have two representations. However, the set of numbers which do not have a unique binary representation is countable, and it's straightforward to fix the function to be a bijection. Take a look at the Wikipedia article. Nothing in this is new, by the way, it already appears on Cantor's article in the 19th century.
The reason that people don't mention this possibility of two distinct representations is that it only arises if you insist on constructing a bijection from the set of binary strings to an interval of real numbers, and if your goal is to simply prove that the reals are uncountable, that's not necessary.
For example, you could just understand the string as a base 10 representation instead of base 2. No problems relating to multiple decimal expansions happen, because no 9's appear. And you can prove that you cannot index the real numbers that have only 0's and 1's in their decimal expansion, and since this is a subset of the reals, you have no hope of indexing the larger set also.
First, for some reason you stick with this way of ordering. But it doesn't list all real numbers, because as I said initial statement allows to list any real number. And many real numbers has inifinite binary digits. For example 1/5 is 0.110011001100 (period 1100) but it's not in your list. None of your numbers has infinity representation. For each of them there is position from which all digits are zero.
Since I don't have an advanced maths background, I'm not very good at explaining my thinking, but I will try.
If I understand correctly, Cantor's diagonal argument is a proof by contradiction (of sorts). It says, essentially: Let's assume that the set of real numbers is countable. This means we can list all the numbers. We proceed to show that using this list we can construct a number that does not exist in the list. Thus the original assumption that the list contains all the real numbers was incorrect.
The thing is, if we make the assumption that the set is countable, and thus we can list all of them in a particular order, it shouldn't matter if we "remap" the numbers to the natural numbers. If we are proving that there are numbers that cannot exist in this countable set, then it shouldn't matter in which order we list the numbers in question, or what the values of those numbers are (as long as every one of them has a unique value).
1/5 is in the list. It's just that it has been "remapped" to eg. the value 16 (using the Calkin-Wilf sequence). If we are just trying to demonstrate that there are numbers that do not exist in the set of rational numbers, this shouldn't make any difference.
If the counter-argument is "but you can't do that with irrational numbers like sqrt(2) or pi", then you are already assuming that irrational numbers are not countable and thus cannot be listed, and thus cannot be "remapped" to the natural numbers. So you are already assuming what you are trying to prove (ie. that the set is uncountable and thus unindexable), which makes the argument circular and contradictory.
If we are proving that there are numbers that cannot exist in this countable set, then it shouldn't matter in which order we list the numbers in question, or what the values of those numbers are (as long as every one of them has a unique value).
It doesn't matter for argument. But for different order you may end up with different constructed number that is not in the list.
Warp wrote:
1/5 is in the list. It's just that it has been "remapped" to eg. the value 16 (using the Calkin-Wilf sequence). If we are just trying to demonstrate that there are numbers that do not exist in the set of rational numbers, this shouldn't make any difference.
Sorry, I mentioned sqrt(2)/2 as an obvious example of number that doesn't listed in your list.
Warp wrote:
If the counter-argument is "but you can't do that with irrational numbers like sqrt(2) or pi", then you are already assuming that irrational numbers are not countable and thus cannot be listed, and thus cannot be "remapped" to the natural numbers.
No, I don't want to say that you can't do that with irrationals. My point was that your list don't have any irrationals. So something is missing already.
All I can do is repeat that for any countable list, cantor's diagonal argument provide process to construct value that is not in the list. By the way p4wn3r pointed out that you can instead use decimal representation (without trailing 9999999) then instead of inversion do following: if digit at position is zero, then set it to 1, otherwise set it to 0. You'll end up with decimal with digits 1 and 0 and it can't have ambiguity. If it would be in the list, then it should be in list as is. So, because for each number at least in single digit it differs, then none of values in the list is equal to it, so it's not in the list.
1/5 is in the list. It's just that it has been "remapped" to eg. the value 16 (using the Calkin-Wilf sequence). If we are just trying to demonstrate that there are numbers that do not exist in the set of rational numbers, this shouldn't make any difference.
If the counter-argument is "but you can't do that with irrational numbers like sqrt(2) or pi", then you are already assuming that irrational numbers are not countable and thus cannot be listed, and thus cannot be "remapped" to the natural numbers. So you are already assuming what you are trying to prove (ie. that the set is uncountable and thus unindexable), which makes the argument circular and contradictory.
The problem is that this "argument" is not Cantor's argument at all.
Cantor's argument is: represent a real number by its decimal expansion, and use this algorithm to contruct another real number which is not on the list. The key for it to work is that the reals can be represented by an infinite decimal expansion. Sets which do not have this property can be countable.
Instead, what you're doing is, you are reassigning every real number to a natural number, which unlike the reals, must have a terminating digit expansion, and apply something analogous to the diagonal argument there. Of course it does not work, because if it did, you would prove that any infinite set is uncountable, you have not used any property of the reals that distinguish them from an arbitrary infinite set.
Joined: 10/27/2004
Posts: 1976
Location: Making an escape
Of all the things to feel oddly proud about, I think I managed to solve dxa/dx for the general case of a using e substitution.
Solve for the following
dxa = f'(x)
dx
Let x = eudeua
deu
Since deu = eudu then
1 . deuaeu du
Apply, the chain rule, you get
aeua = aeuae-u = aeu(a-1)eu
Substitute x=eu back in
f'(x) = axa-1
You may now tell me I'm wrong.
A hundred years from now, they will gaze upon my work and marvel at my skills but never know my name. And that will be good enough for me.
I'd say you're both right and wrong at the same time.
Right because, in spirit, you are using a special form of the chain rule:
dy/dx = (dy/du) / (dx/du)
Wrong because, pedagogically, use of differentials automatically makes any argument "wrong".
P.S. Don't take me seriously.
Joined: 10/27/2004
Posts: 1976
Location: Making an escape
I just checked to see if Wikipedia had something on it, and found that they used what was essentially the exact same proof, only a bit more elegant since they let u=ln x, which then only required one use of the chain rule. Good to know that my thinking wasn't so esoteric after all.
Said article also went on to discuss how negatives raised to irrationals aren't "well behaved", but it didn't say that the proof no longer applied there. Either way, it just confirms that exponentials are weird the moment you start digging into them.
A hundred years from now, they will gaze upon my work and marvel at my skills but never know my name. And that will be good enough for me.
Instead, what you're doing is, you are reassigning every real number to a natural number, which unlike the reals, must have a terminating digit expansion, and apply something analogous to the diagonal argument there. Of course it does not work, because if it did, you would prove that any infinite set is uncountable, you have not used any property of the reals that distinguish them from an arbitrary infinite set.
But the thing is, the argument (ie. the proof by contradiction) starts with the assumption that the set of reals (or, more precisely, the set of all infinite strings) is countable, ie. enumerable, ie. listable. It has to make this assumption, or else it cannot say "take the first digit of the first string, the second digit of the second string, etc."
So my thinking is: If we assume that the list is countable, then it shouldn't make a difference if we replace every element with a natural number (eg. its position in the list). It shouldn't make any difference what we replace every digit of every element in the list with, as long as the resulting remapping is unique. From the point of view of the proof, it shouldn't make a difference.
So if we do that, we are replacing the original list of infinite strings with a list of finite strings, and the only thing that the diagonalization does is to tell us "there are no infinite strings in the list", which is self-evident to the point of being tautological. Of course there aren't, because we replaced them with finite lists in the first place. The only thing that the "proof" is now saying is, in essence, "if you replace all infinite strings with finite strings, there will be no infinite strings."
(In addition, if we do that remapping, and we use eg. base 10 strings, the diagonalization will produce a rational number, because it will have an infinitely repeating digit. Ostensibly rational numbers were in our original list, so it didn't really create a new number.)
If the counter-argument is "you can't replace all the infinite strings with finite ones in a unique way" you'll have to explain why. The answer cannot be "because the set of all infinite strings is uncountable" because that's precisely what we are trying to prove, and we cannot assume what we are trying to prove.
If the counter-argument is "you can't replace all the infinite strings with finite ones in a unique way" you'll have to explain why. The answer cannot be "because the set of all infinite strings is uncountable" because that's precisely what we are trying to prove, and we cannot assume what we are trying to prove.
For the record, I did explain why. It's not wrong to do that mapping, it just does not lead to any meaningful proof of the uncountability of the reals, precisely because by doing it you throw away the information necessary to prove it.
Your argument is essentially doing this: someone says "hey, there exist two matrices A and B such that AB is different from BA!", and you reply, "Wait a second, if I take the determinant, it's always true that det(AB)=det(A)*det(B), and since swapping the two factors give the same number, I don't see how we could have AB different from BA".
There's nothing wrong with this statement, but you simply showed that a line of proof can never succeed, because by restricting your view to the determinant you throw away all the information that's relevant to prove that matrices do not commute. It does not mean that other proof strategies are wrong.
Warp wrote:
So if we do that, we are replacing the original list of infinite strings with a list of finite strings, and the only thing that the diagonalization does is to tell us "there are no infinite strings in the list", which is self-evident to the point of being tautological. Of course there aren't, because we replaced them with finite lists in the first place. The only thing that the "proof" is now saying is, in essence, "if you replace all infinite strings with finite strings, there will be no infinite strings."
OK, so now I will ask you to consider something (not accept, just consider). People have been studying set theory formally for more than a century. In the mean time, many other fields, like theoretical computer science, rely on the diagonalization argument extensively, and we have some foundational results, like the undecidability of the Halting problem, are proven in a very similar manner. It's possible to prove the uncountability of the reals without it, as Cantor did, before he came up with the diagonalization proof.
Now, consider something before you put large quotes around the proof word: what is more probable? That the collective minds of mathematicians of various generations spanning hundreds of years is wrong? Or that you are the one who's not understanding something?
So my thinking is: If we assume that the list is countable, then it shouldn't make a difference if we replace every element with a natural number (eg. its position in the list). It shouldn't make any difference what we replace every digit of every element in the list with, as long as the resulting remapping is unique. From the point of view of the proof, it shouldn't make a difference.
So if we do that, we are replacing the original list of infinite strings with a list of finite strings, and the only thing that the diagonalization does is to tell us "there are no infinite strings in the list", which is self-evident to the point of being tautological. Of course there aren't, because we replaced them with finite lists in the first place. The only thing that the "proof" is now saying is, in essence, "if you replace all infinite strings with finite strings, there will be no infinite strings."
Cantor's diagonal argument is not that.
Cantor's diagonal argument says only: Given any countable list of real numbers that I so choose, you can always find a real number not in this list, using the diagonal argument. This number you choose is dependent on the list I choose.
Cantor's diagonal argument is not about proving that a specific listing lacks some real number; it is not reducible to replacing every element with a natural number and then showing that there are real numbers that are not in the list. So replacing numbers does make a difference.
For the sake of argument, if it were possible to reduce an argument of uncountability to replacing elements with natural numbers and then showing that a number does not exist in the list, then I could "prove" that the set of rational numbers is uncountable as follows:
Suppose the rational numbers are countable. Then from a countable listing of rational numbers, I can replace every rational number with a natural number. Then in this new list, there is a rational number that does not exist in this list: namely 1/2. This is a "contradiction" and so I have "proved" that the set of rational numbers is uncountable.
That isn't what Cantor's diagonal argument is about.
OK, so now I will ask you to consider something (not accept, just consider). People have been studying set theory formally for more than a century. In the mean time, many other fields, like theoretical computer science, rely on the diagonalization argument extensively, and we have some foundational results, like the undecidability of the Halting problem, are proven in a very similar manner. It's possible to prove the uncountability of the reals without it, as Cantor did, before he came up with the diagonalization proof.
Now, consider something before you put large quotes around the proof word: what is more probable? That the collective minds of mathematicians of various generations spanning hundreds of years is wrong? Or that you are the one who's not understanding something?
You are essentially saying that I should accept it without understanding it, and without understanding where the mistakes in my thinking are?
Asking questions about something does not mean "I don't believe it to be true". It simply means "I don't understand this particular thing about it".
As a side note, I noticed that the diagonal argument also proves (I think) that you cannot list all the rational numbers in such an order that eg. their decimal expansions all have the same digit on the diagonal, or in such a way that the diagonal contains a repeating pattern (eg. 0123456789012345... etc)
If you could list all the rational numbers in that way, the diagonalization would just produce a rational number.
I think it's relatively obvious to see why the diagonal cannot contain only one repeated digit (because not all rational numbers contain that digit anywhere). It's less obvious why it can't contain a repeating pattern.
With regards to the non-proof Warp posted, I'll write out the key steps of the diagonal argument as applied to real numbers (handwaving the issue of binary expansions ending in all 1s):
1. If the set of real numbers is countable, we can construct a bijection to the natural numbers.
2. Since every real number corresponds to an infinite binary sequence (binary expansion), we can construct a corresponding list of infinite binary sequences.
3. Using this list we construct an infinite binary sequence that is guaranteed to not be in the list.
4. Since every infinite binary sequence corresponds to a real number we have constructed a real number not in the bijection, which is a contradiction.
As stated above by both p4wn3r and FractalFusion, replacing "infinite binary sequence" with "finite string" changes step 3, which causes the argument to stop working. I'm not sure if there's anything else that needs explanation at this point.
If I write that last idea of mine a bit more semi-formally, I suppose it would be something like:
Let's assume that we can list all rational numbers between 0 and 1 in such an order that the diagonal of their decimal expansion has the infinitely-repeating pattern 0123456789. In other words:
0.0xxxxx...
0.x1xxxx...
0.xx2xxx...
0.xxx3xx...
and so on. We can now construct a new number that consists of all those digits in the diagonal, incremented by 1 (the digit 9 would "wrap around" to 0), ie:
0.123456789012345...
However, since this new number is different from any of the numbers in the list, and this new number is a rational number (all numbers whose decimal expansion is repeating is a rational number), we have a contradiction: The list was supposed to be complete (ie. contain all the rational numbers between 0 and 1) but we created one that was not in the list.
The only possible conclusion is that the assumption that we can list all the rational numbers in such an order is impossible.
But it's not immediately obvious nor intuitive why that's so. I suppose my question would be if there is an intuitive explanation of why they cannot be listed in such an order.
(Or, maybe there's another explanation for this?)
I feel like you've basically proven your own claim. You've given a list of constraints and are asking 'is it possible to list all the rational numbers between 0 and 1 to within these constraints?' On first glance, since the constraints seem fairly restrictive, it's not intutive to me that it should be possible. The fact that it isn't possible is simply demonstrated by finding examples of rational numbers that aren't contained in the list. You found one yourself and another one would be 0.10000000001... (put a 1 when a 0 should occur and 0s elsewhere), which is clearly rational. You can easily find many more.
I don't think there's much more to it than that. The list is incomplete because it assumes an ordering that is too restrictive to contain all the rational numbers. Rather than looking for an intuititve reason for why it isn't possible, I'd rather ask 'why did you think that list would have contained all the rational numbers?'
