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.)
$\begingroup$
$\endgroup$
5
-
$\begingroup$ 0=1 in the zero ring... $\endgroup$– Justin CampbellCommented Dec 10, 2010 at 5:37
-
2$\begingroup$ 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. $\endgroup$– Thierry ZellCommented Dec 10, 2010 at 13:32
-
$\begingroup$ 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. $\endgroup$– JasonCommented Dec 10, 2010 at 15:26
-
$\begingroup$ 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. $\endgroup$– JasonCommented Dec 10, 2010 at 15:32
-
$\begingroup$ @Jason Sure, my parenthetical belongs to Gödel, but Gentzen proved the consistency of PA using transfinite induction. $\endgroup$– David FeldmanCommented Dec 11, 2010 at 3:37
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ 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. $\endgroup$ Commented Dec 10, 2010 at 21:02
-
$\begingroup$ 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. $\endgroup$ Commented Jan 23, 2011 at 15:08
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ @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.) $\endgroup$ Commented Dec 10, 2010 at 15:09
-
5$\begingroup$ @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. $\endgroup$ Commented Dec 10, 2010 at 15:53 -
1$\begingroup$ @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). $\endgroup$ Commented Dec 10, 2010 at 20:50
$\begingroup$
$\endgroup$
5
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
-
$\begingroup$ 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. $\endgroup$– JasonCommented Dec 10, 2010 at 5:41
-
$\begingroup$ 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 $\endgroup$ Commented Dec 10, 2010 at 5:45
-
$\begingroup$ 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".) $\endgroup$ Commented Dec 10, 2010 at 8:28
-
1$\begingroup$ 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? $\endgroup$ Commented Dec 10, 2010 at 13:29
-
$\begingroup$ @Thierry-Zell, I don't think you missed anything, you hit it right on the nose and are absolutely correct. Two apropos comments: If wishes were horses, beggars would ride (en.wikipedia.org/wiki/If_wishes_were_horses,_beggars_would_ride) and GIGO. A proof's conclusions are only based upon and valid for the axiomatic conditions started with and cannot be extrapolated to any other axiomatic system (which is not contained within the starting conditions). $\endgroup$ Commented Dec 10, 2010 at 13:49
$\begingroup$
$\endgroup$
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.