How to ensure that you haven't run into a paradox proving a theorem e.g. by proof by contradiction?

Question

While preparing some lecture notes for next semester and going back to basics (set theory and proof strategies) I came along the following simple question which is about proving theorems in general but exemplified here by the proof by contradiction:

How do you see whether a proof is not only the necessary but also sufficient condition to arive at a "q.e.d"?

As an example let's take the simple example of irrationality of $\sqrt{2}$. Here you suppose that the result will be rational and arrive at a contradiction, so you say it must be irrational because there are only those two possibilities. q.e.d - case closed.

When you look at the Zermelo-Russell paradox you have a similar situation: Two cases which are mutually exclusive: Either $R \in R$ or $R \not \in R$. You then suppose e.g. that $R \in R$ and arrive at a contradiction... but you don't stop there! Otherwise it would not be a paradox! You also test the other case and, again, arrive at a contradiction!

It would not be enough to stop after the first part and arrive at the result that because you arrived at a contradiction it must be the other case, so $R \not \in R$ q.e.d.

So my question is how do you ensure that you can trust your proof and haven't run into another paradox? One possibility where something like this could happen are obviously situations that are self-referencing. But are these the only possibilites? And some proofs are quite long and involved so that even this could slip through, can it not?

Full disclosure: I asked this question on mathoverflow but it got closed (although upvoted!) so I guess it was not sophisticated enough for that forum - yet I am still looking for a satisfying answer...

Answer 1

Your proof is irrelevant -- either the theory you're working in is consistent or it is not. If it is consistent, then you can't derive any antinomies (unless you are actually making invalid arguments).

Whether it is even possible to "know" a theory is consistent is a deep epistemological problem; e.g. see the regress problem. Mathematicians usually settle for proofs relative consistency -- e.g. ZFC can prove that Peano's axioms for the natural numbers are consistent.

That's not quite true: for many things, mathematicians don't even bother to go that far -- e.g. we just accept that our collective experience working with the natural numbers hasn't turned up any antinomies. And even if it did some day, we'd make appropriate adjustments to correct the problem, then continue along.

Answer 2

When you look at the Zermelo-Russell paradox you have a similar situation: Two cases which are mutually exclusive: Either $R \in R$ or $R \not \in R$. You then suppose e.g. that $R \in R$ and arrive at a contradiction... but you don't stop there! Otherwise it would not be a paradox! You also test the other case and, again, arrive at a contradiction!

Suppose that, in your resolution of Russell's Paradox, after you obtained $R\notin R$, you did not go on to obtain $R\in R$. You would still be able to obtain a valid result on generalizing as follows:

1. Suppose $\forall x:[x\in R\iff x\notin x]$

2. By specifying $x=R$ in (1), we have $R\in R\iff R\notin R$

3. Suppose $R\in R$

4. From (2), we obtain $R\notin R$, and the contradiction $R\in R\land R\notin R$

5. By contradiction, we must have $R\notin R$

6. Stopping here, we could nevertheless generalize to obtain

$$\forall r: [\forall x:[x\in r\iff x\notin x] \implies r\notin r]$$

Intuitively, you can see that this will always be true since, vacuously, you will never be able to prove that $\forall x:[x\in R\iff x\notin x]$ for any R. The system works!

Of course, you could also prove

$$\forall r: [\forall x:[x\in r\iff x\notin x] \implies r\in r]$$

But that's OK, too, for the same reason.

So my question is how do you ensure that you can trust your proof and haven't run into another paradox?

You can't be absolutely certain you won't come across some internal inconsistency in whatever system of deduction you are using, but if you stick to the time-tested systems of logic and set theory, it is highly unlikely. As I demonstrate above, even a botched (or partial) resolution of RP is easily handled in ordinary predicate logic.