Finite Factored Sets: Orthogonality and Time

[Scott Garrabrant]

The main way we’ll be using factored sets 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.

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.

[Chris van Merwijk]

I just want to point out some interesting properties of this definition of time: Let time_C refer to the classical notion of time in a dynamical system, and time_FFS the notion defined in this article.

1. Suppose we have a field on space-time generated by a typical differential dynamical law that satisfies time_C-reversal symmetry, and suppose we factorize its histories according to the states of the system at time_C t=0. Then time_FFS doesn’t make a distinction between the “positive” and “negative” part of the time_C. That is, if x is some position (choose a reference frame), then the position (x,2) in space-time (i.e. the value of the field at position x at time_C 2) is later in time_FFS than (x,1), but (x,-2) is also later in time than (x,-1). In this sense, the time_FFS notion of time seems to naturally capture the time-reversal symmetry in the laws of physics: Intuitively, if we start at the big bang, and go “backward in time” we are just as much going into the future as we are if we would go “forward in time”. Both directions are the future.

2. However, more weirdly, time_FFS also allows a comparison between the negative-time_C and positive-time_C events. Namely, (x,1) happens before_FFS (x,-2) while (x, −1) happens before_FFS (x,2). I am not sure what to make of this, or whether we should make anything of it.

3. Suppose a computer is implemented in the physical world and implements a deterministic function $f:X\to Y$, AND we restrict to the set of histories in which this computer actually does this computation. Now let x denote the variable that captures what input is given to this computer (meaning, the data stored in the input register at one particular instance of running this algorithm), and y similarly denote the variable that captures what the output is, then y occurs (weakly) earlier_FFS than x, even though the variable x is defined to be earlier than y (more precisely, to directly apply the definitions of x and y to check their value in a particular history h would involve doing a check for x at a time_C that is earlier_C than the check for y). I’m not sure what to make of this, though it kind of seems like a feature not a bug. If we don’t restrict to the set of histories in which the computer does the computation, I’m pretty sure this result disappears, which makes me think this is actually a desirable property of the theory.

[Gurkenglas]

subpartitions

So you’re doing category theory after all! :)

[DanielFilan]

From def 16:

… if ${\chi }_C^F(x,S)=x$ for all $x\in X$

Should I take this to mean “if ${\chi }_C^F(x,s)=x$ for all $x\in X$ and $s\in S$”?

[EDIT: no, I shouldn’t, since ${\chi }_C^F(x,S)$ and $x$ are both subsets of $S$]

[DanielFilan]

OK I think this is a typo, from the proof of prop 10 where you deal with condition 5:

Thus ${\chi }_C^F(x,s)\in x$.

I think this should be ${\chi }_C^F(x,s)\subseteq x$.

[Scott Garrabrant]

Fixed, Thanks.

[Chris van Merwijk]

In the proof of proposition 18, “part 3” should be “part 4″.

[Scott Garrabrant]

fixed, thanks.

[Chris van Merwijk]

Can’t you define $C{⊢}^{S}X$ for any set $C$ of partitions of $X$, rather than $C{⊢}^{F}X$ w.r.t. a specific factorization $F$, simply as $C{⊢}^{S}X$ iff ${\bigvee }_S\left(C\right){\ge }_{S}X$? If so, it would seem to me to be clearer to define $⊢$ that way (i.e. make 7 rather than 2 from proposition 10 the definition), and then basically proposition 10 says “if $C$ is a subset of factors of a partition then here are a set of equivalent definitions in terms of chimera”. Also I would guess that proposition 11 is still true for ${⊢}^S$ rather than just for ${⊢}^F$, though I haven’t checked that 11.6 would still work, but it seems like it should.

[Scott Garrabrant]

I could do that. I think it wouldn’t be useful, and wouldn’t generalize to sub partitions.