Logical inductor limits are dense under pointwise convergence

bySam Eisenstat3y6th Oct 2016No comments


Logical inductors [1] 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 [2], 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 [1]), 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 [1]. 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 [1], we can define analogous to (5.3.2) in [1]. This is an -strategy by an extension of the argument in [1] 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 [1], 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