4

Formal Proof
Personal Blog

Logical inductors  are very complex objects, and even their limits are hard to get a handle on. In this post, I investigate the topological properties of the set of all limits of logical inductors.

I’ll use the language of universal inductors , but everything I say will also hold for general logical inductors by conditioning. Also, the proofs can be made to apply directly to general logical inductors with relatively few changes.

Universal inductors are measures on Cantor space (i.e. the space of infinite bit-strings) at every finite time, as well as in the limit (this is a bit nicer than the analogous situation for general logical inductors, which are measures on the space of completions of a theory only in the limit). There are many topologies on spaces of measures, and we can ask about topological properties under any of these. Interestingly, the set of universal inductor limits is dense in the topology of weak convergence, but not in the topology of strong convergence (or, a fortiori, the total variation metric topology).

It’s not immediately clear how to interpret this - should we think of the space of measures as being full of universal inductor limits, or should we think of universal inductor limits as being relatively few, with big holes where none exist? A relatively close analogy is the relationship between computable sets (or limit computable sets for a closer analogy) and arbitrary subsets of ; any subset of can be approximated pointwise by limit computable sets (indeed, even by finite sets), but may be impossible to approximate under the norm, i.e. the number of differing bits. Now, on with the proofs!

Theorem 1: The set of limits of universal inductors is dense in the topology of weak convergence on the space of measures .

Proof outline: We need to find a limit of universal inductors in any neighborhood of any measure . That is, for any finite collection of continuous functions, we need a universal inductor that, in the limit, assigns expectations to each such function that is close to the expectation under .

We do this with a modification of the standard universal inductor construction (section 5 of ), adding one additional trader to . This trader can buy and sell shares in events in order to keep these expectations within certain bounds, in a way similar to the Occam traders in the proof of theorem 4.6.4 in . However, we give this trader a much larger budget than the others, allowing its control to be sufficiently tight.

Proof: It suffices to show that for any measure on , any finite set of bounded continuous functions for and any , there is a universal inductor limit such that for all .

It's easier to work with prefixes of bit-strings than continuous functions, so we'll pass to such a description. Consider some . For each world , there is some clopen set such that for all . By compactness, we can pick a finite cover . Letting , we get a disjoint open cover. By construction, for each , there is some such that for all , we have , and we can define a simple function that takes the locally constant value on each set . Then, so we need only control what our universal inductor limit thinks of the clopen sets .

Pass to a single disjoint cover of by clopen sets such that for each and , the set is a union of sets . Further, take such that for all , and pick rational numbers in such that and ; note we can do this since . If we can arrange so that for all , we can conclude as desired.

We now need only find a universal inductor limit such that for all . As mentioned above, we modify by adding a trader. For each , take a sentence that holds exactly on , and define the trader Then, with and as in section 5 of , we can define analogous to (5.3.2) in . This is an -strategy by an extension of the argument in  so, like in the construction of there, we can define a belief sequence and this will not be exploitable by .

Next, we will use the fact that does not exploit to investigate how $\mathrm{Vice}$'s holdings behave over time when trading on the market . As in lemma 5.3.3 in , letting , and , we have that in any world and at any step , so since cannot exploit by construction, cannot as well.

Now, notice that, for fixed , the value is constant by construction as varies within any one set , so, regarding as a measure on the finite -algebra generated by , it makes sense to integrate with respect to that measure. For each , we have that this integral is since for each the two factors are either both positive, both negative, or both zero. This is to say, the value of 's holdings according to the measure given by the numbers is nondecreasing over time. Since for all , we can use our upper bound on to derive a lower bound; if is such that for all and , then for any , say, in ,

We can conclude two things from this, which will finish the argument. First, we get an analogue of lemma 5.3.3 from , from which it follows that is a universal inductor (ignoring minor differences between the definitions of universal and logical inductors; see ). This is since for any of the budgeters defined above, so has its holdings bounded uniformly in and .

Second, defining , we get the desired property that for all . Suppose for contradiction that . Taking with , there is some such that if , then . Then, for all such , it follows that and so in any world , and so 's holdings go to infinity in this world, giving the desired contradiction. By a symmetrical argument, we can't have , so as desired.

One thing I want to note about the above proof is that, to my knowledge, it is the first construction of a logical inductor for which the limiting probability of a particular independent sentence is known.

Theorem 2: The set of universal inductor limits is not dense in the topology of strong convergence of measures or the total variation distance topology on .

Proof: The total variation distance induces a finer topology than the topology of strong convergence, so it suffices to show that this set is not dense under strong convergence. Take any world that is not , and let be a point mass on . The singleton is a measurable set, so it suffices to show that for any universal inductor limit , we have but .

Suppose for contradiction that there was some universal inductor limit for which this failed. By the Lebesgue density theorem, there is some clopen set such that and Then, it is possible to compute from as follows. Each corresponds to some clopen subbase element for the topology on . In order to determin whether , we can improve our estimates of and until we've determined either or . One of these must be the case, and we will eventually determine it since these are both open conditions. Thus, since is , the set is as well, contradicting the hypothesis.

 Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, and Jessica Taylor. 2016. “Logical induction.” arXiv: 1609.03543 [cs.AI].

 Scott Garrabrant. 2016. “Universal inductors.” https://agentfoundations.org/item?id=941.

Formal Proof1
Personal Blog

New Comment