# Why isn't Cantor's diagonal argument just a paradox?

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."

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
It shows that there are more reals in [0,1] than whole numbers. Your question is about the natural numbers and their power set. Same logic, different sets under consideration. No? – jpmc26 Aug 24 '14 at 22:49
@jpmc26, the two arguments are equivalent; imagine the youtube video using base 2 instead of base 10, then think of the 0 or 1 of the n-th digit as the truth value of the property of being included in a set. – nir Aug 25 '14 at 7:23
The diagonalization argument simply shows that there is no bijection between the reals and the integers. We then make definitions of cardinality as a generalization of size. Based on that, I fail to see what could even be the paradox. – James Kingsbery Sep 12 '14 at 16:38

When considering a mathematical result it is important to place all terms in the correct context. Cantor's diagonal argument is a method of proof, so it does not "conclude" anything. It is neither a paradox nor a theorem.

The diagonal argument is used to prove a theorem that states R is not equinumerous with N. Diagonalization is a well-defined, mathematically sound procedure.

The justification for concluding that |R| > |N| is that it has been thus proven in a mathematically rigorous way.

Cantor's result can be proven in ways that employ neither diagonalization nor the reductio-ad-absurdum method. Diagonalization is the popular method of proof because it is the most elegant and intuitively clear. Cantor originally proved the result using an different reductio argument involving nested intervals. An example of a non-reductio proof is given by what is called The Measurement Argument.

Aside : Russell's paradox is a logical (formal) paradox and one could say that it gives rise to a theorem, namely that the cumulative hierarchy (the collection of all sets) is not itself a set. This would not be a theorem of set theory since set theory only deals with sets, but it could be considered a theorem of mathematics in general.

EDIT (Sep 11, '13): When I say that the diagonal argument is a method of proof and so does not conclude anything, I mean to point out that the diagonal argument is an argument used to prove dozens, if not hundreds of mathematical results in many areas of mathematics.

Further, it may not be fair to say that the Measurement Argument is a non-reductio proof of Cantor's result. While the actual proof is non-reductio, it does rely on Measure Theory. Precisely, the proof shows that any countable set has zero measure. However, it may be that those measure-theoretic results which allow us to say that an uncountable set has non-zero measure may themselves currently have only reductio proofs.

Finally, the context of Cantor's result is Set Theory. Set Theory uses classical logic. If you wish to apply a logic which rejects the Law of the Excluded Middle to argue the proof is not valid, fine. But this does not invalidate Cantor's result as a result from Set Theory.

-
The diagonal argument as stated by OP does not use reductio-ad-absurdum, since the conclusion is a negation. Do you have any precise definition of a "proof without diagonalization"? This is not trivial, see e.g. the accepted answer in mathoverflow.net/questions/46970/… – Anders Lundstedt Aug 23 '14 at 19:12
@AndersLundstedt I think you'll find that it does. Specifically it states "Suppose for reductio ...". – Nick R Aug 23 '14 at 19:19
Reduction-ad-absurdum is "suppose not P; derive a contradiction; conclude P". We have "suppose P; derive a contradiction; conclude not P" (with P="N and R have the same cardinality"). – Anders Lundstedt Aug 23 '14 at 19:23
@AndersLundstedt I enjoyed our chat in the chat room. One last comment here. The proof in the original posting ends with the word "Contradiction". So you must admit, it does appear to use reductio. – Nick R Aug 23 '14 at 20:00
@AndersLundstedt If you are still interest... Regarding your previous comment, the two different "schema" you describe are logically equivalent. They are two different ways of expressing reductio. To see this, suppose our proposition P is a proposition of the form not(Q). Substitute this for P in the first schema and you have the second schema. Conversely, substitute into the second to obtain the first. So they are two equivalent schema for the reductio argument. Cheers. – Nick R Aug 23 '14 at 22:06

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.

-

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
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 R 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

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

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.

-

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.

-