Sometimes, I think that I’m being punished.
I’ve written about Cantor crankery so many times. In fact, it’s one of the largest categories in this blog’s index! I’m pretty sure that I’ve covered pretty much every anti-Cantor argument out there. And yet, not a week goes by when another idiot doesn’t pester me with their “new” refutation of Cantor. The “new” argument is always, without exception, a variation on one of the same old boring ones.
But I haven’t written any Cantor stuff in quite a while, and yet another one landed in my mailbox this morning. So, what the heck. Let’s go down the rabbit-hole once again.
We’ll start with a quick refresher.
The argument that the cranks hate is called Cantor’s diagonalization. Cantor’s diagonalization as argument that according to the axioms of set theory, the cardinality (size) of the set of real numbers is strictly larger than the cardinality of the set of natural numbers.
The argument is based on the set theoretic definition of cardinality. In set theory, two sets are the same size if and only if there exists a one-to-one mapping between the two sets. If you try to create a mapping between set A and set B, and in every possible mapping, every A is mapped onto a unique B, but there are leftover Bs that no element of A maps to, then the cardinality of B is larger than the cardinality of A.
When you’re talking about finite sets, this is really easy to follow. If I is the set {1, 2, 3}, and B is the set {4, 5, 6, 7}, then it’s pretty obvious that there’s no one to one mapping from A to B: there are more elements in B than there are in A. You can easily show this by enumerating every possible mapping of elements of A onto elements of B, and then showing that in every one, there’s an element of B that isn’t mapped to by an element of A.
With infinite sets, it gets complicated. Intuitively, you’d think that the set of even natural numbers is smaller than the set of all natural numbers: after all, the set of evens is a strict subset of the naturals. But your intuition is wrong: there’s a very easy one to one mapping from the naturals to the evens: {n → 2n }. So the set of even natural numbers is the same size as the set of all natural numbers.
To show that one infinite set has a larger cardinality than another infinite set, you need to do something slightly tricky. You need to show that no matter what mapping you choose between the two sets, some elements of the larger one will be left out.
In the classic Cantor argument, what he does is show you how, given any purported mapping between the natural numbers and the real numbers, to find a real number which is not included in the mapping. So no matter what mapping you choose, Cantor will show you how to find real numbers that aren’t in the mapping. That means that every possible mapping between the naturals and the reals will omit members of the reals – which means that the set of real numbers has a larger cardinality than the set of naturals.
Cantor’s argument has stood since it was first presented in 1891, despite the best efforts of people to refute it. It is an uncomfortable argument. It violates our intuitions in a deep way. Infinity is infinity. There’s nothing bigger than infinity. What does it even mean to be bigger than infinity? That’s a non-sequiter, isn’t it?
What it means to be bigger than infinity is exactly what I described above. It means that if you have a two infinitely large sets of objects, and there’s no possible way to map from one to the other without missing elements, then one is bigger than the other.
There are legitimate ways to dispute Cantor. The simplest one is to reject set theory. The diagonalization is an implication of the basic axioms of set theory. If you reject set theory as a basis, and start from some other foundational axioms, you can construct a version of mathematics where Cantor’s proof doesn’t work. But if you do that, you lose a lot of other things.
You can also argue that “cardinality” is a bad abstraction. That is, that the definition of cardinality as size is meaningless. Again, you lose a lot of other things.
If you accept the axioms of set theory, and you don’t dispute the definition of cardinality, then you’re pretty much stuck.
Ok, background out of the way. Let’s look at today’s crackpot. (I’ve reformatted his text somewhat; he sent this to me as plain-text email, which looks awful in my wordpress display theme, so I’ve rendered it into formatted HTML. Any errors introduced are, of course, my fault, and I’ll correct them if and when they’re pointed out to me.)
We have been told that it is not possible to put the natural numbers into a one to one with the real numbers. Well, this is not true. And the argument, to show this, is so simple that I am absolutely surprised that this argument does not appear on the internet.
We accept that the set of real numbers is unlistable, so to place them into a one to one with the natural numbers we will need to make the natural numbers unlistable as well. We can do this by mirroring them to the real numbers.
Given any real number (between 0 and 1) it is possible to extract a natural number of any length that you want from that real number.
Ex: From π-3 we can extract the natural numbers 1, 14, 141, 1415, 14159 etc…
We can form a set that associates the extracted number with the real number that it was extracted from.
Ex: 1 → 0.14159265…
Then we can take another real number (in any arbitrary order) and extract a natural number from it that is not in our set.
Ex: 1 → 0.14159266… since 1 is already in our set we must extract the next natural number 14.
Since 14 is not in our set we can add the pair 14 → 0.1415926l6… to our set.
We can do the same thing with some other real number 0.14159267… since 1 and 14 is already in our set we will need to extract a 3 digit natural number, 141, and place it in our set. And so on.
So our set would look something like this…
A) 1 → 0.14159265… B) 14 → 0.14159266… C) 141 → 0.14159267… D) 1410 → 0.141 E) 14101 → 0.141013456789… F) 5 → 0.567895… G) 55 → 0.5567891… H) 555 → 0.555067891… … … Since the real numbers are infinite in length (some terminate in an infinite string of zero’s) then we can always extract a natural number that is not in the set of pairs since all the natural numbers in the set of pairs are finite in length. Even if we mutate the diagonal of the real numbers, we will get a real number not on the list of real numbers, but we can still find a natural number, that is not on the list as well, to correspond with that real number.
Therefore it is not possible for the set of real numbers to have a larger cardinality than the set of natural numbers!
This is a somewhat clever variation on a standard argument.
Over and over and over again, we see arguments based on finite prefixes of real numbers. The problem with them is that they’re based on finite prefixes. The set of all finite prefixes of the real numbers is that there’s an obvious correspondence between the natural numbers and the finite prefixes – but that still doesn’t mean that there are no real numbers that aren’t in the list.
In this argument, every finite prefix of π corresponds to a natural number. But π itself does not. In fact, every real number that actually requires an infinite number of digits has no corresponding natural number.
This piece of it is, essentially, the same thing as John Gabriel’s crankery.
But there’s a subtler and deeper problem. This “refutation” of Cantor contains the conclusion as an implicit premise. That is, it’s actually using the assumption that there’s a one-to-one mapping between the naturals and the reals to prove the conclusion that there’s a one-to-one mapping between the naturals and the reals.
If you look at his procedure for generating the mapping, it requires an enumeration of the real numbers. You need to take successive reals, and for each one in the sequence, you produce a mapping from a natural number to that real. If you can’t enumerate the real numbers as a list, the procedure doesn’t work.
If you can produce a sequence of the real numbers, then you don’t need this procedure: you’ve already got your mapping. 0 to the first real, 1 to the second real, 2 to the third read, 3 to the fourth real, and so on.
So, once again: sorry Charlie: your argument doesn’t work. There’s no Fields medal for you today.
One final note. Like so many other bits of bad math, this is a classic example of what happens when you try to do math with prose. There’s a reason that mathematicians have developed formal notations, formal language, detailed logical inference, and meticulous citation. It’s because in prose, it’s easy to be sloppy. You can accidentally introduce an implicit premise without meaning to. If you need to carefully state every premise, and cite evidence of its truth, it’s a whole lot harder to make this kind of mistake.
That’s the real problem with this whole argument. It’s built on the fact that the premise “you can enumerate the real numbers” is built in. If you wrote it in careful formal mathematics, you wouldn’t be able to get away with that.
You’ve probably covered it already, but I’m unable to find it right away:
> The diagonalization is an implication of the basic axioms of set theory.
What if we take smth like type theory as a foundation? If I’m not mistaken than we can construct set theory using type theoretical foundation, so Cantor’s argument would still exist. How would it look like in this case?
It ends up looking pretty much exactly the same.
Cantor’s diagonalization doesn’t even require the axiom of choice. It’s a constructive proof, which works perfectly, virtually unchanged, in type theory.
I think you misunderstood “today’s crackpot”‘s argument and part of your explanation of what is wrong with it is incorrect.
You say:
“In this argument, every finite prefix of π corresponds to a natural number. But π itself does not. In fact, every real number that actually requires an infinite number of digits has no corresponding natural number.”
The reason you give for π not appearing in the list would also seemingly apply to π-3, which is actually the first number on the list! So the reasoning you used must be wrong.
Here’s what I understood the construction to be:
Tackle all reals in “a certain order”, on x’s turn look at all the finite initial portions of its decimal expansion and pair up x with the first of those numbers that you haven’t used before.
Now, as you say below the quote I used above, “a certain order” might be interpreted to mean “enumerate the reals” in which case the proof assumes what it is trying to prove and is therefore invalid. But one can more charitably interpret the certain order as “using the axiom of choice, well-order the reals and proceed by transfinite induction”. If you do that you are actually guaranteed to be able to carry out the suggested procedure until you get to the first real number that has infinitely many predecessors in your chosen well-ordering. At that point you might have already used all of its initial portions. For example, say the first countable many reals in the well-ordering are 0.22…211… with n 2’s and and infinite tail of 1s. If then the omega-th real is 2/9, the procedure is unable to chose an unused initial segment for it.
Interesting point Omar, may I get your opinion on something that may have some bearing on your comment?
Let pi and pj be two real numbers, where pi is the trite ratio of the circumference to diameter of a circle. Then would it be possible for both numbers to have an infinite number of digits in common followed by a difference that makes pj greater than pi? If your answer is yes then…
pi = 3.14159…inf # digits…589793…
pj = 3.14159…inf # digits…589794…
Which would it be, pi < pj or pi = pj?
That question doesn’t make sense and shows a misunderstanding about what decimal are. In the decimal expansion of a number every digit has only finitely many digits to the left of it. In your supposed numbers you have digits, like the 8s, that have infinitely many digits to the left of them.
To the contrary; even most RATIONAL numbers have infinitely many digits in their decimal expansions! The decimal expansion of 1/3 goes on repeating 3s forever. Restricting attention only to finite decimal expansions not only throws out all irrational numbers, it throws out all rational numbers whose denominators don’t factorize as a product of 2s and 5s. No wonder you think your “numbers” aren’t too numerous!
Either you responded to the wrong comment or misunderstood me. I am well aware that most numbers have infinite decimal expansion (and I also well aware that there are uncountably many real numbers). What I said in the post you responded to is that in a decimal expansion, even if it is infinitely long, the digits are arranged in a sequence that has the order type of the natural numbers. Thus any digit has only finitely many digits to the left of it. Take 1/3, for example. Its decimal expansion is infinite, 0.333… Every 3 occurring in it has only a finite number of 3s to the left of it. There is no 3 that is “infinitely far to the right”. Another way to say it is that every 3 in that expansion occurs at a spot numbered by a positive integer, and the n-th 3 contributes 3/10^n to a sum whose value is 1/3.
Would you then agree, that if two real numbers are not equal, then they will differ at some finite number of digits to the right of the decimal point. (if not sooner)
pi = 3.14159…finite # digits…589793…
pj = 3.14159…finite # digits…589794…
And every real number in any set of real numbers will differ from every other real number in the set at some finite point to the right of the decimal point. (if not sooner)
Yes, that is correct. Two different real numbers cannot have the same decimal expansion[1] and thus differ at some spot and said spot only has finitely many spots to the left of it.
[1] But two different decimal expansions can represent the same number!
Well, Omar is clearly right, and Mark’s statement about π (or π-3) not appearing in the “set” (the guy is thinking in iteration) is wrong, but it does not really invalidates his deeper and actual criticism.
What I am most curious about is not the erroneus conclusions from the fact that a countable subset of the reals extracted by iteration to be countable, but that he believes to be proving that “the natural numbers [are] unlistable as well”. I leave to the reader the very difficult exercise of proposing a way of listing the natural numbers.
Then, if every real number in any set of real numbers will differ from every other real number in the set at some finite point to the right of the decimal point.
Then we can form a natural number from all the digits up to and including the point where the real number differs from all the the other real numbers on the set. This natural number will be finite and this natural number will be unique. It is as if every real number, on any set of real numbers, has a natural number that serves as a serial number.
If you were correct, then you’d be on the way to disproving Cantor. But… This is a classic case of fuzziness of words. It sounds like a good argument, but only because of the vagueness introduced by informal language. There’s a reason that on this blog, I’ve constantly said that the worst math is no math. Informal natural language arguments aren’t math. They’re informal natural language arguments.
If you try to formalize your argument – to make the statement precise, to incorporate it into the logical form of transfinite induction that you’d need to reason about the reals, it would fall apart.
I’d like to be able to make my argument here more precise, by showing how it wouldn’t work. But I have no idea how to turn your argument into the correct formalism.
It’s vague enough that there’s no way I can really render it with sufficient precision. Even if I could, there’s probably a hundred different ways of interpreting the natural language, each of which would be rendered differently in formal language. And even if I could do that, transfinite induction isn’t something I’m particularly comfortable doing on my own. (As I’ve said many times: I’m not a mathematician. I’m an engineer. I love math, but I’m not good enough at it to be a real mathematician. I’m just a dabbler.)
@John Fringe:
Let me try to list the natural numbers. First I’ll list the even numbers (they’re my favorite!) and then the odd numbers:
0,2,4,…,1,5,9,…. Wait, that won’t work. Drat! Back to the drawing board! 🙂
@Carl:
Consider the set of real numbers consisting of 0.11111… (1/9), and then the sequence 0.2, 0.12, 0.112, 0.1112, 0.11112, …
Then there is no point you can cut off 1/9 to see that it is different from all the other numbers in the set; you need all of the infinitely many digits to compare against the infinitely many other numbers.
(hope this is a good “reply” button to click on…)
@carl: well put. You need to do infinitely many steps to determine if a given number is different from every one of an infinite large list of candidate numbers.
MarkCC said “You need to do infinitely many steps to determine if a given number is different from every one of an infinite large list of candidate numbers.”
Would you say this is also true of Cantor’s diagonal argument?
Keep in mind that after every time you check the list, the list will grow ten fold. If you check just the first 100 numbers on your list, you will have a diagonal with 100 digits! You will then have to check the next 10^100 rows to make sure that the diagonal you created is not there, by the time you finish that you will then have to check the next 10^10^100 rows. Are you sure this is possible?
As for the original argument the objection is no problem. Our map would simply look like this.
1 -> 0.111… AKA 1/9
2 -> 0.2
12 -> 0.12
11 -> 0.112
111 -> 0.1112
1111 -> 0.11112
etc…
No, I wouldn’t say that of Cantor’s diagonalization.
The difference in the diagonalization, you’ve got a purported enumeration of the reals. For the Nth real number in the sequence, you need to look at its Nth digit. There’s no process of searching for “the first difference”.
In this other enumeration, given a new real number, you need to find the first place where it differs from every other number that you’ve already added to your enumeration.
So you’ve got the situation where you’ve got an infinite list of infinitely long numbers. Yes, they’ll each differ at some finite position – but you need so search arbitrarily far through an infinite list.
MarkCC said “Yes, they’ll each differ at some finite position – but you need to search arbitrarily far through an infinite list.”
Okay, this is logistically impossible, yet logically possible.
Cantor’s diagonal is also logistically impossible, but it is also logically impossible as well.
I will give you one more argument from logic, take a look at this video. (about 2 minutes)
Dr. Tony Weathers is basically saying…
Let i1 & i2 be irrational numbers so that 0< i1 < i2 <1 then there will always exist a rational number r so that i1 < r < i2.
Therefore, it will always be possible to find a rational number between any two irrational numbers, so the cardinality of the irrational numbers can’t be greater than the rational numbers.
No, not just logistically impossible.
In Cantor’s diagonalization, each step – generating a differing digit for each real in the enumeration – is possible in a specific, finite amount of time.
In this procedure for generating a real mapping, you’ve got an *infinite* number of things that share prefixes. That’s the key thing to wrap your head around. You have an infinite number of real numbers that share prefixes. For some numbers, you’ll *never* reach a point where you can map them onto an integer, because there’s an infinite number of numbers that need to get mapped before them.
In computer sciency terms, you can’t guarantee that the process of finding a mapping from real to integer for every real number will ever terminate – because for some real numbers, it won’t.
MarkCC said “You have an infinite number of real numbers that share prefixes. ”
That is not a problem since I have an even bigger number of finite prefixes to choose from after that.
If you form a list of decimal numbers (between 0 and 1) that can be represented with an infinite number of digits (ex; 1/3, 0.4999…, pi-3, e-2, root(2)-1 etc.) then for each of those numbers you can construct a set with an infinite quantity of natural numbers.
For example; given the number 0.333… you can construct the infinite set {3, 33, 333, …}, given the number pi – 3, you can construct the infinite set {1, 14, 141, …}
Since we can extract an infinite quantity of natural numbers from every real number that does not terminate, then it would be impossible for the set of numbers with an infinite number of digits to have a greater cardinality than the set of natural numbers.
If I understand you correctly Mark, your objection is that as we increase the number of real numbers in our set, we will begin to have a greater amount of repeats. (if I missed your point, please explain further)
For example if we have a real number like pi-3 and a real number that is pi-3 plus 1 divided by a googolplex raised to the power of a googolplex a googolplex number of times, then the first g^g^g^g^g… digits will be repeats and no new prefixes will be generated. But we will still have an infinite number of digits to chose from once we get past that finite section.
Consider the economy argument, if someone gives you an infinite quantity of digits, you can use them to construct one irrational number or an infinite quantity of numbers that terminate. We will always have more of the shorter numbers because we can always slice and dice the longer ones to form shorter ones. The wonder of it all is that the quantity of numbers that go on forever is exactly the same as the numbers that terminate.
Sorry, I forgot the link to the video 🙂
https://youtu.be/0XBPR066jTY?t=44m37s
@Carl:
That is not an argument from logic, but from intuition, and in this case, your intuition fails. For that to be an argument from logic, the conclusions should provably follow the premises, and this is not the case, so no argument from logic.
Your intuition fails in part because the phrasing induces one to think in the card deck simile: between two rational numbers there is an irrational number, and between two irrational numbers there is a rational numbers. Which is true. But actually, it makes one think that there is exactly one number in between, which is false. Actually, between any two real numbers there is an infinite amount of both rational and irrational numbers, and nobody says there is the same number, because, in fact, you can not, because irrationals are uncountable. As Mark says, natural language is imprecise.
When you apply intuition to think about infinite amounts and processes requiring an infinite amount of steps you will end at Zeno’s like paradoxes. These paradoxes are no real paradoxes, just tricky puns. In fact, mathematics trivially “solve” these “paradoxes” in counterintuitive but consistent and physically relevant ways.
For that to be an argument from logic, you should give a series of provable logical steps from the premises (between any two real rational numbers there is – at least – an irrational number and viceversa) to the conclusion (between any two reals, there is an infinite number of reals, including an infinite number of rational and irrational reals). Such a proof does not and cannot exist.
To better illustrate how intuition fails in this case (helped by the wording), consider this fact, which is true: “between any two irrational numbers, there is a rational number, and an infinite amount of irrational numbers”.
I can make such missguiding but strictly true assertions to induce someone to think that the cardinality of rationals is greater, equal or smaller than that of irrationals. Intuition here is useless.
@Omar Antolín Camarena,
You have a very good response to this anti-Cantor argument. But, instead of pairing the naturals with the reals, if our friend tried to pair the naturals with the irrationals. Then your objection would no longer work, and Cantor would still have a problem since the naturals should not be possible to pair with the irrationals.
This thread has haunted me for the past few months, and if I were a young mathematician, I would certainly try to formalize this argument. From where I sit, it looks promosing.
Adam
I don’t know that one infinity is the most obvious thing. There should be more natural numbers than even numbers, for example. I tried working on an partial order for subsets of the natural numbers while waiting for an appointment once, but it couldn’t only work for arbitrary sets, and getting all pairs of sets that one is “obviously” larger than the other to order right is quite tricky.
we will need to make the natural numbers unlistable as well
That seemed to promise to somehow make the natural numbers uncountable, but the rest of the argument seems instead to try and ennumerate the reals. A pity – the former would undoubtedly have been more original madness.
Comments are getting out of order, I guess, so I continue here. This is a reply to Carl,
http://www.goodmath.org/blog/2016/07/05/cantor-crankery-is-boring/#comment-153979
I believe we are overcomplicating things, and that is never a good idea, because we will not be able to see the forest for the tress.
Even more when all this complex association between reals and integers is completely useless, it is just noise. For all practical purposes, the algorithm is equivalent to this one, a lot simpler
S := ∅; for i from 1 to ∞ do ( x = random real between 0 and 1 [almost impossible to repeat, because of zero measure]; n = random natural; S := S ∪ {(n, x)} )
It is almost impossible to repeat a “key”, because of the zero measure of the sets. But if that makes anyone unconfortable, he can add an “instruction” (this were a proof, isn’t it? why are we arguing about executions? This “induction” has state!) to check if any of the numbers is already on the set. This is trivial.
With this simple variation, we can return to the main concern, Carl: the core of your procedure is iteration, and iteration is countable, because you can label the steps with integers. And, being so, you will never extract an uncountable set by this iterative procedure, because the procedure itself is countable. All you are “proving” is that you can match integers to a countable subset of reals, which is a trivial result not surprising at all.
@John Fringe, I like the way you think.
Your method would have two check functions.
1 While( x isElementOf S) x = getRandomReal(0, 1)
2 While( n isElementOf S) n = getRandomInt( > 0)
S := S ∪ {(n, x)}
If Cantor was right, then function 1 will return a value for a lot longer than function 2. If cantor was wrong then functions 1 and 2 would fail at the same time. Since we can’t know when the functions fail, this method will not tell us anything.
The crackpot gets around this problem because, if the call for a random real succeeds then the call to get a natural number can’t fail. If the call for a real number finds a real number that is different from all the reals in set S, then that string will contain a new natural number that is different from all the natural numbers in set S as well.
1 While( x isElementOf S) x = getRandomReal(0, 1)
2 For i from 1 to ∞ do ( n = stringToInt( getStringLength(i)))
if( n isElementOf S) then Next i
S := S ∪ {(n, x)}
His method will only fail if it runs out of real numbers, but will never fail from running out of natural numbers.
Now I believe I am not understanding you at all. Its trivial to make the natural key generation never to fail, because, as I said, this is an interation, and you can label iterations:
S := ∅
for i from 1 to ∞
x = getRandomReal(0,1) not in S
S := S ∪ {(i, x)}
So I repeat myself: this proves nothing, apart from the fact that people like to complicate themself to enumerate a random countable subset of reals.
Am I missing anything?
@John Fringe, When I first saw this argument, I did not get it either, it is a bit subtle.
If we call our function to generate real numbers an infinite number of times, then we will get a lot of real numbers but there will be real numbers missing. We can find some of those numbers by diagonalizing the set of real numbers and mutating the digits.
Cantor’s method used all the natural numbers on the left and then he generated a new number on the right by diagonalization, then he had no natural number to pair with that new found real number, since he had already used up all the natural numbers.
Cantor’s relationship between the left and right side was arbitrary, the crackpot gets around this by making the left side dependent on the right side. Every natural number on the left side is a prefix from the number on the right side that it is associated with.
So, if by chance, no real number begins with the prefix 0.5554555 then we will know that the number 5554555 will not appear anywhere on the left side. So, if we diagonalize the right side and change the digits to something else and get 0.555455545544… we will then be able to pair that real number with the natural number 5554555 since it is not on the left side.
So the crackpot claims that she can always find a natural number for every real number, by simply taking the first n digits of that natural number until she finds a number that does not appear on the left side.
Try reading her version of it in the first post again, and see if it does not make more sense.
@Carl,
The last paragraph should read…
So the crackpot claims that she can always find a natural number for every real number, by simply taking the first n digits of that REAL number until she finds a number that does not appear on the left side.
>> We can find some of those numbers by diagonalizing the set of real numbers and mutating the digits.
No! You cannot! That is the whole idea! And my argument os not subtle at all! It is as crude as I can express it!
Yes, I red both versions carefully, but I only see a horrible confusion between FORALL, FORANY, masked by an mess of iteration more complex than it should just to superficially resemble Cantor’s diagonal argument (very very superficially), and a very surprisingly misguiding idea of “getting out” of elements from an infinite set in an iteration.
Cantor’s proof is not a computer program, it does not involve any kind of “execution” nor any kind of iteration. It is a proof by contradiction. If you suppose you have a correspondence (defined, static; mathematical concepts are not computer variables!) between reals and integers, then you have a real which is not mapped. So contradiction. So no correspondence. End.
The procedure “supposedly” disproving Cantor is nothing like this. In fact, it is exactly what I described: given a random infinite sequence of reals (of anything), one can label them with integers. Which is trivial because that is the defining intrinsic property of sequences. The rest is just not understanding the difference between a property of any finite subset of a sequence, a property of a sequence and a property of set, and not understanding anything about transfinite induction. You do not need to know those names to understand that. Simply put, proving a property in every finite subset of a sequence does not imply that the property is true for the set the sequence is taken from.
In fact, this person’s “proof” is exactly as claiming that there is a finite number of naturals because
S := ∅
for i from 1 to ∞
S := S ∪ {i}
check_S_is_finite
It should be “true”, because this program never fails!
I do not have anything else to add. In fact, this post is totally redundant.
@JOHN FRINGE, you said… “It is a proof by contradiction. If you suppose you have a correspondence between reals and integers, then you have a real which is not mapped. So contradiction. So no correspondence. End.”
Not the end. Indeed we do have a real which is not mapped, but for every real that we have, that is not mapped, we will have a natural that is not mapped as well. So no contradiction. We still have a correspondence, but we just can’t list all the elements of either set.
Nope, wrong.
You can always list all of the members of the set of natural numbers. In fact, you can do it by definition! The *definition* of an enumerable infinite set is any set with a one-to-one correspondence between the set and the natural numbers. There’s obviously a 1:1 correspondence between the natural numbers and itself.
But you’re making another fundamental error that doesn’t even involve the sets of numbers at all. You’re making a profound logic error.
If you have a line of logical inference that produces a contradiction, what that means is that the entire line of reasoning is invalid. That’s the point of a proof by contradiction: you’re starting with a statement that you want to disprove, and then showing that by assuming that statement, you’ve created an invalid system of reasoning.
The thing is, once you’ve shown that assuming the initial statement produces a contradiction, the entire line of reasoning is invalid and inconsistent. You can’t use that line of reasoning *for anything*, because it’s invalid: it’s a system of reasoning which contains a contradiction.
Using a system of inconsistent reasoning, the *only* thing you can prove is that the system is inconsistent. Everything else is out the window, because an inconsistent logical system can produce a proof of *any* statement.
If you start from a chain of reasoning that includes a contradiction, you can “prove” ridiculous things. You can “prove” that the natural numbers aren’t enumerable. You can “prove” that zero equals one. None of that is at all meaningful, because it’s built on a contradiction.
In the diagonalization proof, what you’re really doing is showing that the assumption that there’s an enumeration of the real numbers takes a valid reasoning system (first order predicate logic, with a ZFC set theory model), and makes it invalid. But once you’ve done that, you can’t infer anything else from that invalid system.
@MarkCC, you said… “You’re making a profound logic error.”
I don’t think that logic is on your side here, consider this…
If we have a unit line, then this line will have an infinite number of points in it. Some of these points will be an irrational distance away from the origin and some will be a rational distance away from the origin.
Premise 1.
To have more irrational points on this line than rational points (plus 1), it is necessary to have at least two irrational points on the line so that there exists no rational point between them.
Premise 2.
It is not possible to have have two irrational points on a line so that no rational point exists between them.
Conclusion.
It is not possible to have more irrational points on a line than rational points (plus 1).
This contradicts Cantor’s conclusion, so Cantor must have made a mistake in his reasoning.
You don’t just get to randomly create new premises just because you like them. That’s not how logic works.
In most mathematical settings, including Cantor’s proof, we’re working in a logical system consisting of a bunch of components. We start with first order predicate logic, with the standard FOPL inference rules. Then we choose a set of fundamental axioms – the most common choice is ZFC set theory. (But you can use a variety of different systems: you can use an alternative formulation of set theory; you can use category theory; you can use type theory.)
Once you’ve got that basis, you can start defining new things within your theory. The canonical example of that is the set theoretic construction of the natural numbers using the rules of Peano arithmetic. The rules of Peano arithmetic define the logical behavior of the natural numbers; the FOPL/set theoretic basis used to define those rules show that they’re sound, and have a valid model. When you’re done, you’ve defined a theory of natural numbers.
Once you’ve got the theory of natural numbers, you can keep going, defining the integers, the rationals, and the reals. In each step, you’re defining a set of fundamental rules, and then showing (using the already established rules) that they’re sound, and have a valid logical model.
Every time you introduce a new premise, you need to show that it is consistent with everything that you used to construct it. If you’re using a natural-number based construction of the rationals, then nothing in your construction of the rational numbers can rely on a property of the natural numbers that isn’t already part of theory of natural numbers. You can add new rules – but unless you can show that they are a logical consequence of the theory you’re building on, you don’t get to go backward and apply them to that earlier theory.
For example: in the theory of real numbers, we define the quotient operation. It’s a different quotient operation than what we had in the theory of natural numbers. In real number theory, for any non-zero real number values x and y, there’s a real number z called the quotient of x and y, which follows the rules that if y=x*z, then z=y/x. But you don’t get to then go back and say that because in real number theory that’s true, that there must be a natural number between 1 and 2, because the quotient of 3/2 is greater than 1 and less than 2. You can’t take a rule that isn’t part of the theory of natural numbers, and apply it to natural numbers.
You’re introducing a premise that there are irrational numbers with no rational numbers between them. You don’t get to just randomly do that. You have to show that that statement is fully consistent with the theory of natural numbers. It’s not part of any standard construction of the theory of real numbers. So you’d need to show how it follows from that theory. If it doesn’t, then you don’t get to use it.
If it doesn’t follow from the theory of real numbers, but it’s consistent with them, then you can formulate a new theory of Carlian ultra-real numbers that includes that. But you can’t draw conclusions about the real numbers using a premise of Carlian ultra-real theory.
But it gets even worse for your argument. Because the statements you’ve put up there look nice, but they aren’t actually mathematical statements. They do not have the necessary precision to be real math. They’re fuzzy hand-waving. So you can’t even formulate Carlian ultra-real theory using those. Before you can do anything with them, you need to show that they’re at least consistent with real number theory. Which you can’t do with fuzzy hand-wavy “premises” like those.
To show that they’re consistent with or follow from the rules of real number theory, you need to formulate those in a valid mathematical way. Which you haven’t done. And I’m reasonably sure that you *can’t* do.
So your position is that naturals are unlistable* **, and that there is a one-to-one correspondence between reals and naturals because if you list the unlistable reals by iteration, you can list some arbitrary integers “that cannot be listed” with them.
O_o Errr… ahem… mnnn… ahhh… interesting ¬¬.
* if only someone knew how to list the naturals!!! Noooooooo………!!!!!!
** if only someone could find a one-to-one map between naturals and the very same naturals!!!!! Nooooo……!!!
@Carl: your “premise 1” is totally unfounded, and clearly shows your motivation by intuition from finite sets. If you really believe it to be true, you must prove it.
Gee, thanks. You just managed to take the super-wordy diatribe that I was writing, and condense it down into two clear, pithy statements before I could even finish writing mine.
You’re making me look bad! 🙂
Let’s not turn this into a mutual-admiration society here 😉
A little more seriously: it seems Carl is not asserting that there are irrationals with no rationals between them (see “Premise 2”); he’s saying that IF there are more As than Bs then there must be two As with no Bs between them.
And this is in fact true… if you’re thinking about finite order types! Indeed, if A and B are finite-cardinality sets with card(A) > card(B)+1 then any order of their disjoint union must put two As next to each other with no Bs in between (It’s basically a pigeonhole argument).
Carl’s failure lies in not understanding how radically different the order type of the reals is from the finite order types where he has built his intuition.
Yeah, I was considering explaining how his “premise” would only be true *if* the reals were already enumerable. But I thought I’d already rambled long enough.
@John Armstrong,
My intuition tells me that, if I have a countable infinity of pigeon holes and an uncountable infinity of pigeons, then at least one pigeon hole will have an uncountable infinity of pigeons in it. What does your intuition tell you?
The point is that it doesn’t matter what your intuition tells you.
We’re not doing intuition: we’re doing math. There’s a lot of things in math that aren’t intuitive.
You can cut a sphere into pieces, and then re-assemble those pieces into two spheres the same size as the original. That’s not just non-intuitive, it’s intuitively ridiculous. But it’s mathematically true, and mathematically, it means something. (It tells us that measurement doesn’t necessarily mean what we intuitively think it means. You can take a measurable quantity, and do things to it that make it unmeasurable; and if you do that, then any notion of conservation of measurability needs to be thrown out the window.)
There is a smallest real number greater than 0. Intuitively, that’s ridiculous. Any number we choose as a candidate for that smallest real number isn’t it, because we can divide it in half and get a smaller one. And yet, there is a smallest real number greater than zero, because by the fundamental axioms of the real numbers, any set of reals has a lower bound, which means that the set {x: x > 0} must have a smallest element.
Intuition is great for some things, but not math. In fact, all of math can be understood as an attempt to create a formal system of reasoning to allow us to test our intuitions and determine when they’re wrong.
Intuitively, the idea of uncountable infinity doesn’t make sense. That doesn’t matter.
You can reject the idea of uncountable infinity. But to do that, you have to reject the logical axioms of mathematics that we use. Doing that is a reasonable thing to do: there are many mathematicians who’ve proposed alternate axiomatizations of mathematics. But you can’t talk about ZFC based mathematics, and the axioms of real numbers built on ZFC, and then claim that in that system, the real numbers are countable because your intuition says so.
@markcc “There is a smallest real number greater than 0.” There isn’t, for normal definitions of “smallest” and “real number”, since, as you point out, for any number x, x/2 is a smaller number between it and 0. The reals are not well-ordered under the greater-than relation, and any set {x > C | x is an element of R} has no least element, and the greatest lower bound is going to be C.
Gah, no! I hate to have to call you out here, Mark, but the positive reals are NOT well-ordered. There is no least positive real number.
As to Carl’s question, Mark is right that intuition has nothing to do with it, and one can prove (not intuit) that yes, at least one preimage of any function from an uncountable set to a countable one must itself be countable.
Except that’s not remotely what you asserted before, Carl. You asserted (without proof) that, to quote:
“To have more irrational points on this line than rational points (plus 1), it is necessary to have at least two irrational points on the line so that there exists no rational point between them.”
Which is not true. But it WOULD be true if you were talking about countable order types, instead of the uncountable order type of the reals. That’s where you got your intuition from (if card(A) > card(B)+1 then any arrangement of As and Bs will have two As “next to each other” with no B in between), but it fails you when you move beyond its original context.
@Markcc That smallest real number bigger than zero comment is certainly false.
@Carl Your intuitive transfinite pigeonhole principle is correct actually (indeed a Cartesian product of two countable sets is countable). The problem in the argument you are trying to make is that your pigeonholes aren’t well-defined
@markcc: “And yet, there is a smallest real number greater than zero, because by the fundamental axioms of the real numbers, any set of reals has a lower bound, which means that the set {x: x > 0} must have a smallest element.”
No… completeness doesn’t require that the greatest lower bound is an element of the set. The greatest lower bound of {x: x > 0} is 0.
Gah, yeah. Stupid. And a perfect example of what I keep saying: you have to do math with math, not with words. If I’d taken the time to say that correctly, formally, I would have realized I was remembering it wrong.
MarkCC said… “If you have a line of logical inference that produces a contradiction, what that means is that the entire line of reasoning is invalid.”
We have produced two contradictions (one in the first post and the pigeonhole argument). Either one of these arguments (if true) would invalidate Cantor’s argument.
Mark, you have not been able to defeat either of these arguments. All you have been able to say is that the pigeonhole argument is based on intuition. And I am sure that you understand that it is not possible to defeat an argument simply by discrediting the source of that argument. http://www.nizkor.org/features/fallacies/genetic-fallacy.html
John Armstrong has tried to defeat the pigeonhole argument by saying things like “not understanding how radically different the order type of the reals is from the finite order types” and “but it fails you when you move beyond its original context”. I only hope that John can explain to us what we are not understanding.
Once again, you’re resorting to vague words instead of formal math. And you’re deliberately sidestepping the real points that we’ve been making, over and over again.
Your arguments are wrong. Intuitively, they may look right. But you can’t do math by intuition. You do math by formal logic.
Your argument is using statements as axioms which are incorrect. That’s the problem with trying to present an argument by intuition. It’s not that intuition is bad – it’s that intuition is imprecise. It’s easy to make mistakes in reasoning by intuition.
There’s a reason why mathematicians invented formalisms, and demand reasoning by strict formal logic with specific inference rules. It’s because when you talk in informal logic, it’s easy to make mistakes.
If you actually look at your pigeonhole argument about having adjacent irrationals, it looks nice on the face of it. But the problem is, it’s not a precise mathematical statement. If you turn it into a precise mathematical statement, it’s easy to show that it doesn’t logically follow from any of the axioms of ZFC, Peano arithmetic, and real number theory.
In fact, if you look at it rendered as a proper mathematical statement, it doesn’t follow from ZFC/PA/real number theory. In fact, it contains the implicit assumption that the real numbers are countable: it doesn’t hold logically without that.
That means that your argument is, ultimately circular.
Let’s call your pigeonhole statement P. Let’s call the statement that the real numbers are not countable Q.
What you’ve tried to do is build a proof on P, by showing that P => not(Q).
You’re arguing that since P => not(Q), and P is obviously true, that means not(Q).
The problem is, you haven’t proven P. You’ve just asserted it.
What we’re saying is: if you want to claim that P => not(Q) means not(Q), that you need to show that P is true. And when we look at P, we see a statement that we can’t prove from any of our logical axioms. In fact, when we look at P in mathematical detail, what we see is that it’s not possible to prove that P is true without using the assumption that not(Q) is true. So your argument, essentially, is that not(Q) => P => not(Q).
That’s the problem. And I think that both John, various other commenters, and I were all quite clear about that. But you’re trying to weasel around it, by focusing on irrelevancies of language.
John’s argument isn’t “not understanding how radically different the order type of the reals is”. That’s a bit of language that he threw in, but that’s not the meat of his argument. I’ve gone into much more depth than just saying that you’re arguing from intuition, and that’s wrong.
But typical of a crackpot, you act like the actual arguments people presented don’t exist, and find some stupid thing to focus on so that you can pretend that you’ve answered their arguments.
MarkCC,
I don’t know if you were expecting any response to your last post (I assumed that you were just preaching about methodology) so if you did have some other point, please phrase it in the form of a question that can be answered.
I can understand your desire for a proof to be in ZFC, Peano arithmetic and FOPL, it is a good methodology but not the only one, and I am certain that it is not a perfect one. You are not doing yourself any favors if you let any methodology trump understanding. For me it is far more important to understand a proof, than to just know it “works” under some methodology that simply manipulates symbols.
Take, for example, Euclid’s proof that there is an unlimited number of primes. This is one of the most elegant and beautiful proofs of all time, and yet Euclid did not know anything about ZFC, Peano arithmetic or FOPL, he did not even know any Algebra. Euclid understood what prime and composite numbers were and he understood the consequence of those numbers on how many there are, and he was able to communicate that very understanding to his readers, and that is what makes for an excellent proof more than anything else.
Let me give you one more angle on Cantor and see if you don’t understand what is going on.
For every real number, that does not terminate in a string of zero’s, we can define an infinite set of rational numbers that do terminate.
Ex: From π-3 we can define the set of natural numbers {0.1, 0.14, 0.141, 0.1415, 0.14159, … }
Once you understand this simple point, then you will also understand that the unlistable real numbers will also have an infinite set of rational numbers associated with them as well. It will be impossible for there to exist more real numbers that do not terminate than there are numbers that do terminate. The best that we can hope for is, that when we consider the entire set of real numbers that do not terminate and the associated sets of rational numbers that do terminate, that we will cancel out all the duplicates, and end up with just one number in the sets of rationals that terminate. And that is indeed the case.
Ponder on this for a while, and then we can talk about where Cantor went wrong. Please do not forget to bring the same skepticism that you gave to premise 1 in the pigeonhole argument.
@Carl
Notation:
R = irrational numbers in (0,1)
Q = numbers in (0,1) with finite decimal expansion.
P(Q) = power set of Q
You define a map:
F: R -> P(Q).
Precisely, for r in R, q is in P(r) if and only if
q = floor(10^k*r)/10^k
for some positive integer k (floor takes the integer part of a real number).
No problem there.
Now, when you say:
“The best that we can hope for is, that when we consider the entire set of real numbers that do not terminate and the associated sets of rational numbers that do terminate, that we will cancel out all the duplicates, and end up with just one number in the sets of rationals that terminate. And that is indeed the case.”
It seems to me that what you’re saying here is that for every r in R, there exists q in P(r) such q does not exist in P(r’) for any other r’ in R. That, however, is incorrect because we can show that for any q in Q, q is in P(r’) for infinitely many r’.
And once again, you’re quite deliberately avoiding the point. You’re trying to pretend that what I’m doing is obfuscating by bringing up irrelevant formalisms. But I’m not. What you keep trying to do is introduce new axioms without bothering to prove them, and then purporting to prove that Cantor is wrong using your new axioms. And I keep pointing out that you don’t get to do that: if you want to introduce a new axiom for your proof, you need to prove that that axiom is correct.
What you’re doing in sneaking your conclusion in in a backhanded way. All of your variations on your argument work by introducing an unjustified, informal axiom which contains the implicit assumption that Cantor is wrong. If you tried to take your new axiom, and actually prove that it’s correct, you wouldn’t be able to do it without already having a proof that Cantor was wrong. Your “proof” are nothing but circular reasoning.
You’re trying to get away from that be being informal, and trying to get people to rely on intuition. But intuition isn’t proof. Intuition isn’t math.
WRT Euclid’s proof: Euclid wasn’t using set theory (which makes since given that set theory wouldn’t be invented for another couple of thousand years!) But Euclid *was* starting from a basic set of axioms, and using simple predicate logic, and his proof only makes sense when considered with those principles. (As it happens, they’re part of the theory of natural numbers that we typically express using set theory.) In other words, Euclid’s proof is valid, both in the logical mathematical framework of ancient Greece, and in the logical framework of modern mathematics. It starts with nothing but a fundamental set of axioms describing the natural numbers and simple predicate logic (FOPL as it happens, even if it wasn’t known by that name at the time), and then proves the conclusion using nothing but those axioms and the logical rules of inference. There are no new axioms introduced as part of his proof: just the fundamental axioms of natural numbers.
Cantor’s diagonalization is an argument from set theoretic principles. If you’re interested in talking about Cantor’s proof, then you are necessarily talking about set theory. If you’re not, then why are you bothering with Cantor?
But if you don’t want to use set theory, that’s fine. You can build a mathematical foundation without using set theory. But if you do that, there’s no point in talking about Cantor’s proof. Cantor’s diagonalization is an argument from set theoretic principles, which deals specifically with the cardinality of infinite sets. If you’re interested in talking about Cantor’s proof, then you are necessarily talking about set theory.
And you can whine and moan and avoid the point all you want: but if you want to claim to disprove Cantor, you need to deal with the actual mathematical process of proof. You don’t get to arbitrarily add unproven axioms because they look good. I can prove that 0 = 1 if I get to use the axiom that 1/0 = 0. That’s not an arbitrary example: I’ve gotten lots of email from people who think that that’s a reasonable way of defining division by zero.
But the fact that it looks reasonable isn’t good enough. Division means something. It’s got a formal, mathematical definition. The meaning of division isn’t consistent with the axiom 1/0=0. (In particular, it breaks a ton of fundamental identities in real number theory.) I don’t get to use it just because it looks good.
If I want to build a new form of number theory with that axiom, I can do that. But what I’d be doing wouldn’t be real number theory. It wouldn’t support the basic axioms or identities of real number theory. And anything that I prove in that new system wouldn’t be proofs about real numbers.
“I can understand your desire for a proof to be in ZFC, Peano arithmetic and FOPL, it is a good methodology but not the only one, and I am certain that it is not a perfect one.”
If you’re not arguing from ZF (in this case, C is irrelevant), Peano arithmetic and FOPL, you’re not arguing the same thing. There are a lot of mathematical systems, but most of them are basically equivalent to that or include that as a subset. If you’re arguing from a different framework, you need to explain what framework and justify it.
I think you show a failing in your understand when you say “it is not a perfect one”. I don’t know any way to formulate what it would mean for it to be perfect. If it is good, it is surely consistent, and it has been established to be strong enough to prove or disprove most of ordinary mathematics. There is no perfect set of axioms, but it’s clear this set gets us answers that match the real world and solve problems we need to solve.
Ok, I know I’m just being pedantic here but it would be nice if you mentioned somewhere that by set theory you mean ZF (and other axiomitizations of the iterative hierarchy).
If you don’t some crank might eventually discover NF or other systems in which you *can* have an injection from P(X) -> X (in particular the power set of the universal set is a subset of it).
For those wondering Cantor’s argument fails in NF because comprehension is restricted to stratified formulas and the paradoxical sets used in Cantor’s theorem can’t be so defined. This can get kinda weird, for instance the function x -> {x} turns out not to exist on the universal set. Note that it is still the case in NF that the reals have a large cardinality than the integers it only fails on other sets.
To be fair, as much as I’m a fan of NF one can reasonably argue it should be considered more as a variant of type theory than a formalization of our notion of a ‘set’.
——
Hmm, on second thought ignore me. If people were going to do enough research to even realize that things life NF exist they wouldn’t be engaging in this crackpottery in the first place.
Why all this arguing over decimals? Forget about the diagonal argument. There is a simpler well-known proof that there is more than one infinite cardinality. Suppose X is any nonempty set and let P(X) denote its power set (i.e. set of all subsets of X). Suppose f:X –> P(X) is any function. Let S = {x in X : x is not in f(x)}. Let’s show that S is not the image under f of any member of X. Suppose c is in X such that f(c) = S. Then (1) if c is in S then c is in f(c) and so c is not in S; and (2) if c is not in S then c is not in f(c) and so c is in S. Either way there is a contradiction. So, S is not the image under f of any member of X. Therefore, there can be no surjective (i.e. onto) function f:X –> P(X). So, X and P(X) do not have the same cardinality. For example, if X is the set of all natural numbers then X and P(X) are two different infinite sets with different cardinalities.
I’ve heard endless arguments by the cranks over the years against Cantor’s diagonal argument and they generally also claim that there is only one infinite cardinality. I wonder what they would say to the above proof. It’s so simple it can be easily formalized in the language of, say, ZFC and even verified by computer that it is a theorem.
What all the cranks fail to realize is that mathematics is a formal system and that there are definitions, axioms, and rules of inference. You can’t argue against solid theorems by using intuition or natural language. This is exactly the point of the original post. The fact that the cardinality of the set of reals is larger than the cardinality of the set of natural numbers is not open for debate. You cannot disagree with it. (You can fail to understand it, however.) It is a consequence of mathematicians definitions, axioms, and rules of inference. If you don’t like the result perhaps you’d like to propose a different set of axioms, definitions, or rules of inference.
I think that Cantor gets a lot of attention for two reasons.
One is just familiarity: this is the argument that most people familiar with the idea of multiple infinities know.
Second is the fact that it’s constructive in a really good way. The idea that a set’s powerset has larger cardinality than the set doesn’t have the same intuitive power. You can argue, intuitively, against it by just saying that it’s only true for finite sets. 2 raised to the power infinity is still just infinity; so the size of the powerset of an infinite set is still just an infinite set.
Cantor, in contrast, says “You think you’ve got a way of showing that I’m wrong? Here’s how you build a counterexample.”. The powerset argument is vague enough that people think they can just handwave. Cantor, on the other hand, feels different, so the cranks respond to it.
I’d agree down the line, Mark, except that they’re the same exact argument. Leonard’s argument IS the Cantor diagonal proof. Recast the “decimal” version in terms of binary expansions and it’s isomorphic to the special case of Cantor’s diagonal where X is the natural numbers!
@John: Ahhh! I have heard the term “diagonalization” given to describe the proof I gave, but never understood why until your comment. Thanks very much!
To be even clearer: both proofs use an element x of X in two ways: one is as an argument to the hypothesized function f, and the other is as a “place” in the resulting value f(x) in P(X). The trick is going down the DIAGONAL, where you use the same element x in both places: the ‘x’th place of f(x).
John Armstrong said, “Leonard’s argument IS the Cantor diagonal proof.”
A similar flaw in Leonard’s argument appears in the diagonal argument as well, as I will demonstrate.
Cantor said that it is not possible to list the real numbers, but it is possible.
I will list them in binary, (other bases work in a similar way).
First we list all the numbers that have one digit past the binary point from 0.0 to 1.0, there are two of them.
0.0
0.1
Next we copy and paste our list.
0.0
0.1
0.0
0.1
Then append 0’s to the top half of the list and 1’s to the bottom. We now have all 4 real numbers that can be represented with 2 digits past the binary point.
0.00
0.10
0.01
0.11
Repeat, and we have the 8 numbers that can be represented with 3 digits past the binary point.
0.000
0.100
0.010
0.110
0.001
0.101
0.011
0.111
If we repeat this an infinite number of times, we will have a list with an infinite number of rows and each row will have an infinite string of 0’s and/or 1’s. This will be a list of all the real numbers.
Cantor made the claim that given any list of real numbers, he could find a real number that is not on the list by his diagonalization method.
So, if we diagonalize our list we will get the number 0.000… then we will flip all the bits and we should get a number that is not on the list. Our number will be the bitnot 0.111…, but that number is on the list. (it will always be the last number on the list)
The contradiction that Cantor sought will happen when the diagonal intersects the bitnot. So, the number 0.000… infinite number of 0’s … 1, can’t be on the list. And it is not on the list, it is a number that does not exist.
Cantors whole argument hangs on finding a number not on the list, and instead we find a number that does not exist.
What conclusion can you draw from that?
By definition, there is no “last” number on the list because there is no greatest natural number.
It’s like again and again, he needs to prove the point that informal reasoning doesn’t work.
John Armstrong said “By definition, there is no “last” number on the list because there is no greatest natural number.”
The number that we are looking for does not need to be the last number in the list, it can be anywhere in the list and Cantor’s proof will fail.
Do you agree with these three points?
1. The diagonal number on our list will be 0.000…
2. The anti-diagonal will be 0.111…
3. 0.111… will be on the list.
Just for your information, here is a snippet of the list where the number 0.111… will be in some other place.
0.0000
0.1000
0.0100
0.1100
0.0010
0.1010
0.0110
0.1110
0.1111
0.0001
0.1001
0.0101
0.1101
0.0011
0.1011
0.0111
The number we are looking for needs to only be in any of the rows that is incremented by (1/2)^n
“A similar flaw in Leonard’s argument appears in the diagonal argument as well, as I will demonstrate.”
I looked at your post, and you didn’t even address my argument! How can you point out a flaw in my argument if you don’t even address it? Your next statement is:
“Cantor said that it is not possible to list the real numbers, but it is possible.”
Then you go on to purportedly give a list of the real numbers. This does not address my argument at all. By the way, your listing of the real numbers shows that you know nothing about the real numbers or mathematics.
You say:
“If we repeat this an infinite number of times, we will have a list with an infinite number of rows and each row will have an infinite string of 0’s and/or 1’s.”
That’s ridiculous. What do you mean by “repeat this an infinite number of times?” If you mean you have one row for each natural number (which is what a listing is) then every real number in your list has a finite number of bits after the decimal point (binary point?). If you don’t mean that, then you don’t even understand the statement that Cantor made much less his proof. A listing is a function from the set of natural numbers to some target set.
When you speak about math, use math, or you don’t make any sense.
By the way, before you go on and use any further crank arguments that I’ve heard a million times, please realize that there is no such thing as a natural number with infinitely many digits–each natural number has finitely many digits. I can prove that by something called mathematical induction.
You don’t seem to realize that math is a formal system. It has symbols, definitions, axioms, and rules of inference. It’s all very non-controversial. The proof I gave is simply a statement that a certain string of symbols (the theorem) is derivable from other strings of symbols (the axioms) by applying certain rules of the game (the axioms). That’s it. We are not discussing reality. Hell, I don’t even know what a real number would be in reality. I also don’t know if anything corresponding to the mathematically infinite exists in reality. This is why we cannot use intuition. By the way, your intuition doesn’t even make sense. Cantor’s result is not even counterintuitive or paradoxical.
Your list is missing a bunch of real numbers, for example 1/3 and pi/4. Your list contains no numbers whose binary representation is non-terminating.
You are arguing with a guy that a couple posts ago
http://www.goodmath.org/blog/2016/07/05/cantor-crankery-is-boring/#comment-155140
explicitly said that there is a number c∈ℕ such that c∉ℕ and that this implies no contradiction, while talking about the end of an endless list. Just saying.
Every number on the proposed list is the reversal of its place. That is:
f(0) = 0.[reverse of 0 in binary]
f(1) = 0.[reverse of 1 in binary]
f(2) = 0.[reverse of 2 in binary]
so the nth place to the right of the binary point in 0.[reverse of n in binary] is the nth place to the left of the binary point in n. But if this were 1 then the binary expansion would be greater than 2^n, but n < 2^n, so this is always 0.
So
1) the "diagonal" number is 0.000…
2) the complement is 0.111…
Now as to 3, we notice something else from the description above: all f(n) are not only 0 in the nth place, they're 0 everywhere PAST the nth place. That is, no number that shows up on the list has more than a finite number of 1s in its expansion.
But 0.111… has an infinite number of 1s in its expansion, so NO, it does not occur in the list.
John Armstrong said, “But 0.111… has an infinite number of 1s in its expansion, so NO, it does not occur in the list.”
1a. If we turn our list upside down, then will our first number be 0.111… ?
2a. Will the diagonal number in our list be 0.111… ?
3a.Will the anti-diagonal be 0.000… ?
4a. Will 0.000… be somewhere in the list ?
To construct our list we begin with
0.1
0.0
Then copy and paste
0.1
0.0
0.1
0.0
Add 0.01 to the top half of the list then add 0.00 to the bottom half
0.11
0.01
0.10
0.00
Repeat, add 0.001 to the top half 0.000 to the bottom
0.111
0.011
0.101
0.001
0.110
0.010
0.100
0.000
Etc, forever
0.1111
0.0111
0.1011
0.0011
0.1101
0.0101
0.1001
0.0001
0.1110
0.0110
0.1010
0.0010
0.1100
0.0100
0.1000
0.0000
Your tree contains all real numbers between 0 and 1; it just doesn’t pair these numbers with naturals.
Suppose we want to start numbering the entries of your tree from top to bottom, then left to right.
1 -> 0
2 -> .1
3 -> 0
4 -> .01
5 -> .1
6 -> .11
7 -> 0
8 -> .1
9 -> .01
10 -> .110
11 -> .001
12 -> .101
13 -> .011
14-> .111
and so on.
Give me absolutely any natural, and I can tell you which element of your tree it pairs to. But all of the naturals pair to elements of your tree that have terminating binary representations! You have made a tree that contains every real number 0 to 1, but you haven’t given a way to pair each the elements of the tree with a different natural!
Now Carl’s list contains no decimal expansions with an infinite number of 0s, like 1/3 = 0.010101…
@John Armstrong,
Since you did not object to premises 2a, 3a and 4a from my previous post, I will assume that you think they are valid. Those three points are enough to counter Cantor’s claim that it is always possible to find a real number that is not in the list, given any list of numbers.
To salvage the conclusion of Cantor’s argument, you have proposed some other method to find a real number not on the list. You claim that 1/3 is not on the list because it’s binary expansion has an infinite number of 0s. (I don’t understand your reasoning in this, and it would help if you would explain further.)
We will examine 1/3 or binary 0.010101… to see if it is in our list and where it is.
First we will build our list from the beginning and see if 1/3 could be on the list.
1 – 0.1
2 – 0.0
1/3 can’t be in the first row because the first digits are different, but it could be in row 2 of the 2 rows.
We will expand the list.
1 – 0.11
2 – 0.01
3 – 0.10
4 – 0.00
1/3 could still be in row 2 of 4 rows.
1 – 0.111
2 – 0.011
3 – 0.101
4 – 0.001
5 – 0.110
6 – 0.010
7 – 0.100
8 – 0.000
We can now see that 1/3 can’t be in row 2 because it is different in the third place, but it can be in row 6 of 8 rows.
1 – 0.1111
2 – 0.0111
3 – 0.1011
4 – 0.0011
5 – 0.1101
6 – 0.0101
7 – 0.1001
8 – 0.0001
9 – 0.1110
10 – 0.0110
11 – 0.1010
12 – 0.0010
13 – 0.1100
14 – 0.0100
15 – 0.1000
16 – 0.0000
1/3 can still be in row 6 of 16
1 – 0.11111
2 – 0.01111
3 – 0.10111
4 – 0.00111
5 – 0.11011
6 – 0.01011
…
22 – 0.01010
1/3 can’t be in row 6, but it can be in row 22 of 32 and so on.
We should be able to see a pattern emerge here.
2 / 2 = 1.0
2 / 4 = 0.5
6 / 8 = 0.75
6 / 16 = 0.375
22 / 32 = 0.6875
22 / 64 = 0.3438
86 / 128 = 0.6719
86 / 256 = 0.3359
342 / 512 = 0.6680
342 / 1024 = 0.3340
1366 / 2048 = 0.6670
1366 / 4096 = 0.3335
5462 / 8192 = 0.6667
5462 / 16384 = 0.3334
21846 / 32768 = 0.6667
21846 / 65536 = 0.3333
So if our list were shrunk to a unit length like one meter and our font were made infinitesimally small, then the location of 0.010101… on the list would oscillate between 1/3 and 2/3 of our meter long list. And as our list goes internally to infinity 1/3 would be on that list.
Just because he got tired of responding in the same tired way to the same tired claims doesn’t mean that he accepted them. It just means that he got bored with repeating himself.
You’re not saying anything that we haven’t already responded to a dozen times.
Now, Carl, you’re just flat-out lying. I said
which directly contradicts your (4a)
To be fair, I don’t think he’s lying. I just think he doesn’t understand the actual mathematical implications of many of the things he says, and so he doesn’t understand that your response actually applied to his statement.
@John Armstrong,
I apologize for offending you, at times internet debates are a more of a contact sport than we may wish them to be. For what it is worth, the reason I was “picking” on you, is because I thought you were the most reasonable voice in this thread.
Mark is right about the importance of ideas being communicated accurately from one person to the other. In this case I really did not understand, and it would be very helpful if someone could explain it.
John said “Now Carl’s list contains no decimal expansions with an infinite number of 0s, like 1/3 = 0.010101…
which directly contradicts your (4a)”
Where 4a. is “Will 0.000… be somewhere in the list ?”
Looking back on what you said, it seems like the thing that I totally missed is that 0.0 might not be the same thing as 0.000…, is that what you were saying?
I’m just going to point out that you’re the guy who’s claiming to be able to overthrow the conclusions accepted by almost 100 years of the best mathematicians on the planet. But you’re not able to follow a very simple mathematical statement, because you lack the background to understand simple terminology.
You’ve repeatedly demanded that other people do your work for you. You’re the one making grandiose claims. So you’re the one who needs to do the work.
You need to show that you understand what you’re claiming to prove. You need to show that you’re capable of actually formulating a valid proof. You haven’t been able to do that. Instead, you’ve just thrown up smokescreens, trying to constantly obfuscate the fact that you have no idea how to actually do math.
So, to prove that reals are countable, this is, that you can assign a natural number to every real, Carl proposes a tortuous procedure that, in the limit, associates a _real_ (and not a natural) in [0,1] to every… real in [0,1]. Great. Now the only step remaining is to prove that you can associate a natural number to every real number. His proof seems recursive.
The irony is that it is painfully obvious that Carl is not building a countable list, as it has already being told to him several times, and as even him should have realized by now given the painfully gibberich he had to resort just to explain his procedure. What he is building is a kind of uncountable tree called… Cantor’s tree. Oh the irony!
By the way, as I got caught again in the trap of returning to this Cantor’s infinite topic, I will explicit the error in Carl last attempt at an argument, which is the very exact error in Gabriel’s rants, which is a very common error. It has already be said here, but I’d like to write it more explicitly.
I would have told him before, but as his description of “the series of sets Sn of all binary sequences of length n” was taking him too many many posts, while irrelevantly permuting its elements, exchanging 1s and 0s, and so on, I never had the opportunity.
As Carl did not even formalize his argument, I am doing it here, to show his not so hidden assumption about which he is not even concious:
1) let Sn=”the set of all binary sequences of length n”
2) let P(X)=”X is enumerable”
3) show that ∀n∈ℕ: P(Sn)
4) wrongly assume that ∀n∈ℕ: P(Sn) implies P(limit of Sn as x→∞)
⇒ by 3 and 4, and as (limit of Sn as x→∞)=ℕ, ℕ is countable
The problem is that there assumption 4) is completely and utterly unjustified, and it is wrong. Just imagine the kind of mathematics you could do with such a rule:
1) let Sn=”the first n natural numbers”
2) let P(X)=”the sum of elements in X is finite”
3) show that ∀n∈ℕ: P(Sn)
4) wrongly assume that ∀n∈ℕ: P(Sn) implies P(limit of Sn as x→∞)
⇒ by 3 and 4, the sum of all natural number is finite
You could do all kind of silly things, like prove that 0>0 or whatever you do. And that is because 4) is an inconsistent assumption.
Of course Carl is not conscious of this, being all consumed by his explanation of the absolutely trivial Cantor’s tree. He just assumes it implicitly, without even thinking about it, so he just spend all his time explaining the trivial points 1) and 2), and showing us examples of 3). But 4) is the actual issue here, which he never address.
So please, future Cantor’s counterprover, please, do not explain us again what a tree containing all real numbers between 0 and 1 is. We know, it is trivial. Instead, tell us why we should assume 4).
@John Fringe said “Instead, tell us why we should assume 4).”
That is a good question, perhaps you could help us out by telling us why Cantor assumed 4).
1) let Sn = ”a set of real numbers with n elements”
2) let d(X ) = ”anti diagonal of X”
3) show that ∀n∈ℕ: d(Sn) ∉ Sn
4) wrongly assume that ∀n∈ℕ: d(Sn) ∉ Sn implies d(limit of Sn as x→∞) ∉ (limit of Sn as x→∞)
⇒ by 3 and 4, (limit of Sn as x→∞) is uncountable
The only little litthe problem there being that Cantor’s proof does not even remotely resemble what you have written. Annoying, isn’t if?
@John Fringe, wrote “Annoying, isn’t if?”
No, not annoying at all. Just the opposite, it is very helpful to know that this version of the argument is not correct. This should help to take me closer to the correct, formal proof of the diagonal argument. If you know what it looks like, I would greatly appreciate it if you cold post it or link to it.
John Fringe said “Cantor’s proof does not even remotely resemble what you have written.”
Tu quoque, the “proof” that you formalized, does not even remotely resemble what you have written either. You did not understand what I was saying. It was not a proof or even an argument, it was a counter example.
To refute any proof, Sir Andrew Wiles proof for example, I would not need to understand it or even look at it, all I would need to do is simply produce a counter example (4 integers that satisfies the equation x^n + y^n = z^n). And that is what I did here, I gave you a counter example to Cantor’s proof.
Cantor said that any list of real numbers will be incomplete because he could always find a number that is not in the list, by diagonalizing the list, and then changing every digit in the diagonal to something else. I produced a list of real numbers and diagonalization did not produce a number that is not on the list, so Cantor has been refuted.
Does my list prove that the real numbers are uncountable or unlistable? No, it only shows that Cantors proof is not a valid proof to show that the real numbers are uncountable or unlistable.
Thanks for the replay, MARKCC. Yes, I understand why the cranks gravitate toward the diagonalization argument. Decimals are intuitive. I also understand that if you say a power set has a larger cardinality than the original set, then the cranks will say, “Yes, for finite sets, but 2 to the infinity is still infinity.” But the proof I presented in my last comment does not simply state that the cardinality of the power set is larger than the cardinality of the original set, it *proves* it. The proof is short, simple, and unassailable, and I still wonder how a crank would attack it. There doesn’t seem to be a foothold for crankery. Of course, I find the diagonal argument you’ve been discussing also to be short, simple, and unassailable (smile). Maybe it’s a matter of “I don’t care about your proof, I have my proof that the cardinalities are the same; so either math is broken or your proof is wrong.”
The solution to your paradox, is to find a function that maps x to f(x) in such a way that x is never an element of f(x)
Let X be the set of natural numbers N.
Let S = {x in N : x is not in f(x)}
Let c be in N and c maps to S
Then we can map them like this
x f(x)
———–
1 {}
2 {1}
3 {2}
4 {2,1}
5 {3}
6 {3,1}
7 {3,2}
8 {3,2,1}
9 {4}
etc…
…
…
c S
Since x is never in f(x) then
S will be the set {1,2,3,4,5,6,7,8,9, etc…} which is the universal set N
But if c is not in S then it should be by the definition of S
Since S = N and c is in N then c is in S as well
No contradiction
“The solution to your paradox, is to find a function that maps x to f(x) in such a way that x is never an element of f(x).”
When debating cranks, I make it a policy to stop reading their post after the first error. Your first sentence makes no sense for a few reasons, and therefore I did not read beyond it.
First I have no paradox. I presented a very clear, simple proof of a standard theorem.
Second, I am not requesting a “solution.” I asked no questions. I posed no problems. I stated a theorem and gave a very clear, simple proof of it.
Third, even though I am not sure to what paradox you are referring or what it is you are trying to solve, I will say that finding any function with any properties you mention has nothing to do with the proof of the theorem I gave. I proved (or rather someone else did and I am reporting the proof) that there is no surjection from X to P(X) by supposing there is a surjection and providing a contradiction. To address this you cannot begin by trying to find a function. You can only point out any errors I may have made in my proof. It seems you may want to state the negation of my theorem and then provide your own proof of its negation. If this is what you wish to do, I have no desire to read it. If you have no desire to read my theorem and its proof and check its validity then please don’t reply to my post.
Yes contradiction. Every single natural number maps to a finite set under the function you describe [if you wanted to, you could prove by induction that for any n, f(n) has cardinality at most log_2(n), but the exact sizes are unimportant]. Hence no such natural number c exists which would map to S=N.
More directly, borrowing from the original argument above, if f(c)=S=N, then c does not belong to S by definition of S, so c does not belong to N, the domain of f. Thus no such c exists.
I think the key thing you are misunderstanding in all your arguments is the fact that *all natural numbers are finite*. If I wrote a program to list out the natural numbers in order, any particular number would be reached in finite time. It boils down to a misunderstanding of the distinction between “there exist natural numbers which are arbitrarily large” (true) and “there exist natural numbers which are infinite” (false).
The sequence of points (n-1)/n with limit 1 is a strictly monotonic increasing sequence, i.e., according to analysis it does not attain its limit 1 as a term. The points with coordinate (n-1)/n lie on the real axis in the interval [0, 1). When connecting every point geometrically by a line to the origin 0 we get the sequence of intervals [0, (n-1)/n]. Obviously these connections have no influence on the limit, such that the limit of this sequence is [0, 1]
The “set-theoretical limit” is the union of all closed intervals, namely [0, 1). However, this is not the least upper bound because every x < 1 is contained in infinitely many closed intervals [0, (n-1)/n] of the sequence together with infinitely many y such that x < y < 1.
We see here a tiny difference between the analytical limit and the set-theoretical limit. This is usually acknowledged. "In the infinite" however, where this gap grows to a yawning chasm, it is neglected. If the sequence of FISONs is considered then their analytical (improper) limit omega with |omega| = aleph_0 is identified with the union |N of FISONs (or natural numbers) with cardinality less than aleph_0
As a result we can state: The union |N of FISONs is not the (improper) analytical limit omega of the sequence of FISONs and does not contain aleph_0 FISONs (or natural numbers).
Therefor set theory is nonsense from the scratch.
Regards, WM
I believe that I can summarize this with: “Set theory contains results that I don’t like, therefore it’s nonsense”.
That’s not the way that math works. If you want to show that set theory is nonsense, what you need to do is show that it’s inconsistent. You’re not doing that.
There are many inconsistencies. For instance it is impossible to order non-material elements without identifying and distinguishing them by finite names. Since all finite names in all possible languages form a countable set, the axiom of choice is contradicted for uncountable sets. But set theorists are unable by a psychological defect to recognize contradictions:
https://www.hs-augsburg.de/~mueckenh/Transfinity/The%20little%20demon.pdf
It is not a matter of mathematics.
Regards, WM
No, you are going astray. Set theory yields results that contradict mathematics as well as the foundations r5equired for all axiomatic systems.
An example for the latter is the fact that only countably many elements can be distinguished or defined but uncountably many elements can be well-ordered. That is an axiom like “there are 10 even prime numbers”.
An example for a contradiction to mathematics is the claim that the following arithmogeometrical figure contains more numbers than every row. If we shift all numbers into the first row, then we get more than are in any row.
1
1, 2
1, 2, 3
…
This contradicts inclusion monotony.
Regards, WM
http://www.goodmath.org/blog/2016/07/05/cantor-crankery-is-boring/#comment-155204
If only a genius mathematician could prove that if 0.111111… is the n-th element of a list of numbers so that the diagonal has a 1 in the n-th position then the n-th digit of the diagonal’s complement will be 0 so it cannot be 0.1111111…
(Ops, I’ll apply it to myself. I’m arguing with a guy who talks about the end of endless lists and that contradictions do not imply contradictions).
Can someone show me why this argument is wrong? Thanks. I assume you know the diagonal method.
Before choosing a number, Cantor’s number falls into the interval (0,1). After choosing his first digit, it falls into the interval [0.1,0.2). After the second, [0.11,0.12); then [0.112,0.113); then [0.1121,0.1122); and so on. Each of these intervals can be bijected to [0,1), and so all contain the same number of elements. Ergo, no matter how many elements of the enumeration Cantor examines, he always has at least as many still to check as when he first starts. Consequently, the number he is identifying is in the enumeration, it’s just in that part he hasn’t looked at yet. In terms of set sizes, Cantor is arguing that infinity divided by 10 an infinite number of times is 0, which looks to me like nonsense.
The problem I see with your argument is that it does argument nothing against Cantor’s theorem, if that is what you are asking.
Before the “Consequently, the…” you are just speaking about how the tree containing all sequences of symbols (which, by the way, is called Cantor’s tree, at least for binary sequences) contains any concrete sequence.
But this has no relation with the uncountability of reals. Cantor’s tree is known to have an uncountable number of nodes and, being infinite, it has no leaves at all. You are addressing this countability nowhere. So, what’s the argument, actually?
This brings me to the main point, which Mark correctly identifies: your “argument” is loosely described, and this allows you to take unjustified steps you do not see, like going from this tree containing all numbers (which pose no problems) to the “consequently, the number he is identifying is in the enumeration”. In what enumeration, may I ask? Are you assuming a priori that a tree is an enumeration? Because then yes, if you assume reals to be enumerables, then reals are enumerable. But that is a wrong assumption, as Cantor’s theorem proves. So, what enumeration are you speaking about?
The only enumeration I can see in your argument is the steps required to find a concrete real in the tree of all reals. But that is clearly enumerable, as the digits in a decimal expansion are enumerable. So, again, what enumeration are you speaking about?
So, in the end, the particular problem is that you are trying to counterargument the non existence of a bijection between naturals and reals without addressing in any way this enumeration. And the general problem is that you are not formalizing an argument enough for even you to see this.
That’s not the diagonal argument. Certainly looking at a finite number of elements on an infinite list is not sufficient to say a number is not on the list, but by that method one can’t exclude that 3 is not on a list of the powers of two. Instead the diagonal argument says give me a list; I will show you a number that logically can’t be on that list.
Let me be more explicit, because I ignored that the number you are speaking about is Cantor’s number because you never use its properties, so you could just be speaking about any number equally, and this is why I say you are not addressing Cantor’s argument in any way.
You say x is Cantor’s number, and then you show it can be found between the reals. Which is true. But if x is Cantor’s number, then you are assuming that the reals are countable (which is required to define Cantor’s number), and you can use this to lead to a contradiction (by Cantor’s proof). So you are working in an inconsistent system. And, in an inconsistent system you can prove everything you want, a thing and its opposite. You are showing that x can be found in [0,1], but it is equally possible to prove the opposite. This is exactly the expected when working with inconsistent axioms.
Because, as I said, you are not addressing the countability of reals and you are just ignoring any property of Cantor’s number.
To clarify, my post is addressing Cantor’s diagonal argument, in which he starts by assuming an enumeration of the real numbers, and then by examining successive elements and digits in the enumeration shows the existence of a number that is not part of it. John Fringe, I don’t understand your posts. Your arguments don’t seem to have anything to do with my post.
John Fringe, sorry, I misread your reply. I am not making an argument about Cantor’s number (x), I am making an argument about the process used to identify that number. I am not assuming that the reals are countable. Cantor is assuming that they are and then trying to use his method to prove the opposite.The question at hand is whether that method actually works.
I am pretty certain that you are assuming that the reals are countable, because you need that to define Cantor’s number, needn’t you?
I am assuming that by Cantor’s number you are referring to the number resulting from taking a list of all reals and changing taking a digit different from the first one from the first number, the second one from the second number, and so on. So, if you do not have such a list (that would make reals countable), what are you calling Cantor’s number, exactly?
With respect to my posts, you may understand better what I mean by this example.
Suppose I call n∈ℕ a natural number such that n>6 and n<4.
I claim that there is no such number in ℕ, and I prove it because, by the transitivity of <, I can deduce 64, so there would be a contradiction.
This is what Cantor did, a proof by contradiction. One assumption is wrong. In his case, countability of reals. In mine, the existence of a number with such weird properties.
Now your argument is basically equivalent to this one: there is indeed a n∈ℕ such that x>6 and x<4 because, if you assume so, then you can design a procedure to find it. For example, as ℕ is enumerable, you can start with 1, check if it is n, and if not try the next. Under the assumption that there is such n in N, you will eventually find it. So it exists. What's wrong with this argument?
What is wrong with your argument is that you are working under an inconsistent system. There you can prove whatever you want. Of course, inconsistencies do not jump at your face, you have to find them. The fact that you didn't fint one does not mean there are not. In fact, you habe been told where it is. You are assuming it to even define the number you are working with.
I will ask you to explicitly define what you are calling Cantor’s number, because Cantor defined his contradictory number from an assumed list of all reals, and without that list you cannot build the number. Now you tell me you are not assuming that reals are enumerable, so I highly doubt that we are talking about the same number.
John Fringe, sorry if I’m not making myself clear. I’ll start again.
Cantor uses his diagonal method to show that there is no enumeration of the real numbers. He starts by bijecting the real numbers onto the interval (0,1) and then assuming that the numbers in that range can be enumerated in some fashion. He constructs a number as follows. He examines the first digit of the first number in the enumeration. If it is a 1, he chooses a 2, otherwise he chooses a 1. He examines the second digit of the second number and does the same thing. In this fashion he examines each succeeding digit in each succeeding element of the enumeration, always choosing a different digit to that present.
Initially the number he is constructing could be any number in the range (0,1). After choosing the first digit (say it is a 1), it can be could be any number in the range [0.1,0.2). After the second, [0.11,0.12). And so on. What these ranges are will depend on what digits he chooses, but they will always have the same format. Every one of these ranges can be bijected onto the range [0,1), and so they all contain the same number of elements. This means that no matter how many elements of the enumeration Cantor examines, there will always be at least as many left to examine as when he first starts. In order to construct his number he must examine every element of the enumeration, but he can never do that. So he can never finish constructing his number. Consequently, the number he is identifying is in the enumeration, it’s just in that part he hasn’t looked at yet. And so he has not shown that there is no enumeration of the real numbers.
In terms of set sizes, Cantor is arguing that infinity divided by 10 an infinite number of times is 0, which looks to me like nonsense.
Given an enumeration of the reals E, the nth digit of Cantor’s number is 5 if the nth digit of element n of E is 2 and 2 otherwise. (That’s one formulation, but equivalent.) Therefore you can’t find the Cantor’s number in the enumeration, because if you did it would differ at digit n, where n is the place of Cantor’s number.
“left to examine” here has nothing to do with the mathematics of the issue. By limiting Cantor to finite actions, you’re basically dismissing the idea of infinity. Which is a way to do mathematics, but not one where you can argue meaningfully about the size of the reals, nor one which has much to do with mathematics as everyone knows it.
Cantor is arguing no such thing. The question is not well-defined; take the natural numbers, and remove the first item over and over. After doing that an infinite number of times, you’ll have no elements left. Remove the second item over and over, and after an infinite number of times, you’ll have just the first left. Remove the ten thousandth over and over, and you’ll have 9,999 left. Remove the first even element over and over, and you’ll leave the infinite odd numbers. Similar but more complex arguments could be made for division.
Ahem, that’s what I expected. You are not working with Cantor’s number, then. Cantor’s number is not constructed progressively. It is defined. And the fact that any finite approximation does not implies any contradiction does not mean that the full number does not implies one. By thinking in proofs as processes you are never going to find any infinite. Ever. Nope.
But then, you are not using any property of Cantor’s number, so you are just proving that any real number between 0 and 1 is in the (uncountable) tree which contains all real numbers between 0 and 1. This has no implications at all for the countability of reals.
I believe you are not understanding where the contradiction is.
What causes a contradiction is to assume the countability of reals. Why? Because then you can define Cantor’s number and prove that it is a real and it is not in the enumerable list of reals.
You are not doing this. You are following a procedure where you locate a real in the tree containing all reals, while “not assuming the countability of reals”. If you do not assume the countability of reals you cannot define Cantor’s number, the you are not defining Cantor’s number, because you really actually need an infinite list to define what its infinite digits are by diagonalization, and either
1) if you don’t assume that reals are enumerable, then there is no contradiction. Your list of infinite reals cannot contain all reals as Cantor said, so you are just defining a real by diagonalization from a list that is an enumerable subset of reals. So, in the end, you’ve got that a real is not in a subset of reals, that pose no problem. But you are not even checking this, because you are just checking that it is in the tree of all reals. Of course it is, but this has no relation with Cantor or the countability of numbers. And, in any way, Cantor’s number defined from a partial subset of reals is not Cantor’s number.
2) if you actually assume that reals are enumerable, contrary with what you are saying, then you can actually define Cantor’s number from the list of all reals. But then you can arrive at a contradiction the way Cantor did. The fact that you are not explicitly arrive at a contradiction has no consequences, because you can operate in a inconsystem system without arrive at a contradiction. Contradictions do not appear in every sum. You will still infer invalid things, you just do not know. And why are you not finding the contradiction? Because you are not looking your real in the enumerable list from the start. You are looking for your number in the uncountable tree of all reals. You expect that if there was a problem you would find a problem with this, but that is false, because the inconsistency is not in Cantor’s number, but in the supposition of the enumerability of reals, that you don’t use. If I assume the existence of a natural number n6 then my system is inconsistent, but I still can sum 2+1=3 because I am not using in any way the inconsistency. Of course, the sum has no meaning, but I will not see it.
In addition to this, you have a big confusion with proofs and processes. I can check all my life that 1/2>0, 1/4>0, 1/8>0, 1/16>0, and I will never ever understand that the limit of 1/(2**n) is not greater than zero. It is not.
So, to sum up, there is a whole lot of problems with your argument, even when in the end it has no relation to the problem of countability of reals at all.
> Given an enumeration of the reals E, the nth digit of Cantor’s number is 5 if the nth digit of element n of E is 2 and 2 otherwise. (That’s one formulation, but equivalent.) Therefore you can’t find the Cantor’s number in the enumeration, because if you did it would differ at digit n, where n is the place of Cantor’s number.
So it differs from every element up to the one at position n. That means it’s either not in the enumeration or it is in the enumeration at a position greater than n. In order to actually define a number that is not in the enumeration Cantor must produce a number that differs from every element in the enumeration, not just from every one up to position n. He can only say that the number he is defining is not present when he has looked at every number in the enumeration, and he can never do that because he can never reduce the size of the set of elements left to look at.
The truth is Cantor never actually defines any number. All he ever produces is a finite prefix, which has the property that all the numbers that start with that prefix are in that part of the enumeration that he hasn’t looked at yet.
> “left to examine” here has nothing to do with the mathematics of the issue. By limiting Cantor to finite actions, you’re basically dismissing the idea of infinity.
But you are assuming that if Cantor takes an infinite number of actions he will examine the whole enumeration. It’s that assumption that is wrong.
Cantor’s proof isn’t a computer program: it’s a definition.
By your reasoning, every proof using mathematical induction is invalid, because if you look at it as a program, a mathematical induction can only ever prove anything for a finite prefix of the infinite sequence of natural numbers.
That’s not how math works.
You are talking without understanding what a definition is, Jim. This is preventing you from understanding Cantor’s proof, because it implies definitions, which you don’t understand. Let me tell you what a definition is and why it does not require an infinite amount of steps.
I may define P(x)=”x is a living person and x is at least 6 foot and 7 inches”. This defines the people I am talking about. Note that I have not find them, I don’t know who they are, I don’t even know if there is any person fulfilling this predicate, and more importantly, that to specify them has take me notoriously less time (and less money) than it would have taken me to go person by person in the world to see who they actually are.
Similarly, when I define sqrt(2) to be any entity such that fulfills P(x)=”x*x=2″, I have already defined what entities I am referring to. I have not found them explicitly, but the entities I am referring to are settled. Even if it would take me infinite steps to compute their decimal expansions. And, more importantly, I can operate on these entities and prove things about them even not knowing their explicit form. For example, I can prove sqrt(2)(aqrt(2)+1) = sqrt(2) + 2 very trivially. And I have not taken the infinite steps required to completely express sqrt(2) in decimal form.
The fact that I don’t know the explicit names of those very tall people nor the infinite digits of sqrt(2) does not retract in any way from the definition. The definition already specifies clearly what elements I am talking about. And I can make reasonings about them base on the predicate that defines them. Without spending the time required to find them.
This is what you don’t understand, despite being absolutely trivial.
This is what Cantor’s definition of number x do. Given the assumption of a list L containing all reals, x is a number such that fulfills P(x)=”the nth decimal digit of x is makeDifferent(the nth decimal digit of x”. He then proves, without the need to compute it, that this number exists under this assumptions (which is trivial) and that it leads to a contradiction. So some assumption is wrong. And if you don’t assume the existence of L, then there is no contradiction.
Now, what would take an infinite number of steps is to express this number x, not to define it. But nobody needs to do so. Defining it does not take any step at all, and neither does proving its properties and arriving at the contradiction.
By critizing Cantor’s proof on the fact that expressing the number he defined would take an infinite amount of work only proves, and sorry to express this so explicitly, that you have no clue about what a definition is and have no mathematical training nor understanding at all. Which, to pretend to refute a century old formally proved theorem would be of great help.
Of course, you are making more fallacies based on your lack of mathematical understanding, like believing that proving that x is in the tree of all reals (of course, is a real) some how is equivalent to prove that it is in a countable list, that would have any relation to Cantor, while what you are trying has none. Of course the assumed real x would be in the tree containing all reals. But when you are not grasping what a definition is and what makes them different to computer programs, that’s minutiae.
Thanks for your input guys. I understand the point you are making, I don’t agree with it. Further argument would be circular, and that’s boring. So I’ll present the same argument a different way.
Assume there is an enumeration of the natural numbers. Assume that each element can be padded with leading zeros as necessary. Examine the units column of the first element, the tens column of the second element, the hundreds column of the third element, and so on. In each case, choose a different digit. This process constructs (or if you prefer defines) a natural number that does not match any element of the enumeration. Therefore, the natural numbers cannot be enumerated.
Applying Cantor’s diagonal method to the natural numbers produces a conclusion that is obviously wrong. So there must be an error in the logic somewhere. Where is it?
Merry Christmas.
“Obviously wrong” is a pretty bad criteria for math. “Obviously wrong” comes down to “my intuition says that this isn’t correct”. But our intuition is frequently drastically wrong.
For example, I know what the square root of two is. Intuitively, it seems like I should be able to write a program which looks at other programs, and tells me whether or not they compute the square root of two.
But I can’t. It’s impossible. The intuition is wrong.
Heck, intuitively, the idea of a number that goes on and on forever without any pattern seems ridiculous. I remember, when I first learned about irrational numbers, it bugged the heck out of me. But numbers like that do exist – and I’ve learned what’s wrong with my intuition about that.
Math is about formal reasoning, not about intuition.
The procedure with natural numbers you propose does not define a natural number, so it poses no problem by not being in the list. It defines other kind of entity. I could easily prove that to someone with any kind of mathematical training or at least a good actitude. But i am getting tired and writing from a phone, so instead of that, i prefer to put the ball in your roof: you freely claimed that the thing you are defining there is a natural. Prove it. Hint: natural numbers have a finite number of digits, your entity does not. Hint 2: you will not be able. Hint 3: if you are thinking of apply this to cantor’s, you already showed that x is indeed a real.
Observe that I explicitly told that Cantor proved that there was a real with those properties under his assumptions, while you cannot prove that there is a natural number with your properties. You just do not understand cantor nor how logic works.
All natural numbers in binary must be “padded” by an infinite string of 0s. Almost none (in the technical sense, but read this as “very few”) of the binary expansions of real numbers in [0,1) end in an infinite string of 0s. That’s the difference.
Oh, and to answer your sneaky implication that “there must be an error in the logic [of Cantor’s argument]”: the error is in the logic of your own argument.
markcc: “Obviously wrong” is a pretty bad criteria for math.
Are you saying that the conclusion is not obviously wrong? Do I need to produce the identity bijection? A good mathematician doesn’t need to be spoon fed. I realise that I am not good at explaining things, but really.
John Fringe: The procedure with natural numbers you propose does not define a natural number,
So demonstrate that it doesn’t. You’re big on preaching, but you’re not very big on actual mathematics.
There is no number infinity. Nothing has a digit count equal to infinity. So no natural number has infinity digits. But then, that’s not what infinity means. Rather, it means there is no upper limit. There is no upper limit to the number of digits that a natural number can have. If the enumeration contains n elements then the defined number will have n digits. If we were talking about finite things that would be a problem. But we’re not. I can biject the set of positions of elements in the enumeration onto the set of positions that can exist in the representation of a natural number. So, however many elements there are in the enumeration, there is certainly a natural number that has that many digits.
Yes, I am saying that the conclusion of Cantor’s proof is not obviously wrong.
For the same damn reason that I’ve explained literally hundreds of times over the history of this blog. And I’m tired of it.
@markcc, you read Jim’s post too fast (not that I blame you): what he found “obviously wrong” was the conclusion that natural numbers cannot be enumerated.
@Jim
No, because the enumeration has an infinite number of elements. That’s exactly why Cantor’s proof applies to real numbers but not to natural numbers: real numbers can have an infinite number of “digits”, whereas natural numbers cannot (and you seem to agree with this).
Jim, there’s basically no mathematician that believes the way you do. So, yes, if you’re arguing against a century of mathematicians it would help to produce a very solid argument.
We have an enumeration of the natural numbers: f(n) = n. For n > 1, the digit in position n is 0. Thus your “natural number” that is not in this list has non-zeros in all positions, therefore it’s not a natural number.
“the enumeration contains n elements” is your problem. It doesn’t have n elements, for any n ∈ ℕ. You’re basically fighting the idea of infinity, the idea that infinity can be considered a number, or rather countable infinity can be considered a number. Rejecting the idea of infinity like that can be done, but you basically loose the ability to define reals at all, making the question moot.
Oh, my. I knew you were mathematically challenged, but, onus probandi? Seriously? You make the unjustified aseertion that cantor diagonalization on naturals produce a natural number and it is a valid proof until someone (me) explicitly prove it trivially wrong? Seriously? Because you are right by default? Even when you can just go and read any of the century of papers since cantor? And you call this “mathematics”?
Well, even then i would go explain uselessly to you, but tbe competent people here are faster than me.
You guys just don’t get it.
If I have a set of symbols containing at least two symbols, and I form ordered strings (or series) of those symbols of length n, and I put n of those strings into a list, then I can apply Cantor’s diagonal method to the list and it will produce a string that is not on the list. If I let the list be arbitrarily long and the strings be the same then the list will still display the same property. That property has nothing to do with set sizes or enumerability, it is only to do with the infinite nature of the list. It holds for any list that follows the pattern, including enumerations of the natural numbers, the real numbers, series of zeroes and ones, or anything else.
Except, as I’ve already said (http://www.goodmath.org/blog/2016/07/05/cantor-crankery-is-boring/#comment-155510) natural numbers in binary (or n-ary) representation all start with an infinite padding of 0s. That extra structure is exactly what you need to break the argument, since the “Cantor number” generated by any listing of natural numbers will not itself start with an infinite padding of 0s, and thus isn’t expected to be a natural number in the first place.
Seriously, it’s like that old trope of the kid with no reach trying to swing at the boxer who just holds the kid off with a hand on his forehead. You’re not remotely in the same weight class, Jim. Why not try actually learning something for once in your life?
Yup, the property is indeed true! Given an enumeration of the natural numbers, the diagonal method produces a string that is not in the list. But this string is not a natural number, because it contains an infinite number of (nonzero) digits, as John Armstrong explained.
There’s actually a really interesting wrinkle here.
If you take Cantor’s procedure, and try to use it on the set of natural numbers, it will fail. In fact, it will even fail on finite subsets of the natural numbers.
Jim is *wrong* when he says that Cantor’s diagonalization works if he generates finite-length sequences from an alphabet. Cantor’s argument relies on the fact that in the real numbers, you can create a one-to-one map between natural numbers and positions in representation of a real number.
If you don’t have infinitely long representations, then Cantor’s diagonalization doesn’t work. (I should turn this into a post – this is, I think, an interesting point.)
What do you mean by Cantor’s diagonalization doesn’t work? There are more than n bit strings of length n. It’s not an interesting result, but it is a correct lower bound.
What I mean is: take the set of all strings of digits of length 5. If you try to use Cantor’s diagonalization on that set, it can’t create a string that isn’t in the set. The diagonalization relies on the fact that you can create a 1:1 mapping between natural numbers and positions in the representation string.
Jim, it has everything to do with set sizes. For finite n, you’ve established that 2^n is larger than n. For countably infinite n, you’ve established that 2 ^ n is larger than n, that there is no function from the natural numbers to the set of infinite bit strings that actually maps a natural number to every bit string. Which, modulo some messy details about the reals, is what Cantor was trying to prove.
You’re arguing against something that is well-established among mathematicians. Isn’t it time you think that maybe you don’t get it?
The answer I seem to be continually getting here is that you can’t have a string of digits that has infinity elements but if you put a ‘0.’ on the start of it then suddenly you can. Can someone explain to me how this is anything more that sophistry?
Nope, you misunderstood. You can have a string of digits that has infinity elements, no problem. But this string of digits won’t be a natural number (except if it begins by infinity zeroes).
What do you mean by “it works / it doesn’t work”? I must be missing something, because I don’t understand the problem.
This part seems clearly true:
If you apply it to some finite set of natural numbers, it will produce a natural number that is not in the set. Of course this does not prove anything (except that there is an infinity of natural numbers), but the procedure “works”.
This is also true, since it does not add anything:
I guess Jim thought that it meant the list and the strings could be infinite (he seems to confuse infinity and arbitrary length), but anyway, the property is also true for an infinite list of infinite strings. Hence my previous comment.
Of course for finite lists of infinite strings, or infinite list of finite strings, the procedure is not applicable, but that’s not what Jim was talking about.
What am I missing?
The definition of infinity for the natural numbers is that the set is closed under its successor function. Which means that there is no element of the set which is not followed by a larger element. When you use the term infinity it does not refer to some infinite largest natural number, it means that for every finite natural number there will be another finite natural number that is larger.
If you multiply 10 by infinity you get infinity. That means that if the set has a finite element n such that if you multiply 10 by n you get 10n, it must also have another finite element n’ which is greater than n such that when you multiply 10 by n’ you get 10n’. It’s this relationship that is meant by the term infinity.
The lengths of digit strings are natural numbers. When you use the expression infinite digit string it means that the length of the string is infinite, meaning that if there is a finite digit string then there must be a longer finite digit string.
markcc: If you don’t have infinitely long representations, then Cantor’s diagonalization doesn’t work.
And it’s because you don’t have infinitely long representations that Cantor’s diagonalisation doesn’t work. For any string of n digits there are 10 ^ n representations, so if you create a list of n elements it can’t contain all the representations and so Cantor’s number is just one of the ones not in the list. Taking it to infinity means that for any particular combination of n digits and n elements there will be a larger combination of n’ digits and n’ elements where n’ is larger than n.
No. What we mean by “infinity” in this context is “the cardinal of the set of natural numbers”. It is not unrelated to what you’re talking about, but it’s more specific.
No. “Taking it to infinity” means that we consider strings that have as many digits as there are natural numbers. More formally, each string is a mapping from N to {0,…,9}. These are perfectly valid mathematical objects.
Do you realize that if one refuses infinitely long representations, most real numbers are not representable? Basically, you’re arguing that by only allowing the existence of a countable number of reals, there are as many reals as there are natural numbers. Well, duh!
You realize that your “argument” means that π, and e don’t exist?
In fact, your entire argument is just yet another example of exactly the kind of sloppy reasoning that this post was criticizing.
You’re asserting a new definition of “infinity”, and then asserting that it’s equivalent to the set theoretic definition.
In fact, “infinity” is a poorly defined word – it’s a nice, informal term that we throw around, which doesn’t have one definition.
In math, we don’t really use it, except when we’re chatting informally. In Cantor’s proof, we don’t talk about “infinity”. Instead, we talk about a specific, well-defined measure of the “size” of a set. But we don’t use the word size – because, again, size is the same kind of fuzzy multi-definition word as “infinity”. Instead, we use a new term, which is precisely defined mathematically, called cardinality. For any set, we can describe the cardinality of the set.
When we’re talking about Cantor’s proof, we care about the cardinality of two sets of values: the set of natural numbers, and the set of real numbers.
Both of those sets have infinite cardinality. Neither of those sets has a cardinality equal to infinity. Infinity isn’t a number of any sort. ℵ0 (the cardinality of the set of natural numbers), on the other hand, is a number of a specific sort called a transfinite cardinal.
We can trivially show that the sequence of digits in the decimal representation of π have a 1:1 relationship with the natural numbers. That’s what we mean when we say that the sequence of digits of π is infinite: it’s got the cardinality ℵ0.
If you can’t have a number whose representation as a sequence has cardinality ℵ0, then you’re saying that a whole lot of numbers – in fact that the majority of real numbers does not exist. You’re saying that the irrational numbers don’t exist. That important, fundamental transcendental numbers don’t exist.
And that’s just stupid.
markcc: You realize that your “argument” means that π, and e don’t exist?
No, it means that the decimal representations of those numbers are not real things. Any number can be represented in many different ways. Pi can be represented by a Greek letter. But it has no decimal representation. The lack of a representation in a particular representational system does not mean the lack of the number.
markcc: You’re asserting a new definition of “infinity”, and then asserting that it’s equivalent to the set theoretic definition.
No, it’s not a new definition, it’s the axiom of infinity. Look it up. What I’ve said is what it says.
markcc: ℵ0 (the cardinality of the set of natural numbers), on the other hand, is a number of a specific sort called a transfinite cardinal.
Transfinite cardinals are not defined in the axioms. In order to say they exist you must prove that they do. To do that you need either Cantor’s diagonal argument or Cantor’s theorem, as well as the axioms of infinity and powerset.
The axiom of infinity denies a largest natural number, because every number has to have a larger successor. If there were an actual number ℵ0 such that the natural numbers contained ℵ0 numbers, the axiom of infinity would say that there was another number ℵ0+1 such that the natural numbers contained ℵ0 + 1 natural numbers. So ℵ0 could not be the size of the natural numbers. The claim that ℵ0 is a number contradicts one of the axioms, so it doesn’t exist.
markcc: We can trivially show that the sequence of digits in the decimal representation of π have a 1:1 relationship with the natural numbers.
That’s a bijection mate. Bijections are about matching things up, not about looking at how many of them there are. You only have to look at the bijection between the natural numbers and their squares to see that. “There’s always another digit” is not the same thing as “there is an actual number of digits.” Most infinite bijections work because the successor function is closed, not because the sets have the same element count.
markcc: In fact, your entire argument is just yet another example of exactly the kind of sloppy reasoning that this post was criticizing.
The argument that you make here is “it has to be true because otherwise a whole lot of other things would be wrong.” How is that not sloppy reasoning?
Actually, by the definition of cardinality, bijections do give us a way of looking at how many of something there are.
That’s part of why I’m being so picky about “cardinality” versus “size”. The cardinality of two sets is the same, by definition, if there exists a total one-to-one mapping between the two sets.
The axiom of infinity doesn’t define infinity: it demonstrates that set theory can be used to create a set with non-finite cardinality.
You can argue all you want about how you shouldn’t compare the “size” of sets using bijections – but the fact remains that if you’re talking about set-theory based mathematics, that’s what the definitions mean.
You’re welcome to reject set theory as a valid basis for math. There are people who do that. I’ve been writing about type theory, which is one interesting way of building a non-set-theory based mathematics. But if you’re talking about conventional math, this is the way it works.
You’re claiming that virtually every major mathematician in the last century somehow missed a trivially obvious problem with Cantor. And your argument is based, largely, on redefining some words, and rejecting the definition of others in a nonsensical, arbitrary way. Why, on earth, should we take you seriously?
This graf made me wonder if Jim is secretly an ultrafinitist. Is it possible to tell the difference between an ultrafinitist and a stubborn ass?
Okay, we seem to be in this loop where I say something and you say the same thing in a different way. It’s obvious you are not understanding me, so I’ll try it a different way.
Assume that there is an enumeration of the natural numbers. Define a number as follows. It starts with a ‘1’. If the nth number in the enumeration is formed from k digits, then the ‘1’ will be followed by at least k ‘0’s. As every number in the enumeration is finite, every number must be represented by a finite digit string, and that string must have a finite length. Adding one to a finite number gives a finite number, so the number produced must have a finite length. So the number produced is represented by a finite string of decimal digits and so is a natural number. But it’s not the first number, because it has more digits. And it’s not the second number, because it has more digits. And so on. So it is not in the enumeration. As the enumeration must contain all natural numbers, it follows that the natural numbers cannot be enumerated.
Don’t tell me the conclusion is bunk; I already know that. Don’t tell me that the above must be wrong because it’s conclusion is wrong, because you can’t contradict the an argument by asserting the truth of its conclusion. Don’t tell me the number is not a natural number because it has infinite digits, because I have shown that it doesn’t. Don’t tell me the mathematics of the process doesn’t work, because it can be shown by induction that it does.
I’m keen to see your argument, because you know I’m going to apply it to Cantor’s diagonal argument.
In my career as a software engineer, there’s one kind of person that I’ve had to deal with over and over again, and it drives me crazy. It’s the person who’s used to always being the smartest person in the room. They’ve grown up always being smarter than the people around them. So they’ve learned to expect that they’re always the smartest person around. Any time they’re dealing with anyone else, they’re always working from the assumption that they are obviously the smartest, and that therefore, if someone disagrees with what they’re saying, it must because they don’t understand it.
The pattern of interaction that follows is infuriating. A moron says the brilliant person is wrong, and explains why. The brilliant person doesn’t listen to what they’re saying at all: after all, they’re smarter, and they know the moron is wrong. Since the moron doesn’t accept what the brilliant person said, and (obviously), they’re a moron, the problem must be that the moron doesn’t understand what the brilliant person said. So the brilliant person tries to explain it again, in slightly different words.
Repeat ad infinitum.
That’s what’s going on here. You’ve decided on a definition of infinity that is non-infinite. That definition is wrong. But you’re not going to listen to anyone who tells you that. You’ve got a naive misunderstanding of the concept of infinity based on a naive understanding of the axiom of infinity, and you’re not going to listen to anyone who tells you otherwise.
Your “proof” fails miserably, because it’s based on always working with finite prefixes of an infinite sequence – not with the infinite sequence itself. The infinite sequence is the limit of the never-ending sequence of finite prefixes. The numbers that you’re constructing are always part of infinite sequence. Given any finite prefix, there’s a huge number of ways that you can construct a new number that isn’t part of that finite prefix – but that doesn’t mean that it’s not part of the infinite sequence.
Of course, you’re not going to accept that. You’re just going to rephrase slightly, and repeatedly hammer on your argument that because you can always find a number that isn’t part of a finite prefix – while completely ignoring the actual concept of infinity because you don’t understand it – and while again refusing to consider the possibility that the problem here isn’t that we don’t understand you, but that you don’t understand the math.
Suppose the enumeration of the naturals is the trivial one where the nth number is n. What number is produced by your procedure?
Here’s my prediction, based on my understanding of his argument.
He doesn’t believe that there is an answer to that question – he’ll say, essentially, that the question is ill-formed.
Under his argument, there is no such thing as an infinite sequence. There are just lots of finite prefixes of an infinite sequence. For any finite sequence 0..N, his procedure produces a value which isn’t in the sequence. Since there is no such thing as a real infinite sequence, and he can produce a value outside the sequence for any finite one, he’s shown that the whole concept is bosh.
(Of course, his argument, while denying that there’s any such thing as an infinite sequence, actually relies on the fact that there’s an infinite sequence underlying it. But he won’t see or admit to that, because he’s smarter than every mathematician in the world.)
I had the same thought, and so I started in to apply it. You’ll find very quickly that Jim’s “procedure” is, to put it mildly, incoherent gibberish. This is the very least his proposed argument should be able to answer, and it just can’t.
So, having noted Mark’s astute observations below, I ask Jim again: given the enumeration where the nth natural number is the number n itself, what number do you think your procedure returns? Show your work.
I’m going to go back to an earlier comment, because it demonstrates exactly the kind of cluelessness that pervades your arguments:
First: The axiom of infinity does exactly one thing: it demonstrates that axiomatic set theory is capable of defining an infinite set. The axiom of infinity doesn’t actually say anything about natural numbers at all.
The classic formulation of the axiom of infinity says:
Note that the concept of number, much less natural number, exists nowhere in that axiom.
You can construct a model of the set of natural numbers using a simple set-theoretic construction using a pattern very similar to the pattern in the axiom of infinity – but the axiom isn’t talking about numbers.
Second: the number ℵ0 isn’t a natural number. It’s a transfinite cardinal. ℵ0 + 1 isn’t a natural number, either. Nor is 2*ℵ0.
Transfinite numbers aren’t natural numbers. They don’t behave like natural numbers. They don’t satisfy the axioms of natural numbers. And that’s fine: they don’t have to, because they are not natural numbers.
For any natural number N, ℵ0 + 1 = ℵ0. That might seem counterintuitive. But remember: ℵ0 is the cardinality of an infinite set. It’s not a natural numbers: it’s a measure of infinity.
The prof who first taught me about this stuff liked to introduce it by singing a goofy song to the class. Remember, back on school trips, people used to sing 99 bottles of beer? The mathematician’s version is:
If you don’t understand this, then you shouldn’t be arguing with mathematicians about the concept of infinity.
It is not only that he uses different definitions for standard concepts. He is using the very same already shown fallacious logic that Gabriel, Carl, and so on that we already addressed. He does not understand how induction works, as he does not understand how definitions, infinity or logic work.
@John Fringe said “He is using the very same already shown fallacious logic that Gabriel, Carl, and so on that we already addressed.”
John, you did not address my logic, you did not even understand my argument. You only beat up a straw man version of my argument. If you wish, I can explain it to you again.
The standard line of a crank: “it’s not that my argument doesn’t work, it’s that no one understands it.”
Take it easy, Mark. He has been exposing his arguments here for just a very short six months now. Barely time to make oneself clear.
He has something intelligible and correct to say that proves that every single mathematician has overlooked an error in several formal, detailed and quite simple proofs for a century while operating in an inconsistent system for that long without noticing, but as explaining what a Cantor’s tree is has took him severals months, making himself clear can be a lifelong task.
@John Fringe said “…making himself clear can be a lifelong task.”
I am in no hurry, if God is willing, I have plenty of time.
So, John, look at what Chris Cogan wrote “IF we had what we took to be a complete enumeration, by ANY method, of the reals, then, despite that, here is how we could define a further real that is not already enumerated.”
Then apply that to the enumeration of the reals that I gave you. You can diagonalize it and come up with a number, and when you change every digit to something else you will get a number that IS on the list. This, given what Chris Cogan wrote about Cantor’s method, will refute Cantor’s proof, but it will NOT prove the opposite, it only shows that Cantor’s argument does not prove that the reals are unlistable.
Now, John, is this how you understood my argument when you presented a formalized version my argument?
Except, Carl, that that isn’t what you did. You can keep shouting all you want: Cantor’s proof produces a number that *is not* in the list: it will different from every number on the list in at least one position.
Of course, you’ll just keep on handwaving, because you have no clue of what you’re doing wrong. That’s the endless story of dealing with Cantor cranks. The same mistakes, over and over again. The same vague handwaving nonsense, the same endless attempts to transfer the burden of proof.
We’ve explained to you, over and over again, that your “enumeration” doesn’t work. It’s based on invalid, incorrect assumptions, which you try to weasel around by stating them vaguely enough that the errors are disguised by the cloud of vagueness.
I think Carl’s trying to view the construction of Cantor’s number as a process, which would be interesting if he knew the difference between “arbitrarily long” and “infinitely long” times.
It’s one of the very common mistakes that people make. It’s what Jim was doing here as well. They take Cantor’s definition of the number as a program to generate the number, and then find ways to play with things based on the fact that it’s a program that never finishes.
(Of course, the other classic version of cantor crankery errs in the opposite direction – like the John Gabriel nonsense, where individual entries in the list are infinite and non-enumerable.)
Carl, you seem to be under the impression that you and me are arguing about the validity of Cantor’s theorem. Just to make me clear, I am not. Six months of your bad arguments, ignorance to address any criticism, inability to write a detailed step by step argumentation and random change of topics were more than enough for me. I am just helping to expose the obvious trivial errors in your arguments, but you are certainly not my target audience.
@MarkCC, you responded to my comment with the following…
Carl said “John, you did not address my logic, you did not even understand my argument.”
MarkCC said “The standard line of a crank: “it’s not that my argument doesn’t work, it’s that no one understands it.””
Was the intent of your comment “just an off the wall insult” or were you trying to say that I was wrong in saying that John had not understood my argument, and that you think that John’s formal version of my argument is indeed accurate? Or was there some entirely different intent behind your comment?
I’ve been saying all along that you aren’t really making a mathematical argument at all.
The point of that comment was that you continue to play the same idiotic game, where you present a sloppy, informal, imprecise mess of an argument, and then pretend that the refutations of that argument don’t count, because the people refuting you don’t really understand.
Your arguments, as written, are at best, full of mathematically ambiguous statements. (More often, they’re full of statements which aren’t even ambiguous: they’re just pure nonsense if you try to actually interpret them mathematically.)
That’s a very common pattern – I’ve seen it many times before. The people who use it fall into two categories: the clueless, and the malicious.
The clueless are the people who don’t even understand that there’s a problem with their argument – they don’t understand the math enough to see the ambiguity.
The malicious are the ones who know that they’re being ambiguous, and use that fact. You can’t ever “refute” these people, because they use the ambiguity to turn the discussion into a gish gallop: whatever meaning you pick for the ambiguity, they just say you obviously picked the wrong one.
I think you’re a bit of the clueless, but also a bit of the malicious. You’re clearly playing a game here pretending that people don’t understand your arguments.
markcc, I have posted to a lot of crackpot web sites over the years and after a while you realise that you always find the same pattern. The crackpot knows he’s right and so he knows you are wrong. If he can deal with your argument he will, but if he can’t he won’t, he just ignores it and quotes his beliefs at you. He knows the moon landings were faked, so nothing you can say will persuade him differently. Eventually he gets exasperated, and starts trying to brush you aside, or results to things like ad hominem attacks or proof by popularity, or produces a long diatribe about how idiots who don’t accept his claims drive him crazy. If you are going make a claim you have to be able to support it against all arguments. Crackpots can’t do that. Can’t and won’t are two different things, but… From where I sit you have consistently responded like a crackpot. If the shoe fits…
I tried to find the quote for the following, but I don’t have the energy to chase through all of your blog, so… You have said that applying Cantor’s argument to the natural numbers won’t work, because the digit string produced is infinite, and there is no natural number that can be represented as an infinite string of digits. Was that you? Is that what you are saying? My interpretation of that is that if I enumerate the natural numbers, every element of the enumeration must be a particular finite digit string; no element can be an infinite string. Is that correct?
You’re the one making the extravagant claims here, not me. You need to be able to
defend your claims against the conclusion of pretty much *every* mathematician of the last century.
Let’s face it: I’m not a mathematician. I’ve never claimed otherwise. But you haven’t even been able to address my pathetic criticisms. I’ve responded to you in significant detail – and you just ignore it.
Tell me why I should continue to waste time on re-stating the same objections?
Yes, all natural numbers are, by definition, finite; and therefore, they have finite representations. So what?
None of this discussion has actually been about finite representations. You insist that infinite representations and infinite sequences don’t exist. That’s a ridiculous claim, and you’ve continually ignored the people who pointed it out.
markcc: you haven’t even been able to address my pathetic criticisms.
You’re making assumptions. I’m not posting here to try and convince you that I’m right. I wouldn’t waste my time doing that. I’m posting here to try and prove to myself that I’m wrong. I figure that if anyone can break an anti-Cantor argument it’s going to be you. You need to bounce ideas off other people in order to test them; I don’t know anyone who is capable of giving me an argument.
markcc: Yes, all natural numbers are, by definition, finite; and therefore, they have finite representations. So what?
I have some reservations about the following argument, but I will leave them aside.
Any string of digits must represent a natural number. If I enumerate the set of digit strings, I can just say that the digit string at position n represents the number n. So it follows that an enumeration of digit strings must have the same property as an enumeration of natural numbers, i.e. every one of them must be a particular finite string. The set is infinite, but the elements are not. Or rather, there are infinite digit strings in the set, but they can’t be part an enumeration of digit strings.
I can also note that the there are many ways to represent a number. I can represent 123 as 0.321, adding a prefix and writing the digits left to right instead of right to left. If follows that an enumeration of digit strings in the interval (0,1) can be seen as an enumeration of the natural numbers (excluding 0) using a different representation system. Give me any particular element of the enumeration, I can reproduce the natural number it represents.
The important point here is that the enumeration Cantor produces cannot contain any infinite digit strings; they must all be finite. The simple fact that it is an enumeration guarantees that. So there can be no representation in it for pi, or e, or 1/3, or 22/7, because these are things that can only be represented by infinite digit strings. You don’t need to pull silly tricks to prove that; it follows directly from your argument.
So an enumeration of digit strings cannot contain an element that represents 1/3, because 1/3 needs to be represented by an infinite string and the enumeration cannot contain one. Does that prove that the rational numbers cannot be enumerated? Of course not. It just proves that you cannot enumerate them using digit strings. Cantor enumerated them using fractions. Fractions work; digit strings can’t.
An enumeration of digit strings cannot contain an element that represents pi. So you can’t enumerate the real numbers using digit strings. That doesn’t mean they can’t be enumerated, it just means that the method Cantor tried to use doesn’t work. There may be another way of representing real numbers that allows them to be enumerated.
So Cantor’s diagonal argument is worthless.
Cantor’s proof doesn’t produce “strings”. It produces a single number.
You’re continuing to make the same mistake, refusing to accept the fact that a mathematical definition isn’t a computer program. Cantor’s proof defines the value of every digit in an infinitely long representation.
Cantor’s proof works for every possible attempted enumeration of the real numbers. Given any enumeration of the reals, it will produce a real number that isn’t in the enumeration.
You don’t understand the concept of infinity, and you keep making the same damned mistake. You did exactly what I said you would: play a game of finite prefixes, and pretend that somehow that means something about infinity.
It doesn’t.
And I have to add that nothing demonstrates the weakness of your reasoning than this little quote:
You’ve picked a part-time hobbyist blogger who doesn’t have the mathematical ability to actually be a mathematician as the very best person you can imagine to shoot down your shoddy arguments? Really? You can’t imagine anyone better than me? I should be flattered, but instead, I’m just appalled. That’s pathetic!
I’m honest about myself and my ability. I’m no mathematician. Like I said above: I couldn’t be a mathematician: I’m not good enough at it. I’m arrogant enough to say that I’m a damned good computer scientist and systems software engineer. That’s what I do, and I’m really good at it.
But a mathematician, I am not. The best expert to shoot down a bit of weak-sauce Cantor crankery? Hell no.
But thanks for giving me a good laugh.
Jim:
Are you saying that there cannot be an enumeration that contains infinitely long digit strings? Because there can be. For instance:
The list of strings whose first element is the digits to the right of the decimal point of pi/10, whose second element is the digits to the right of the decimal point pi/100, and so on.
Or the list of strings whose first four elements are “1111111…”, “1010101…”, “1001001…”, “1000100…”.
markcc: Cantor’s proof works for every possible attempted enumeration of the real numbers. Given any enumeration of the reals, it will produce a real number that isn’t in the enumeration.
Mate, go back and read what I said. I have never said that the number Cantor produces is not a real number. But so what if it is? By the logic you’ve put forward it is also true that it is not in the enumeration. But so what? You don’t need Cantor’s argument to know that there are numbers that can’t be in the enumeration.
As you claim not to be a mathematician, I will put this another way for you. You can’t write software using a hammer, you need a computer. Showing that you can’t write software with a hammer does not prove that it is impossible to write software. It only proves that a hammer is the wrong tool for the job.
You can’t enumerate the rational numbers using digit strings. You have to use fractions. Showing that you can’t enumerate the rational numbers using digit strings doesn’t prove that the rational numbers can’t be enumerated.
Cantor has not shown that there is not some other way of representing real numbers that would allow them to be enumerated. That’s why his argument is worthless.
markcc: You’ve picked a part-time hobbyist blogger who doesn’t have the mathematical ability to actually be a mathematician as the very best person you can imagine to shoot down your shoddy arguments?
No. I kind of thought that someone who had the hubris to set himself up as an authority on good or bad mathematics would have some talent for it. If you had put a statement on your home page announcing that you had no talent for mathematics I would not have bothered with you. Mind you, I think you are doing yourself down.
And you continue to make exactly the same stupid mistake that you’ve been called out for over and over and over again.
Of *course* you can represent fraction in decimal notation. You can’t represent them as with finite decimal notations, but in reality, that doesn’t matter. There’s no finite notation that can represent all real numbers. But that doesn’t matter, because while we can’t write down an infinite representation, we can define it and talk about it.
Just because you don’t understand how infinite sequences work in mathematics doesn’t mean that they don’t exist or that you can’t reason about them in valid ways.
You can whine about it all you want, but you’re continuing to make the same damned mistake. And you’ll continue to be wrong until you actually learn some real math.
You can do finitist math, where you reasoning is valid. But the problem with that is, you’re talking about math in terms of axiomatic set theory – and that’s not finitist. You’re talking about real numbers – which are defined in terms of infinite sequences. You can’t reject infinite sequences, and then meaningfully discuss properties of real numbers.
To use a variation of your own metaphor, you’re trying to use a hammer to cook a hamburger.
@Jim
He doesn’t need to. All real numbers are representable by infinite strings of digits (or equivalently, by mappings from N to {0,…,9}, since it seems that you cannot accept the existence of infinite strings). His proof shows, in a very simple way, that given any enumeration of infinite strings of digits, there exist at least one infinite string of digits that is not in the enumeration. So there exists no enumeration of infinite strings of digits. So there exists no enumeration of real numbers.
It’s quite straightforward really.
You’re right, but Jim won’t accept it. He’ll just regurgitate a variation on his incomprehension of infinity: he won’t accept that the infinite representations actually “exist”. He’ll say that there are only finite prefixes, blah blah blah.
sff9 is right: Cantor’s proof doesn’t depend on any specific way of enumerating the reals. It works absolutely without regard for the specific nature of the mapping function. It says, in effect, “IF we had what we took to be a complete enumeration, by ANY method, of the reals, then, despite that, here is how we could define a further real that is not already enumerated.”
An infinite sequence of digits shows that there are infinitely many ways to fail to produce a real number. Why do you believe that infinitely many flops are a success?
Regards, WM
Cantor was the father of all mathematical cranks.
A set is countable if and only if its members can be systematically named (*). That’s why Cantor chose the set of natural numbers.
(*) For this reason, there is no such thing as a set of “real” numbers. Hence it’s no surprise the imaginary set of real numbers is uncountable – it doesn’t exist.
You vile Jew idiot Mark Chu-Carroll! You are stupid beyond belief and there is no hope for you or your fellow cranks ever. Chuckle.
Eat shit and die you moron!
Interesting.
Last time we spoke, you argued quite vehemently that you had a perfect procedure for enumerating the real numbers, and that Cantor was a crank for saying that you couldn’t.
Now, suddenly, the real numbers don’t exist.
What changed, John? Did you realize that your enumeration procedure was a pile of nonsense?
(Interestingly, mathematically, you have even less foot to stand on here than you did in your old argument. The real numbers are pretty easy to define axiomatically. The real numbers are the unique least upper-bounded complete field. You can’t make that definition invalid without rejecting all of abstract algebra. Will you throw out algebra, too, in order to defend your fragile little ego?)
Hello,
I recently noticed a Russian webpage http://khazarzar.skeptik.net/other/zlotnik.htm
Seems he has expressed his hatred to the infinity, the continuum, mathematical logic, fundamental theorem of algebra and p-adic numbers, and also relativity theory! The most interesting part is that his criticism of logical deduction a→b.
Also I once noticed a German webpage http://www.mathe-neu.de
The author says that plus a negative number is not equal to minus a positive number, and even more, boolean algebr is flawed! He also says that Euler’s identity is wrong, imaginary unit doesn’t exist and Cantor’s view of infinity is wrong. That’s quite refreshing, I haven’t seen such a crank before.