Finite Factored Sets: Orthogonality and Time

post by Scott Garrabrant · 2021-06-10T01:22:34.040Z · LW · GW · 9 comments

Contents

  3.1. Generating a Partition with Factors
  3.2. History
  3.3. Orthogonality
  3.4. Time
None
9 comments

The main way we'll be using factored sets [? · GW] is as a foundation for talking about concepts like orthogonality and time. Finite factored sets will play a role that's analogous to that of directed acyclic graphs in Pearlian causal inference.

To utilize factored sets in this way, we will first want to introduce the concept of generating a partition with factors.

 

3.1. Generating a Partition with Factors

Definition 16 (generating a partition). Given a finite factored set $F=(S,B)$, a partition $X\in Part\left(S\right)$, and a $C\subseteq B$, we say $C$ generates $X$ (in $F$), written $C{⊢}^{F}X$, if ${\chi }_C^F(x,S)=x$ for all $x\in X$.

The following proposition gives many equivalent definitions of ${⊢}^F$.

Proposition 10. Let $F=(S,B)$ be a finite factored set, let $X\in Part\left(S\right)$ be a partition of $S$, and let $C$ be a subset of $B$. The following are equivalent:

1. $C{⊢}^{F}X$.
2. ${\chi }_C^F(x,S)=x$ for all $x\in X$.
3. ${\chi }_C^F(x,S)\subseteq x$ for all $x\in X$.
4. ${\chi }_C^F(x,y)\subseteq x$ for all $x,y\in X$.
5. ${\chi }_C^F(s,t)\in [s{]}_X$ for all $s,t\in S$.
6. ${\chi }_C^F(s,t){\sim }_{X}s$ for all $s,t\in S$.
7. $X{\le }_S{\bigvee }_S\left(C\right)$.

Proof. The equivalence of conditions 1 and 2 is by definition.

The equivalence of conditions 2 and 3 follows directly from the fact that ${\chi }_C^F(s,s)=s$ for all $s\in x$, so ${\chi }_C^F(x,S)\supseteq {\chi }_C^F(x,x)\supseteq x$.

To see that conditions 3 and 4 are equivalent, observe that since $S={\bigcup }_{y\in X}y$, ${\chi }_C^F(x,S)={\bigcup }_{y\in X}{\chi }_C^F(x,y)$. Thus, if ${\chi }_C^F(x,S)\subseteq x$, ${\chi }_C^F(x,y)\subseteq x$ for all $y\in X$, and conversely if ${\chi }_C^F(x,y)\subseteq x$ for all $y\in X$, then ${\chi }_C^F(x,S)\subseteq x$.

To see that condition 3 is equivalent to condition 5, observe that if condition 5 holds, then for all $x\in X$, we have ${\chi }_C^F(s,t)\in [s{]}_X=x$ for all $s\in x$ and  $t\in S$. Thus ${\chi }_C^F(x,S)\subseteq x$. Conversely, if condition 3 holds, ${\chi }_C^F(s,t)\in {\chi }_C^F\left(\right[s{]}_X,S)\subseteq [s{]}_X$ for all $s,t\in S$.

Condition 6 is clearly a trivial restatement of condition 5.

To see that conditions 6 and 7 are equivalent, observe that if condition 6 holds, and $s,t\in S$ satisfy $s{\sim }_{{\bigvee }_S\left(C\right)}t$, then ${\chi }_C^F(s,t)=t$, so $t={\chi }_C^F(s,t){\sim }_{X}s$. Thus $X{\le }_S{\bigvee }_S\left(C\right)$. Conversely, if condition 7 holds, then since ${\chi }_C^F(s,t){\sim }_{{\bigvee }_S\left(C\right)}s$ for all $s,t\in S$, we have ${\chi }_C^F(s,t){\sim }_{X}s$. $\square$

Here are some basic properties of ${⊢}^F$.

Proposition 11. Let $F=(S,B$) be a finite factored set, let $C$ and $D$ be subsets of $B$, and let $X,Y\in Part\left(S\right)$ be partitions of $S$.

1. If $X{\le }_{S}Y$ and $C{⊢}^{F}Y$, then $C{⊢}^{F}X$.
2. If $C{⊢}^{F}X$ and $C{⊢}^{F}Y$, then $C{⊢}^{F}X{\vee }_{S}Y$.
3. $B{⊢}^{F}X$.
4. $\left\{\right\}{⊢}^{F}X$ if and only if $X={\text{Ind}}_S$.
5. If $C\subseteq D$ and $C{⊢}^{F}X$, then $D{⊢}^{F}X$.
6. If $C{⊢}^{F}X$ and $D{⊢}^{F}X$, then $C\cap D{⊢}^{F}X$.

Proof. For the first 5 parts, we will use the equivalent definition from Proposition 10 that $C{⊢}^{F}X$ if and only if $X{\le }_S{\bigvee }_S\left(C\right)$.

Then 1 follows directly from the transitivity of ${\le }_S$.

2 follows directly from the fact that any partition $Z$ satisfies $X{\vee }_{S}Y\le Z$ if and only if $X\le Z$ and $Y\le Z$.

3 follows directly from the fact that ${\bigvee }_S\left(B\right)={\text{Dis}}_S$ by Proposition 3 [LW · GW].

4 follows directly from the fact that ${\bigvee }_S\left(\right\{\left\}\right)={\text{Ind}}_S$, together with the fact that $X{\le }_S{\text{Ind}}_S$ if and only if $X={\text{Ind}}_S$.

5 follows directly from the fact that if $C\subseteq D$, then ${\bigvee }_S\left(C\right)\le {\bigvee }_S\left(D\right)$.

Finally, we need to prove part 6. For this, we will use the equivalent definition from Proposition 10 that $C{⊢}^{F}X$ if and only if ${\chi }_C^F(s,t){\sim }_{X}s$ for all $s,t\in S$. Assume that for all $s,t\in S$, ${\chi }_C^F(s,t){\sim }_{X}s$ and ${\chi }_D^F(s,t){\sim }_{X}s$. Thus, for all $s,t\in S$, ${\chi }_{C\cap D}^F(s,t)={\chi }_C^F\left({\chi }_D^F\right(s,t),t){\sim }_X{\chi }_D^F(s,t){\sim }_{X}s$. Thus $C\cap D{⊢}^{F}X$. $\square$

Our main use of ${⊢}^F$ will be in the definition of the history of a partition.

 

3.2. History

Definition 17 (history of a partition). Given a finite factored set $F=(S,B)$ and a partition $X\in Part\left(S\right)$, let $h^F\left(X\right)$ denote the smallest (according to the subset ordering) subset of $B$ such that $h^F\left(X\right){⊢}^{F}X$.

The history of $X$, then, is the smallest set of factors $C\subseteq B$ such that if you're trying to figure out which part in $X$ any given $s\in S$ is in, it suffices to know what part $s$ is in within each of the factors in $C$. We can informally think of $h^F\left(X\right)$ as the smallest amount of information needed to compute $X$.

Proposition 12. Given a finite factored set $F=(S,B)$, and a partition $X\in Part\left(S\right)$, $h^F\left(X\right)$ is well-defined.

Proof. Fix a finite factored set $F=(S,B)$ and a partition $X\in Part\left(S\right)$, and let $h^F\left(X\right)$ be the intersection of all $C\subseteq B$ such that $C{⊢}^{F}X$. It suffices to show that $h^F\left(X\right){⊢}^{F}X$; then $h^F\left(X\right)$ will clearly be the unique smallest (according to the subset ordering) subset of $B$ such that $h^F\left(X\right){⊢}^{F}X$.

Note that $h^F\left(X\right)$ is a finite intersection, since there are only finitely many subsets of $B$, and that $h^F\left(X\right)$ is an intersection of a nonempty collection of sets since $B{⊢}^{F}X$. Thus, we can express $h^F\left(X\right)$ as a composition of finitely many binary intersections. By part 6 of Proposition 11, the intersection of two subsets that generate $X$ also generates $X$. Thus $h^F\left(X\right){⊢}^{F}X$. $\square$

Here are some basic properties of history.

Proposition 13. Let $F=(S,B)$ be a finite factored set, and let $X,Y\in Part\left(S\right)$ be partitions of $S$.

1. If $X{\le }_{S}Y$, then $h^F\left(X\right)\subseteq h^F\left(Y\right)$.
2. $h^F\left(X{\vee }_{S}Y\right)=h^F\left(X\right)\cup h^F\left(Y\right)$.
3. $h^F\left(X\right)=\left\{\right\}$ if and only if $X={\text{Ind}}_S$.
4. If $S$ is nonempty, then $h^F\left(b\right)=\left\{b\right\}$ for all $b\in B$.

Proof. The first 3 parts are trivial consequences of history's definition and Proposition 11.

For the fourth part, observe that $\left\{b\right\}{⊢}^{F}b$ by condition 7 of Proposition 10. $b$ is nontrivial, and since $S$ is nonempty, $b$ is nonempty. So we have $\neg \left(\right\{\left\}{⊢}^{F}b\right)$ by part 4 of Proposition 11. Thus $\left\{b\right\}$ is the smallest subset of $B$ that generates $b$. $\square$

 

3.3. Orthogonality

We are now ready to define the notion of orthogonality between two partitions of $S$.

Definition 18 (orthogonality). Given a finite factored set $F=(S,B)$ and partitions $X,Y\in Part\left(S\right)$, we say $X$ is orthogonal to $Y$ (in $F$), written $X{\perp }^{F}Y$, if $h^F\left(X\right)\cap h^F\left(Y\right)=\left\{\right\}$.

If $\neg \left(X{\perp }^{F}Y\right)$, we say $X$ is entangled with $Y$ (in $F$).

We could also unpack this definition to not mention history or chimera functions.

Proposition 14. Given a finite factored set $F=(S,B)$, and partitions $X,Y\in Part\left(S\right)$,  $X{\perp }^{F}Y$ if and only if there exists a $C\subseteq B$ such that $X{\le }_S{\bigvee }_S\left(C\right)$ and $Y{\le }_S{\bigvee }_S(B\setminus C)$.

Proof. If there exists a $C\subseteq B$ such that $X{\le }_S{\bigvee }_S\left(C\right)$ and $Y{\le }_S{\bigvee }_S(B\setminus C)$, then $C{⊢}^{F}X$ and $B\setminus C{⊢}^{F}Y$. Thus, $h^F\left(X\right)\subseteq C$ and $h^F\left(Y\right)\subseteq B\setminus C$, so $h^F\left(X\right)\cap h^F\left(Y\right)=\left\{\right\}$.

Conversely, if $h^F\left(X\right)\cap h^F\left(Y\right)=\left\{\right\}$, let $C=h^F\left(X\right)$. Then $C{⊢}^{F}X$, so $X{\le }_S{\bigvee }_S\left(C\right)$, and $B\setminus C\supseteq h^F\left(Y\right)$, so $B\setminus C{⊢}^{F}Y$, so $Y{\le }_S{\bigvee }_S(B\setminus C)$. $\square$

Here are some basic properties of orthogonality.

Proposition 15. Let $F=(S,B)$ be a finite factored set, and let $X,Y,Z\in Part\left(S\right)$ be partitions of $S$.

1. If $X{\perp }^{F}Y$, then $Y{\perp }^{F}X$.
2. If $X{\perp }^{F}Z$ and $Y{\le }_{S}X$, then $Y{\perp }^{F}Z$.
3. If $X{\perp }^{F}Z$ and $Y{\perp }^{F}Z$, then $\left(X{\vee }_{S}Y\right){\perp }^{F}Z$.
4. $X{\perp }^{F}X$ if and only if $X={\text{Ind}}_S$.

Proof. Part 1 is trivial from the symmetry in the definition. 

Parts 2, 3, and 4 follow directly from Proposition 13. $\square$

 

3.4. Time

Finally, we can define our notion of time in a factored set.

Definition 19 ((strictly) before). Given a finite factored set $F=(S,B)$, and partitions $X,Y\in Part\left(S\right)$, we say $X$ is before $Y$ (in $F$), written $X{\le }^{F}Y$, if $h^F\left(X\right)\subseteq h^F\left(Y\right)$.

We say $X$ is strictly before $Y$ (in $F$), written $X{<}^{F}Y$, if $h^F\left(X\right)\subset h^F\left(Y\right)$.

Again, we could also unpack this definition to not mention history or chimera functions. 

Proposition 16. Given a finite factored set $F=(S,B)$, and partitions $X,Y\in Part\left(S\right)$,  $X{\le }^{F}Y$ if and only if every $C\subseteq B$ satisfying $Y{\le }_S{\bigvee }_S\left(C\right)$ also satisfies $X{\le }_S{\bigvee }_S\left(C\right)$.

Proof. Note that by part 7 of Proposition 10, part 5 of Proposition 11, and the definition of history, $C$ satisfies $Y{\le }_S{\bigvee }_S\left(C\right)$ if and only if $C\supseteq h^F\left(Y\right)$, and similarly for $X$. 

Clearly, if $h^F\left(Y\right)\supseteq h^F\left(X\right)$, every $C\supseteq h^F\left(Y\right)$ satisfies $C\supseteq h^F\left(X\right)$. Conversely, if $h^F\left(X\right)$ is not a subset of $h^F\left(Y\right)$, then we can take $C=h^F\left(Y\right)$, and observe that $C\supseteq h^F\left(Y\right)$ but not $C\supseteq h^F\left(X\right)$. $\square$

Interestingly, we can also define time entirely as a closure property of orthogonality. We hold that the philosophical interpretation of time as a closure property on orthogonality is natural and transcends the ontology set up in this sequence.

Proposition 17. Given a finite factored set $F=(S,B)$, and partitions $X,Y\in Part\left(S\right)$, $X{\le }^{F}Y$ if and only if every $Z\in Part\left(S\right)$ satisfying $Y{\perp }^{F}Z$ also satisfies $X{\perp }^{F}Z$.

Proof. Clearly if $h^F\left(X\right)\subseteq h^F\left(Y\right)$, then every $Z$ satisfying $h^F\left(Y\right)\cap h^F\left(Z\right)=\left\{\right\}$ also satisfies $h^F\left(X\right)\cap h^F\left(Z\right)=\left\{\right\}$.

Conversely, if $h^F\left(X\right)$ is not a subset of $h^F\left(Y\right)$, let $b\in B$ be an element of $h^F\left(X\right)$ that is not in $h^F\left(Y\right)$. Assuming $S$ is nonempty, $b$ is nonempty, so we have $h^F\left(b\right)=\left\{b\right\}$, so $Y{\perp }^{F}b$, but not $X{\perp }^{F}b$. On the other hand, if $S$ is empty, then $X=Y=\left\{\right\}$, so clearly $X{\le }^{F}Y$. $\square$

Here are some basic properties of time.

Proposition 18. Let $F=(S,B)$ be a finite factored set, and let $X,Y,Z\in Part\left(S\right)$ be partitions of $S$.

1. $X{\le }^{F}X$.
2. If $X{\le }^{F}Y$ and $Y{\le }^{F}Z$, then $X{\le }^{F}Z$.
3. If $X{\le }_{S}Y$, then $X{\le }^{F}Y$.
4. If $X{\le }^{F}Z$ and $Y{\le }^{F}Z$, then $\left(X{\vee }_{S}Y\right){\le }^{F}Z$.

Proof. Part 1 is trivial from the definition.

Part 2 is trivial by transitivity of the subset relation.

Part 3 follows directly from part 1 of Proposition 13.

Part 4 follows directly from part 2 of Proposition 13. $\square$

Finally, note that we can (circularly) redefine history in terms of time, thus partially justifying the names.

Proposition 19. Given a nonempty finite factored set $F=(S,B)$ and a partition $X\in Part\left(S\right)$, $h^F\left(X\right)=\{b\in B\mid b{\le }^{F}X\}$.

Proof. Since $S$ is nonempty, part 4 of Proposition 13 says that $h^F\left(b\right)=\left\{b\right\}$ for all $b\in B$. Thus $\{b\in B\mid b{\le }^{F}X\}=\{b\in B\mid \{b\}\subseteq h^F(X\left)\right\}=\{b\in B\mid b\in h^F(X\left)\right\}=h^F\left(X\right)$. $\square$

 

In the next post, we'll build up to a definition of conditional orthogonality by introducing the notion of subpartitions.

9 comments

Comments sorted by top scores.