The fundamental theorem of finite factored sets tells us that (conditional) orthogonality data can be inferred from probabilistic data. Thus, if we can infer temporal data from orthogonality data, we will be able to combine these to infer temporal data purely from probabilistic data. In this section, we will discuss the problem of inferring temporal data from orthogonality data, mostly by going through a couple of examples.

6.1. Factored Set Models

We'll begin with a sample space, $\Omega$.

Naively, one might except that temporal inference in this paradigm involves inferring a factorization of $\Omega$. What we'll actually be doing, however, is inferring a factored set model of $\Omega$. This will allow for the possibility that some situations are distinct without being distinct in $\Omega$—that there can be latent structure not represented in $\Omega$.

Definition 38 (model). Given a set $\Omega$, a model of $\Omega$ is a pair $M=(F,f)$, where $F$ is a finite factored set and $f:\text{set}\left(F\right)\to \Omega$ is a function from the set of $F$ to $\Omega$.

Definition 39. Let $S$ and $\Omega$ be sets, and let $f:S\to \Omega$ be a function from $S$ to $\Omega$. 

Given a $\omega \in \Omega$, we let $f^{-1}\left(\omega \right)=\{s\in S\mid f(s)=\omega \}$. 

Given an $E\subseteq \Omega$, we let $f^{-1}\left(E\right)=\{s\in S\mid f(s)\in E\}$. 

Given an $X\in \text{Part}\left(\Omega \right)$, we let $f^{-1}\left(X\right)\in \text{Part}\left(S\right)$ be given by $f^{-1}\left(X\right)=\left\{f^{-1}\right(x)|x\in X,f^{-1}(x)\ne \{\left\}\right\}$.

Definition 40 (orthogonality database). Given a set $\Omega$, an orthogonality database on $\Omega$ is a pair $D=(O,N)$, where $O$ and $N$ are both subsets of $\text{Part}\left(\Omega \right)\times \text{Part}\left(\Omega \right)\times \text{Part}\left(\Omega \right)$.

Definition 41. Given an orthogonality database $D=(O,N)$ on a set $\Omega$, and partitions $X,Y,Z\in \text{Part}\left(\Omega \right)$, we write $X{\perp }_{D}Y|Z$ if $(X,Y,Z)\in O$, and we write $X{\rightleftharpoons }_{D}Y|Z$ if $(X,Y,Z)\in N$. 

Definition 42. Given a set $\Omega$, a model $M=(F,f)$ of $\Omega$, and an orthogonality database $D=(O,N)$ on $\Omega$, we say $M$ models $D$ if for all $X,Y,Z\in \text{Part}\left(\Omega \right)$,

1. if $X{\perp }_{D}Y|Z$ then $f^{-1}\left(X\right){\perp }^F{f}^{-1}\left(Y\right)|f^{-1}\left(Z\right)$, and
2. if $X{\rightleftharpoons }_{D}Y|Z$ then $\neg \left(f^{-1}\left(X\right){\perp }^F{f}^{-1}\left(Y\right)|f^{-1}\left(Z\right)\right)$.

Definition 43. An orthogonality database $D$ on a set $\Omega$ is called consistent if there exists a model $M$ of $\Omega$ such that $M$ models $D$. 

Definition 44. An orthogonality database $D$ on a set $\Omega$ is called complete if for all $X,Y,Z\in \text{Part}\left(\Omega \right)$, either $X{\perp }_{D}Y|Z$ or $X{\rightleftharpoons }_{D}Y|Z$.

Definition 45. Given a set $\Omega$, an orthogonality database $D$ on $\Omega$, and $X,Y\in \text{Part}\left(\Omega \right)$, we say $X{<}_{D}Y$ if for all models $(F,f)$ of $\Omega$ that model $D$, we have $f^{-1}\left(X\right){<}^F{f}^{-1}\left(Y\right)$. 

6.2. Examples

Example 1. Let $\Omega =\{00,01,10,11\}$ be the set of all bit strings of length $2$. For $i\in \{0,1\}$, let $x_i=\{i0,i1\}$ be the event that the first bit is $i$, and let $y_i=\{0i,1i\}$ be the event that the second bit is i. Let $X=\{x_0,x_1\}$ and let $Y=\{y_0,y_1\}$. 

Let $v_0=\{00,11\}$ be the event that the two bits are equal, let $v_1=\{01,10\}$ be the event that the two bits are unequal, and let $V=\{v_0,v_1\}$. 

Let $D=(O,N)$, where $O=\left\{\right(X,V,\left\{\Omega \right\}\left)\right\}$ and $N=\left\{\right(V,V,\left\{\Omega \right\}\left)\right\}$.

Proposition 33.  In Example 1, $D$ is consistent.

Proof. First observe that $F=(\Omega ,\{X,V\left\}\right)$ is a factored set, and so $M=(F,f)$ is a model of $\Omega$, where $f$ is the identity on $\Omega$. It suffices to show that $M$ models $D$.

Indeed $h^F\left(X\right)=\left\{X\right\}$, and $h^F\left(V\right)=\left\{V\right\}$, so $X{\perp }^{F}V$, so $f^{-1}\left(X\right){\perp }^F{f}^{-1}\left(V\right)|f^{-1}\left(\right\{\Omega \left\}\right)$. 

Further, it is not the case that $V{\perp }^{F}V$, since $V\ne {\text{Ind}}_{\Omega }$. Thus it is not the case that $f^{-1}\left(V\right){\perp }^F{f}^{-1}\left(V\right)|f^{-1}\left(\right\{\Omega \left\}\right)$.

Thus $M$ satisfies all of the conditions to model $D$, so $D$ is consistent. $\square$

Proposition 34. In Example 1, $X{<}_{D}Y$.

Proof. Let $(F,f)$ be any model of $\Omega$ that models $D$. Let $F=(S,B)$. For any $A\in \text{Part}\left(\Omega \right)$, let $H_A=h^F\left(f^{-1}\right(A\left)\right)$. Our goal is to show that $H_X$ is a strict subset of $H_Y$.

First observe that $X{\le }_{\Omega }Y{\vee }_{\Omega }V$, so for any $s,t\in S$, if $s{\sim }_{f^{-1}\left(Y\right)}t$ and $s{\sim }_{f^{-1}\left(V\right)}t$, then $f\left(s\right){\sim }_{Y}f\left(t\right)$ and $f\left(s\right){\sim }_{V}f\left(t\right)$, so $f\left(s\right){\sim }_{X}f\left(t\right)$, so $s{\sim }_{f^{-1}\left(X\right)}t$. Thus $f^{-1}\left(X\right){\le }_S{f}^{-1}\left(Y\right){\vee }_S{f}^{-1}\left(V\right)$.

It follows that $H_X\subseteq h^F\left(f^{-1}\right(Y\left){\vee }_S{f}^{-1}\right(V\left)\right)=H_Y\cap H_V$. However, since $X{\perp }_{D}V|\left\{\Omega \right\}$, we have that $H_X\cap H_V=\left\{\right\}$, so $H_X\subseteq H_Y$.

By swapping $X$ and $V$ in the argument above, we also get that $H_V\subseteq H_Y$. Since $V{\rightleftharpoons }_{D}V|\left\{\Omega \right\}$, we have that $H_V\ne \left\{\right\}$. Thus $H_V$ contains some element $b$. Observe that $b\notin H_X$, but $b\in H_Y$. Thus $H_X$ is a strict subset of $H_Y$, so $f^{-1}\left(X\right){<}^F{f}^{-1}\left(Y\right)$.

Since $(F,f)$ was an arbitrary model of $\Omega$ that models $D$, this implies that $X{<}_{D}Y$. $\square$

Example 2. Let $\Omega =\{000,001,010,011,100,101,110,111\}$ be the set of all bit strings of length $3$. For $i\in \{0,1\}$, let $x_i=\{i00,i01,i10,i11\}$ be the event that the first bit is $i$, let $y_i=\{0i0,0i1,1i0,1i1\}$ be the event that the second bit is $i$, and let $z_i=\{00i,01i,10i,11i\}$ be the event that the third bit is $i$. Let $X=\{x_0,x_1\}$, let $Y=\{y_0,y_1\}$, and let $Z=\{z_0,z_1\}$. 

Let $v_0=\{000,001,110,111\}$ be the event that the first two bits are equal, let $v_1=\{010,011,100,101\}$ be the event that the first two bits are unequal, and let $V=\{v_0,v_1\}$. 

Let $D=(O,N)$, where $O=\left\{\right(X,V,\left\{\Omega \right\}),(X,Z,Y),(V,Z,Y\left)\right\}$ and $N=\left\{\right(X,Z,\left\{\Omega \right\}),(V,Z,\left\{\Omega \right\}),(Z,Z,Y\left)\right\}$.

Proposition 35. In Example 2, $D$ is consistent.

Proof. Let $S=\Omega \cup \{00,01,10,11\}$ be the set of all bit strings of length either $2$ or $3$. 

For $i\in \{0,1\}$, let $x_i^{\prime }=\{i00,i01,i10,i11,i0,i1\}$ be the event that the first bit is $i$, and let $X^{\prime }=\{x_0^{\prime },x_1^{\prime }\}$.

For $i\in \{0,1\}$, let $y_i^{\prime }=\{0i0,0i1,1i0,1i1,0i,1i\}$ be the event that the second bit is $i$, and let $Y^{\prime }=\{y_0^{\prime },y_1^{\prime }\}$.

Let $v_0^{\prime }=\{000,001,110,111,00,11\}$ be the event that the first two bits are equal, let $v_1^{\prime }=\{010,011,100,101,01,10\}$ be the event that the first two bits are unequal, and let $V^{\prime }=\{v_0^{\prime },v_1^{\prime }\}$.

For $i\in \{0,1\}$, let $z_i^{\prime }=\{00i,01i,10i,11i\}$ be the event that the third bit exists and is $i$, let $z_2^{\prime }=\{00,01,10,11\}$ be the event that there are only two bits, and let $Z^{\prime }=\{z_0^{\prime },z_1^{\prime },z_2^{\prime }\}$.

Let $B=\{X^{\prime },V^{\prime },Z^{\prime }\}$. Clearly, $(S,B)$ is a finite factored set.

Let $f:S\to \Omega$ be given by $f\left(s\right)=s$ if $s\in \Omega$, $f\left(00\right)=000$, $f\left(01\right)=011$, $f\left(10\right)=100$, and $f\left(11\right)=111$, so $f$ copies the last bit on inputs of length $2$, and otherwise leaves the bit string alone. We will show that $(F,f)$ models $D$.

First, observe that $f^{-1}\left(X\right)=X^{\prime }$, $f^{-1}\left(Y\right)=Y^{\prime }$, $f^{-1}\left(V\right)=V^{\prime }$, and $f^{-1}\left(Z\right)=\left\{\right\{000,010,100,110,00,10\},\{001,011,101,111,01,11\left\}\right\}$. 

It is easy to verify that $h^F\left(X^{\prime }\right)=\left\{X^{\prime }\right\},h^F\left(V^{\prime }\right)=\left\{V^{\prime }\right\},h^F\left(Y^{\prime }\right)=\{X^{\prime },V^{\prime }\}$, and $h^F\left(f^{-1}\right(Z\left)\right)=B$. From this, we get that $X^{\prime }{\perp }^F{V}^{\prime }$ holds, but  $X^{\prime }{\perp }^F{f}^{-1}\left(Z\right)$ and $V^{\prime }{\perp }^F{f}^{-1}\left(Z\right)$ do not hold.

Next, observe that for $i\in \{0,1\}$, $X^{\prime }|y_i=V^{\prime }|y_i=\left\{\right\{0i0,0i1,0i\},\{1i0,1i1,1i\left\}\right\}$. It is easy to verify that $h^F\left(X^{\prime }|y_i\right)=h^F\left(V^{\prime }|y_i\right)=\{X^{\prime },V^{\prime }\}$.

Also, observe that $f^{-1}\left(Z\right)|y_0=\left\{\right\{000,100,00,10\},\{001,101\left\}\right\}$, and observe that $f^{-1}\left(Z\right)|y_1=\left\{\right\{010,110\},\{011,111,01,11\left\}\right\}$. It is easy to verify that $h^F\left(f^{-1}\right(Z\left)|y_0\right)=h^F\left(f^{-1}\right(Z\left)|y_1\right)=\left\{Z^{\prime }\right\}$.

From this, we get that $X^{\prime }{\perp }^F{f}^{-1}\left(Z\right)|Y^{\prime }$ and $V^{\prime }{\perp }^F{f}^{-1}\left(Z\right)|Y^{\prime }$ hold, and $f^{-1}\left(Z\right){\perp }^F{f}^{-1}\left(Z\right)|Y^{\prime }$ does not hold. 

Thus, $(F,f)$ models $D$, so $D$ is consistent. $\square$

Proposition 36. In Example 2, $X{<}_{D}Y{<}_{D}Z$.

Proof. Let $(F,f)$ be any model of $\Omega$ that models $D$. Let $F=(S,B)$. For any $A\in \text{Part}\left(\Omega \right)$, let $H_A=h^F\left(f^{-1}\right(A\left)\right)$. Our goal is to show that $H_X$ is a strict subset of $H_Y$ and that $H_Y$ is a strict subset of $H_Z$.

First observe that $X{\le }_{\Omega }Y{\vee }_{\Omega }V$, so $f^{-1}\left(X\right){\le }_S{f}^{-1}\left(Y\right)\vee f^{-1}\left(V\right)$, so $H_X\subseteq H_Y\cup H_V$. Since $X{\perp }_{D}Y|\left\{\Omega \right\}$, $H_X\cap H_V=\left\{\right\}$, so $H_X\subseteq H_Y$. Symmetrically, $H_V\subseteq H_Y$, so $H_X\cup H_V\subseteq H_Y$.

Similarly, $Y{\le }_{\Omega }X{\vee }_{\Omega }V$, so $H_Y\subseteq H_X\cup H_V$. Thus $H_Y=H_X\cup H_V$.

We also know that $H_X$ and $H_V$ are nonempty, because $X{\rightleftharpoons }_{D}Z|\left\{\Omega \right\}$ and $Y{\rightleftharpoons }_{D}Z|\left\{\Omega \right\}$.

Thus $H_X$ is a strict subset of $H_Y$, so $X{<}_{D}Y$.

Let $C\subseteq B$ be arbitrary such that $H_X\cap C$ and $H_V\cap (B\setminus C)$ are both nonempty. Fix some $b_X\in H_X\cap C$ and $b_V\in H_V\cap (B\setminus C)$.

Since $b_X\in H_X$, there must exist $s_0,s_1\in S$ such that $s_0{\sim }_b{s}_1$ for all $b\in B\setminus \left\{b_X\right\}$, but not $s_0{\sim }_{f^{-1}\left(X\right)}{s}_1$. Thus it is not the case that $f\left(s_0\right){\sim }_{X}f\left(s_1\right)$. Without loss of generality, assume that $f\left(s_0\right)\in x_0$ and $f\left(s_1\right)\in x_1$.

Similarly, since $b_V\in H_V$, there must exist $t_0,t_1\in S$ such that $t_0{\sim }_b{t}_1$ for all $b\in B\setminus \left\{b_V\right\}$, but not $t_0{\sim }_{f^{-1}\left(V\right)}{t}_1$. Again, without loss of generality, assume that $f\left(t_0\right)\in v_0$ and $f\left(t_1\right)\in v_1$. 

For $i,j\in \{0,1\}$, let $r_{ij}={\chi }_{H_X}^F(s_i,t_j)$.

Next, observe that $r_{ij}{\sim }_{f^{-1}\left(X\right)}{s}_i$, so $f\left(r_{ij}\right){\sim }_{X}f\left(s_i\right)\in x_i$, so $f\left(r_{ij}\right)\in x_i$. Similarly, $f\left(r_{ij}\right)\in v_j$, so $f\left(r_{ij}\right)\in x_i\cap v_j$. Thus, if $i=j,f\left(r_{ij}\right)\in y_0$, and if $i\ne j$, $f\left(r_{ij}\right)\in y_1$.

Further, observe that ${\chi }_C^F(r_{00},r_{11})=r_{01}$, since $r_{00}$ and $r_{11}$ agree on all factors other than $b_X$ and $b_V$. In particular, this means that ${\chi }_C^F\left(f^{-1}\right(y_0),f^{-1}(y_0\left)\right)\ne f^{-1}\left(y_0\right)$. Similarly, since ${\chi }_C^F(r_{01},r_{10})=r_{00}$, we have that ${\chi }_C^F\left(f^{-1}\right(y_1),f^{-1}(y_1\left)\right)\ne f^{-1}\left(y_1\right)$.

We will use this to show that for any $y\in f^{-1}\left(Y\right)$ and $A\in \text{Part}\left(y\right)$, either $h^F\left(A\right)\cap H_Y=\left\{\right\}$, or $H_Y\subseteq h^F\left(A\right)$. This is because $h^F\left(A\right){⊢}^{F}A$, so ${\chi }_{h^F\left(A\right)}^F(y,y)=y$, so by the above argument, if $h^F\left(A\right)\cap H_X$ is nonempty, then $H_V\subseteq h^F\left(A\right)$, which since $H_V$ is nonempty means $h^F\left(A\right)\cap H_V$ is nonempty, so $H_X\subseteq h^F\left(A\right)$, so $H_Y\subseteq h^F\left(A\right)$. Symmetrically, we also have that if $h^F\left(A\right)\cap H_V$ is nonempty, then $H_Y\subseteq h^F\left(A\right)$. Thus, if $h^F\left(A\right)\cap H_Y$ is nonempty, then either $h^F\left(A\right)\cap H_X$ or $h^F\left(A\right)\cap H_V$ is nonempty, so $H_Y\subseteq h^F\left(A\right)$.

Note that for any $y\in f^{-1}\left(Y\right)$, two of the elements among the four $r_{ij}$ defined above are in $y$, and those two elements are in different parts in $f^{-1}\left(X\right)$, so $f^{-1}\left(X\right)|y$ has at least two parts, so $h^F\left(f^{-1}\right(X\left)|y\right)$ is nonempty. However, $h^F\left(f^{-1}\right(X\left)|y\right)\subseteq h^F\left(f^{-1}\right(X\left){\vee }_S{f}^{-1}\right(Y\left)\right)=H_Y$. Thus, $h^F\left(f^{-1}\right(X\left)|y\right)\cap H_Y\ne \left\{\right\}$, so $H_Y\subseteq h^F\left(f^{-1}\right(X\left)|y\right)$, so $h^F\left(f^{-1}\right(X\left)|y\right)=H_Y$. Symmetrically, $h^F\left(f^{-1}\right(V\left)|y\right)=H_Y$.

In particular, this means that $h^F\left(f^{-1}\right(Z\left)|y\right)\cap H_Y=\left\{\right\}$, since $X{\perp }_{D}Z|Y$. 

Since $X{\rightleftharpoons }_{D}Z|\left\{\Omega \right\}$, there exists some $b_Z\in H_X\cap H_Z$. Since $b_Z\in H_Z$, there exist $u_0,u_1\in S$ such that $u_0{\sim }_b{u}_1$ for all $b\in B\setminus \left\{b_Z\right\}$, but it is not the case that $u_0{\sim }_{f^{-1}\left(Z\right)}{u}_1$. Without loss of generality, assume that $f\left(u_0\right)\in z_0$ and $f\left(u_1\right)\in z_1$. Let $y=[u_0{]}_{f^{-1}\left(Y\right)}$.

Let $b_y$ be an arbitrary element of $H_Y$. Since $b_Y\in H_Y$, there exist $q_0,q_1\in S$ such that $q_0{\sim }_b{q}_1$ for all $b\in B\setminus \left\{b_Y\right\}$, but it is not the case that $q_0{\sim }_{f^{-1}\left(Y\right)}{q}_1$. Without loss of generality, assume that $q_0\in y$ and $q_1\notin y$.

Consider $p_0={\chi }_{H_Y}^F(q_0,u_0)={\chi }_{H_Y}^F(q_0,u_1)$. Since $q_0\in y$, $p_0\in y$. Since $u_0$ is also in $y$,  ${\chi }_{h^F\left(f^{-1}\right(Z\left)|y\right)}^F(p_0,u_0){\sim }_{f^{-1}\left(Z\right)}{p}_0$. However, since $h^F\left(f^{-1}\right(Z\left)|y\right)\cap H_Y=\left\{\right\}$, we have ${\chi }_{h^F\left(f^{-1}\right(Z\left)|y\right)}^F(p_0,u_0)=u_0$, so $u_0{\sim }_{f^{-1}\left(Z\right)}{p}_0$.

If $u_1$ were in $y$, we would similarly have $u_1{\sim }_{f^{-1}\left(Z\right)}{p}_0$, which would contradict the fact that it is not the case that $u_0{\sim }_{f^{-1}\left(Z\right)}{u}_1$. Thus $u_1\notin y$.

Next, consider $p_1={\chi }_{H_Y}^F(q_1,u_0)={\chi }_{H_Y}^F(q_1,u_1)$. Since $q_1\notin y$, $p_1\notin y$. Since $u_1$ is also not in $y$,  ${\chi }_{h^F\left(f^{-1}\right(Z\left)|\right(S\setminus y\left)\right)}^F(p_1,u_1){\sim }_{f^{-1}\left(Z\right)}{p}_1$. However, since $h^F\left(f^{-1}\right(Z\left)|\right(S\setminus y\left)\right)\cap H_Y=\left\{\right\}$, we have ${\chi }_{h^F\left(f^{-1}\right(Z\left)|\right(S\setminus y\left)\right)}^F(p_1,u_1)=u_1$, so $u_1{\sim }_{f^{-1}\left(Z\right)}{p}_1$. 

Thus, it is not the case that $p_0{\sim }_{f^{-1}\left(Z\right)}{p}_1$. However, we constructed $p_0$ and $p_1$ such that $p_0{\sim }_b{p}_1$ for all $b\ne b_Y$. Thus $b_Y\in H_Z$. Since $b_Y$ was arbitrary in $H_Y$, we have that  $H_Y\subseteq H_Z$. Finally, we need to show that this subset relation is strict. 

Since $Z{\rightleftharpoons }_{D}Z|Y$, there is some $y$ such that $h^F\left(f^{-1}\right(Z\left)|y\right)\ne \left\{\right\}$. Let $b$ be any element of $h^F\left(f^{-1}\right(Z\left)|y\right)$. Since $h^F\left(f^{-1}\right(Z\left)|y\right)\cap H_Y=\left\{\right\}$, $b\notin H_Y$. However, $b\in h^F\left(f^{-1}\right(Z\left)|y\right)\subseteq h^F\left(f^{-1}\right(Z\left){\vee }_S{f}^{-1}\right(Y\left)\right)=h_Z\cup H_Y$. Therefore $b\in H_Z$. Thus $H_Y$ is a strict subset of $H_Z$, so $Y{<}_{D}Z$. $\square$

In the next post, we'll discuss applications and future research directions.