Say we start with some deductive sequence ${D_{n}}$ 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 \geq n}$ according to $D_{m} = D_{m - 1} \cup {ϕ_{m}}$ where $ϕ_{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 ${P_{n}}$ . Here PA proves the convergence of the logical inductor as in the paper.

Fix $ϕ$ and $ϵ > 0$ , and write $X_{n} := P_{n} (ϕ)$ and $X := P_{\infty} (ϕ)$ . 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 | \geq ϵ) < ϵ$ (as PA proves that $X_{n}, X \in [0, 1]$ which gives that $| X_{n} - X | \leq 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]^{< ω}$ such that PA proves that $| X_{n} - X | < ϵ$ for $n \notin A$ . Define $ψ_{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} (\neg ψ_{n}) \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} (\neg ψ_{n}) < ϵ$ 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.

Reply

[-]IAFF-User-1849yΩ220

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 $χ := C o n (P A)$ then it seems to me that we should have for any deferral function $f (n)$

$E_{n} (P_{f (n)} (ϕ) | χ) ≂_{n} P_{n} (ϕ)$

The reason why I think it's true is that conditioning on $χ$ which is true should only improve our estimate of $P_{f (n)} (ϕ)$ , 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 χ$ 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 ${P_{n}}$ be constructed as in the paper. Then $P A + C o n (P A)$ proves that ${P_{n}}$ and ${P_{f (n)}}$ are logical inductors. We get that

$E_{n} (P_{f (n)} (ϕ) | χ) ≂_{n} E_{n} (P_{\infty} (ϕ) | χ) ≂_{n} E_{n} (P_{n} (ϕ) | χ)$

Here the final expression can be expanded out as

$n \sum k = 1 \frac{1}{n} P_{n} (P_{n} (ϕ) > k / n \land χ) / P_{n} (χ)$

Fix $ϵ > 0$ we can pick $n > 1 / ϵ$ large enough that $P_{n}$ believes that $P_{n} (ϕ)$ is within an interval of size $ϵ$ with probability at least $1 - ϵ$ . Then $P_{n}$ believes that $P_{n} (ϕ) > k / n \land χ$ is equivalent to $⊥$ or $χ$ (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} (P_{n} (ϕ) > k / n \land χ) = P_{n} (P_{n} (ϕ) > k / n) P_{n} (χ)$ (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} (P_{n} (ϕ) > k / n) = E_{n} (P_{n} (ϕ)) ≂_{n} P_{n} (ϕ)$

Reply

Moderation Log

LESSWRONG
LW

LESSWRONG
LW

5

Logical Inductors that trust their limits

5

Ω 3

5

Ω 3