Welcome to MathOverflow

Question

5

3

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

asked Dec 10 2010 at 5:13

Jason

community wiki

0=1 in the zero ring... – Justin Campbell Dec 10 2010 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 2010 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 2010 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 2010 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 2010 at 3:37

David Harris · Accepted Answer · 2010-12-10 13:10:30Z UTC

5

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.

answered Dec 10 2010 at 13:10

David Harris

community wiki

	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 2010 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 2011 at 15:08

David Feldman · Answer 2 · 2010-12-10 07:20:07Z UTC

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.

Gerhard Paseman · Answer 3 · 2010-12-10 05:21:50Z UTC

1

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

answered Dec 10 2010 at 5:21

Gerhard Paseman
811●1●5●5

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 2010 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 2010 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 2010 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 2010 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 2010 at 13:29

show 1 more comment

none · Answer 4 · 2011-01-23 09:16:14Z UTC

0

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

answered Jan 23 2011 at 9:16

none

community wiki

Zero-knowledge proof that 0 = 1

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

4 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.