Counterfactual Induction (Lemma 4)

by Diffractor6 min read17th Dec 2019No comments


Ω 2

Crossposted from the AI Alignment Forum. May contain more technical jargon than usual.

Lemma 4:


For notational convenience, we will abuse notation a bit and abbreviate as . This is just turning A from a finite collection of axioms to a sentence, and from there to the set of worlds where that sentence is true. And if , we will abbreviate as . denote arbitrary elements of , and by our previous abuse of notation, is an element of when it appears as a subscript, and otherwise, via the translation from groups of sentences to sets of worlds.

Our axioms of interest are:

1: Unitarity:

2: Subadditivity:

3: Empty Set:

4: Law of Excluded Middle:

5: Sane Conditioning:

6: Monotonicity:

Notice that 6 implies 5. 6 is the powerset analogue of propositional monotonicity (where the precondition is ), and 5 is the powerset analogue of propositional equivalence (where the precondition is ). Also note that 1,4, and 5 imply 3 because by LEM, and by sane conditioning and unitarity.

is the set of all valuations that fulfill properties 1,2,3,4, and 6 (this also gets 5) is the set of all valuations that fulfill properties 1,2, and 3, while ,, are the subsets of that fulfill properties 4, 5, and 6 respectively. .

Also, in some of the sublemmas, we will be working heavily with the powerset lattice . It is the lattice of all subsets of worlds, ordered by set inclusion. Sup in this lattice corresponds to union, inf corresponds to intersection, and given some set , refers to the ideal of all subsets of , and refers to the filter of all supersets of . Thinking of this lattice may help give some geometric intuition to the proofs for the reader, and we will freely move back and forth between the subset view and the lattice view.

The subvaluation property is defined as follows: . A similar definition applies when we're working with sentences rather than sets. This means that the new valuation assigns an equal or lower value to every statement, for all conditionals. The property of being a subvaluation is preserved when the function (which restricts to )is applied, so if , then . Being a subvaluation is also transitive.

Lemmas 5, 6, and 7 will be used in the proof and proved afterwards.

Lemma 5:


For any valuation which applies to sentences that fits the "shortest disproof" property and a few others, there's another valuation which, when translated into a valuation on sentences, is a subvaluation.

Lemma 6:

For any valuation over sets of worlds that fulfills sane conditioning, there is a valuation over sets of worlds which fulfills subset monotonicity, and is a subvaluation.

For Lemma 7, we need to introduce the concept of a frozen set.

is a function which takes a conditional and a valuation , and returns a set of "frozen sets" at or below , defined as the minimum closure of the following two rules:

1: is frozen.

2: If is frozen, and , then and are frozen. Notice that this implies is frozen, since is.

If , then is "totally frozen" (note that this refers to in the role of a conditional, not as a statement within the lattice). If this holds for all , then is "totally frozen". The set of these valuations is denoted as .

Lemma 7:

For all , if isn't totally frozen, there's a such that: , and, for all which aren't totally frozen,

Proof of Lemma 4:

Select an arbitrary . Now, define a sequence of valuations as follows:

Let be the valuation guaranteed to exist by Lemma 5, so and is a subvaluation of .

For odd , they are the valuation guaranteed to exist by applying Lemma 6 to . They are all subvaluations of , and all lie in the closed set .

For even , if is totally frozen, they are just equal to . Otherwise, is defined to be equal to the valuation produced by repeatedly applying Lemma 7 until a totally frozen set is produced. (this is guaranteed to exist by the finite size of and , and the total number of frozen nodes increasing for every application of Lemma 7.) Note that these valuations all lie in .

If a valuation is totally frozen and fulfills monotonicity, it also fulfills the law of the excluded middle. The proof of this is as follows:

Select an arbitrary with nonzero intersection with , which also isn't a superset of . The set is frozen. By the definition of frozen, this means there is a strict superset of , , which is still a subset of , and a corresponding which is also a subset of . More formally, , and by the definition of when a set freezes. Keep repeating this argument until you eventually hit a set equivalent to itself. . This means that .

Because , and because (by monotonicity and subadditivity respectively), and because implies, which is a violation of subadditivity, this means that and thus that .

Now, because by monotonicity, and the same goes for , we get that .

Now, assume . Then by sane conditioning and empty set. Also, , so by sane conditioning and unitarity, so. A symmetric argument applies when , showing LEM for all sets.

Further, the set of frozen valuations is a closed set. Fixing a Cauchy sequence of valuations, for all of the finitely many , pairs, additivity (not subadditivity!) either holds or doesn't hold on any given timestep. If it doesn't hold for some pair in the limiting valuation, then there is some finite time after which additivity never holds. Thus, there is some finite time after which all violations-of-additivity in the limit are a violation-of-additivity in the corresponding valuation at timestep . Because the limiting distribution has as many or more instances of additivity holding than the timestep valuation, and the timestep valuation is totally frozen, then the limiting distribution must be totally frozen as well.

Now, in the sequence of valuations we just defined, the odd-numbered elements are in the closed set , and the even-numbered elements are all in the closed set . Because it's a sequence of subvaluations, decreases or stays the same with each step, for all and . Due to the fact that we have a monotonically decreasing function with a lower bound for each of the finitely many arguments, this means that we have defined a Cauchy sequence of valuations, so there is a limiting valuation which is a subvaluation of all other ones in the sequence. By splitting the sequence into the even-numbered valuations and the odd-numbered ones, both of which limit to , and applying the closedness of the sets and , we find that and since this implies LEM, we know that this means .

Anyways, since , and it's a subvaluation of the whole sequence, in particular , and the property of being a subvaluation can be transferred through , then , and we already have by Lemma 5 that , then the transitivity of subvaluations implies the desired Lemma 4.

Proof of Lemma 5:

Because , it fulfills subadditivity, unitarity, LEM, and propositional equivalence.

We must then show that there is a which is a subvaluation, and fulfills unitarity, subadditivity, LEM, and sane conditionals. Because unitarity, LEM, and sane conditionals imply the empty set axiom, we can get that .

Let . Although, by propositional equivalence for , if , .By the definition of a subvaluation, is a subvaluation, because for an arbitrary pair,

Also, , so unitarity for is shown by unitarity for .

Given an arbitrary and , let and be some representative for and .

Therefore, by the definition of , , and subadditivity for , we get subadditivity for .

Now to show LEM. Let be a representative for E. Note that is a representative for .

, by LEM for .

Now for sane conditionals. Fix and in the usual way. Assuming , these two statements are propositionally equivalent.

by propositional equivalence for . And we're done!

Proof of Lemma 6:

Our task is to go from an arbitrary which fulfills subadditivity, unitarity, empty set, and sane conditionals to a which is a subvaluation, and fulfills subaddivity, unitarity, empty set, and monotonicity.

Let .

Clearly this is a subvaluation because , so every set can only remain the same or decrease in value.

To prove unitarity, apply sane conditionals and unitarity for to show .

To prove empty set, apply empty set for to show

To prove sane conditionals for , (Not ! Notice the '. We'll need this as an intermediate result), note that if , then , and by sane conditionals for , . Therefore, . is a larger subset of the lattice than , so you'd naively think that minimizing over produces a smaller value, but this outcome is prevented by any minimizing having produce the same value by sane conditioning, and being in . Then,

To prove subset monotonicity, assume that . Since the latter is above the former, this means that , and, by the definition of , and sane conditionals for , that

To prove subadditivity, notice that for all , . (ie, a set having and as subsets also has as a subset, and vice-versa). Fix arbitrary and . and have a minimal-valued element in them, according to , call these minimal-valued elements and . Also, . Now, by the definition of , , and (and similar for and )

Therefore, is a subvaluation of that is in .

Proof of Lemma 7:

By assumption, the distribution is not totally frozen, so there is some set of 's which remain unfrozen.

The task is to show unitarity, subadditivity, empty set, sane conditioning, that is a subvaluation, that for all unfrozen , the number of frozen nodes in strictly increases.

For each unfrozen , and unfrozen , . If is frozen, . Otherwise, the valuation is extended outside of by setting . The is selected for each to be the maximum possible which does not violate a subadditivity constraint when applied. We will show that if is not totally frozen, is positive.

Obviously, unitarity applies because , by unitarity of , and the set being frozen. Similarly, empty set applies because and is frozen. Sane conditioning obviously applies because of how the valuation was extended outside of .

To show subadditivity, we carry out a proof by cases. First, observe that .

In the first case, is unfrozen. Then

And subadditivity is shown. Admittedly, or might be frozen, but taking this into account, the final still applies.

In case 2, is frozen, and By the definition of frozen, and are frozen as well, so none of the valuations change, and the equality is preserved and subadditivity holds.

In case 3, ( is frozen, and Because was selected to be the maximum which did not violate any subadditivity constraints,

In short, while the upper bound on may shrink, while the value itself remains the same, the just leads to a narrowing of the gap. can be as large as 1 and not violate subadditivity in case 1 or 2, but due to (finitely many) instances of case 3 existing in , since it isn't totally frozen, will be positive (due to each being associated with its own that measures the degree of subadditivity), and there only being finitely many of them), and in fact will end up being just big enough to produce a new equality of the form where was frozen, and one of either or was not frozen. However, due to the new equality which was produced, at least one extra frozen node is produced.

Showing that is a subvaluation is trivial, because .


Ω 2