A Loophole for Self-Applicative Soundnesspost by Diffractor · 2018-06-11T07:57:26.000Z · LW · GW · None comments
See comments. This is a rediscovery of a result from the 1980's that allow concluding from via a -length proof, and even the statement that the theory has no disproof of length or less has a single -length proof. This is not vulnerable to Critch's Bounded Parametric Lob proof, and was created by looking for ways to make it fail.
This result is just an idea developed very recently, and I'd put ~2:1 odds on it having a fatal flaw, but it looks extremely promising if it works out. EDIT: It works. None of the proof theory checks have been done yet, but it does causes both Lob's theorem, and Critch's Bounded Parametric Lob result to fail.
So, to begin with, if a theory thinks it is sound, then it is inconsistent. Proof by Lob's theorem.
Well that didn't work.
What if we give the theory a soundness schema over any proof which is of bounded length? Maybe the "there exists a proof" in the standard provability predicate is causing problems.
Well then Critch's Bounded Parametric Lob comes in to ruin our day. The entire proof will be reproduced below.
Let , , and be such that , , and , asymptotically.
As a specific example, this can be done by , , and .
If it takes a constant number of steps to derive a specific proof regardless of , the number on it will be suppressed for readability. Also, technically, the original proof has instead of , but this change doesn't alter much.
(Parametric Diagonal Lemma) (Bounded Necessitation) (Quantifier Distribution) (Implication Distribution) (Implication Distribution) Now specialize to a=g(k), b=h(k). Also, for sufficiently large k above . (Bounded Inner Necessitation) Now, Specializing to a=g(k), we get Now, since after some time , Pick a specific value of k, , which is sufficiently large. By the soundness schema, . The length of this proof isn't constant, because might be really big, so then it'd take about characters to write down the single application of the soundness schema. (By the definition of ) eventually. Since was previously selected to be sufficiently big, Now we no longer care about 's size, because has been fixed, so
However, not all is lost. If you look carefully at this, you see that the introduction of the soundness scheme lead to a minor proof blowup. Sure, it's not enough of a blowup to surpass , so the proof of still goes through, but this seems like it might be exploitable....
So then the next step is to make sure that can only ever be proved by a proof of steps or more. The agent can conclude its own soundness for bounded proofs, but it may take a while.
I'm pretty sure this is doable by having an axiom schema of the form for each individual and seperately, but I'm not entirely sure of that. EDIT: Doesn't work, see comments.
Regardless, assume that any proof of via iterated soundness axioms will always take or more steps. EDIT: You don't need to assume this, there's an explicit proof of that statement.
Then, if we go through the proof again, something interesting happens. Instead of making its way to the length of the proof, we get (or more). in order to get an earlier step of the proof to go through, but then the resulting proof of takes at least steps to work, so that proof cannot be used with the definition of to conclude .
I'd suspect there's some more subtle argument that can conclude inconsistency, but breaking the proof of Lob's theorem is promising.
What's the use of this, though, if it doesn't shorten proofs?
Well, there's a lot of -length proofs, but the "royal road" of abstractly establishing soundness or consistency would allow concluding the sentence directly without having to embark on an exhaustive search for the original proof.
If you spent a while proving something, and then wrote down the result in your notebook, and forgot about it, then, upon observing the notebook page, you can conclude and, since you can bound how good you are at math, you can establish an upper bound on the length of the proof, . This provides a way to establish without having to reprove the thing from scratch, by just thinking for a while about "Do I trust my own bounded proofs? Yes I do."
This solves the Notebook Problem in Vingean Reflection.
Comments sorted by top scores.