Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose one day I came up with a proof that 0 = 1 in some formal system such as PA or ZFC that cannot prove its own consistency (unless it is inconsistent). Would it be possible to have a zero-knowledge proof of this? In other words, would it be possible for me to convince you with high probability that I had derived such a proof without (feasibly) revealing the proof of the contradiction? (I haven't by the way...found such a contradiction.)

share|improve this question
    
0=1 in the zero ring... –  Justin Campbell Dec 10 '10 at 5:37
2  
Jason: I'm not sure what value there is in your question as is, as it sounds too much like idle speculation. Nonetheless, I think you should remind MO users that downvoting a question without useful feedback goes against MO guidelines and is not particularly helpful. –  Thierry Zell Dec 10 '10 at 13:32
    
As for downvoting, you just did, and I agree. To your other point, I think the value of this question is asking whether if I have a proof of something, can I somehow hide it from you and yet still reveal something to you that would reasonably prove that I had found it? However, the question in its current formulation is not as I had intended, and I'm sorry I posted it like this. In fact, I had accidentally posted it before I had finished thinking about it, and then I mistakenly left it up like this. I really would have to think of a better formulation of this to qualify as a real question. –  Jason Dec 10 '10 at 15:26
    
While I agree with everything said in David Feldman's answer (except I would attribute the first thing he said to Gödel's Second Incompleteness Theorem), I'm not sure how this answers the question. In my humble opinion, David Harris's answer best addresses the question. –  Jason Dec 10 '10 at 15:32
    
@Jason Sure, my parenthetical belongs to Gödel, but Gentzen proved the consistency of PA using transfinite induction. –  David Feldman Dec 11 '10 at 3:37

4 Answers 4

up vote 5 down vote accepted

In this setting, the adversary seeks to find a deduction $\phi_0, \dots, \phi_n$ of $P \wedge \neg P$ quickly. If ZFC, for example, is inconsistent, there exists such a deduction and hence there exists a (constant time) adversary, which simply publishes $\phi$.

In order to have a zero-knowledge proof problem, one needs a family of problems, for which the adversary's task becomes increasingly hard as $n \rightarrow \infty$. With just one theory, such as ZFC, this does not happen.

share|improve this answer
    
But one may view ZFC as one theory among many possible theories that use the same language. One has to work a little because ZFC isn't finitely axiomatizable, but one can isolate a class of theories with easily checkable proofs (this involves recognizing axioms as well valid deductions). One then gets various decision problems, in NP, that ask whether a given theory leads to a "short" contradiction. The length of a hypothetical ZFC contradiction will satisfy any number of bounds in terms of the length of a specification of ZFC, hence various candidates for a zero-knowledge mechanism. –  David Feldman Dec 10 '10 at 21:02
    
Technically, if the length of the proof is, say, 10,000 then both 10,000$^2$ and $2^{10,000}$ are $O(1)$ constants, so the asymptotic analysis doesn't apply and you can't technically say it's a zero-knowledge proof. But in practice, if you need a computation of length $2^{10,000}$ to deduce any information from the proof, it's effectively zero-knowledge. –  Peter Shor Jan 23 '11 at 15:08

Well you're not going to prove 0=1 in PA, because PA is consistent, (though not PA-provably so), following Gentzen. But I digress.

If you proved 0=1 in, say, ZFC, that would simply mean that ZFC was inconsistent - that the entities it purported to describe had no reasonable interpretation and that logical conclusions derived from the axiom had, in general, no bearing on the world. In particular, it would be irrelevant that you had proved P = NP. But I still digress.

My main point: your 0=1 proof is a purely combinatorial object - a symbol sequence that satisfies syntactic constraints that can be checked in polynomial time. The standard Zero-Knowledge Proof technology would apply to this proof just as to any other. The cataclysmic semantics of the proof's conclusion would simply be irrelevant.

Surely if ZFC turns out inconsistent, much of set theory could still be saved by suitably weakening say, the particular axiom whose self-evidence turned out illusory. (Consensus in the short term concerning which axiom to give up might turn out difficult to achieve). At the end of the day, the offending axiom would simply seem overambitious, just as the occasional large cardinal axiom turns out to be a turkey, roadkill on the transfinite superhighway if you will. Most of classical mathematics will still go through intact, and the theory of finite sets, PA essentially, already strong enough to articulate the P=NP conjecture, will remain consistent.

share|improve this answer
    
@David Feldman: mostly a lovely answer, but I’m not sure I follow your first paragraph; to find Gentzen’s proof convincing one has to accept induction over $\epsilon_0$ self-evident, and in that case one surely accepts PA as self-evident, hence consistent, anyway? (Or maybe you were being more tongue-in-cheek there than I realised.) –  Peter LeFanu Lumsdaine Dec 10 '10 at 15:09
5  
@Peter: Although Gentzen used induction over a bigger ordinal ($\varepsilon_0$) than PA does ($\omega$), he uses it for far simpler formulas (essentially quantifier-free) whereas PA uses induction for formulas with arbitrary alternations of quantifiers. So it does not seem absurd to me to regard Gentzen's assumptions as somehow more evident than those incorporated in PA. In effect, Gentzen exhibited a trade-off between the length of the induction and the complexity of the statement to be inductively proved. –  Andreas Blass Dec 10 '10 at 15:53
    
@Peter Exactly, I guess, as tongue-in-cheek as Gentzen and his proof. So, true confession - I've never understood the real world interest in seeking consistency proofs for a system within that system. After all, if you find one, what does it tell you, for real anyway? Well, either it tells that the system is really consistent (provided you believe that the axioms model your metamathematical practice), or that it's really inconsistent (since then system proves everything anyway, including the formal statement of its consistency). –  David Feldman Dec 10 '10 at 20:50

I doubt it. If nothing else, you would have a proof of P=NP as well, and since zero-knowledge proofs depend on the hardness of certain problems, you would "have a proof" that you could not have a zero-knowledge proof.

I suggest rephrasing the question so that it is less likely to be closed. Perhaps something like "Has anyone considered the impact of inconsistent theories on zero knowledge proofs (and published their considerations)?"

Gerhard "Ask Me About System Design" Paseman, 2010.12.09

share|improve this answer
    
But maybe being able to prove P = NP would mean that you could prove that 0 = 1 so that wouldn't be a problem? This question may have answers with paraconsistent logics, but I may be treading on dangerous ground here with the formality of this question especially since this is outside my area. I'm considering deleting it. –  Jason Dec 10 '10 at 5:41
    
Do as you wish. I do think the question can (and should) be improved to something a little more appropriate. Gerhard "Ask Me About System Design" Paseman, 2010.12.09 –  Gerhard Paseman Dec 10 '10 at 5:45
    
I agree there is some value in this question, but I'd feel more comfortable if people more knowledgable in paraconsistent logics edited it. Accordingly, I decided to make this a community wiki. –  Jason Dec 10 '10 at 6:00
    
Well, you could interpret $0 = 1$ in the sense that $0$ is the additive identity and $1$ is the multiplicative identity for $\mathbb{R}$ (and in addition, that the identity element is unique for both addition and multiplication in $\mathbb{R}$). The "problem", of course, is that the additive identity does not have a multiplicative inverse (at least in $\mathbb{R}$). (You would typically call that a "pseudoproblem", but in my mind, that is the "central problem".) –  Jose Arnaldo Dris Dec 10 '10 at 8:28
1  
There is obviously something I'm overlooking here. But: proving that P=NP does not make it true, if the proof exists in an inconsistent axiom system. So Jason would have a "proof" that zero-knowledge proofs don't exist, but could still produce one! Do I have a point, or did I miss something? –  Thierry Zell Dec 10 '10 at 13:29

The [[PCP theorem]] says you can give such an argument for any theorem you have a proof of, not just 0=1. Hmm, maybe it relies on consistency though.

http://en.wikipedia.org/wiki/PCP_theorem

share|improve this answer

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.