Finite Factored Sets: Orthogonality and Time

by Scott Garrabrant6 min read10th Jun 20214 comments

17

Finite Factored Sets
Frontpage

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 , a partition , and a , we say  generates  (in ), written , if  for all .

The following proposition gives many equivalent definitions of .

Proposition 10. Let  be a finite factored set, let  be a partition of , and let  be a subset of . The following are equivalent:

  1. .
  2.  for all .
  3.  for all .
  4.  for all .
  5.  for all .
  6.  for all .
  7. .

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

The equivalence of conditions 2 and 3 follows directly from the fact that  for all , so .

To see that conditions 3 and 4 are equivalent, observe that since . Thus, if  for all , and conversely if  for all , then .

To see that condition 3 is equivalent to condition 5, observe that if condition 5 holds, then for all , we have  for all  and  . Thus . Conversely, if condition 3 holds,  for all .

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  satisfy , then , so . Thus . Conversely, if condition 7 holds, then since  for all , we have 

Here are some basic properties of .

Proposition 11. Let ) be a finite factored set, let  and  be subsets of , and let  be partitions of .

  1. If  and , then .
  2. If  and , then .
  3. .
  4.  if and only if .
  5. If  and , then .
  6. If  and , then .

Proof. For the first 5 parts, we will use the equivalent definition from Proposition 10 that  if and only if .

Then 1 follows directly from the transitivity of .

2 follows directly from the fact that any partition  satisfies  if and only if  and .

3 follows directly from the fact that  by Proposition 3.

4 follows directly from the fact that , together with the fact that  if and only if .

5 follows directly from the fact that if , then .

Finally, we need to prove part 6. For this, we will use the equivalent definition from Proposition 10 that  if and only if  for all . Assume that for all  and . Thus, for all . Thus 

Our main use of  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  and a partition , let  denote the smallest (according to the subset ordering) subset of  such that .

The history of , then, is the smallest set of factors  such that if you're trying to figure out which part in  any given  is in, it suffices to know what part  is in within each of the factors in . We can informally think of  as the smallest amount of information needed to compute .

Proposition 12. Given a finite factored set , and a partition  is well-defined.

Proof. Fix a finite factored set  and a partition , and let  be the intersection of all  such that . It suffices to show that ; then  will clearly be the unique smallest (according to the subset ordering) subset of  such that .

Note that  is a finite intersection, since there are only finitely many subsets of , and that  is an intersection of a nonempty collection of sets since . Thus, we can express  as a composition of finitely many binary intersections. By part 6 of Proposition 11, the intersection of two subsets that generate  also generates . Thus 

Here are some basic properties of history.

Proposition 13. Let  be a finite factored set, and let  be partitions of .

  1. If , then .
  2. .
  3.  if and only if .
  4. If  is nonempty, then  for all .

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

For the fourth part, observe that  by condition 7 of Proposition 10.  is nontrivial, and since  is nonempty,  is nonempty. So we have  by part 4 of Proposition 11. Thus  is the smallest subset of  that generates 

 

3.3. Orthogonality

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

Definition 18 (orthogonality). Given a finite factored set  and partitions , we say  is orthogonal to  (in ), written , if .

If , we say  is entangled with  (in ).

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

Proposition 14. Given a finite factored set , and partitions ,   if and only if there exists a  such that  and .

Proof. If there exists a  such that  and , then  and . Thus,  and , so .

Conversely, if , let . Then , so , and , so , so 

Here are some basic properties of orthogonality.

Proposition 15. Let  be a finite factored set, and let  be partitions of .

  1. If , then .
  2. If  and , then .
  3. If  and , then .
  4.  if and only if .

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

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

 

3.4. Time

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

Definition 19 ((strictly) before). Given a finite factored set , and partitions , we say  is before  (in ), written , if .

We say  is strictly before  (in ), written , if .

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

Proposition 16. Given a finite factored set , and partitions ,   if and only if every  satisfying  also satisfies .

Proof. Note that by part 7 of Proposition 10, part 5 of Proposition 11, and the definition of history,  satisfies  if and only if , and similarly for 

Clearly, if , every  satisfies . Conversely, if  is not a subset of , then we can take , and observe that  but not 

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 , and partitions  if and only if every  satisfying  also satisfies .

Proof. Clearly if , then every  satisfying  also satisfies .

Conversely, if  is not a subset of , let  be an element of  that is not in . Assuming  is nonempty,  is nonempty, so we have , so , but not . On the other hand, if  is empty, then , so clearly 

Here are some basic properties of time.

Proposition 18. Let  be a finite factored set, and let  be partitions of .

  1. .
  2. If  and , then .
  3. If , then .
  4. If  and , then .

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. 

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  and a partition .

Proof. Since  is nonempty, part 4 of Proposition 13 says that  for all . Thus 

 

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

17

5 comments, sorted by Highlighting new comments since Today at 4:58 AM
New Comment

From def 16:

... if for all

Should I take this to mean "if for all and "?

[EDIT: no, I shouldn't, since and are both subsets of ]

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

Thus .

I think this should be .

Can't you define  for any set  of partitions of , rather than  w.r.t. a specific factorization , simply as  iff ? 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  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  rather than just for , though I haven't checked that 11.6 would still work, but it seems like it should.

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