9

Cantor's diagonal argument concludes the cardinality of the power set of a countably infinite set is greater than that of the countably infinite set.

In other words, the infiniteness of real numbers is mightier than that of the natural numbers.

The proof goes as follows (excerpt from Peter Smith's book):

Consider the powerset of N, in other words the collection P whose members are all the sets of numbers (so X ∈ P iff X ⊆ N).

Suppose for reductio that there is a function f : N → P which enumerates P, and consider what we’ll call the diagonal set D ⊆ N such that n ∈ D iff n ∉ f(n).

Since D ∈ P and f by hypothesis enumerates all the members of P, there must be some number d such that f(d) = D. So we have, for all numbers n, n ∈ f(d) iff n ∉ f(n). Hence in particular d ∈ f(d) iff d ∉ f(d). Contradiction!

This is similar to Russell's paradox: Let R = { x | x ∉ x }, then R ∈ R iff R ∉ R

What is the justification for concluding a difference of cardinality of infinity, rather than concluding a paradox?


EDIT - It is possible I should not have used the term paradox in this question, although the proof does seem to meet this definition of a paradox from the Wikipedia: "A veridical paradox produces a result that appears absurd but is demonstrated to be true nevertheless."

Nevertheless, lets say there is no paradox, just a contradiction.

I was interested in why it is justified to resolve the contradiction with different cardinalities of infinities. If you don't see the problem, then you should probably not answer this question; here is for example what Wittgenstein had to say about this:

From Cantor's proof, however, set theorists erroneously conclude that “the set of irrational numbers” is greater in multiplicity than any enumeration of irrationals (or the set of rationals), when the only conclusion to draw is that there is no such thing as the set of all the irrational numbers.

Can you provide a reference to criticism of his opinion, explaining why he was wrong (except for dismissing him as a finitist)?

  • It's the same logic as this: youtube.com/watch?v=A-QoutHCu4o. It's a method of showing there's no bijection between the naturals and their power set. – jpmc26 Aug 24 '14 at 0:28
  • @jpmc26, "it's the same logic" and the same problem. – nir Aug 24 '14 at 19:00
  • 1
    Re your edit: So it appears that Wittgenstein, who was reportedly a pretty smart guy, failed to grasp Cantor's simple argument. All this shows is that smart guys sometimes make silly errors. It does not follow that the silly errors need to be taken seriously, or that we should expect them to generate much in the way of published criticism. – WillO Dec 15 '15 at 0:22
  • 2
    @WillO, do you really assume that W failed to grasp the diagonal proof? you must be kidding me! – nir Dec 15 '15 at 7:34
  • 1
    @nir: No, I do not assume this. I conclude it, based on the quote you provided. – WillO Dec 15 '15 at 7:43
5

There is no justification for one or the other.

Russell's paradox is a paradox if you believe** in unrestricted comprehension (for each P there is a set {x | P}), or at least if you believe** that the set {x | x ∉ x} exists. Russel's paradox is not a paradox if you use it to conclude that the set {x | x ∉ x} does not exist.

Cantor's diagonal argument is a paradox if you believe** that all infinite sets have the same cardinality, or at least if you believe** that an infinite set and its power set have the same cardinality. Cantor's diagonal argument is not a paradox if you use it to conclude that a set's cardinality is not that of its power set.


** "to believe" need here not be interpreted literally. It may be replaced by e.g. "to have as an axiom of a theory of sets".

  • but what is the justification for inventing new classes of infinity rather than concluding the definition of the diagonal set is invalid (as in Russell's paradox) ? – nir Aug 23 '14 at 14:23
  • 1
    We do not invent any new classes of infinity. What Cantor's diagonal argument shows is that these different classes of infinity is a consequence of the definition of cardinality as "X and Y have the same cardinality iff there is a bijection from X to Y". – Anders Lundstedt Aug 23 '14 at 14:25
  • It is perfectly fine to reject the conclusion of the diagonal argument. Then you have to prevent the diagonalization in some way. I believe some set theories do this. Perhaps a set theorist can provide you with a reference. – Anders Lundstedt Aug 23 '14 at 14:28
  • Sorry, I had to down-vote this reply. I've never down voted and I feel terribly guilty. My reason for down-voting is that diagonalization is a well-defined mathematical procedure and therefore cannot be called paradox. Diagonalization can be used to argue that a particular statement is a paradox, but diagonaliztion itself cannot be considered a paradox. – Nick Aug 23 '14 at 18:22
  • @NickR When calling "Cantor's diagonal argument" a paradox, I of course mean that its conclusion is a paradox. I do not mean that the method is a paradox, which of course makes no sense. – Anders Lundstedt Aug 23 '14 at 18:49
3

A paradox (in this context) consists of two theorems that contradict each other.

Russell's paradox, for example, consists of the two theorems "R is an element of R" and $R is not an element of R" (where R stands for the Russell set.

In the case of Cantor, we have one theorem, namely that there is no surjective map from the natural numbers to the real numbers. For this to be part of a paradox, we'd need a second theorem that says there is a surjective map from the natural numbers to the real numbers. Nobody (or more precisely nobody using the standard axioms of set theory) has proved such a theorem, so there is no paradox.

1

Well spotted. It turns out that a number of traditional paradoxes rely on what is called the diagonal argument, and which can be interpreted as a fixpoint argument as the abstract of this paper by Yanufsky points out:

Following F. William Lawvere, we show that many self-referential paradoxes, incompleteness theorems and fixed point theorems fall out of the same simple scheme. We demonstrate these similarities by showing how this simple scheme encompasses the semantic paradoxes, and how they arise as diagonal arguments and fixed point theorems in logic, computability theory, complexity theory and formal language theory.

In fact Yanufsky takes a less sophisticated approach to Lawvere who uses Category theory to establish the fixed point theorem; but he does allude to it.

One interpretation of paradoxes in mathematics is to say something is wrong in the general framework used; in Cantors case he had to extend his 'mathematical' framework to incorporate a new notion of infinities (cardinalities); and in Russells case he ramified his type theory; ie instead of on type there was a hierarchy of them

  • It seems that while he explains how these paradoxes are created, he does not question Cantor's conclusion at all. – nir Aug 24 '14 at 20:45
1

Russell's paradox uses a combination of logic and set theory to "prove" a contradiction - X <- X iff X </- X asserts that two opposite statements are equivalent. From this, we can prove anything we want, by the principle of explosion. If we want set theory to be useful, this must be resolved, by changing set theory to prevent us creating the set of all sets that don't contain themselves. This goes against our prior beliefs about set theory.

On the other hand, the resolution to the contradiction in Cantor's diagonalization argument is much simpler. The resolution is in fact the object of the argument - it is the thing we are trying to prove. The resolution enlarges the theory, rather than forcing us to change it to avoid a contradiction.

1

Cantor's diagonal argument in the end demonstrates "If the integers and the real numbers have the same cardinality, then we get a paradox". Note the big If in the first part. Because the paradox is conditional on the assumption that integers and real numbers have the same cardinality, that assumption must be false and integers and real numbers have different cardinalities.

Now if you were to find a proof that integers and real numbers have the same cardinality, then we could add your proof and Cantor's diagonal argument and have a real paradox. This is very unlikely to happen.

1

In relation to Witrgenstein's comment on the proof, I think this is what he was getting at:

Between two finite sets, we say they have the same number of elements if we can put them in one-to-one correspondence. Cantor's proof is interpreted as meaning that there are cardinalities of infinities, with the reals being of a greater kind of infinity. It is deemed to represent an important discovery in the nature of infinite sets. What I think Wittgenstein is saying is that it's not really a discovery about sets so much as a mathematical creation. In using terms like "cardinality" and "set" and "one-to-one correspondence" we're making it sound like we have discovered something about them, as opposed to constructing new forms of these terms with different properties than their usual ones. In his eyes, the problem may be that you're using the term "set" when you say "set of all irrational numbers" in a way that is an extension of the idea of the set. Wittgenstein is possibly saying he doesn't like that extension of the idea, or he is just saying we should be aware that it is an extension of the term. I don't think he's necessarily denying the proof itself, maybe more somebody taking something very metaphysical out of it, thinking they've discovered something new about sets instead of inventing a new set of rules in set theory.

-2

The only paradox connected with Cantor's diagonal argument is the fact that so many mathematicians believe in it. Cantor's first premise is already wrong, namely that the "list" can contain all counting numbers, i.e., natural numbers. There is no complete set of natural numbers in mathematics, and there is a simple proof for that statement: Up to every natural number n the segment 1, 2, 3, ..., n is finite and is followed by potentially infinitely many further natural numbers. Cantor simply proves that his premise is wrong.

But even if we accept his idea, we will never get a real "diagonal number", because a real number is not defined by digits unless there is a last one.

  • 1
    Please consider citing sources to improve this answer (it's really cranky-sounding right now) – Joseph Weissman Jul 15 '17 at 13:43
  • 1
    @Joseph Weissman: Are you joking? Try to find a natural number that does not belong to a finite initial segment followed by infinitely many further numbers. Cranky is only the belief that nevertheless universal quantification is possible. Obviously it is not. Or try to define a real number by a list of digits. That is impossible too. (Don't mistake "a list" with a finite formula like "0.111..." or SUM(1/n!)) Cranky is only the belief that nevertheless a real number can be defined by digits. – Heinrich Jul 16 '17 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.