# Convincing proofs, proofs by contradiction and countability

Disclaimer: I have a (modest) background in mathematical physics, not logic, so I know very little of the latter.

Although when I understood Cantor's argument for the first time (from one of Martin Gardner's books) I was immediately taken by its beauty, recently I have grown slightly suspicious of it. I realize that it sounds like a beginning of a very cranky opinion, but I'll state it anyway: Cantor's argument, an argument by contradiction, seems to be very unlike the direct arguments for countability of $\mathbb{Q}$ and $\mathbb{Z}$. It is surprising, especially taken in its historical context, and, from a naive point of view that I do not necessarily espouse, almost unconvincing: why can't this ingenious construction be toppled with some other, even more ingenious?

Given these, admittedly dubious, considerations, I'll try to pose the question: is there a possibility of direct argument that would prove the uncountability of reals? And if there is not, what would be the reasons for the lack of its existence?

P.S.: I have just discovered this question and think that another way to reformulate my question would be: is the uncountability of reals provable in minimal logic?

• With some ingenuity of function definition, it can be demonstrated that $\Bbb R$ is equinumerous with $\mathcal{P}(\Bbb N)$ by the Schroder-Bernstein Theorem. Once you know this, you can prove by Cantor's Theorem that the reals are of strictly larger cardinality than the natural numbers. – Robert Wolfe Mar 1 '14 at 23:44
• @Bryan: The diagonal argument is the proof of Cantor's theorem in the countable case (which is also often presented as a proof by contradiction). – Asaf Karagila Mar 1 '14 at 23:47
• I know the set-theoretic proof. That is if $f:A\rightarrow\mathcal{P}(A)$ were surjective, then there'd be an element mapped to $\{x\in A: x\not\in f(x)\}$. The existence of such an element leads to a contradiction. I don't particularly like the general argument given when one uses the Cantor's Diagonal argument, as not all reals are uniquely represented by their decimal expansions. It's easy to account for these cases but is rarely mentioned or left to the reader to finish up. – Robert Wolfe Mar 1 '14 at 23:53
• @Bryan: The method of the proof is the same. If you think about it in terms of binary sequences, it's the same proof. – Asaf Karagila Mar 1 '14 at 23:56
• I get that. But even binary sequences do not give unique representations of reals in decimal notation. I just don't like having to take a side-step to account for weird elements. – Robert Wolfe Mar 2 '14 at 0:02

Cantor's diagonal is not an argument by contradiction.

The argument says, given a countable list of real numbers, we can produce a number not on that list. Therefore there is no function from $\Bbb N$ to $\Bbb R$ which is surjective.

• This is a classic example of how people often rush to contradiction; and how obfuscating and obscuring this can be. – Asaf Karagila Mar 1 '14 at 23:43

I will add some notes to @Asaf Karagila's answer, with which I totally agree.

In natural deduction we use a couple of rules with the falsum connective [see Dirk van Dalen, Logic and Structure (5th ed - 2013), page 30]; one is the falsum rule :

$$\frac {\bot } { \varphi}$$

The other one is RAA :

$$\frac {\frac {[\lnot \varphi]} \bot } {\varphi}$$

This one is the rule used in indirect proofs or proofs by contradiction; if we re-write it in "axiom form", we get: $(\lnot \varphi \rightarrow \bot) \rightarrow \varphi$ and using the definition of $\lnot$ in terms of $\bot$, (i.e. $\lnot \varphi$ is $\varphi \rightarrow \bot$) we have the usual Double Negation rule of classical logic :

$\lnot \lnot \varphi \rightarrow \varphi$.

This in turn, exploiting the equivalence in classical logic between $\lnot p \rightarrow q$ and $p \lor q$, is the Law of Ecluded Middle :

$\lnot \varphi \lor \varphi$.

RAA is not :

$$\frac {\frac {[\varphi]} \bot } {\lnot \varphi}$$

(usually called $\lnot$-introduction).

The last one is simply an application of modus ponens (in natural deduction called $\rightarrow$-intro) :

$$\frac {\frac {[\varphi]} \bot } {\varphi \rightarrow \bot}$$

rewritten using the definition of $\lnot \varphi$ as $\varphi \rightarrow \bot$.

RAA and $\lnot$-introduction, despite being decptivly similar, are very very different; intuitionists accept the last one, as well as the falsum rule, but reject RAA (and its equivalent forms).

About the confusion remarked by Asaf, see in Sara Negri & Jan von Plato, Structural Proof Theory (2001), page 27 :

the inference pattern, if something leads to a contradiction the contrary follows, is known as the principle of reductio ad absurdum. Dictionary definitions of this principle rarely make the distinction into a genuine indirect proof and a proof of a negative proposition: If $A$ leads to a contradiction, then $\lnot A$ can be inferred. Mathematical and even logical literature are full of examples in which the latter inference, a special case of a constructive proof of an implication, is confused with a genuine reductio. A typical example is the proof of irrationality of a real number $x$ : Assume that $x$ is rational, derive a contradiction, and conclude that $x$ is irrational. The fallacy in claiming that this is an indirect proof stems from not realizing that to be an irrational number is a negative property : There do not exist integers $n, m$ such that $x = n/m$.

Cantor's Diagonal Argument follows the same pattern :

Suppose that $S = \{ x_1, x_2, x_3, . . . \}$ is a countable set of real numbers ...

i.e. let us assume that "$\exists$ a bijection from $\mathbb N$ to ...."; then we construct a number $x$ not in $S$, so that : "$\exists$ a bijection $\rightarrow \bot$", i.e. (by $\lnot$-introduction) : "$\lnot \exists$ a bijection ...".

Going back to intuitionists, they accept Cantor's argument, i.e. the proof of the non-existence of a bijection from the assumption of its existence.

They reject, instead, the assertion of the existence of an object (number, set or function) based on RAA, i.e.they do not accept to conclude the existence of an object from the derivation of a contradiction from the assumption of the non-existence of it.

I want to try to expand on parts of several answers. A key source of confusion about these things is that many mathematicians know proof only in a natural-language sense, and so the may call something a "proof by contradiction" even when it is not really a proof by contradiction in any formal sense.

In most areas of constructive mathematics (where they are particularly careful about proof by contradiction), a negative statement $\lnot \phi$ is viewed as an abbreviation for $\phi \to \bot$, where $\bot$ is some identically false proposition. For example, in settings where numbers are available we could use $0=1$ for $\bot$.

Under that standard convention, a negative statement $\lnot \phi$ becomes an implication statement, and we can prove that implication statement directly just like any other implication: we assume $\phi$ holds and prove that $\bot$ also holds.This is not a proof by contradiction, however - more on that below. As another answer indicates, in some formal deduction systems it goes by the name "$\lnot$-introduction".

Here is a similar example. How would we give a direct and constructive proof that $\lnot (\phi \land \lnot \phi)$ holds for arbitrary $\phi$? First, rewrite the sentence as an implication: $$(\phi \land (\phi \to \bot)) \to \bot$$ Now, assume the hypothesis: we assume $\phi$ and we assume $\phi \to \bot$. Applying modus ponens, we see that $\bot$ must hold. That is the conclusion we wanted to establish, which completes the proof.

An important property of the example - which helps show why it is not a proof by contradiction - is that the example does not depend on any assumption that every statement is true or false, with no other option. We never needed to say "well, this is false, so its negation is true". Instead, to prove that the implication was true, we simply assumed its hypothesis was true, and proved that its conclusion must also be true. The proof would go through in any system that has the property that some statements are true, and in which modus ponens preserves truth.

There is nothing dubious about a proof by contradiction if you are trying to prove the non-existence of some object, for example "There is no bijection from $\mathbb N$ to $\mathbb R$". Assume there exists such a bijection; derive a contradiction; and you have established the result, even for the strictest of constructivists.

It is only if you are trying to prove the existence of some object that a proof by contradiction is less satisfactory than a constructive proof.