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

Question

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)?

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.