Finite Factored Sets: Conditional Orthogonality

post by Scott Garrabrant · 2021-07-09T06:01:46.747Z · LW · GW · 2 comments

Contents

  4.1 Generating a Subpartition
  4.2 History of a Subpartition
  4.3 Conditional Orthogonality
None
2 comments

We now want to extend our notion of orthogonality [? · GW] to conditional orthogonality. This will take a bit of work. In particular, we will have to first extend our notions of partition generation and history to be defined on partitions of subsets of $S$.

 

4.1 Generating a Subpartition

Definition 20 (subpartition). A subpartition of a set $S$ is a partition of a subset of $S$. Let $\text{SubPart}\left(S\right)={\bigcup }_{E\subseteq S}\text{Part}\left(E\right)$ denote the set of all subpartitions of $S$.

Definition 21 (domain). The domain of a subpartition $X$ of $S$, written $\text{dom}\left(X\right)$, is the unique $E\subseteq S$ such that $X\in \text{Part}\left(E\right)$.

Definition 22 (restricted partitions). Given sets $S$ and $E$ and a partition $X$ of $S$, let $X|E$ denote the partition of $S\cap E$ given by $X|E=\left\{\right[e{]}_X\cap E\mid e\in E\}$.

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

Note that this definition clearly coincides with Definition 16 [? · GW], when $X$ has domain $S$. Despite the similarity of the definitions, the idea of generating a subpartition is a bit more complicated than the idea of generating a partition of $S$.

To see this, consider the following list of equivalent definitions. Notice that while the first five directly mirror their counterparts in Proposition 10 [? · GW], the last two (and especially the last one) require an extra condition.

Proposition 20. Let $F=(S,B)$ be a finite factored set, let $X\in \text{SubPart}\left(S\right)$ be a subpartition of $S$, let $E=\text{dom}\left(X\right)$ be the domain of $X$, and let $C$ be a subset of $B$. The following are equivalent.

1. $C{⊢}^{F}X$.
2. ${\chi }_C^F(x,E)=x$ for all $x\in X$.
3. ${\chi }_C^F(x,E)\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 E$.
6. ${\chi }_C^F(s,t)\in E$ and ${\chi }_C^F(s,t){\sim }_{X}s$ for all $s,t\in E$.
7. $X{\le }_E\left({\bigvee }_S\right(C\left)|E\right)$ and ${\chi }_C^F(E,E)=E$.

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,E)\supseteq {\chi }_C^F(x,x)\supseteq x$.

To see that conditions 3 and 4 are equivalent, observe that since $E={\bigcup }_{y\in X}y$, ${\chi }_C^F(x,E)={\bigcup }_{y\in X}{\chi }_C^F(x,y)$. Thus, if ${\chi }_C^F(x,E)\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,E)\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 E$. Thus ${\chi }_C^F(x,E)\subseteq x$. Conversely, if condition 3 holds, ${\chi }_C^F(s,t)\in {\chi }_C^F\left(\right[s{]}_X,E)\subseteq [s{]}_X$ for all $s,t\in E$.

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, then ${\chi }_C^F(s,t)\in E$ for all $s,t\in E$, so ${\chi }_C^F(E,E)\subseteq E$, so ${\chi }_C^F(E,E)=E$. Further, if $s,t\in E$ satisfy $s{\sim }_{{\bigvee }_S\left(C\right)|E}t$, then $s{\sim }_{c}t$ for all $c\in C$, so ${\chi }_C^F(s,t)=t$, so $t={\chi }_C^F(s,t){\sim }_{X}s$. Thus $X{\le }_E{\bigvee }_S\left(C\right)|E$. 

Conversely, if condition 7 holds, then for all $s,t\in E$, we have ${\chi }_C^F(s,t){\sim }_{{\bigvee }_S\left(C\right)}s$, so ${\chi }_C^F(s,t){\sim }_{{\bigvee }_S\left(C\right)|E}s$, and thus ${\chi }_C^F(s,t){\sim }_{X}s$. Further, clearly ${\chi }_C^F(E,E)=E$ implies ${\chi }_C^F(s,t)\in E$ for all $s,t\in E$. $\square$

The first half of condition 7 in the above proposition can be thought of as saying that the values of factors in $C$ are sufficient to distinguish between the parts of $X$.

The second half can be thought of as saying that no factors in $C$ become entangled with any factors outside of $C$ when conditioning on $E$. This second half is actually necessary (for example) to ensure that the set of all $C$ that generate $X$ is closed under intersection. As such, we will need this fact in order to extend our notion of history to arbitrary subpartitions.

Proposition 21. Let $F=(S,B)$ be a finite factored set, let $C$ and $D$ be subsets of $B$, let $X,Y,Z\in \text{SubPart}\left(S\right)$ be subpartitions of S, and let $\text{dom}\left(X\right)=\text{dom}\left(Y\right)=E$.

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

Proof. The first 4 parts will use the equivalent definition from Proposition 20 that $C{⊢}^{F}X$ if and only if $X{\le }_S{\bigvee }_S\left(C\right)$. 1 and 2 are immediate from this definition.

3 follows directly from Definition 23. 

4 follows directly from the fact that ${\bigvee }_S\left(\right\{\left\}\right)={\text{Ind}}_S$, and ${\text{Ind}}_S|E={\text{Ind}}_E$ so $X{\le }_E{\bigvee }_S\left(C\right)|E$ if and only if $X={\text{Ind}}_E$.

For part 5, we will use the equivalent definition from Proposition 20 that $C{⊢}^{F}X$ if and only if ${\chi }_C^F(s,t)\in [s{]}_X$ for all $s,t\in E$. Assume that for all $s,t\in E$, ${\chi }_C^F(s,t)\in [s{]}_X$ and ${\chi }_D^F(s,t)\in [s{]}_X$. Thus, for all $s,t\in E$, ${\chi }_{C\cap D}^F(s,t)={\chi }_C^F\left({\chi }_D^F\right(s,t),t)\in \left[{\chi }_D^F\right(s,t){]}_X=[s{]}_X$. Similarly, for all $s,t\in E$, ${\chi }_{C\cup D}^F(s,t)={\chi }_C^F(s,{\chi }_D^F(s,t\left)\right)\in [s{]}_X$. Thus $C\cap D{⊢}^{F}X$ and $C\cup D{⊢}^{F}X$.

For part 6, we use the definition that $C{⊢}^{F}X$ if and only if ${\chi }_C^F(x,y)\in x$ for all $x,y\in X$. Clearly if $X\subseteq Z$, and ${\chi }_C^F(x,y)\in x$ for all $x,y\in Z$, then ${\chi }_C^F(x,y)\in x$ for all $x,y\in X$.

Note that while the set of $C$ that generate an $X\in \text{Part}\left(S\right)$ is closed under supersets, the set of $C$ that generate an $X\in \text{SubPart}\left(S\right)$ is merely closed under union.

Further note that part 6 of Proposition 21 uses the subset relation on subpartitions, which is a slightly unnatural relation.

 

4.2 History of a Subpartition

Definition 24 (history of a subpartition). Given a finite factored set $F=(S,B)$ and a subpartition $X\in \text{SubPart}\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$.

Proposition 22. Given a finite factored set $F=(S,B)$, $h^F:\text{SubPart}\left(S\right)\to P\left(B\right)$ is well-defined, and if $X$ is a partition of $S$, this definition coincides with Definition 17 [? · GW].

Proof. Fix a finite factored set $F=(S,B)$ and a subpartition $X\in \text{SubPart}\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$. The fact that this definition coincides with Definition 17 [? · GW] if $X\in \text{Part}\left(S\right)$ is clear.

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 a nonempty intersection since $B{⊢}^{F}X$. Thus, we can express $h^F\left(X\right)$ as a (possibly empty) composition of finitely many binary intersections. By part 5 of Proposition 21, the intersection of two subsets that generate $X$ also generates $X$. Thus $h^F\left(X\right){⊢}^{F}X$. 

We will now give five basic properties of the history of subpartitions, followed by two more properties that are less basic.

Proposition 23. Let $F=(S,B)$ be a finite factored set, let $X,Y,Z\in \text{SubPart}\left(S\right)$ be subpartitions of $S$, and let $\text{dom}\left(X\right)=\text{dom}\left(Y\right)=E$.

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

Proof. Parts 1, 3, and 4 are trivial consequences of Proposition 21, and part 5 is just a restatement of part 4 of Proposition 13 [? · GW].

For part 2, first observe that $h^F\left(X{\vee }_{E}Y\right)\supseteq h^F\left(X\right)\cup h^F\left(Y\right)$, by part 1 of Proposition 21. Thus it suffices to show that $h^F\left(X\right)\cup h^F\left(Y\right)\supseteq h^F\left(X{\vee }_{E}Y\right)$, by showing that $h^F\left(X\right)\cup h^F\left(Y\right){⊢}^{F}X{\vee }_{E}Y$.

We will use condition 7 in Proposition 20. Clearly

$$\begin{array}{cc}X& {\le }_E\left({\bigvee }_E\right(h^F\left(X\right)\left)|E\right)\\ & {\le }_E\left({\bigvee }_S\right(h^F\left(X\right)\cup h^F\left(Y\right)\left)|E\right),\end{array}$$

 and similarly,

$$\begin{array}{cc}Y& {\le }_E\left({\bigvee }_E\right(h^F\left(Y\right)\left)|E\right)\\ & {\le }_E\left({\bigvee }_{S}e\right(h^F\left(X\right)\cup h^F\left(Y\right)\left)|E\right).\end{array}$$

Thus, $X{\vee }_{E}Y{\le }_E\left({\bigvee }_S\right(h^F\left(X\right)\cup h^F\left(Y\right)\left)|E\right)$.

Next, we need to show that ${\chi }_{h^F\left(X\right)\cup h^F\left(Y\right)}^F(E,E)=E$. Clearly $E\subseteq {\chi }_{h^F\left(X\right)\cup h^F\left(Y\right)}^F(E,E)$. 

Let $s$ and $t$ be elements of $E$, and observe that ${\chi }_{h^F\left(X\right)\cup h^F\left(Y\right)}^F(s,t)={\chi }_{h^F\left(X\right)}^F(s,{\chi }_{h^F\left(Y\right)}^F(s,t\left)\right)$. We have that ${\chi }_{h^F\left(Y\right)}^F(s,t)\in E$, since ${\chi }_{h^F\left(Y\right)}^F(E,E)=E$. Thus, we also have that ${\chi }_{h^F\left(X\right)}^F(s,{\chi }_{h^F\left(Y\right)}^F(s,t\left)\right)\in E$, since ${\chi }_{h^F\left(X\right)}^F(E,E)=E$. Thus, ${\chi }_{h^F\left(X\right)\cup h^F\left(Y\right)}^F(E,E)\subseteq E$.

Thus we have that $X{\vee }_{E}Y{\le }_E\left({\bigvee }_S\right(h^F\left(X\right)\cup h^F\left(Y\right)\left)|E\right)$ and ${\chi }_{h^F\left(X\right)\cup h^F\left(Y\right)}^F(E,E)=E$. Thus, by condition 7 in Proposition 20, $h^F\left(X\right)\cup h^F\left(Y\right){⊢}^{F}X{\vee }_{E}Y$, so $h^F\left(X{\vee }_{E}Y\right)=h^F\left(X\right)\cup h^F\left(Y\right)$. $\square$

Lemma 1. Let $F=(S,B)$ be a finite factored set, and let $X,Y\in \text{Part}\left(E\right)$ be subpartitions of $S$ with the same domain. If $h^F\left(X\right)\cap h^F\left(Y\right)=\left\{\right\}$, then $h^F\left(X\right)=h^F\left(X|y\right)$ for all $y\in Y$.

Proof. Let $F=(S,B)$ be a finite factored set, let $E\subseteq S$, and let $X,Y\in \text{Part}\left(E\right)$.

We start by showing that $(B\setminus h^F(X\left)\right){⊢}^{F}Y$ and $(B\setminus h^F(Y\left)\right){⊢}^{F}X$. Observe that ${\chi }_{B\setminus h^F\left(X\right)}(E,E)={\chi }_{h^F\left(X\right)}(E,E)=E$. Further observe that $B\setminus h^F\left(X\right)\supseteq h^F\left(Y\right)$, so ${\bigvee }_S(B\setminus h^F(X\left)\right){\ge }_S{\bigvee }_S\left(h^F\right(Y\left)\right)$, so $\left({\bigvee }_S\right(B\setminus h^F\left(X\right)\left)|E\right){\ge }_E\left({\bigvee }_S\right(h^F\left(Y\right)\left)|E\right){\ge }_{E}Y$. Thus, $(B\setminus h^F(X\left)\right){⊢}^{F}Y$. Symmetrically, $(B\setminus h^F(Y\left)\right){⊢}^{F}X$.

Fix some $y\in Y$. We start by showing that $h^F\left(X\right)\supseteq h^F\left(X|y\right)$. 

We have that ${\chi }_{B\setminus h^F\left(X\right)}^F(y,E)\subseteq y$, so ${\chi }_{h^F\left(X\right)}^F(E,y)\subseteq y$, so for all $x\in X$, we have ${\chi }_{h^F\left(X\right)}^F(x\cap y,y)\subseteq y$. We also have ${\chi }_{h^F\left(X\right)}^F(x\cap y,y)\subseteq {\chi }_{h^F\left(X\right)}^F(x,E)\subseteq x$. Thus  ${\chi }_{h^F\left(X\right)}^F(x\cap y,y)\subseteq x\cap y$. Every element of $X|y$ is of the form $x\cap y$ for some $x\in X$, so we have $h^F\left(X\right){⊢}^F\left(X|y\right)$, so $h^F\left(X\right)\supseteq h^F\left(X|y\right)$.

Next, we need to show that $h^F\left(X\right)\subseteq h^F\left(X|y\right)$. For this, it suffices to show that $h^F\left(X|y\right){⊢}^{F}X$. Let $s,t$ be arbitrary elements of $E$. It suffices to show that ${\chi }_{h^F\left(X|y\right)}^F(s,t)\in [s{]}_X$. 

First, observe that since $(B\setminus h^F(Y\left)\right)\supseteq h^F\left(X\right)\supseteq h^F\left(X|y\right)$, we have that ${\chi }_{h^F\left(X|y\right)}^F(s,t)={\chi }_{B\setminus h^F\left(Y\right)}^F\left({\chi }_{h^F\left(X|y\right)}^F\right(s,t),t).$

Let $r$ be an arbitrary element of $y$. We thus have:

$$\begin{array}{cc}{\chi }_{h^F\left(X|y\right)}^F(s,t)& ={\chi }_{B\setminus h^F\left(Y\right)}^F\left({\chi }_{h^F\left(X|y\right)}^F\right(s,t),t)\\ & ={\chi }_{B\setminus h^F\left(Y\right)}^F\left({\chi }_{h^F\left(Y\right)}^F\right(r,{\chi }_{h^F\left(X|y\right)}^F(s,t)),t)\\ & ={\chi }_{B\setminus h^F\left(Y\right)}^F\left({\chi }_{h^F\left(X|y\right)}^F\right({\chi }_{h^F\left(Y\right)}^F(r,s),{\chi }_{h^F\left(Y\right)}^F(r,t)),t).\end{array}$$

Let $s^{\prime }={\chi }_{h^F\left(X|y\right)}^F\left({\chi }_{h^F\left(Y\right)}^F\right(r,s),{\chi }_{h^F\left(Y\right)}^F(r,t\left)\right)$. Note that ${\chi }_{h^F\left(Y\right)}^F(r,t)$ and ${\chi }_{h^F\left(Y\right)}^F(r,s)$ are both in $y$. Thus we have that $s^{\prime }\in \left[{\chi }_{h^F\left(Y\right)}^F\right(r,s){]}_{\left(X|y\right)}$. Since $(B\setminus h^F(Y\left)\right){⊢}^{F}X$, ${\chi }_{h^F\left(Y\right)}^F(r,s)={\chi }_{B\setminus h^F\left(Y\right)}^F(s,r)\in [s{]}_X$. Thus $\left[{\chi }_{h^F\left(Y\right)}^F\right(r,s){]}_{\left(X|y\right)}\subseteq [{\chi }_{h^F\left(Y\right)}^F(r,s){]}_X=[s{]}_X$, so $s^{\prime }\in [s{]}_X$.

We have that ${\chi }_{h^F\left(X|y\right)}^F(s,t)={\chi }_{B\setminus h^F\left(Y\right)}^F(s^{\prime },t)$. However, since $B\setminus h^F\left(Y\right){⊢}^{F}X$, we have ${\chi }_{B\setminus h^F\left(Y\right)}^F(s^{\prime },t)\in [s^{\prime }{]}_X=[s{]}_X$. Thus, $h^F\left(X\right)\subseteq h^F\left(X|y\right)$, so $h^F\left(X\right)=h^F\left(X|y\right)$. $\square$

Lemma 2. Let $F=(S,B)$ be a finite factored set. Let $E\subseteq S$ and let $X,Y\in \text{Part}\left(E\right)$ be subpartitions of $S$ with the same domain. Then $h^F\left(X{\vee }_{E}Y\right)=h^F\left(X\right)\cup {\bigcup }_{x\in X}{h}^F\left(Y|x\right)$.

Proof. Since $X{\le }_{E}X{\vee }_{E}Y$, we have $h^F\left(X\right)\subseteq h^F\left(X{\vee }_{E}Y\right)$. Similarly, for all $x\in X$, since $Y|x\subseteq X{\vee }_{E}Y$, we have $h^F\left(Y|x\right)\subseteq h^F\left(X{\vee }_{E}Y\right)$. Thus, $h^F\left(X{\vee }_{E}Y\right)\supseteq h^F\left(X\right)\cup {\bigcup }_{x\in X}{h}^F\left(Y|x\right)$. We still need to show that $h^F\left(X{\vee }_{E}Y\right)\subseteq h^F\left(X\right)\cup {\bigcup }_{x\in X}{h}^F\left(Y|x\right)$.

We start with the special case where $|X|=2$. Let $X=\{x_0,x_1\}$. In this case, we want to show that $h^F\left(X{\vee }_{E}Y\right)=h^F\left(X\right)\cup h^F\left(Y|x_0\right)\cup h^F\left(Y|x_0\right)$. Let $C=h^F\left(X\right)$, let $C_0=h^F\left(Y|x_0\right)$, and let $C_1=h^F\left(Y|x_1\right)$.

Consider arbitrary $s,t\in E$. Without loss of generality, assume that $s\in x_0$, and let $y=[s{]}_Y$. It suffices to show that ${\chi }_{C\cup C_0\cup C_1}^F(s,t)\in x_0\cap y$. Fix some $r\in x_1$.

$$\begin{array}{cc}{\chi }_{C\cup C_0\cup C_1}^F(s,t)& ={\chi }_{C_0}^F(s,{\chi }_C^F(s,{\chi }_{C_1}^F(s,t)\left)\right)\\ & ={\chi }_{C_0}^F(s,{\chi }_C^F(s,{\chi }_C^F(r,{\chi }_{C_1}^F(s,t\left)\right)\left)\right)\\ & ={\chi }_{C_0}^F(s,{\chi }_C^F(s,{\chi }_{C_1}^F\left({\chi }_C^F\right(r,s),{\chi }_C^F(r,t\left)\right)\left)\right).\end{array}$$

Observe that ${\chi }_C^F(r,s)$ and ${\chi }_C^F(r,t)$ are both in $x_1$, so ${\chi }_{C_1}^F\left({\chi }_C^F\right(r,s),{\chi }_C^F(r,t\left)\right)\in x_1$, and thus is in $E$. Combining this with the fact that $s\in x_0$ gives us that ${\chi }_C^F(s,{\chi }_{C_1}^F({\chi }_C^F(r,s),{\chi }_C^F(r,t)\left)\right)\in x_0.$ Thus, since $s\in x_0\cap y$, ${\chi }_{C\cup C_0\cup C_1}^F(s,t)={\chi }_{C_0}^F(s,{\chi }_C^F(s,{\chi }_{C_1}^F\left({\chi }_C^F\right(r,s),{\chi }_C^F(r,t\left)\right)\left)\right)\in x_0\cap y$.

Now, consider the case where $|X|\ne 2$. If $|X|=0$, then $E=\left\{\right\}$, so all subpartitions involved are empty, and thus have the same (empty) history. If $|X|=1$, let $X=\left\{E\right\}$. Then

$$\begin{array}{cc}{h}^F\left(X{\vee }_{E}Y\right)& =h^F\left(Y\right)\\ & =h^F\left(Y|E\right)\subseteq h^F\left(X\right)\cup h^F\left(Y|E\right)\\ & =h^F\left(X\right)\cup \bigcup _{x\in X}{h}^F\left(Y|x\right).\end{array}$$

Thus, we can restrict our attention to the case where $|X|\ge 3$. 

Observe that $X{\vee }_{E}Y={\bigvee }_E\left(\right\{\left(Y|x\right)\cup \{E\setminus x\}\mid x\in X\left\}\right)$. Thus $h^F\left(X{\vee }_{E}Y\right)={\bigcup }_{x\in X}{h}^F\left(\right(Y|x)\cup \{E\setminus x\left\}\right)$. However, from the case where $|X|=2$, we have

$$\begin{array}{cc}{h}^F\left(\right(Y|x)\cup \{E\setminus x\left\}\right)& =h^F\left(\right\{x,E\setminus x\left\}{\vee }_E\right(\left(Y|x\right)\cup \{E\setminus x\}\left)\right)\\ & =h^F\left(\right\{x,E\setminus x\left\}\right)\cup h^F\left(\right\{E\setminus x\left\}\right)\cup h^F\left(Y|x\right).\end{array}$$

$h^F\left(\right\{E\setminus x\left\}\right)$ is empty, so this gives us that $h^F\left(X{\vee }_{E}Y\right)={\bigcup }_{x\in X}\left(h^F\right(Y|x)\cup h^F(\{x,E\setminus x\}\left)\right)$. Since ${\bigvee }_E\left(\right\{\{x,E\setminus x\}\mid x\in X\left\}\right)=X$, ${\bigcup }_{x\in X}{h}^F\left(\right\{x,E\setminus x\left\}\right)=h^F\left(X\right)$, so we have $h^F\left(X{\vee }_{E}Y\right)=h^F\left(X\right)\cup {\bigcup }_{x\in X}{h}^F\left(Y|x\right)$. $\square$

 

4.3 Conditional Orthogonality

We can also extend our notions of orthogonality and time to subpartitions.

Definition 25. Let $F=(S,B)$ be a finite factored set. Let $X,Y\in \text{SubPart}\left(S\right)$ be subpartitions of $S$. We write $X{\perp }^{F}Y$ if $h^F\left(X\right)\cap h^F\left(Y\right)=\left\{\right\}$, we write $X{\le }^{F}Y$ if $h^F\left(X\right)\subseteq h^F\left(Y\right)$, and we write $X{<}^{F}Y$ if $h^F\left(X\right)\subset h^F\left(Y\right)$.

We give this definition in general, but it is not clear whether orthogonality and time should be considered philosophically meaningful when the domains of the inputs differ from each other. Further, the temporal structure of subpartitions will mostly be outside the scope of this paper, and the orthogonality structure on subpartitions will mostly just be used for the following pair of definitions.

Definition 26 (conditional orthogonality given a subset). Given a finite factored set $F=(S,B)$, partitions $X,Y\in \text{Part}\left(S\right)$, and $E\subseteq S$, we say $X$ and $Y$ are orthogonal given $E$ (in $F$), written $X{\perp }^{F}Y|E$, if $\left(X|E\right){\perp }^F\left(Y|E\right)$.

Definition 27 (conditional orthogonality). Given a finite factored set $F=(S,B)$, and partitions $X,Y,Z\in \text{Part}\left(S\right)$, if $X{\perp }^{F}Y|z$ for all $z\in Z$, then we say $X$ and $Y$ are orthogonal given $Z$ (in $F$), written $X{\perp }^{F}Y|Z$.

Unconditioned orthogonality can be thought of as a special case of conditional orthogonality, where you condition on the indiscrete partition.

Proposition 24. Given a finite factored set $F=(S,B)$ and partitions $X,Y\in \text{Part}\left(S\right)$, $X{\perp }^{F}Y$ if and only if $X{\perp }^{F}Y|{\text{Ind}}_S$. 

Proof. If $S=\left\{\right\}$, then there is only one partition $X=\left\{\right\}$, and $X{\perp }^{F}X$ holds. Also, since ${\text{Ind}}_S$ is empty, $X{\perp }^{F}X|{\text{Ind}}_S$ holds vacuously.

If $S\ne \left\{\right\}$, then ${\text{Ind}}_S=\left\{S\right\}$, so $X{\perp }^{F}Y|{\text{Ind}}_S$ if and only if $X{\perp }^{F}Y|S$ if and only if $X|S{\perp }^{F}Y|S$ if and only if $X{\perp }^{F}Y$. $\square$

The primary combinatorial structure of finite factored sets that we will be interested in is the structure of orthogonality ($X{\perp }^{F}Y$), conditional orthogonality ($X{\perp }^{F}Y|Z$), and time $(X{\le }^{F}Y$ and $X{<}^{F}Y)$ on inputs that are partitions.

We now will show that conditional orthogonality satisfies (a slight modification of) the axioms for a compositional semigraphoid. 

Theorem 2. Let $F=(S,B)$ be a finite factored set, and let $X,Y,Z,W\in \text{Part}\left(S\right)$ be partitions of $S$.

1. If $X{\perp }^{F}Y|Z$, then $Y{\perp }^{F}X|Z$.   (symmetry)
2. If $X{\perp }^F\left(Y{\vee }_{S}W\right)|Z$, then $X{\perp }^{F}Y|Z$ and $X{\perp }^{F}W|Z$.   (decomposition)
3. If $X{\perp }^F\left(Y{\vee }_{S}W\right)|Z$, then $X{\perp }^{F}Y|\left(Z{\vee }_{S}W\right)$.   (weak union)
4. If $X{\perp }^{F}Y|Z$ and $X{\perp }^{F}W|\left(Z{\vee }_{S}Y\right)$, then $X{\perp }^F\left(Y{\vee }_{S}W\right)|Z$.   (contraction)
5. If $X{\perp }^{F}Y|Z$ and $X{\perp }^{F}W|Z$, then $X{\perp }^F\left(Y{\vee }_{S}W\right)|Z$.   (composition)

Proof. Symmetry is clear from the definition.

Decomposition and composition both follow directly from the fact that for all $z\in Z$, $h^F\left(\right(Y{\vee }_{S}W\left)|z\right)=h^F\left(\right(Y|z\left){\vee }_z\right(W|z\left)\right)=h^F\left(Y|z\right)\cup h^F\left(W|z\right)$.

For weak union, assume that $X{\perp }^F\left(Y{\vee }_{S}W\right)|Z$. Thus, for all $z\in Z$, $h^F\left(X|z\right)\cap h^F\left(\right(Y{\vee }_{S}W\left)|z\right)=\left\{\right\}$. In particular, this means that $h^F\left(X|z\right)\cap h^F\left(W|z\right)=\left\{\right\}$, so by Lemma 1, for all $w\in W$, $h^F\left(X|z\right)=h^F(X|w\cap z)$. Further, we have that for all $w\in W$, $h^F(Y|w\cap z)\subseteq h^F\left(Y{\vee }_{S}W|z\right)$. Thus, for all $w\in W$, $h^F(X|w\cap z)\cap h^F(Y|w\cap z)=\left\{\right\}$, which since every element of $W{\vee }_{S}Z$ is of the form $w\cap z$ for some $w\in W$ and $z\in Z$, means that $X{\perp }^{F}Y|\left(Z{\vee }_{S}W\right)$.

Finally, for contraction, assume that $X{\perp }^{F}Y|Z$ and $X{\perp }^{F}W|Z{\vee }_{S}Y$. Fix some $z\in Z$. We want to show that $h^F\left(X|z\right)\cap h^F\left(\right(Y{\vee }_{S}W\left)|z\right)=\left\{\right\}$. We have that $h^F\left(\right(Y{\vee }_{S}W\left)|z\right)=h^F\left(\right(Y|z\left){\vee }_z\right(W|z\left)\right)$, and by Lemma 2, $h^F\left(\right(Y|z\left){\vee }_z\right(W|z\left)\right)=h^F\left(Y|z\right)\cup {\bigcup }_{y\in Y}{h}^F\left(W|\right(y\cap z\left)\right)$. Thus, it suffices to show that $h^F\left(X|z\right)\cap h^F\left(Y|z\right)=\left\{\right\}$ and $h^F\left(X|z\right)\cap h^F\left(W|\right(y\cap z\left)\right)=\left\{\right\}$ for all $y\in Y$.

The fact that $h^F\left(X|z\right)\cap h^F\left(Y|z\right)=\left\{\right\}$ follows directly from $X{\perp }^{F}Y|Z$. 

Fix a $y\in Y$. If $y\cap z=\left\{\right\}$, then $h^F\left(W|\right(y\cap z\left)\right)=\left\{\right\}$, so $h^F\left(X|z\right)\cap h^F\left(W|\right(y\cap z\left)\right)=\left\{\right\}$. Otherwise, we have $h^F\left(X|z\right)=h^F\left(X|\right(y\cap z\left)\right)$ by Lemma 1, and we have that $h^F\left(X|\right(y\cap z\left)\right)\cap h^F\left(W|\right(y\cap z\left)\right)=\left\{\right\}$, since $X{\perp }^{F}W|Z{\vee }_{S}Y$, so we have $h^F\left(X|z\right)\cap h^F\left(W|\right(y\cap z\left)\right)=\left\{\right\}$. 

Thus, $X{\perp }^F\left(Y{\vee }_{S}W\right)|Z$. $\square$

The first four parts of Theorem 2 are essentially the semigraphoid axioms. The difference is that the semigraphoid axioms are normally defined as a ternary relation on disjoint sets of variables. We use partitions instead of sets of variables, use common refinement instead of union, and have no need for the disjointness condition. The fifth part (composition) is a converse to the decomposition axiom that is sometimes added to define a compositional semigraphoid.

The results in this paper will not depend on the theory of compositional semigraphoids, so we will not need to make the analogy any more explicit, but it is nice to note the similarity to existing well-studied structures.

We also get a nice relationship between conditional orthogonality and the refinement order.

Proposition 25. Let $F=(S,B)$ be a finite factored set, and let $X,Y\in \text{Part}\left(S\right)$ be partitions of S. $X{\perp }^{F}X|Y$ if and only if $X{\le }_{S}Y$.

Proof. If $X{\perp }^{F}X|Y$, then for all $y\in Y,h^F\left(X|y\right)=\left\{\right\}$, so $X|y={\text{ind}}_y$, so for all $s,t\in y$, we have $s{\sim }_{X|y}t$, and thus $s{\sim }_{X}t$. Thus, for all $s,t\in S$, if $s{\sim }_{Y}t$, then $s{\sim }_{X}t$. Thus $X{\le }_{S}Y$.

Conversely, if $X{\le }_{S}Y$, observe that for all $y\in Y$, $X|y={\text{ind}}_y$, so $h^F\left(X|y\right)=\left\{\right\}$. Thus, $X{\perp }^{F}X|Y$. $\square$

 

In the next post, we will prove the fundamental theorem of finite factored sets, which says that conditional orthogonality exactly corresponds to conditional independence in all probability distributions that can be put on the relevant finite factored set.

2 comments

Comments sorted by top scores.