## Monday, November 02, 2009

### Misunderstood Mathematics

One of my long-term book projects is about mathematical theorems that give people fits. A good example is Cantor's theorem that the real numbers are uncountable. The proof is simple enough that you can explain it to a 10-year-old, but some adults simply don't get it, no matter how many times it is explained.

For example, see this thread over at Mark Chu-Carroll's blog. It just goes on and on, with one poster ("Vorlath") babbling away, but making no progress at all in comprehending this very simple proof.

I'd be interested in understanding the psychological mechanisms behind this kind of misunderstanding. It reminds me of the difficulty that some religious people appear to have in understanding evolution - you just go 'round and 'round with them, but they make no progress. Is it willful? That is, do they secretly know they are talking nonsense, but can't accept it because of their preconceptions? Or are they truly baffled?

Harriet said...

1. If you have time, read the chapter on this in Underwood Dudley's book Mathematical Cranks. One Academy of Science (Wisconsin?) actually published a "refutation" of Cantor's diagonal argument and a "proof" that the real numbers are countable. I met the author at a small math conference.

2. I don't know how much time you spend with undergraduate students of average ability but if you did, it'd be easy to understand why so many can't understand Cantor's argument.

I swear, I once had to a SENIOR MATH MAJOR trying to explain to him why the following operation is invalid:

(simga n = 1 to infinity) (n*(2/3)^n) = n*(sigma n = 1 to infinity)((2/3)^n)
was an invalid operation (he factored the index n from the infinite sums)

He felt insulted when I told him to write out the terms in the long way and then try to do the operation.

Jeffrey Shallit said...

Yes, I know about Dudley's book, and have a copy.

The paper you are referring to is Dilworth, William
A correction in set theory. Wisconsin Acad. Sci. Lett. Trans. 62 (1974), 205-216.

Serge said...

Coincidentally, I was teaching this proof to a group of future high school math teachers last week. This is in the context of their last math class ever; they are seniors. I had a revolt on my hands!

It was interesting to see them react, and we had a lively discussion, but I never expected this resistance. I think that one of the problems they had is that they feel uncomfortable with a proof by contradiction.

To be fair, historically, a number of mathematicians have wanted to do away with them so my students are in good company.

Anonymous said...

I think that one of the problems they had is that they feel uncomfortable with a proof by contradiction.

This is pretty common. I think the underlying reason is that most people, even many math majors at decent universities, have never had a completely clear understanding of any proof except the very most basic ones. They may have read some more sophisticated proofs, and even had a decent high-level understanding of them, but the idea that everything is supposed to be crystal clear (from the outline down to the details) is completely foreign to them. They don't even realize that this is possible, since they've never experienced it.

This happens a lot more often than you might guess. Even proof-based undergraduate classes usually don't demand real understanding: at most schools, the homework and exams ask for only pretty easy proofs (a couple of steps applying the definitions and theorems from class), so a student who never really internalizes the proofs covered in class can still get an A and believe they have a solid understanding.

This means proofs by contradiction just aren't that convincing: if you don't thoroughly understand them, it's easy to imagine that there must be loopholes. The conversation can go around in circles, with the crank listening to proofs and honestly believing he fully understands them while missing the point entirely. To him, the fact that all mathematicians agree is evidence of collusion and a lack of openness to new ideas, rather than evidence of a profound shared understanding.

The comparison with evolution is apt, since it helps explain why this particular proof by contradiction is so disturbing to people. I think a lot of people have vaguely mystical ideas about infinity, viewing it as an ideal or a manifestation of God. They really don't like the idea that mathematicians can tell them counterintuitive facts about infinity. For example, if you conceive of God's omnipotence in terms of infinity, then being told that there is a whole hierarchy of transfinite numbers, with no largest ones, is rather disturbing. I don't mean to suggest that all disbelievers in the diagonal argument are religious. Some just have a fascination with infinity that greatly matters to them for non-religious reasons. The upshot is that infinity is one of the few mathematical topics that many people have strongly felt opinions on, so it's no surprise that they dislike being told they are thinking about it wrong.

Maybe I'm wrong, but while the proof itself may not be hard to understand, I have a feeling it's hard for people to grasp what it means - in the sense that there are an infinite number of fraction in between any two fractions, but we can still enumerate those, vs. real numbers where we can't.

Eamon Knight said...

As a non-mathematician (who nonetheless knows more math than I strictly need to), perhaps I make a good guinea pig? I'm also an engineer, and therefore part of that "little knowledge" demographic which tends to produce crackpots on all sorts of subjects.

It seems to me that the concept of infinity is inherently fraught with contradictions and counter-intuitives. Resolving the contradictions seems to be a matter of deciding which intuitions to satisfy, and which will just have to suffer. And from the outside, that choice seems a bit arbitrary.

For example, Mark uses the fact that the power set of a finite set is larger than the original set to argue that the power set of an infinite set is also larger than the original set. OK, that satisfies one intuition at the expense of violating the intuition that infinity is infinity and all equal.

But what happens when I apply that same analogous reasoning to compare the set of even natural numbers with the set of all natural numbers? If I compare the set of all naturals less than 1000 with the set of all evens less than 1000, obviously the former set is larger. But if I do the same comparison between N and even-N, you will tell me that they are the same size. OK, I can sort of see that one, in that I can construct even-N by multiplying each element of N by 2, therefore there is a one-to-one mapping between the sets. But I can also construct even-N by removing every second element of N, implying it should be smaller. Which of my opposing intuitions should I accept as "true" and why? The standard mathematics answer is that the one-to-one mapping intuition is the one to go with.

But this brings me back to Mark's original example of power sets: The cardinality of N is the same as the cardinality of the rational numbers Q, because I can create a one-to-one mapping between N and Q. I have seen enough of a demonstration to show me (intuitively) that it can be done in principle, even though the task of actually doing it unto infinity is in practice impossible. But why can I not create such a mapping between N and its power set? The power set consists of discrete items, and (intuitively) it seem no harder (or easier ;-)) to number them all starting at 1 than it was for the rationals. But again, standard mathematics tells me that this intuition is "wrong".

Now not being a crackpot, I'm not claiming that all mathematicians are wrong. I can see that the theory of infinities (insofar as I have grasped it) is self-consistent, and perhaps that's all that matters. But am I correct in my impression that the choices made to resolve the contradictions are arbitrary conventions? Could a different (but consistent) theory of infinities be constructed by choosing to privilege a different set of intuitions, or is there some deeper reason to prefer the ones we got from Cantor?

In any case, does my (semi-knowledgable layman's) confusion on this issue shed any light on the psychology of mathematical crackpottery?

Jeffrey Shallit said...

Here's a brief response. First, what non-mathematicians don't always understand, but which you seem to appreciate, is that mathematical definitions are, to some extent, arbitrary. For example, when we create definitions on how to compare the sizes of sets, we are looking for definitions that (a) capture some intuition about size and (b) lead to interesting mathematics. There are, indeed, other ways to compare the sizes of sets, but the problem is, they lead to uninteresting or even more unintuitive results.

Let's take one possibility that is suggested by your commentary. Suppose we say that a set A has a smaller cardinality than a set B (and write A < B) if A is a proper subset of B. Using this idea, then, we can indeed claim that 2Z, the set of all even integers, is "smaller" than the set Z of all integers. Using the above notation, 2Z < Z. Furthermore, < obeys the usual rules we think of for the symbol: the transitive property, for example.

The problem with this definition is that it is not particularly interesting! For one thing, it doesn't really capture the notion of size -- because we can only compare two sets when one is a subset of another. We cannot compare, for example, 2Z and 1+2Z.

Now you might say that "clearly" 2Z and 1+2Z (the evens and the odds) have the same cardinality, because we can "rename" each even to odd just by adding one. So we could try to rescue it, say by writing A << B if we can "rename" all the elements of A in such a way that A < B. The problem is, using this definition, N << N, since we can "rename" 1 to be 2, 2 to be 3, etc. and produce a set that is a proper subset of N. So this attempt to define << results in something we might consider "contradictory" -- more precisely, it contradicts our intuition about how such a symbol should behave. Nevertheless, if we replace << by <= suddenly it behaves better, and in fact we get the ordinary notion of "equipollent".

Whenever you try to generalize a concept in mathematics, you often run into some set of properties that is no longer preserved under the generalization. The "art" of mathematics is to choose the "proper" generalization so that interesting consequences appear. What is fun is that often the "proper" generalization is so good that nearly everybody accepts it right away - as with the case with Cantor.

Eamon Knight said...

Jeff: thank you; it's nice to have my, um, intuitions confirmed ;-).

To get back to your psychological question: perhaps the problem with the stubbornly ineducable is that they cannot get past their own intuitions about how the world works. I do not consider that I "believe" something until I have understood it, and I don't properly understand unless and until I have developed some way of looking at it that "makes sense" (in a hard-to-articulate way) to me -- some metaphor or narrative or, well, intuition. But where I can entertain two mutually inconsistent intuitions about a subject, and either hold them in tension, or deliberately choose one over the other, the crackpot cannot "see" the alternative they are being offered. And since they cannot understand the answer, they cannot believe it.

Paul C. Anagnostopoulos said...

Jeffrey's point is important: There's math and then there's the interpretation of the math. This causes problems with infinities, but those problems pale in comparison to the problems in causes with quantum mechanics.

As Jamie Whyte said, "It is a rare foray into gobbledygook that does not begin with a tribute to quantum mechanics."

~~ Paul

Frank said...

Eh, I read the proof of Cantor's theorem at Wiki, and frankly, I don't think my 10 year old would get it. Perhaps you were speaking in hyperbole?

Anyway, how simple can it be if there's a controversy over it?

http://en.wikipedia.org/wiki/Controversy_over_Cantor%27s_theory

http://en.wikipedia.org/wiki/
Controversy_over_Cantor%27s_theory

"As Leopold Kronecker claimed: "I don't know what predominates in Cantor's theory - philosophy or theology, but I am sure that there is no mathematics there." Many mathematicians agreed with Kronecker that the completed infinite may be part of philosophy or theology, but that it has no proper place in mathematics."

Jeffrey Shallit said...

Perhaps you were speaking in hyperbole?

No, I don't think so. I explained it to my kids at that age and they understood it.

Anyway, how simple can it be if there's a controversy over it?

There's a "controversy" over it in precisely the same way that there's a "controversy" over evolution: virtually every professional mathematician accepts Cantor, and most would regard anyone who questions it as a crackpot.

Frank said...

Kids tend to pretend to understand stuff in order to rush off to play Nintendo. I'd double check and see if he could explain Cantor's theory back to you, including dealing with the challenges to the theory.

"most would regard anyone who questions it as a crackpot."

Well, was Zermelo a crackpot or wasn't he? And Kronecker, too?

Frank said...

(I forgot to mention Hermann Weyl.)

Jeffrey Shallit said...

I'd double check and see if he could explain Cantor's theory back to you, including dealing with the challenges to the theory.

Thanks - I am a professional educator, and I think I know whether students understand me. My kids can explain the ideas to others, and I feel confident they understand it.

Challenges? There are no reasonable challenges to Cantor's theorem. The proof is trivial. You can debate things like whether the axiom of infinity is a reasonable axiom, but no reasonable person disputes the proof

As for Zermelo, Kronecker, and so forth: when ideas are new, the established order often refuses to understand them. Darwin, for example, had opposition from experts such as Agassiz.

When I say "virtually every professional mathematician accepts Cantor" I am speaking in the present tense, about mathematicians today.

Frank said...

Concerning the opposition to Cantor's theory, all I can say is that there have been quite a number of theories that have been so well established, but have been overturned. "Just as the doctrine of evolution is universally accepted among biologists, so also the geosynclinal origin of the major mountain systems is an established principle in geology." -- Clark, T.H. and Stern, C.W., Geologic History of North America, 1960, p. 43 (Plate techtonics -- whose proponents were probably seen as crackpots -- overturned that theory.) We mustn't forget that groupthink often rules in academia.

Jeffrey Shallit said...

Frank:

Actually, there is very little groupthink in academia, precisely because you make your reputation by doing something new. Of course there are exceptions, but in my experience they are extremely rare.

Your comparison with scientific theories is not apt. A scientific theory depends on the weight of evidence, whereas mathematical statements are subject to rigorous proof that they follow from the axioms. Scientific evidence may accumulate over time, but this is not true of mathematical theorems.

No one has ever presented any credible argument that Cantor's proof is incorrect.

Frank said...

"No one has ever presented any credible argument that Cantor's proof is incorrect."

Maybe that's not what Poincare, (the "crackpot") who called Cantor's ideas a "grave disease," was /even trying to do/. Rather, I suspect, Poincare was saying that the theorem didn't even belong in math.

Jeffrey Shallit said...

Frank:

Surely you recognize that an "argument" like Poincare's is just dumb. Hey, I don't like category theory, but I'd never claim it shouldn't be a part of math.

Frank said...

Not "category theory" but "Cantor's theorem."

Ben said...

There is a very elegant proof for the proposition that every set has smaller cardinality than its power set, which mirrors Russell's Paradox. Namely, it demonstrates that given any function f from a set S to its power set P(S), f can not be onto. For define M as the subset of S containing all elements x of S such that x is not an element of f(x). Then there is no element y in S such f(y)=M. For such a y could not be contained in either M or the complement of M, by construction (here the similarity to Russell's Paradox arises.) Hence, f is not onto.

Today, mathematicians do not even need to use Cantor's diagonalization argument to establish that the reals are uncountable, although it remains the simplest and most elegant. Instead, by constructing the basics of Lebesgue Measure theory, we can quickly show that the measure of any interval (a,b) is b-a, that the measure of any countable set is 0, and hence any non-degenerate interval (any thus the reals) must be uncountable.

Filipe, from Brazil said...

About teaching this to a 10 year old child, I recall now that, about this age (I'm 19 now), sometimes I would find myself interested in the possibility of existing groups "more infinite than others" - that's the way I used to think- , like R in comparison to N.

A philosophy blog with focus on Mathematics. said...

"The proof is simple enough that you can explain it to a 10-year-old, but some adults simply don't get it, no matter how many times it is explained."

1. Well, I wouldn't even call it a proof, for it is devoid of logic.
2. You can explain many things to 10 year olds - you won't know if they understood unless you actually ask them to apply the theory.
3. Did you perhaps mean many adults don't get it?
Now why does that not surprise me - I have never "gotten it" because there is nothing to get!

Cantor was the father of all mathematical cranks. Only a Jew could pull off something like this. His followers are by implication fools entering into his fool's paradise.

Jeffrey Shallit said...

John Gabriel:

You get exactly one chance to issue anti-semitic slurs on my blog. You've now used your one chance up. Get lost.

Vorlath said...

I am the Vorlath you speak of.

Out of curiosity, do you agree that in the list of reals, there is a subset of rationals that have a single digit set to one?

Do you also agree that there is one of these rationals for each digit?

In Cantor's diagonal, we must take one digit from each row, correct?

This means we must take a different digit from each of those rationals at the very least.

So pray tell, what digit would you include in the diagonal for the number zero if all the digits are already in the diagonal?

And they call me a crackpot???

Sheesh!

Jeffrey Shallit said...

Vorlath:

I'm less interested in trying to decipher your poorly-expressed argument than I am in your psychology.

Tell me - do you find it at all surprising that nearly every professional mathematician understands and can explain Cantor's proof - and they have done so for more than a hundred years - and they all accept it ... but you, who are not a professional mathematician, somehow have managed to find a mistake that has eluded everyone else? Does that seem at all plausible to you? And if so, why?

Vorlath said...

Because I've worked out the proof. It's not by choice. It's there in plain sight.

1. Given the list of all reals, Cantor's diagonal must intersect at least all the strings that have a single digit set to one leaving no digits unused.

2. But there are more reals than that, like the number zero. No matter what digit index we select, it has already been included in the diagonal. So |Q|>|N|.

3. But we know |Q|=|N|.

QED

I've proven that Cantor's diagonal argument is flawed. You can argue with fallacies of appeal to authority all you want. It doesn't make the counter proof go away.

BTW, Cantor was a nutjob. You're on the wrong side of the fence on this one. And your topic shows how you have to indoctrinate people even though they know the diagonal argument is trivially flawed. Most people see it instantly.

As to why it's been accepted for 100 years? Because it hasn't. Everyone who's done any work on the topic ended up in an insane asylum. Everyone else that agrees with their work is essentially agreeing with lunacy.

You know, when people who did the work get thrown in an insane asylum, it's kinda difficult to take anyone seriously that claim it's the other people who are crazy.

Jeffrey Shallit said...

Vorlath:

Yes, I understand quite well that you think that you have found a flaw. But that's not my question. I was asking if you ever consider the possibility that these "flaws" that you think you find are actually mistakes in your own cognition? And if not, why not?

By the way, I am not using an appeal to authority. I am not saying Cantor's proof is correct because nearly all professional mathematicians accept it. I view it as correct because the steps are simple and I am convinced by every one. In this case, I am also a professional mathematician, so I feel confident in my judgment.

I'd like to interview you sometime for my book, so if you're willing to send me your e-mail address, I'd appreciate it.

P. S. It is also completely false that "Everyone who's done any work on the topic ended up in an insane asylum". There are lots of people who work on the topic, such as Bob Soare, who I know personally, and none of them are in insane asylums.

Vorlath said...

You can interview me only if you tell me which digit index remains unused by the rows of the identity matrix when in R.

Jeffrey Shallit said...

Vorlath:

I can't answer your question because I don't understand what it is you are trying to say. Part of mathematics is expressing ideas clearly.

Vorlath said...

Here's a link to an identity matrix.

http://en.wikipedia.org/wiki/Identity_matrix

An infinite identity matrix would contain the following rationals {1/2,1/4,1/8, etc.}.

In R, what digit index is not set to 1 by those same elements?

Jeffrey Shallit said...

Thanks, Vorlath, but I know what an identity matrix is.

I'm afraid I still don't know what you mean, though. An identity matrix has 1's on the diagonal; it contains no rational numbers other than 1 and 0.

Perhaps you are thinking of each row of an identity matrix as containing the base-2 representation of a number, but that is another thing entirely.

I would prefer strongly to conduct this conversation by e-mail, as the process of approving comments and typing in the comment box is too painful.

Michael said...

The cardinality of N is the same as the cardinality of the rational numbers Q, because I can create a one-to-one mapping between N and Q. I have seen enough of a demonstration to show me (intuitively) that it can be done in principle, even though the task of actually doing it unto infinity is in practice impossible.

Right, it is precisely as impossible as the task of listing all natural numbers is. But for any rational someone gives, with enough time the precise natural it corresponds to can be calculated. If someone had the ability to give "all the rationals" (which of course you can't, because infinity), then they would get the "entire" mapping back.

But why can I not create such a mapping between N and its power set? The power set consists of discrete items, and (intuitively) it seem no harder (or easier ;-)) to number them all starting at 1 than it was for the rationals. But again, standard mathematics tells me that this intuition is "wrong".

I don't think there is any consistent way to create that mapping, under any set of axioms, and here is why - the power set contains an infinite number of elements of size one, of size two, etc ... and an infinite number of infinite-size elements.

You can devise a dovetailing procedure that will assign a unique natural number to all of the finite subsets - list one of size one, then one of size two, then one of size one again, then two, then three, etc. Devising such a procedure is a relatively simple task - I'm sure you could come up with one in a few moment's thought.

However, any such procedure will never assign a natural number to the subset consisting of all even numbers, and if your first response is "oh we'll just solve that by adding it explicitly", well, what about the set of all even numbers greater than 2? or greater than 4? or ... you get the idea.

In fact, no matter what your procedure is, I can devise an infinite set that is not listed - and precisely by Cantor's diagonal! First, let us assume you have a procedure that you believe can put every element of the power set of N into one-to-one correspondence with the elements of N. Then, what we do is, for each element n of N, find the set you say corresponds to n, and find out if it contains the natural number n or not. If it does, I don't put n into my new set. If it doesn't, I do. I now have a subset of the natural numbers that is not in your list. This is a contradiction, and the only way to resolve it is to either completely reject the idea of comparing infinities... or conclude that the power set of the set of natural numbers is strictly bigger than the natural numbers.

Now, you might want to object that my set feels "wrong" somehow, but it is clearly a fully-defined set; we can take anything and test it for membership in that set: If it's not a natural number, it's not a member. If it is a natural number, it's a member iff the subset your procedure associates with that natural number does not contain it. If that's not enough, then we can't define infinite sets at all!

Vorlath said...

Cantor didn't prove that the reals are uncountable. He proved that the digits are not mapped one to one with their possible permutations (the digits are a proper subset) within the grid. As independent sets, they can be remapped one to one as per Dedekind's theorem. But when one set is created from another in this way, they have a very specific relationship that does not have to be one to one.

To map the naturals to reals, you need to have both sets bounded or not bounded. There is one way to make the naturals bounded.

Write out all N on a single row (on the right hand side). Then write all elements at odd indexes on the top row and all even indexes on the bottom row (again on the right hand side). Assign the top row the digit 0 and the bottom row digit 1 (on the left hand side).

Keep doing this for each new row and add the new digit at each iteration to the immediated right of the previously assigned digits (which are always on the left). So the next step will have assigned digits of 00,01,10,11. On the right, each list of naturals on each row is still infinite. In fact, you can remap them one to one with N at each iteration as per Dedekind's theorem since they are all proper subsets.

Doing this infinitely many times will yield infinitely many assigned digits per row (on the left), all of which are known to map one to one with R (since Cantor uses the same amount of digits for the reals by putting a decimal point in front). For each row, there is one or more natural (on the right). |N|>=|R|. By the fact that |R|>|N| and |N|>=|R|, then |R|=|N|.

Jeffrey Shallit said...

Well, again, Vorlath, I am fascinated by why you think your argument is a convincing one. I'm still hoping to interview you for my book. If you could send me your e-mail address or phone number, I'd appreciate it.

For the record:

- you haven't defined what you mean by "independent set"

- in order to map one set to another, it is not necessary that "both sets [are] bounded or not bounded". For example, the map x -> 1/x maps the bounded set (0,1] to the unbounded set [1, infinity).

- if |R|>|N| as you claim, then clearly it is impossible that |R| = |N|

Vorlath said...

"- you haven't defined what you mean by "independent set""

A set that does not use a mapping to another set for its definition.

"- in order to map one set to another, it is not necessary that "both sets [are] bounded or not bounded". For example, the map x -> 1/x maps the bounded set (0,1] to the unbounded set [1, infinity)."

Here's what I said.

"To map the naturals to reals, you need to have both sets bounded or not bounded."

You're using reals. Show me how naturals can be bounded and remain naturals. Otherwise, you can show a bogus contradiction as found in Cantor's first proof where he uses this very fact with bonded ranges.

"- if |R|>|N| as you claim, then clearly it is impossible that |R| = |N|"

Dedekind's theorem says otherwise. A set S can have the following property |S| > |S| because all infinite sets are their own proper subsets. They can be remapped one to one.

Sorry, but your last comment was really bad. It's accepted that if you show |A|>|B| and |B|>|A|, then |A| = |B|. Do even understand the concept of proper subsets?

And no, I don't want to be interviewed because you're only interested in ridicule. And that last comment... oh boy. OUCH!

Jeffrey Shallit said...

Show me how naturals can be bounded and remain naturals.

You seem confused. Of course the natural numbers are not bounded. But you claimed that it was impossible to map an unbounded set to a bounded set of real numbers -- at least, that's how I interpret your claim "To map the naturals to reals, you need to have both sets bounded or not bounded". I provided a counterexample to this claim.

A set S can have the following property |S| > |S| because all infinite sets are their own proper subsets.

No, you're very confused. For any set S, infinite or not, we have |S| = |S|, not |S| > |S|.

It's accepted that if you show |A|>|B| and |B|>|A|, then |A| = |B|.

No, this is not accepted. You are confused. Your assertion would, however, become true if you replaced ">" by ">=".

Anonymous said...

"Tell me - do you find it at all surprising that nearly every professional mathematician understands and can explain Cantor's proof - and they have done so for more than a hundred years - and they all accept it ... but you, who are not a professional mathematician, somehow have managed to find a mistake that has eluded everyone else? Does that seem at all plausible to you? And if so, why?"

This is untrue. Many mathematicians can neither understand nor explain Cantor's diagonal. More than a hundred years? I don't think so. This statement of yours is only your speculative view.

Jeffrey Shallit said...

This statement of yours is only your speculative view.

No, it's much more than that. I am, after all, a professional mathematician, and I've published dozens of papers and talked to hundreds, if not thousands, of mathematicians. I have never met a single professional mathematician who could not understand or explain Cantor's argument.

Vorlath said...

> I have never met a single professional mathematician who could not understand or explain Cantor's argument.

You know, if you can't tell who's the mathematician that can't describe Cantor's argument...

Seriously, you don't even understand Dedekind's theorem.

Just one day, I would hope you would sit and look at the problem on your own instead of questioning people's mental stability. Keep and open mind and don't tell anyone about the results you find concerning Cantor's diagonal argument. Just look at what Cantor's diagonal is doing. For one moment, use Cantor's argument from the other side. Don't use the diagonal to create the new number. Instead, I get to give you a representation from any element in my list every time you select a digit. Cantor uses representations to state that he's found a new number, correct? So I just need to find a representation not used when all digits have been selected.

When you select digit #1, I give you 0.100000...

When you select digit #2, I give you 0.010000....

When you select digit #3, I give you element 0.001000...

On and on...

Do tell, when do I get to give you elements that have more than one digit set to 1 if we're going by representations?

Whatever you think, I've just proven that Cantor's grid is a subset of my list. Cantor can never use all reals. This happens to be the exact premise trying to be proven, hence the circular logic. Cantor's grid is set up to fail. It can't even use all of Q. Is |Q|>|N|? Of course not. QED.

On your own, I would then suggest to look at differences in generators to find out why the order is of the utmost importance and using digits (representations) changes the generator of the given list to cause the bogus contradiction. Cantor proved that these are different generators: 1) sequential generators and 2) generators where new members formed between any two existing members are different.

Digit selection uses a sequential generator. Reals in binary form do not use a sequential generator.

Now use the same generator for N and R.

Jeffrey Shallit said...

Well, I've got to admit that I'm utterly fascinated by the kind of mental pathology that thinks the preceding gibberish constitutes an argument.

Anonymous said...

It does not take a genius to see that Cantor's diagonal argument is nonsense.

I am not interested in debating this with you but I am interested in what motivates academics like yourself psychologically to accept arguments you clearly do not understand?

Jeffrey Shallit said...

Well, first you have to establish that it is "nonsense" and that all professional mathematicians are deluded.

Miranda said...

"you have to establish that... all professional mathematicians are deluded."

Why say "all" when you could've said "most"?
http://en.wikipedia.org/wiki/Controversy_over_Cantor%27s_theory says his theory was "largely accepted" and "The rejection of Cantor's infinitary ideas influenced the development of schools of mathematics such as constructivism and intuitionism."

Jeffrey Shallit said...

Miranda:

You really don't understand anything on this blog at all, do you?

Why does it interest you to make fatuous comments on things you know nothing about?

Miranda said...

I know mathematics like you know the meaning of the word "all."

Jeffrey Shallit said...

Miranda:

Your continued cluelessness never fails to amuse. You don't even understand why your quoted sentence from wikipedia doesn't contradict what I said.

Anonymous said...

This list enumerates all 2 bit binary sequences:

00
01
10
11

This one enumerates all 3 bit binary sequences:

000
001
010
011
100
101
110
111

Using diagonalization on the first to produce a sequence that is not in the list fails. It produces '10' which *is* in the list.

Using diagonalization on the second list also fails. It produces '111' which *is* in the list.

Clearly, increasing the length of the sequences does not produce lists in which diagonalization will achieve its purpose, i.e. to produce binary sequences of a given length which are not already in the list.

So if we were to compile an enumeration of infinite length binary sequences, how do we know that diagonalization produces a sequence not contained in the list?

P.S. This is not an attempt to prove that the Real numbers are either countable or not. It is simply to raise a question about one of the proofs that they are not

Jeffrey Shallit said...

So if we were to compile an enumeration of infinite length binary sequences, how do we know that diagonalization produces a sequence not contained in the list?

We know it [that diagonalization produces a sequence not on the list] because Cantor's proof produces such a sequence. He says, suppose it is on the list. Then it must appear in some row, say row n. But then it differs from row n in position n.

Lots of things are true for finite prefixes p of infinite things x, which fail to be true for x, and vice versa. A simple example: the set {1} is missing a positive integer, the set {1,2} is missing a positive integer, the set {1,2,3} is missing a positive integer, and so forth. But {1,2,3, ...} is not missing any positive integers.

George said...

The diagonalization argument works for a finite list if the number of rows and columns are the same. You would need to use:

0000
0100
1000
1100

The diagonalization argument gives you 1011, which indeed is not in the list.

John Gabriel said...

The truth is always anti-semitic. Say anything about a Jew (it does not matter if he is a crackpot or no) that other Jews don't like and you are by default anti-semitic.

Cantor was a crackpot. That sets of well-defined objects are countable is a non-remarkable observation. The real numbers are uncountable because, wait for it,... they are not well-defined.

If the real numbers can be all be represented in decimal (FALSE), then the set of real numbers IS indeed countable. I proved this in a knol many years ago.

Go ahead, publish my comment if you dare!

http://thenewcalculus.weebly.com

Jeffrey Shallit said...

John Gabriel:

I have an extremely low tolerance for anti-semitism on this blog. I'm giving you a second chance only because I'd like to interview you for a book I am writing on mathematical crackpots. If you are willing to answer a number of questions, contact me by e-mail at shallit@cs.uwaterloo.ca .

Harriet said...

Oh my goodness; I just read some of the comments. Professor Shallit: I don't know where your patience comes from.

Winston Smith said...

Actually, there is very little groupthink in academia, precisely because you make your reputation by doing something new. Of course there are exceptions, but in my experience they are extremely rare.

"The definitive study of the herd instincts of astronomers has yet to be written, but there are times when we resemble nothing so much as a herd of antelope, heads down in tight formation, thundering with firm determination in a particular direction across the plain. At a given signal from the leader
we whirl about, and, with equally firm determination, thunder off in a quite different direction,
still in tight parallel formation."

Jeffrey Shallit said...

How about in certain scientific fields?

As I said, in my experience they are very rare. My guess is that Ferrie is talking about "fashion", which is something completely different from "groupthink". In theoretical computer science, there was (for a time) a "fashion" to investigate VLSI, and many papers appeared quickly. Now nobody is working on it. But that is very different from "groupthink".

My guess is that our pseudonymous Winston is not a scientist.

Winston Smith said...

If you were familiar with the history of determining the age of the earth, I believe you'd conclude that groupthink was about just that, groupthink, and not fashion.

Your comment that I'm probably not a scientist supports what I suspect is your position: "If you're not "in the field", then your opinion means little." For that matter, I suspect you're not a historian of science.

Jeffrey Shallit said...

If you were familiar with the history of determining the age of the earth, I believe you'd conclude that groupthink was about just that, groupthink, and not fashion.

I'm very familiar with it, because I've read Dalrymple's book. Have you?

You're not one of those young-earth crackpots, are you?

For that matter, I suspect you're not a historian of science.

And you would be wrong. You can read my article in Historia Mathematica, 21 (1994), 401-419. Enjoy!

Winston Smith said...

I love how you "wonder" if I'm a young-earth crackpot because I believe there was a ton of
groupthink going on in Kelvin's time, and even today, according to my understanding of Fernie.
In your "wonder", there's an implied, though I'm sure unintended, admitting of deficiency of challenging the consensus going on in the science world. An insider charging "Groupthink"? Unthinkable! He must be a creationist! Sad.

If a historian of math is the same as a historian of science, then you win. If not...

Jeffrey Shallit said...

because I believe there was a ton of
groupthink going on in Kelvin's time

Wrong. Up to now you hadn't mentioned Kelvin. I suspected you were a young-earth creationist because (a) you adopt a pseudonym to conceal your real name (b) you like to quote-mine to make points and (c) you provided no references and are incoherent in your points.

Winston Smith said...

I don't understand your point about my not mentioning Kelvin. An understanding of the history of the herd mentality in this issue can't be done without his name being front and center. a) This is a silly assumption, based on http://www.noforbiddenquestions.com/2011/04/should-i-blog-anonymously/ b) A quote that rubs you the wrong way is by definition "quote-mined". c) ad hominem.

Jeffrey Shallit said...

Yes, I see there's a lot you don't understand. I was responding to your claim that I love how you "wonder" if I'm a young-earth crackpot because I believe there was a ton of groupthink going on in Kelvin's time. How could that possibly have been my justification, when up to then you hadn't mentioned Kelvin? Try to pay attention.

You don't seem to understand my other response, either. People make guesses about other people's behavior & motivations based on lots of social cues; these need not be based on "logic" and hence calling "ad hominem" or justifying your decision to hide behind a pseudonym misses the point entirely. You asked why I thought you were a creationist, and I gave my reasons for making that guess.

Finally, as for "quote-mining". nobody serious (even historians of science) thinks you can answer questions about complex behaviors like "groupthink" by producing a single unsourced quote which is probably about something else entirely (but since you didn't cite the paper, we can't check so easily). That's typical creationist behavior.

Jeffrey Shallit said...

If a historian of math is the same as a historian of science, then you win. If not...

I fully expected cavilling about the point that mathematics is not science. True enough. The point remains, I'm very interested in the history of ideas and their acceptance, and I've even gotten a peer-reviewed paper published on that topic. Now, how about your expertise in the subject?

Winston Smith said...

I'm also very interested in the history of ideas and their acceptance (and herd mentality). I edited a book which included a chapter on the topic. But sorry, I'm not saying which one.
PS: What you're calling cavil, I call significant.
"Yes, I see there's a lot you don't understand." -- Hmmm, I can definitely see why you're fan of Callan Bentley.

Jeffrey Shallit said...

I edited a book which included a chapter on the topic. But sorry, I'm not saying which one.

Coward. But I bet it either doesn't exist or it's with a primarily religious publisher.

Winston Smith said...

For Fernie's quote, go look up Fernie J D (1969) "The period-luminosity relation: a historical review." Publ. Astron. Society Pacific, vol. 81 p707-731. I'm sure you will continue to believe that I took his quote out of context.

I like your assumption that a science publisher is automatically better than a religious publisher when it comes to the history of nineteenth century science.

Jeffrey Shallit said...

I like your assumption that a science publisher is automatically better than a religious publisher when it comes to the history of nineteenth century science.

I said nothing about scientific publishers. Tell me, are you actually this incompetent at reading comprehension, or are you just trolling?

And yes, if someone chooses to publish about the history of science with a primarily religious publisher, that says volumes about their motivation.

George said...

Hmm ... a single quote from more 44 years ago does not make a very convincing argument. I believe astronomers are among the most open minded and diverse of scientists. You can't exactly travel to a gamma-ray burst to figure out what is really going on, so there are many competing theories.

I recently heard a podcast about astronomer George Chapline, who doesn't believe in black holes. Instead, he replaces them by "dark-energy stars". I'm not sure if his theory has gained any acceptance.

Winston Smith said...

"And yes, if someone chooses to publish about the history of science with a primarily religious publisher, that says volumes about their motivation. "
Hey Mr. Reading Comprehension Guru, I never said the book I edited was a book about the history of science. I said it included a chapter on the history of dating the Earth. And I didn't even say it was with a religious publisher.

The term troll is subjective.

I'll accept being called a coward for wishing to remain anonymous as long as you call all of your friends who also blog anonymously cowards. That link I provided above suggests you have many such friends.

Jeffrey Shallit said...

Hey Mr. Reading Comprehension Guru, I never said the book I edited was a book about the history of science. I said it included a chapter on the history of dating the Earth.

Ok, now I know you are just trolling, since I was simply responding to your comment that "I like your assumption that a science publisher is automatically better than a religious publisher when it comes to the history of nineteenth century science".

Go bother someone who gives a damn what you think.

Vorlath said...

Hi, it's been a while.

What if it's possible to enumerate N using only a subset of N for the digits? (This assumes using binary or higher base).

If so, then all Cantor has proven is that the same is true with R. You only need a subset of R (aka N) digits to enumerate all of R.

But since a subset of N can map one to one with N outside of the digit/row relationship, then it means it's also possible that a subset of R (aka N) can map to R.

It doesn't mean that there is necessarily a bijection between N and R. But it would show a flaw in the proof, no?

Would you agree with this? On the condition the first question above is true?

The reason people have problem with Cantor's proof is that they believe the first question I posed above is true.

Do you have a proof that it is false? Note that we're talking about the digits needed to represent N. Not if there is a bijection outside of this relationship. Also, we are talking about binary or higher base.

Jeffrey Shallit said...

What if it's possible to enumerate N using only a subset of N for the digits?

I don't even know what this is supposed to mean.

Anonymous said...

An irrefutable proof that real numbers don't exist:

http://www.spacetimeandtheuniverse.com/math/4507-0-999-equal-one-317.html#post21409

Jeffrey Shallit said...

Entertaining crackpottery, John. Of course real numbers don't "exist" and neither do integers.

Benjamin Schak said...

Going back to the part of the thread with Eamon Knight (about 4 years ago now), I can think of a somewhat natural notion of cardinality that would set |2Z+1| = |2Z|, but would not be equivalent to the usual notion:

|A| = |B| iff there is some indexing A_k and B_k of A and B such that {A_k – B_k} is bounded.

Clearly (at least by my intuition) not as deep as the standard notion of cardinality, but I could imagine it might be good for a few cute theorems with a combinatorial flavor.

Nick R said...

I believe it was Bertrand Russell who said : A stupid man's understanding of what a clever man says can never be accurate, because he unconsciously translates what he hears into something he can understand.

I give you full marks for your patience Dr Shallit. Good luck with your book. I hope it is as amusing as this blog.