Logical Inductors that trust their limits

[Scott Garrabrant]

Here is another open question related to Logical Inductors. I have not thought about it very long, so it might be easy.

Does there exist a logical inductor $\left\{P_n\right\}$ over PA such that for all $\varphi$:

1. PA proves that $P_{\infty }\left(\varphi \right)$ exists and is in $[0,1]$, and

2. $E_n\left(P_{\infty }\right(\varphi \left)\right){\eqsim }_n{P}_n\left(\varphi \right)$?

---

Note that $P_{\infty }\left(\varphi \right)$ need not be computable so this does not happen by default.

For example, consider the logical inductor described in the paper with the extra condition that if ever the deductive state is discovered to be inconsistent, all probabilities are set to 0 forever. This clause will never be executed, since PA is consistent, but since this clause exists, PA can prove that $P_{\infty }\left(\varphi \right)$ exists. (PA proves that if PA is consistent, the limit exists using the proof in the paper, and if PA is inconsistent, the limit exists and equals 0.)

However, this logical inductor will not satisfy the second property. Consider the sentence $\top$. $P_n\left(\top \right)$ will converge to 1, while $E_n\left(P_{\infty }\right(\top \left)\right)$ will converge to the probability according to $P_{\infty }$ that $PA$ is consistent. (PA proves that if PA is consistent, the limit is 1 using the proof in the paper, and that if PA is inconsistent, the limit is 0.)

If a Logical Inductor with the above property is found, there are many follow up questions you could ask.

Can you make an analogue of the self trust property that works for $P_{\infty }$? Does the above property imply that self trust property?

Is there some simple extra condition that could be added to the definition of a Logical Inductor, that implies everything we could want about beliefs about $P_{\infty }$?

---

A good place to start with this question might be to analyze a logical inductor that in the spirit of the Demski prior adds sentences to the deductive state only if they are propositionally consistent with all previous sentences. This way, PA will prove that the algorithm defines a logical inductor over some consistent propositional theory (even if it does not know if that theory is PA).

[IAFF-User-184]

I still feel like I don’t understand most things in the paper, but I think this construction should work:

Say we start with some deductive sequence $\left\{D_n\right\}$ that is PA-complete. Now redefine the computation of this deductive sequence to include the condition that if ever at some stage $n$ we find that PA is inconsistent (i.e. that $D_n$ is propositionally inconsistent) we continue by computing $\{D_m:m\ge n\}$ according to $D_m=D_{m-1}\cup \left\{{\varphi }_m\right\}$ where ${\varphi }_m$ is the lexicographically-first sentence propositionally consistent with $D_{m-1}$.

Since PA is consistent this deductive process is extensionally identical to the one we had before, but now PA proves that it’s a deductive process: assuming consistency it’s a PA-complete deductive process, and assuming inconsistency it’s over some very arbitrary, but complete and computable, propositional theory. We can now carry out the construction in the paper to get the necessary logical inductor over PA which we denote by $\left\{P_n\right\}$. Here PA proves the convergence of the logical inductor as in the paper.

Fix $\varphi$ and $ϵ>0$, and write $X_n:=P_n\left(\varphi \right)$ and $X:=P_{\infty }\left(\varphi \right)$. We want to say that eventually $|X_n-E_{n}X|<ϵ$, but by self-trust and linearity it’s enough to show that eventually $E_n(|X_n-X|)<ϵ$. This would follow from eventually having $P_n(|X_n-X|\ge ϵ)<ϵ$ (as PA proves that $X_n,X\in [0,1]$ which gives that $|X_n-X|\le 1$)

[edit2: this paragraph is actually false as written, I have a modified proof that works for PA+¬Con(PA), but it suggests that this construction is broken] From the proof that $X_n\to X$ we have that there is some $A\in [N{]}^{<\omega }$ such that PA proves that $|X_n-X|<ϵ$ for $n\notin A$. Define ${\psi }_n$ to be $|X_n-X|<ϵ$. This is an efficiently computable sequence of sentences of which all but finitely many are theorems, so we get that $P_n\left(\neg {\psi }_n\right)\to 0$ (consider starting the inductor at some later point after all the non-theorems have passed) which means that there is some $N$ where $n>N$ implies $P_n\left(\neg {\psi }_n\right)<ϵ$ which proves the result. [edit: some polishing to this paragraph]

Note, this ignores some subtleties with the fact that $X$ could be irrational and therefore not a bona fide Logically Uncertain Variable. These concerns seem beside the point as we can get the necessary behavior by formalizing Logically Uncertain Variables slightly differently in terms of Dedekind cuts or perhaps more appropriate CDFs: Cumulative Distribution Formulae.

[IAFF-User-184]

I initially played around with the idea of freezing the final probability assignments when you find a contradiction, but couldn’t get it to work. The difficulty was that if you assumed the inconsistency of PA you got that the limit was simply the assignment at some future time, but you couldn’t defer to this because the function was not computable according to PA (by the consistency results in the paper). Something along these lines might still work.

As I worked on this approach I noticed a statement that seems both true and interesting which I delayed proving because I wasn’t sure how to get everything else to work. Let $\chi :=Con\left(PA\right)$ then it seems to me that we should have for any deferral function $f\left(n\right)$

$$E_n\left(P_{f\left(n\right)}\right(\varphi \left)|\chi \right){\eqsim }_n{P}_n\left(\varphi \right)$$

The reason why I think it’s true is that conditioning on $\chi$ which is true should only improve our estimate of $P_{f\left(n\right)}\left(\varphi \right)$, but if this estimate is actually improved it will be exploited by some poly-time trader. It would be very interesting if this weren’t the case since then conditioning on a true statement might actually be bad for us, but if it is true we automatically get the same for $\neg \chi$ instead by some simple algebra (we could then say that infinitary consistency and inconsistency are irrelevant for determining probabilities at any computable times).

Edit, Proof: Let $\left\{P_n\right\}$ be constructed as in the paper. Then $PA+Con\left(PA\right)$ proves that $\left\{P_n\right\}$ and $\left\{P_{f\left(n\right)}\right\}$ are logical inductors. We get that

$$E_n\left(P_{f\left(n\right)}\right(\varphi \left)|\chi \right){\eqsim }_n{E}_n\left(P_{\infty }\right(\varphi \left)|\chi \right){\eqsim }_n{E}_n\left(P_n\right(\varphi \left)|\chi \right)$$

Here the final expression can be expanded out as

$$\sum _{k=1}^n\frac{1}{n}{P}_n\left(P_n\right(\varphi )>k/n\wedge \chi )/P_n\left(\chi \right)$$

Fix $ϵ>0$ we can pick $n>1/ϵ$ large enough that $P_n$ believes that $P_n\left(\varphi \right)$ is within an interval of size $ϵ$ with probability at least $1-ϵ$. Then $P_n$ believes that $P_n\left(\varphi \right)>k/n\wedge \chi$ is equivalent to $\perp$ or $\chi$ (depending on whether $k$ is above or below some threshold) with probability at least $1-ϵ$. In both of these cases we get that $P_n\left(P_n\right(\varphi )>k/n\wedge \chi )=P_n\left(P_n\right(\varphi )>k/n)P_n\left(\chi \right)$ (or perhaps some extra epsilons here)

Now we can cancel and get that the expression is eventually within $Cϵ$ (for some $C<10$) of

$$\sum _k\frac{1}{n}{P}_n\left(P_n\right(\varphi )>k/n)=E_n\left(P_n\right(\varphi \left)\right){\eqsim }_n{P}_n\left(\varphi \right)$$