I think a subpartition of S can be thought of as a partial function on S, or equivalently, a variable on S that has the possible value "Null"/"undefined".
That's right. A partial function can be thought of as a subset (of its domain) and a total function on that subset. And a (total) function can be thought of as a partition (of its domain): the parts are the inverse images of each point in the function's image.
We now want to extend our notion of orthogonality 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 .
Definition 20 (subpartition). A subpartition of a set is a partition of a subset of . Let denote the set of all subpartitions of .
Definition 21 (domain). The domain of a subpartition of , written , is the unique such that .
Definition 22 (restricted partitions). Given sets and and a partition of , let denote the partition of given by .
Definition 23 (generating a subpartition). Given a finite factored set , and , and a , we say generates (in ), written , if for all .
Note that this definition clearly coincides with Definition 16, when has domain . 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 .
To see this, consider the following list of equivalent definitions. Notice that while the first five directly mirror their counterparts in Proposition 10, the last two (and especially the last one) require an extra condition.
Proposition 20. Let be a finite factored set, let be a subpartition of , let be the domain of , and let be a subset of . The following are equivalent.
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, then for all , so , so . Further, if satisfy , then for all , so , so . Thus .
Conversely, if condition 7 holds, then for all , we have , so , and thus . Further, clearly implies for all .
The first half of condition 7 in the above proposition can be thought of as saying that the values of factors in are sufficient to distinguish between the parts of .
The second half can be thought of as saying that no factors in become entangled with any factors outside of when conditioning on . This second half is actually necessary (for example) to ensure that the set of all that generate 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 be a finite factored set, let and be subsets of , let be subpartitions of S, and let .
Proof. The first 4 parts will use the equivalent definition from Proposition 20 that if and only if . 1 and 2 are immediate from this definition.
3 follows directly from Definition 23.
4 follows directly from the fact that , and so if and only if .
For part 5, we will use the equivalent definition from Proposition 20 that if and only if for all . Assume that for all , and . Thus, for all , . Similarly, for all , . Thus and .
For part 6, we use the definition that if and only if for all . Clearly if , and for all , then for all .
Note that while the set of that generate an is closed under supersets, the set of that generate an 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.
Definition 24 (history of a subpartition). Given a finite factored set and a subpartition , let denote the smallest (according to the subset ordering) subset of such that .
Proposition 22. Given a finite factored set , is well-defined, and if is a partition of , this definition coincides with Definition 17.
Proof. Fix a finite factored set and a subpartition , 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 . The fact that this definition coincides with Definition 17 if is clear.
Note that is a finite intersection, since there are only finitely many subsets of , and that is a nonempty intersection since . Thus, we can express as a (possibly empty) composition of finitely many binary intersections. By part 5 of Proposition 21, the intersection of two subsets that generate also generates . Thus .
We will now give five basic properties of the history of subpartitions, followed by two more properties that are less basic.
Proposition 23. Let be a finite factored set, let be subpartitions of , and let .
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.
For part 2, first observe that , by part 1 of Proposition 21. Thus it suffices to show that , by showing that .
We will use condition 7 in Proposition 20. Clearly
and similarly,
Thus, .
Next, we need to show that . Clearly .
Let and be elements of , and observe that . We have that , since . Thus, we also have that , since . Thus, .
Thus we have that and . Thus, by condition 7 in Proposition 20, , so .
Lemma 1. Let be a finite factored set, and let be subpartitions of with the same domain. If , then for all .
Proof. Let be a finite factored set, let , and let .
We start by showing that and . Observe that . Further observe that , so , so . Thus, . Symmetrically, .
Fix some . We start by showing that .
We have that , so , so for all , we have . We also have . Thus . Every element of is of the form for some , so we have , so .
Next, we need to show that . For this, it suffices to show that . Let be arbitrary elements of . It suffices to show that .
First, observe that since , we have that
Let be an arbitrary element of . We thus have:
Let . Note that and are both in . Thus we have that . Since , . Thus , so .
We have that . However, since , we have . Thus, , so .
Lemma 2. Let be a finite factored set. Let and let be subpartitions of with the same domain. Then .
Proof. Since , we have . Similarly, for all , since , we have . Thus, . We still need to show that .
We start with the special case where . Let . In this case, we want to show that . Let , let , and let .
Consider arbitrary . Without loss of generality, assume that , and let . It suffices to show that . Fix some .
Observe that and are both in , so , and thus is in . Combining this with the fact that gives us that Thus, since , .
Now, consider the case where . If , then , so all subpartitions involved are empty, and thus have the same (empty) history. If , let . Then
Thus, we can restrict our attention to the case where .
Observe that . Thus . However, from the case where , we have
is empty, so this gives us that . Since , , so we have .
We can also extend our notions of orthogonality and time to subpartitions.
Definition 25. Let be a finite factored set. Let be subpartitions of . We write if , we write if , and we write if .
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 , partitions , and , we say and are orthogonal given (in ), written , if .
Definition 27 (conditional orthogonality). Given a finite factored set , and partitions , if for all , then we say and are orthogonal given (in ), written .
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 and partitions , if and only if .
Proof. If , then there is only one partition , and holds. Also, since is empty, holds vacuously.
If , then , so if and only if if and only if if and only if .
The primary combinatorial structure of finite factored sets that we will be interested in is the structure of orthogonality (), conditional orthogonality (), and time and 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 be a finite factored set, and let be partitions of .
Proof. Symmetry is clear from the definition.
Decomposition and composition both follow directly from the fact that for all , .
For weak union, assume that . Thus, for all , . In particular, this means that , so by Lemma 1, for all , . Further, we have that for all , . Thus, for all , , which since every element of is of the form for some and , means that .
Finally, for contraction, assume that and . Fix some . We want to show that . We have that , and by Lemma 2, . Thus, it suffices to show that and for all .
The fact that follows directly from .
Fix a . If , then , so . Otherwise, we have by Lemma 1, and we have that , since , so we have .
Thus, .
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 be a finite factored set, and let be partitions of S. if and only if .
Proof. If , then for all , so , so for all , we have , and thus . Thus, for all , if , then . Thus .
Conversely, if , observe that for all , , so . Thus, .
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.