Counterfactual Induction (Lemma 4)

post by Diffractor · 2019-12-17T05:05:15.959Z · LW · GW · 0 comments

Contents

  Lemma 4:
  Notation:
  Lemma 5:
  Lemma 6:
  Lemma 7:
  Proof of Lemma 4:
  Proof of Lemma 5:
  Proof of Lemma 6:
  Proof of Lemma 7:
None
No comments

Lemma 4:

$\forall V\in \Lambda :\exists V\in {\Xi }^{\prime }:t\left(V{)}_A\right(\varphi )\le V_A(\varphi )$

Notation:

For notational convenience, we will abuse notation a bit and abbreviate $f\left(g\right(A\left)\right)$ as $A$. 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 $E\in L$, we will abbreviate $E/P\left(S\right)$ as $\neg E$. $E,F$ denote arbitrary elements of $L$, and by our previous abuse of notation, $A$ is an element of $A$ when it appears as a subscript, and $L$ otherwise, via the translation from groups of sentences to sets of worlds.

Our axioms of interest are:

1: Unitarity: $\forall A:V_A\left(A\right)=1$

2: Subadditivity: $\forall A,E,F:V_A(E\cup F)\le V_A\left(E\right)+V_A\left(F\right)$

3: Empty Set: $\forall A:V_A\left(\varnothing \right)=0$

4: Law of Excluded Middle: $\forall A,E:V_A\left(E\right)+V_A\left(\neg E\right)=1$

5: Sane Conditioning: $\forall A,E:V_A\left(E\right)=V_A(A\cap E)$

6: Monotonicity: $\forall A,E,F:A\cap E\subseteq A\cap F\to V_A\left(E\right)\le V_A\left(F\right)$

Notice that 6 implies 5. 6 is the powerset analogue of propositional monotonicity (where the precondition is $A{⊢}_{pc}\varphi \to \psi$), and 5 is the powerset analogue of propositional equivalence (where the precondition is $A{⊢}_{pc}\varphi \leftrightarrow \psi$). Also note that 1,4, and 5 imply 3 because $V_A\left(\varnothing \right)+V_A\left(P\right(S\left)\right)=1$ by LEM, and $V_A\left(P\right(S\left)\right)=V_A\left(A\right)=1$ by sane conditioning and unitarity.

${\Xi }^{\prime }$ is the set of all valuations that fulfill properties 1,2,3,4, and 6 (this also gets 5) ${\Theta }^{\prime }$ is the set of all valuations that fulfill properties 1,2, and 3, while ${\Theta }_{lem}^{\prime }$,${\Theta }_{cond}^{\prime }$,${\Theta }_{mono}^{\prime }$ are the subsets of ${\Theta }^{\prime }$ that fulfill properties 4, 5, and 6 respectively. ${\Xi }^{\prime }={\Theta }_{lem}^{\prime }\cap {\Theta }_{mono}^{\prime }$.

Also, in some of the sublemmas, we will be working heavily with the powerset lattice $L$. 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 $A$, $A\downarrow$ refers to the ideal of all subsets of $A$, and $A\uparrow$ refers to the filter of all supersets of $A$. 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: $V^{\prime }\le V\leftrightarrow \forall A,E:V_A^{\prime }\left(E\right)\le V_A\left(E\right)$. A similar definition applies when we're working with sentences rather than sets. This means that the new valuation $V^{\prime }$ assigns an equal or lower value to every statement, for all conditionals. The property of being a subvaluation is preserved when the function $t:{\Theta }_{lem}^{\prime }\cap {\Theta }_{cond}^{\prime }\to V$ (which restricts to ${\Xi }^{\prime }\to \Xi$)is applied, so if $V^{\prime }\le V$, then $t\left(V^{\prime }\right)\le t\left(V\right)$. Being a subvaluation is also transitive.

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

Lemma 5:

$\forall V\in \Lambda :\exists V\in {\Theta }_{cond}^{\prime }:t\left(V\right)\le V$.

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:

$\forall V\in {\Theta }_{cond}^{\prime }:\exists V^{\prime }\in {\Theta }_{mono}^{\prime }:V^{\prime }\le V$

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.

$F:{\Theta }^{\prime }\times A\to P(A\downarrow )$ is a function which takes a conditional $A$ and a valuation $V$, and returns a set of "frozen sets" at or below $A$, defined as the minimum closure of the following two rules:

1: $A$ is frozen.

2: If $B\cup C$ is frozen, and $V_A(B\cup C)=V_A\left(B\right)+V_A\left(C\right)$, then $B$ and $C$ are frozen. Notice that this implies $\varnothing$ is frozen, since $A$ is.

If $|F(V,A)|=|A\downarrow |$, then $A$ is "totally frozen" (note that this refers to $A$ in the role of a conditional, not $A$ as a statement within the lattice). If this holds for all $A$, then $V$ is "totally frozen". The set of these valuations is denoted as ${\Theta }_{froz}^{\prime }$.

Lemma 7:

For all $V\in {\Theta }_{cond}^{\prime }$, if $V$ isn't totally frozen, there's a $V^{\prime }\in {\Theta }_{cond}^{\prime }$ such that: $V^{\prime }\le V$, and, for all $A$ which aren't totally frozen, $|F(V,A)|<|F(V^{\prime },A)|$

Proof of Lemma 4:

Select an arbitrary $V\in \Lambda$. Now, define a sequence of valuations $\{V_n{\}}_{n\in N}$ as follows:

Let $V_0$ be the valuation guaranteed to exist by Lemma 5, so $V_0\in {\Theta }_{cond}^{\prime }$ and $t\left(V_0\right)$ is a subvaluation of $V$.

For odd $V_n$, they are the valuation guaranteed to exist by applying Lemma 6 to $V_{n-1}$. They are all subvaluations of $V_{n-1}$, and all lie in the closed set ${\Theta }_{mono}^{\prime }$.

For even $V_n$, if $V_{n-1}$ is totally frozen, they are just equal to $V_{n-1}$. Otherwise, $V_n$ 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 $A$ and $L$, and the total number of frozen nodes increasing for every application of Lemma 7.) Note that these valuations all lie in ${\Theta }_{cond}^{\prime }$.

If a valuation $V$ 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 $E$ with nonzero intersection with $A$, which also isn't a superset of $A$. The set $E\cap A$ is frozen. By the definition of frozen, this means there is a strict superset of $E\cap A$, $E_1$, which is still a subset of $A$, and a corresponding $E_{1\ast }$ which is also a subset of $A$. More formally, $E_1=(E\cap A)\cup E_{1\ast }$, and $V_A(E\cap A)+V_A\left(E_{1\ast }\right)=V_A\left(E_1\right)$ by the definition of when a set freezes. Keep repeating this argument until you eventually hit a set $E_n$ equivalent to $A$ itself. $(E\cap A)\cup {\bigcup }_{1\le i\le n}{E}_{i\ast }=A$. This means that $(\neg E\cap A)\subseteq {\bigcup }_{1\le i\le n}{E}_{i\ast }$.

Because $V_A(E\cap A)+{\sum }_{1\le i\le n}{V}_A\left(E_{i\ast }\right)=V_A\left(E_n\right)=1$, and because $V_A(\neg E\cap A)\le V_A\left({\bigcup }_{1\le i\le n}{E}_{i\ast }\right)\le {\sum }_{1\le i\le n}{V}_A\left(E_{i\ast }\right)$ (by monotonicity and subadditivity respectively), and because $V_A(\neg E\cap A)<{\sum }_{1\le i\le n}{V}_A\left(E_{i\ast }\right)$ implies$V_A(E\cap A)+V_A(\neg E\cap A)<V_A\left(A\right)=1$, which is a violation of subadditivity, this means that $V_A(\neg E\cap A)={\sum }_{1\le i\le n}{V}_A\left(E_{i\ast }\right)$ and thus that $V_A(E\cap A)+V_A(\neg E\cap A)=1$.

Now, because $V_A\left(E\right)=V_A(E\cap A)$ by monotonicity, and the same goes for $V_A\left(\neg E\right)$, we get that $V_A\left(E\right)+V_A\left(\neg E\right)=1$.

Now, assume $E\cap A=\varnothing$. Then $V_A\left(E\right)=V_A(E\cap A)=V_A\left(\varnothing \right)=0$ by sane conditioning and empty set. Also, $\neg E\cap A=A$ , so $V_A\left(\neg E\right)=V_A(\neg E\cap A)=V_A\left(A\right)=1$ by sane conditioning and unitarity, so$V_A\left(E\right)+V_A\left(\neg E\right)=0+1=1$. A symmetric argument applies when $E\cap A=A$, showing LEM for all sets.

Further, the set of frozen valuations ${\Theta }_{froz}^{\prime }$ is a closed set. Fixing a Cauchy sequence of valuations, for all of the finitely many $E$,$F$ pairs, additivity (not subadditivity!) either holds or doesn't hold on any given timestep. If it doesn't hold for some $E,F$ 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 $n$. Because the limiting distribution has as many or more instances of additivity holding than the timestep $n$ valuation, and the timestep $n$ 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 ${\Theta }_{mono}^{\prime }$, and the even-numbered elements are all in the closed set ${\Theta }_{froz}^{\prime }\cap {\Theta }_{cond}^{\prime }$. Because it's a sequence of subvaluations, $V_{n,A}\left(E\right)$ decreases or stays the same with each step, for all $A$ and $E$. 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 $V_{\infty }$ 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 $V_{\infty }$, and applying the closedness of the sets ${\Theta }_{mono}^{\prime }$ and ${\Theta }_{froz}^{\prime }$, we find that $V_{\infty }\in {\Theta }_{mono}^{\prime }\cap {\Theta }_{froz}^{\prime }$ and since this implies LEM, we know that this means $V_{\infty }\in {\Theta }_{mono}^{\prime }\cap {\Theta }_{lem}^{\prime }={\Xi }^{\prime }$.

Anyways, since $V_{\infty }\in {\Xi }^{\prime }$, and it's a subvaluation of the whole sequence, in particular $V_0$, and the property of being a subvaluation can be transferred through $t$, then $t\left(V_{\infty }\right)\le t\left(V_0\right)$, and we already have by Lemma 5 that $t\left(V_0\right)\le V$, then the transitivity of subvaluations implies the desired Lemma 4.

Proof of Lemma 5:

$\forall V\in \Lambda :\exists V\in {\Theta }_{cond}^{\prime }:t\left(V\right)\le V$

Because $V\in \Lambda$, it fulfills subadditivity, unitarity, LEM, and propositional equivalence.

We must then show that there is a $V$ 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 $V\in {\Theta }_{cond}^{\prime }$.

Let $V_A\left(E\right):={min}_{\psi \in f^{-1}\left(E\right)}{V}_A\left(\psi \right)$ . Although, by propositional equivalence for $V$, if $f\left(A\varphi \right)=f\left(\psi \right)$, $V_A\left(\varphi \right)=V_A\left(\psi \right)$.By the definition of a subvaluation, $t\left(V\right)$ is a subvaluation, because for an arbitrary $A,\varphi$ pair,

$t\left(V{)}_A\right(\varphi )=V_A(f\left(\varphi \right))={min}_{\psi \in f^{-1}\left(f\right(\varphi \left)\right)}{V}_A(\psi )=V_A(\varphi )$

Also, $V_A\left(A\right)={min}_{\psi \in f^{-1}\left(A\right)}{V}_A\left(\psi \right)=V_A\left(A\right)=1$, so unitarity for $V$ is shown by unitarity for $V$.

Given an arbitrary $E$ and $F$, let ${\psi }_E$ and ${\psi }_F$ be some representative for $E$ and $F$.

$V_A(E\cup F)={min}_{\psi \in f^{-1}(E\cup F)}{V}_A\left(\psi \right)=V_A({\psi }_E\vee {\psi }_F)\le V_A\left({\psi }_E\right)+V_A\left({\psi }_F\right)=V_A\left(E\right)+V_A\left(F\right)$

Therefore, by the definition of $V$, ${\psi }_E\vee {\psi }_F\in f^{-1}(E\cup F)$, and subadditivity for $V$, we get subadditivity for $V$.

Now to show LEM. Let ${\psi }_E$ be a representative for E. Note that $\neg {\psi }_E$ is a representative for $\neg E$.

$V_A\left(E\right)+V_A\left(\neg E\right)=V_A\left({\psi }_E\right)+V_A\left(\neg {\psi }_E\right)=1$ , by LEM for $V$.

Now for sane conditionals. Fix ${\psi }_E$ and ${\psi }_{E\cap A}$ in the usual way. Assuming $A$, these two statements are propositionally equivalent.

$V_A\left(E\right)=V_A\left({\psi }_E\right)=V_A\left({\psi }_{A\cap E}\right)=V_A(A\cap E)$ by propositional equivalence for $V$. And we're done!

Proof of Lemma 6:

$\forall V\in {\Theta }_{cond}^{\prime }:\exists V^{\prime }\in {\Theta }_{mono}^{\prime }:V^{\prime }\le V$

Our task is to go from an arbitrary $V$ which fulfills subadditivity, unitarity, empty set, and sane conditionals to a $V^{\prime }$ which is a subvaluation, and fulfills subaddivity, unitarity, empty set, and monotonicity.

Let $V_A^{\prime }\left(E\right):={min}_{F\in E\uparrow }{V}_A\left(F\right)$.

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

To prove unitarity, apply sane conditionals and unitarity for $V$ to show $V_A^{\prime }\left(A\right)={min}_{F\in A\uparrow }{V}_A\left(F\right)={min}_{F\in A\uparrow }{V}_A(F\cap A)=V_A\left(A\right)=1$.

To prove empty set, apply empty set for $V$ to show

$V_A^{\prime }\left(\varnothing \right)={min}_{F\in \varnothing \uparrow }{V}_A\left(F\right)\le V_A\left(\varnothing \right)=0$

To prove sane conditionals for $V^{\prime }$, (Not $V$! Notice the '. We'll need this as an intermediate result), note that if $F\in E\uparrow$, then $F\cap A\in (E\cap A)\uparrow$, and by sane conditionals for $V$, $V_A\left(F\right)=V_A(F\cap A)$. Therefore, ${min}_{F\in (E\cap A)\uparrow }{V}_A\left(F\right)={min}_{F\in E\uparrow }{V}_A\left(F\right)$. $E\uparrow$ is a larger subset of the lattice than $(E\cap A)\uparrow$, so you'd naively think that minimizing over $E\uparrow$ produces a smaller value, but this outcome is prevented by any minimizing $F$ having $F\cap A$ produce the same value by sane conditioning, and $F\cap A$ being in $(E\cap A)\uparrow$. Then,

$V_A^{\prime }\left(E\right)={min}_{F\in E\uparrow }{V}_A\left(F\right)={min}_{F\in (E\cap A)\uparrow }{V}_A\left(F\right)=V_A^{\prime }(E\cap A)$

To prove subset monotonicity, assume that $E\cap A\subseteq F\cap A$. Since the latter is above the former, this means that $(F\cap A)\uparrow \subseteq (E\cap A)\uparrow$, and, by the definition of $V^{\prime }$, and sane conditionals for $V^{\prime }$, that

$V_A^{\prime }\left(E\right)=V_A^{\prime }(A\cap E)={min}_{G\in (A\cap E)\uparrow }{V}_A\left(G\right)\le {min}_{G\in (A\cap F)\uparrow }{V}_A\left(G\right)=V_A^{\prime }(A\cap F)=V_A^{\prime }\left(F\right)$

To prove subadditivity, notice that for all $E,F$, $(E\uparrow )\cap (F\uparrow )=(E\cup F)\uparrow$. (ie, a set having $E$ and $F$ as subsets also has $E\cup F$ as a subset, and vice-versa). Fix arbitrary $E$ and $F$. $E\uparrow$ and $F\uparrow$ have a minimal-valued element in them, according to $V_A$, call these minimal-valued elements $G$ and $H$. Also, $G\cup H\in E\uparrow \cap F\uparrow =(E\cup F)\uparrow$. Now, by the definition of $V^{\prime }$, $G\cup H\in (E\cup F)\uparrow$, and $V_A\left(G\right)=V_A^{\prime }\left(E\right)$ (and similar for $H$ and $F$)

$V_A^{\prime }(E\cup F)={min}_{I\in (E\cup F)\uparrow }{V}_A\left(I\right)\le V_A(G\cup H)\le V_A\left(G\right)+V_A\left(H\right)=V_A^{\prime }\left(E\right)+V_A^{\prime }\left(F\right)$

Therefore, $V^{\prime }$ is a subvaluation of $V$ that is in ${\Theta }_{mono}^{\prime }$.

Proof of Lemma 7:

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

The task is to show unitarity, subadditivity, empty set, sane conditioning, that $V^{\prime }$ is a subvaluation, that for all unfrozen $A$, the number of frozen nodes in $A\downarrow$ strictly increases.

For each unfrozen $A$, and unfrozen $E\in A\downarrow$, $V_A^{\prime }\left(E\right):=(1-{ϵ}_A)V_A\left(E\right)$. If $E$ is frozen, $V_A^{\prime }\left(E\right)=V_A\left(E\right)$. Otherwise, the valuation is extended outside of $A\downarrow$ by setting $V_A^{\prime }\left(E\right):=V_A^{\prime }(E\cap A)$. The $ϵ$ is selected for each $A$ to be the maximum possible which does not violate a subadditivity constraint when applied. We will show that if $A$ is not totally frozen, $ϵ$ is positive.

Obviously, unitarity applies because $V_A^{\prime }\left(A\right)=V_A\left(A\right)=1$, by unitarity of $V$, and the set $A$ being frozen. Similarly, empty set applies because $V_A^{\prime }\left(\varnothing \right)=V_A\left(\varnothing \right)=0$ and $\varnothing$ is frozen. Sane conditioning obviously applies because of how the valuation was extended outside of $A\downarrow$.

To show subadditivity, we carry out a proof by cases. First, observe that $V_A^{\prime }(E\cup F)=V_A^{\prime }\left(\right(E\cup F)\cap A)$.

In the first case, $(E\cup F)\cap A$ is unfrozen. Then

$V_A^{\prime }\left(\right(E\cup F)\cap A)=(1-{ϵ}_A)V_A\left(\right(E\cup F)\cap A)\le (1-{ϵ}_A)\left(V_A\right(E\cap A)+V_A(F\cap A\left)\right)\le V_A^{\prime }(E\cap A)+V_A^{\prime }(F\cap A)=V_A^{\prime }\left(E\right)+V_A^{\prime }\left(F\right)$

And subadditivity is shown. Admittedly, $E\cap A$ or $F\cap A$ might be frozen, but taking this into account, the final $\le$ still applies.

In case 2, $(E\cup F)\cap A$ is frozen, and $V_A\left(\right(E\cup F)\cap A)=V_A(E\cap A)+V_A(F\cap A)$ By the definition of frozen, $E\cap A$ and $F\cap A$ are frozen as well, so none of the valuations change, and the equality is preserved and subadditivity holds.

In case 3, ($E\cup F)\cap A$ is frozen, and $V_A\left(\right(E\cup F)\cap A)<V_A(E\cap A)+V_A(F\cap A)$ Because ${ϵ}_A$ was selected to be the maximum $ϵ$ which did not violate any subadditivity constraints,

$V_A^{\prime }(E\cup F)=V_A^{\prime }\left(\right(E\cup F)\cap A)\le (1-ϵ)\left(V_A\right(E\cap A)+V_A(F\cap A\left)\right)\le V_A^{\prime }(E\cap A)+V_A^{\prime }(F\cap A)=V_A^{\prime }\left(E\right)+V_A^{\prime }\left(F\right)$

In short, while the upper bound on $V_A\left(\right(E\cup F)\cap A)$ may shrink, while the value itself remains the same, the $<$ just leads to a narrowing of the gap. ${ϵ}_A$ 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 $V$, since it isn't totally frozen, ${ϵ}_A$ 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 ${ϵ}_A$ will end up being just big enough to produce a new equality of the form $V_A^{\prime }\left(\right(E\cup F)\cap A)=V_A^{\prime }(E\cap A)+V_A^{\prime }(F\cap A)$ where $(E\cup F)\cap A$ was frozen, and one of either $E\cap A$ or $F\cap A$ was not frozen. However, due to the new equality which was produced, at least one extra frozen node is produced.

Showing that $V^{\prime }$ is a subvaluation is trivial, because $V_A^{\prime }\left(E\right)=V_A^{\prime }(E\cap A)\le V_A(E\cap A)=V_A\left(E\right)$.

0 comments

Comments sorted by top scores.