Context: Logical Induction is a framework that makes sense of intuitively plausible statements like “the probability that the th digit of is odd is about ”.
People often do this sort of informal reasoning about mathematical conjectures. Like “The Collatz conjecture has been checked up to , and held for all those—updating on this, I increase my likelyhood that the conjecture is true in general”. Logical induction seems to provide, in principle, a set of rules that such updates should follow. How many of these rules are known?
Some example rules that seem very plausible (here all my variables are implicitly natural numbers):
The observation that is true does not decrease the likelyhood of .
Updating on the observations ” for all ”, the probability of goes to as
Do these hold for logical inductors?
Logical induction doesn’t have this property. No alternatives can either.
To make sense of this answer, I recommend reading
https://www.lesswrong.com/posts/3FoMuCLqZggTxoC3S/logical-pinpointing
and
https://www.lesswrong.com/posts/i7oNcHR3ZSnEAM29X/standard-and-nonstandard-numbers
In short, logical induction can’t be sure if its operating in a nonstandard context or not. So suppose that ϕ is true for all standard numbers, but false for some nonstandard number. Logical Induction has no way to know whether it is operating in the standard or non-standard numbers, so assigns a probability strictly between 0 and 1 to it.
Suppose you had an alternate algorithm that didn’t do that. A Turing machine can be formally specified in PA, so we can talk about the output of the algorithm. The concept of limits can be discussed in PA using ∀ϵ∃δ of foundational calculus. (The ϵ and δ actually need to be Natural numbers, but you can encode rational numbers in them with prime factors)
So for every formula ϕ in PA there exists another formula ϕ′ that says that your algorithm assigns probability 1 to ϕ in the limit. (And ϕ′ is computable from ϕ)
Let K be a PA formula with one free variable.K takes in a number a. If a does not encode a PA formula with one free variable, then K is false. If a encodes A, then K=¬(A(a))′. Now consider k an integer encoding K. And consider K(k) .
This is a straightforward modification of godels incompleteness theorem. If you have any procedure that can perfectly distinguish between true and false statements within the structure of PA, then you can make a “this statement is false” and get a contradiction.
Technical Note. I am also assuming that your proposed alternative to logical induction respects negation and implication in the limit. (Ie if limn→∞P(ψ)=1⟺limn→∞P(¬ψ)=0 and ( limn→∞P(ψ)=1 ∧ limn→∞P(ψ⟹ϕ)=1)⟹limn→∞P(ϕ)=1 .)
Some expressions in PA have multiple qualifiers ∀a∃b∀c... Suppose we know that P(ϕ(a))=1 for every particular a. Then by finite combinations of probabilities, P(∀a<N:ϕ(a))=1 and so P(∀a:ϕ(a))=1. As ∃a=¬∀a¬, then it follows that any attempt at logical induction with this property must fail.
EDIT:
I have realized that I was confusing two separate concepts. You can’t have any function from formulas to booleans that has the property ∀x:f(′ϕ(x)′)⟹f(′∀x:ϕ(x)′). and the trivial preservation of logical operations. (definable within a formal first order theory with the same symbols)
However, if you have a process that returns True, False or Maybe, and is never wrong, then you can extend it to another process like this. Take f(ϕ) the first function. If f(ϕ) is True or False, define g(ϕ)=f(ϕ) otherwise, if ϕ=∀x:ψ(x) and ∀x:f(ψ(x)) then g(ϕ)=True. Otherwise Maybe.
You can’t always combine infinite sequences of your own beliefs, but you can combine infinite sequences of beliefs from some weaker system, and each time you do that you move further up the arithmetic hierarchy.
https://en.wikipedia.org/wiki/Arithmetical_hierarchy
As totally computable functions are in Δ0, the limit of a sequence of boolean functions is in Σ2. So as taking a forall over a function makes it a Π the highest you can get while still having
Is Π1. This means that you can have your asymtotic property compared to any Π1 function.
Limits in the rationals add a ∀ϵ>0 to the front, puting them in Π3. Meaning that your asymtotic property holds for all Π3 sets.
What this means is that if you have a computable function px(n)∈[0,1] which tends to 1 as n→∞ if and only if ϕ(x) then you can construct q(n)=∑nx=12−xpx(n) which tends to 1 if and only if ∀x:ϕ(x).
The downside of this approach is that it assigns probability almost 1 to false statements.
The boolean function case is to take a function that searches for an explicit counterexample, and return a probability that tends to one if no counter example has been found yet.
Sorry if these are stupid questions...
The question specified “all my variables are implicitly natural numbers”. Why can’t there be traders that specialize on questions specifically about standard numbers and ignore others? (I assume that the natural numbers are standard numbers, correct?) Also, what’s the connection between nonstandard numbers and your Godel-like proof?
I think it would be fun to find a concrete example… here’s my attempt...
P=”the logical inductor will assign probability <0.5 to P in the limit of infinitely many steps”
ϕ(n) = “the logical inductor will assign probability <0.5 to P after n inference steps”
so P=∀nϕ(n).
Then maybe any individual ϕ(n) will be true, but the algorithm will never assign >0.5 probability to P=∀nϕ(n).
Did I get that right? I’m very out of practice with my self-referential math so I have low confidence. :-P
Your self referential maths is nearly right. Technically the limit is defined as ∃N∀n>N:ϕ(n) as your ∀n:ϕ(n) could fail because ϕ(1) is false, and logical induction only behaves well in the limit.
The paper says that Pn=" the logical inductor will assign probability <0.5 to Pn after n inference steps”
tend to 0.5 as n→∞. But I havn’t yet worked out the infinite case.
You can’t do that because non-standard numbers look really similar to standard numbers from the inside. There is no formula ϕ(x) that is true on all standard numbers, and false on nonstandard numbers.
Suppose you had a logical induction procedure that had the property that after updating on ϕ(1),ϕ(2)... it believed ∀x:ϕ(x).
So suppose you had p1,p2...∈[0,1] with each pn depending only on ϕ(1)..ϕ(n). and pn→1 if ∀x:ϕ(x) else 0 as n→∞. (Produced by your alternative to logical induction, these represent the probability assigned to ∀x:ϕ(x))
Suppose you prove all that in PA. As PA has nonstandard models, the proof also holds in those. But we can pick a ϕ such that ∀x:ϕ(x) is true in the standard model, but false for some nonstandard x. There must exist nonstandard n such that 1−pn is infinitesimal.
Otherwise the formula ∃m:1−pm<1/k would distinguish standard k from nonstandard k. Assigning infinitesimal probability to something that actually happend is a form of bad behaviour that I think can be transported back to the standard domain.
I think that the resulting behaviour is consistent, but results in poor behaviour.
Will post more as I think of it.
Thank you very much!
I guess an argument of this type rules out a lot of reasonable-seeming inference rules—if a computable process can infer “too much” about universal statements from finite bits of evidence, you do this sort of Gödel argument and derive a contradiction. This makes a lot of sense, now that I think about it.