A Loophole for Self-Applicative Soundness

diffractor

A Loophole for Self-Applicative Soundness

post by Diffractor · 2018-06-11T07:57:26.000Z · LW · GW · 4 comments

See comments. This is a rediscovery of a result from the 1980's that allow concluding $ϕ$ from $□_{n} (ϕ)$ via a $O (n)$ -length proof, and even the statement that the theory has no disproof of length $n$ or less has a single $O (n)$ -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.

$⊢ □ ⊥ \to ⊥ \Rightarrow⊢ ⊥$

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 $g (k)$ , $f (k)$ , and $h (k)$ be such that $f (k) \geq g (k) + h (k) + log (k)$ , $E g (k) < h (k)$ , and $log (f (k)) < g (k)$ , asymptotically.

As a specific example, this can be done by $g (k) = k$ , $h (k) = k^{2}$ , and $f (k) = k^{3}$ .

If it takes a constant number of steps to derive a specific proof regardless of $k$ , the number on it will be suppressed for readability. Also, technically, the original proof has $O log (k)$ instead of $log (k)$ , but this change doesn't alter much.

$G (⌈ ψ ⌉, k) := □_{g (k)} ψ (k) \to ⊥$ $⊢ \forall k : ψ (k) \leftrightarrow G (⌈ ψ ⌉, k)$ (Parametric Diagonal Lemma) $⊢ □ \forall k : ψ (k) \leftrightarrow G (⌈ ψ ⌉, k)$ (Bounded Necessitation) $⊢ \forall k : □_{log (k)} (ψ (k) \to G (⌈ ψ ⌉, k))$ (Quantifier Distribution) $⊢ \forall k, a : □_{a} ψ (k) \to □_{a + log (k)} G (⌈ ψ ⌉, k)$ (Implication Distribution) $⊢ \forall k, a, b : □_{a} ψ (k) \to (□_{b} □_{g (k)} ψ (k) \to □_{a + b + log (k)} ⊥)$ (Implication Distribution) Now specialize to a=g(k), b=h(k). Also, $f (k) \geq g (k) + h (k) + log (k)$ for sufficiently large k above $k_{1}$ . $⊢ \forall k > k_{1} : □_{g (k)} ψ (k) \to (□_{h (k)} □_{g (k)} ψ (k) \to □_{f (k)} ⊥)$ $⊢ \forall k, a : □_{a} ψ (k) \to □_{E a} □_{a} ψ (k)$ (Bounded Inner Necessitation) Now, Specializing to a=g(k), we get $⊢ \forall k : □_{g (k)} ψ (k) \to □_{E g (k)} □_{g (k)} ψ (k)$ Now, since $E g (k) < h (k)$ after some time $k_{2}$ , $⊢ \forall k > k_{2} : □_{g (k)} ψ (k) \to □_{f (k)} ⊥$ Pick a specific value of k, $k^{'}$ , which is sufficiently large. $⊢ □_{g (k^{'})} ψ (k^{'}) \to □_{f (k^{'})} ⊥$ By the soundness schema, $□_{f (k^{'})} ⊥ \to ⊥$ . The length of this proof isn't constant, because $f (k^{'})$ might be really big, so then it'd take about $log (f (k^{'}))$ characters to write down the single application of the soundness schema. $⊢_{log (f (k^{'}))} □_{g (k^{'})} ψ (k^{'}) \to ⊥$ $⊢_{log (f (k^{'}))} ψ (k^{'})$ (By the definition of $ψ (k^{'})$ ) $⊢_{E log (f (k^{'}))} □_{log (f (k^{'}))} ψ (k^{'})$ $log (f (k)) < g (k)$ eventually. Since $k^{'}$ was previously selected to be sufficiently big, $⊢_{E log (f (k^{'}))} □_{g (k^{'})} ψ (k^{'})$ Now we no longer care about $log (f (k^{'}))$ 's size, because $k^{'}$ 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 $g (k)$ , 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 $□_{n} ϕ \to ϕ$ can only ever be proved by a proof of $n$ 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 $□_{n} ϕ \to □_{n - 1} ϕ$ for each individual $n$ and $ϕ$ seperately, but I'm not entirely sure of that.~~ EDIT: Doesn't work, see comments.

Regardless, assume that any proof of $□_{n} ϕ \to ϕ$ via iterated soundness axioms will always take $c$ or more steps. EDIT: You don't need to assume this, there's an explicit $O (n)$ proof of that statement.

Then, if we go through the proof again, something interesting happens. Instead of $log (f (k))$ making its way to the length of the proof, we get $f (k)$ (or more). $f (k) \geq g (k)$ in order to get an earlier step of the proof to go through, but then the resulting proof of $ψ (k)$ takes at least $f (k)$ steps to work, so that proof cannot be used with the definition of $ψ (k)$ 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 $n$ -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, $□_{n} ϕ$ . 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.

4 comments

Comments sorted by top scores.

comment by SamEisenstat · 2018-06-12T08:47:23.000Z · LW(p) · GW(p)

As you say, this isn't a proof, but it wouldn't be too surprising if this were consistent. There is some $k \in N$ such that $□_{n} ϕ \to ϕ$ has a proof of length $n^{k}$ by a result of Pavel Pudlák (On the length of proofs of finitistic consistency statements in first order theories). Here I'm making the dependence on $n$ explicit, but not the dependence on $ϕ$ . I haven't looked at it closely, but the proof strategy in Theorems 5.4 and 5.5 suggests that $k$ will not depend on $ϕ$ , as long as we only ask for the weaker property that $□_{n} ϕ \to ϕ$ will only be provable in length $n^{k}$ for sentences $ϕ$ of length at most $k$ .

Replies from: Diffractor

↑ comment by Diffractor · 2018-06-11T15:01:10.000Z · LW(p) · GW(p)

I found an improved version by Pavel, that gives a way to construct a proof of $ϕ$ from $□_{n} ϕ$ that has a length of $O (n)$ . The improved version is here.

There are restrictions to this result, though. One is that the C-rule must apply to the logic. This is just the ability to go from $\exists x : ϕ (x)$ to instantiating a $c$ such that $ϕ (c)$ . Pretty much all reasonable theorem provers have this.

The second restriction is that the theory must be finitely axiomatizable. No axiom schemas allowed. Again, this isn't much of a restriction in practice, because NBG set theory, which proves the consistency of ZFC, is finitely axiomatizable.

The proof strategy is basically as follows. It's shown that the shortest proof of a statement with quantifier depth n must have a length of $Ω (n^{2})$ , if the maximum quantifier depth in the proof is $2 n$ or greater.

This can be flipped around to conclude that if there's a length-n proof of $ϕ$ , the maximum quantifier depth in the proof can be at most $O (\sqrt{n})$ .

The second part of the proof involves constructing a bounded-quantifier version of a truth predicate. By Tarski's undefinability of truth, a full truth predicate cannot be constructed, but it's possible to exhibit a formula for which it's provable that $q d (¯ ¯¯ ¯ ψ) \leq n \to (S a t_{n} (¯ ¯¯ ¯ ψ, x) \leftrightarrow Σ (S a t_{n}, ¯ ¯¯ ¯ ψ, x))$ ( $Σ$ is the formula laying out Tarski's conditions for something to be a truth predicate). Also, if $n \geq$ quantifier depth of $ψ$ , there's a proof of $S a t_{n} (¯ ¯¯ ¯ ψ, x) \leftrightarrow ψ [x]$ ( $ψ [x]$ is the sentence $ψ$ with its free variables substituted for the elements enumerated in the list $x$ ) Also, there's a proof that $S a t_{n}$ is preserved under inference rules and logical axioms, as long as everything stays below a quantifier depth of $n$ .

All these proofs can be done in $O (n^{2})$ lines. One factor of $n$ comes from the formula abbreviated as $S a t_{n} (x, y)$ getting longer at a linear rate, and the other factor comes from having to prove $S a t_{n}$ for each $n$ seperately as an ingredient for the next proof.

Combining the two parts, the $O (\sqrt{n})$ bound on the quantifier depth and the $O (n^{2})$ bound on how long it takes to prove stuff about the truth predicate, make it take $O (n)$ steps to prove all the relevant theorems about a sufficiently large bounded quantifier depth truth predicate, and then you can just go "the statement that we are claiming to have been proved must have $S a t_{n}$ apply to it, and we've proved this is equivalent to the statement itself"

As a further bonus, a single $O (n)$ -length proof can establish the consistency of the theory itself for all $n$ -length proofs.

It seems like a useful project to develop a program that will automatically write a proof of this form, to assess whether abstract unpacking of bounded proofs is usable in practice, but it will require digging into a bunch of finicky details of exactly how to encode a math theory inside itself.

comment by Diffractor · 2018-06-04T22:25:12.000Z · LW(p) · GW(p)

Caught a flaw with this proposal in the currently stated form, though it is probably patchable.

When unpacking a proof, at some point the sentence $□_{1} ϕ$ will be reached as a conclusion, which is a false statement.

Replies from: SamEisenstat

↑ comment by SamEisenstat · 2018-06-05T20:46:31.000Z · LW(p) · GW(p)

I misunderstood your proposal, but you don't need to do this work to get what you want. You can just take each sentence $□_{n} ϕ \to ϕ$ as an axiom, but declare that this axiom takes $n$ symbols to invoke. This could be done by changing the notion of length of a proof, or by taking axioms $ψ_{ϕ, n} \to (□_{n} ϕ \to ϕ)$ and $ψ_{ϕ, n}$ with $ψ_{ϕ, n}$ very long.