Relativized Definitions as a Method to Sidestep the Löbian Obstacle

homotowat

Relativized Definitions as a Method to Sidestep the Löbian Obstacle

post by homotowat · 2022-02-27T06:37:00.199Z · LW · GW · 4 comments

The goal of this post is to outline a loophole of sorts in Gödel's Second Incompleteness (GSI) theorem (and of Löb's theorem by corollary) and give a somewhat sketchy description for how it might be exploited.

I'll begin by describing the loophole. Essentially, it's merely the observation that Second Incompleteness is a syntactic property rather than a semantic one. Assume that is a provability predicate which is subject to GSI. GSI does not prohibit the existence of a predicate $Bew 2$ not subject to GSI such that $[[Bew]] = [[Bew 2]]$ , where $[[P]]$ is the set corresponding to the predicate $P$ in the standard semantics. That is to say, it's possible for two predicates to be the same, semantically, while one is subject to GSI and the other is not. Explicitly constructing an example is not hard, take the following definition for example;

$Bew 2 (X) := Bew (X) \land X \neq “ ⊥ ”$

Meta-theoretically, we know that ⊥ is not provable, and so can prove in some ambient theory that $Bew 2$ and $Bew$ are, really, the same predicate. Internal to PA, or some similar system, however, GSI holds for $Bew$ but fails rather trivially for $Bew 2$ . $Bew 2$ is called a relativized definition, of $Bew$ .

This demonstrates the loophole, but this particular "exploitation" of it is obviously not very satisfying. Ideally we'd not have to rely on meta-theoretic reasoning to justify the alternative definition. Of course, there are limitations to what we can do. If GSI holds for one definition and not the other then we cannot prove a material equivalence between the two without causing an inconsistency. Instead, we need a weaker notion of internal equivalence. Specifically, we can use the following conditions;

If $P (X) \to Q (X)$ then $P$ is at most $Q$ .
If $Φ [Q]$ is a definition for $Q$ , and $Φ [P]$ holds, then $P$ is at least $Q$ .

If both 1. and 2. hold then we've internally demonstrated that $P$ and $Q$ are semantically equivalent. Though both conditions are syntactically weaker than material equivalence, so we can't use it for the same purposes in general. They are, however, sufficient to treat $P$ as if it were $Q$ for many purposes.

To demonstrate these conditions, I want to switch to a weaker system for a bit. Robinson's Q is basically just PA without induction. This prevents us from directly proving almost any interesting theorem. We can't, for example, directly prove that addition is associative. We can, however, do the following.

Firstly, we can observe the following definition of the natural numbers;

$N (0) \land (\forall x . N (x) \to N (s (x)))$

Next, consider the following definition;

$N_{a} (X) := N (X) \land \forall y z . y + (z + X) = (y + z) + X$

We can prove that;

$N_{a} (X) \to N (X)$
$N_{a} (0) \land (\forall x . N_{a} (x) \to N_{a} (s (x)))$

1. is trivial. 2. relies on the definition of addition used in Robinson's Q;

$X + 0 = X$
$X + s (Y) = s (X + Y)$

but is ultimately fairly straightforward. 1. and 2. are special cases of our previous conditions for internally verifying the semantic equivalence between two predicates; so we've essentially just demonstrated that $N$ and $N_{a}$ are, really, the same predicate. We can also prove, rather easily, that

$\forall x y z . N_{a} (z) \to x + (y + z) = (x + y) + z$

giving us, not a proof of associativity exactly, but a relativized proof of it. This particular technique was heavily emphasized in Predicative Arithmetic by Edward Nelson which is all about doing mathematics in Robinson's Q and it's where I learned this technique from. That book goes on to prove that we can relativize the definition of $N$ so that the totality of and all the standard algebraic properties of addition and multiplication are relativizable. Near the end, it proves that one can't relativize the definition of $N$ so that the totality of exponentiation relativizes. However, there's a different, rather enlightening, construction not considered in that book which at least gives us closure, though not full totality.

Assume $N_{m}$ is a predicate defining numbers which are closed under multiplication. In other words, we know that;

$N_{m} (0)$
$\forall x . N_{m} (x) \to N_{m} (s (x))$
$\forall x y . N_{m} (x) \land N_{m} (y) \to N_{m} (x \times y)$

Now observe that exponentiation, as a ternary relation, can be defined with;

$(\forall x . ↑ (x, 0, 1)) \land (\forall x y z . ↑ (x, y, z) \to ↑ (x, s (y), x \times z))$

Define a new ternary relation;

$↑_{2} (x, y, z) := ↑ (x, y, z) \land (N_{m} (x) \to N_{m} (z))$

We can observe that;

$\forall x y z . ↑_{2} (x, y, z) \to ↑ (x, y, z)$
$(\forall x . ↑_{2} (x, 0, 1)) \land (\forall x y z . ↑_{2} (x, y, z) \to ↑_{2} (x, s (y), x \times z))$
$\forall x y z . N_{m} (x) \land N_{m} (y) \land ↑_{2} (x, y, z) \to N_{m} (z)$

All of these are fairly easy to prove. This demonstrates that $↑$ and $↑_{2}$ are, really, the same predicate, and further that $N_{m}$ is closed under exponentiation using the $↑_{2}$ definition.

One more example before going back to PA.

Fix a binary predicate which I'll suggestively call $\in$ . I will not make any additional assumptions about $\in$ .

Next, consider the following predicate;

$N_{i} (X) := N (X) \land \forall p . \in (p, 0) \to (\forall n . \in (p, n) \to \in (p, s (n))) \to \in (p, X)$

we can easily prove

$N_{i} (X) \to N (X)$
$N_{i} (0) \land (\forall x . N_{i} (x) \to N_{i} (s (x)))$

demonstrating that $N_{i}$ , which effectively relativizes induction over $\in$ in Robinson's Q, is semantically the same predicate as $N_{i}$ . Furthermore, we can easily prove that;

$\forall p . \in (p, 0) \to (\forall n . \in (p, n) \to \in (p, s (n))) \to \forall n . N_{i} (n) \to \in (p, n)$

If we were working in a system with proper second-order quantification, I would say that induction, period, relativizes, but in a purely first-order system we are stuck with a fixed, but arbitrary, binary predicate.

Back to PA, you can hopefully see where we're going. I want to sketch out a proof that transfinite induction up to $ε_{0}$ relativizes in PA, and further sketch how to get a relativizing proof predicate not subject to GSI. I've not formalized this, so there may be some technical errors ahead, but I wanted to get some feedback before dedicating the effort to perfecting what's beyond this point.

Firstly, we can observe the following definition of cantor-normal form ordinals and their ordering relation

$ε_{0} (0) \land (\forall x y . ε_{0} (x) \land ε_{0} (y) \land (fst (y) < x \lor fst (y) = x) \to ε_{0} (ω^{x} + y))$

where

$fst (0) = 0 \land \forall x y . fst (ω^{x} + y) = x$

and

$\forall x y . 0 < ω^{x} + y$
$\forall x y z . x < z \to ω^{x} + y < ω^{z} + w$
$\forall x y z w . x = z \to y < w \to ω^{x} + y < ω^{z} + w$

we can't directly relativize transfinite induction. Instead, we relativize structural induction over cantor normal form terms;

$ε_{0}^{'} (X) := ε_{0} (X) \land \forall p . \in (p, 0) \to (\forall x y . \in (p, x) \to \in (p, y) \to fst (y) \leq x \to \in (p, ω^{x} + y)) \to \in (p, X)$

I don't think we need to relativize the ordering relation, but I'm not certain, so I'll leave it as a possibility here.

We can easily prove;

$ε_{0}^{'} (x) \to ε_{0} (x)$
$ε_{0}^{'} (0) \land (\forall x y . ε_{0}^{'} (x) \land ε_{0}^{'} (y) \land (fst (y) < x \lor fst (y) = x) \to ε_{0}^{'} (ω^{x} + y))$

demonstrating that $ε_{0}$ and $ε_{0}^{'}$ are, really, the same predicate. We can also easily prove structural induction;

$\forall p . \in (p, 0) \to (\forall x y . \in (p, x) \to \in (p, y) \to fst (y) \leq x \to \in (p, ω^{x} + y)) \to \forall x . ε_{0}^{'} (x) \to \in (p, x)$

and from this we can prove transfinite induction;

$\forall p . \in (p, 0) \to (\forall o . (\forall e . e < o \to \in (p, e)) \to \in (p, o)) \to \forall x . ε_{0}^{'} (x) \to \in (p, x)$

this derivation is not so easy, but I don't think it's overly hard either. A derivation of transfinite induction from structural induction can be found in lines 76-150 in this Agda file, though, that derivation relies on a somewhat sophisticated mutual induction-recursion gadget that I've never seen formalized in PA, but I don't think it will be a problem. There are also other derivations out there, but this is the simplest presentation I know of.

Once we have this, we should be able to internally reproduce a proof by transfinite induction that PA is consistent. Essentially, we'd have a function, $O$ which assigns a proof term an element of $ε_{0}$ . We'd then, assuming we already have a proof predicate $Pr (x, y)$ , where y is an encoding for a proof of x, relativize Pr with

${Pr}^{'} (x, y) := Pr (x, y) \land ε_{0}^{'} (O (y))$

Proving relativization for this would be quite involved, mostly because of how complicated the proof predicate is. I've tried sketching out a presentation of a proof predicate which is as simple as possible, coming up with the following based on Krivine realizability;

$PrC (Δ, Γ, var (a), A) \leftarrow (a, A) \in Γ$
$PrC (Δ, Γ, λ a . M, A \to B) \leftarrow PrC (Δ, (a, A) :: Γ, M, B)$
$PrC (Δ, Γ, M @ N, B) \leftarrow \exists A . PrC (Δ, Γ, N, A) \land PrC (Δ, Γ, M, A \to B)$
$PrC (Δ, Γ, ⋆, ⊤)$
$PrC (Δ, Γ, (M, N), A \land B) \leftarrow PrC (Δ, Γ, M, A) \land PrC (Δ, Γ, N, B)$
$PrC (Δ, Γ, {proj}_{1} (P), A) \leftarrow \exists B . PrC (Δ, Γ, P, A \land B)$
$PrC (Δ, Γ, {proj}_{2} (P), B) \leftarrow \exists A . PrC (Δ, Γ, P, A \land B)$
$PrC (Δ, Γ, [α] M, ⊥) \leftarrow \exists A . (α, A) \in Δ \land PrC (Δ, Γ, M, A)$
$PrC (Δ, Γ, μ α . M, A) \leftarrow PrC ((α, A) :: Δ, Γ, M, ⊥)$
$PrC (Δ, Γ, Λ z . M, \forall x . A) \leftarrow fresh y . PrC (Δ, Γ, M [var (y) / z], A [var (y) / x])$
$PrC (Δ, Γ, M {t}, A [t / x]) \leftarrow PrC (Δ, Γ, M, \forall x . A) PrC (Δ, Γ, refl, a = a)$
$PrC (Δ, Γ, sym (f), a = b) \leftarrow PrC (Δ, Γ, f, b = a)$
$PrC (Δ, Γ, trans (f, g), a = c) \leftarrow \exists b . PrC (Δ, Γ, f, a = b) \land PrC (Δ, Γ, g, b = c)$
$PrC (Δ, Γ, sapp (p), s (a) = s (b)) \leftarrow PrC (Δ, Γ, p, a = b)$
$PrC (Δ, Γ, sinj (p), a = b) \leftarrow PrC (Δ, Γ, p, s (a) = s (b))$
$PrC (Δ, Γ, con (p), ⊥) \leftarrow \exists n . PrC (Δ, Γ, p, z = s (n))$
$PrC (Δ, Γ, add0, x + 0 = x)$
$PrC (Δ, Γ, adds, x + s (y) = s (x + y))$
$PrC (Δ, Γ, mul0, x \times 0 = 0) .$
$PrC (Δ, Γ, muls, x \times s (y) = x + (x \times y))$
$PrC (Δ, Γ, ind (p z, p s), \forall x . P) \leftarrow PrC (Δ, Γ, p z, P [0 / x]) \land PrC (Δ, Γ, p s, \forall n . P [n / x] \to P [s (n) / x])$

Note that quotations are left implicit for the sake of succinctness. I've also not checked that this is completely correct, but it's 95% of the way there at least. Enough for demonstration purposes. As you can see, it's quite a beast. Thinking back to the relativized definition from the beginning, attempting something similar with this predicate would result in;

${PrC}^{'} (Δ, Γ, a, A) := PrC (Δ, Γ, a, A) \land (Δ = \emptyset \land Γ = \emptyset \to A \neq⊥)$

Why can't we prove that this relativizes? Most clauses actually are provable since either the conclusion is syntactically not ⊥ or the contexts are assumed to be nonempty. One of the exceptions is

$PrC (Δ, Γ, con (p), ⊥) \leftarrow \exists n . PrC (Δ, Γ, p, 0 = s (n)) .$

to prove this clause we need to prove that z = s(n) isn't derivable in the empty context for any n, which is as hard as proving consistency in the first place. So we ultimately get nowhere. However, if we do our ordinal relativization;

${PrC}^{'} (Δ, Γ, a, A) := PrC (Δ, Γ, a, A) \land ε_{0}^{'} (O (a))$

then this should relativize fine for all clauses, as far as I can tell. Finally, we should be able to prove (with an appropriately selected $\in$ ) that

$\neg \exists a . {PrC}^{'} (\emptyset, \emptyset, a, ⊥)$

demonstrating that ${PrC}^{'}$ is not subject to GSI (or Löb's theorem) despite the fact that we can internally verify that it's the same predicate as $PrC$ .

Stepping back, what's the ultimate point of all this? Traditional wisdom states that GSI and Löb's theorem puts fundamental limitations on various formal logics preventing them from reasoning about themselves in a useful way. I no longer believe this to be the case. We can, with some cleverness, get these systems to do just that.

I'm not really sure where to go from here, so I hope to get helpful feedback from you readers. I could go through the effort of trying to formalize this completely. I tried doing that but ran into the hell that is doing real mathematics rigorously within PA, so I quit early on. Honestly someone would have to pay me to complete that project. I'd rather try a different system, such as a weak higher-order logic, or a first-order logic where the data are lambda terms or something so one doesn't require Gödel encoding everything. That might be better since it naturally represents programs.

Anyway, thanks for reading. I hope this ends up being useful.

4 comments

Comments sorted by top scores.

comment by Gordon Seidoh Worley (gworley) · 2022-03-01T02:54:39.058Z · LW(p) · GW(p)

Stepping back, what's the ultimate point of all this? Traditional wisdom states that GSI and Löb's theorem puts fundamental limitations on various formal logics preventing them from reasoning about themselves in a useful way. I no longer believe this to be the case. We can, with some cleverness, get these systems to do just that.

Taking the outside view (the traditional wisdom), I'd expect it more likely there's some mistake here I'm not adept enough to identify or that it doesn't actually grant you as much as you think it does. So I guess the question would be what the case is that others missed this and that you've discovered something novel?

(Note: asking this question in the spirit of starting a conversation. I didn't have time to follow the math closely enough and I've been out of this sort of math for long enough that I don't have a very informed opinion of what's going on here, so this is mostly about poking to see what you think about this makes it different and exciting and likely to be useful.)

Replies from: homotowat

↑ comment by homotowat · 2022-03-01T07:37:22.868Z · LW(p) · GW(p)

I do worry that there's some technical subtlety not obvious until the end game that makes this particular construction impossible. I've been trying to spot some places where something might go wrong, and there are a few parts I don't know how to fill in. I think there might be a problem relativizing a proof of the totality of ordinal multiplication which may prevent either the proof predicate relativization or the transfinite induction derivation from working. Or there may be some more subtle reason the steps I outlined won't work. I was hoping that someone in the community might be able to say "I've seen this before, and it didn't work because of XYZ", but that hasn't happened yet, which means I'll probably have to attempt to formalize the whole argument to get a definitive answer, which I'm not confident is worth the effort.

Regardless, I don't think my idea relies on this specific construct. The example from the beginning of the post that I find unsatisfying already sidesteps lob's theorem, and just because I'm unsatisfied with it doesn't mean it, or something equally as simple, isn't useful to someone. Even if there's a mistake here, I think the broad idea has legs.

comment by tailcalled · 2022-02-27T17:43:46.368Z · LW(p) · GW(p)

The end of this post got too advanced for me to quickly understand. But near the beginning you say:

1. and 2. are special cases of our previous conditions for internally verifying the semantic equivalence between two predicates; so we've essentially just demonstrated that and $N_{a}$ are, really, the same predicate.

Which seems just false; that requires induction, which Robinson's Q doesn't have.

Replies from: homotowat

↑ comment by homotowat · 2022-02-27T23:08:06.578Z · LW(p) · GW(p)

I think you've misunderstood what I was saying. I am not claiming that we can prove a material equivalence, an internal formal equivalence, between N and Na; that would require induction. The only things which that statement claimed were being formally proved within Q were 1. and 2. Neither of those statements require induction. 1. allows us to treat Na as, at most, N. 2. allows us to treat Na as, at least, N. Both together allow us to treat Na as N (within limits). Only 1. and 2. are internal, there are no other formal statements. That 1. and 2. are sufficient for demonstrating that N and Na are semantically the same is a metatheoretic observation which I think is intuitively obvious.

The point is that we can see, through internal theorems, that N and Na are the same, not with a material equivalence, but with some weaker conditions. This justifies treating Na as an alternative definition of N, one which we can use to formally prove more than we could with N. This is a different perspective than is usually taken with formal mathematics where there's often considered only one definition, but incompleteness opens the possibility for formally distinct, semantically equivalent definitions. I think that's exploitable but historically hasn't been exploited much.