Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
For proof by contradiction there are always only two choices: a statement and its negation. If you assume something and arrive at a contradiction, then you have proved its negation. If you are working in a consistent theory, then that is all you have to do. –  Tim Seguine Jan 24 at 17:54
1  
The working assumption is that ZFC is consistent. Questioning that is relatively pointless due to Gödel's second incompleteness theorem. –  Tim Seguine Jan 24 at 18:05
2  
And your question got closed because this is not research level mathematics. –  Tim Seguine Jan 24 at 18:08
1  
@AsafKaragila Has ZFC been proven to be consistent? –  Dan Christensen Jan 24 at 19:53
1  
Sounds like fun... I guess. Has anyone ever returned from one of these universes? –  Dan Christensen Jan 24 at 21:20

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
The OP's proof is not irrelevant. As you point out, the system is robust enough to handle any known contradictions. Along this line, I have shown that it can handle even what might be called a "partial resolution" of Russell's Paradox. –  Dan Christensen Jan 26 at 15:40
    
When you say "mathematicians don't even bother to...", I believe you are unfairly disparaging them. Consistent with GIT, proofs of consistency are probably a nothing more than a wild-goose chase, the quarry forever eluding us in an infinite regress: Prove system A is consistent using system B, and you must prove system B is consistent in yet another system, and so on. Realistically, the best we can do is to establish a robust set of axioms, taking them as far as we can, and tweaking them as required when intractable problems arise. –  Dan Christensen Jan 26 at 15:46
2  
@Dan: It wasn't meant to be disparaging on mathematicians -- it was trying to express the fact that these foundational issues aren't as important to actual practice as they're sometimes made out to be. I suppose I was unclear that "mathematicians" was referring to the 'average' practice, rather than the totality: certainly some subset of mathematicians do spend some subset of their time delving into foundational and epistemological issues (and that's a good thing). –  Hurkyl Jan 26 at 16:14

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.

share|improve this answer
1  
Here is a formal version this proof written with the aid of my proof checking software at: dcproof.com/PartialRussell.htm BTW, your students may this software useful. Free download at my website dcproof.com –  Dan Christensen Jan 24 at 19:42
    
Thank you, looks promising! –  vonjd Jan 24 at 19:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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