Finite Factored Sets: Introduction and Factorizations

post by Scott Garrabrant · 2021-06-04T17:41:34.827Z · LW · GW · 2 comments

Contents

  1. Introduction
    1.1. Pearlian Causal Inference
    1.2. Overview
  2. Factorizations
    2.1. Partitions
    2.2. Factorizations
    2.3. Chimera Functions
    2.4. Trivial Factorizations
    2.5. Finite Factored Sets
  Footnotes
None
2 comments

This is a longer, more mathematically dense introduction to "Finite Factored Sets." For a shorter introduction, see my Topos talk/transcript [LW · GW].

---

Abstract: We propose a new approach to temporal inference, inspired by the Pearlian causal inference paradigm—though quite different from Pearl's approach formally. Rather than using directed acyclic graphs, we make use of factored sets, which are sets expressed as Cartesian products. We show that finite factored sets are powerful tools for inferring temporal relations. We introduce an analog of d-separation for factored sets, conditional orthogonality, and we demonstrate that this notion is equivalent to conditional independence in all probability distributions on a finite factored set.

---

1. Introduction

1.1. Pearlian Causal Inference

Judea Pearl's theory of inferred causation (e.g., as presented in chapter 2 of Causality: Models, Reasoning, and Inference) was a deep advance in our understanding of the nature of time. The Pearlian paradigm allows us to infer causal relationships between variables using statistical data, and thereby infer temporal sequence—in defiance of the old adage that correlation does not imply causation.

In particular, given a collection of variables and a joint probability distribution over those variables, the Pearlian paradigm can often infer temporal relationships between the variables.

The joint probability distribution is usually what gets emphasized in discussions of Pearl's approach. Quite a bit of work is being done, however, by the assumption that we are handed "a collection of variables" to reason about. The Pearlian paradigm is not inferring temporal relationships from purely statistical data, but rather inferring temporal relationships from statistical data together with data about how to factorize the world into variables.[1]

A doctor who misdiagnoses their patient or misidentifies a symptom may base their subsequent reasoning on a wrong factorization of the situation into causally relevant variables. We would ideally like to build fewer assumptions like this into our model of inference, and instead allow the reasoner to figure such facts out, consider the merits of different factorizations into variables, etc.

Instead of beginning with a collection of variables and a joint probability distribution over those variables, one could imagine starting with just a finite sample space and a probability distribution on that sample space. In this way, we might hope to do temporal inference purely using statistical data, without relying on a priori knowledge of a canonical way of factoring the situation into variables.

How might one do temporal inference without an existing factorization? One way might be to just consider all possible variables that can be defined on the sample space. This gives us one variable for each partition of the set.

However, when one tries to apply Pearl's methods to this collection of variables, one quickly runs into a problem: many of the variables definable on a fixed set are deterministic functions of each other. The Pearlian paradigm, as presented in the early chapters of Causality, lacks tools for performing temporal inference on variables that are highly deterministically related.[2]

We will introduce a new approach to temporal inference instead—one which is heavily inspired by the Pearlian paradigm, but approaches the problem with a very different formal apparatus, and does not make use of graphical models.

 

1.2. Overview

We'll begin by introducing the concept of a finite factored set, in Section 2. This will be our analogue of the directed acyclic graphs in Pearl's framework.

In Section 3, we will introduce the concepts of time and orthogonality, which can be read off of a finite factored set. In Pearl's framework, "time" corresponds to directed paths between nodes, and "orthogonality" corresponds to nodes that have no common ancestor.

In Section 4, we will introduce conditional orthogonality, which is our analogue of d-separation. We show that conditional orthogonality satisfies (a modified version of) the compositional semigraphoid axioms. We then (in Section 5) prove the fundamental theorem of finite factored sets, which states that conditional orthogonality is equivalent to conditional independence in all probability distributions on the finite factored set.

In Section 6, we discuss how to do temporal inference using finite factored sets, and give two examples. Finally, in Section 7 we discuss applications and future work, with an emphasis on temporal and conceptual inference, generalizing finite factored sets to the infinite case, and applications to embedded agency [? · GW].

And here, we take our leave of Pearl. We've highlighted this approach's relationship to the Pearlian paradigm in order to motivate finite factored sets and explain how we'll be using them in this sequence. Formally, however, our approach is quite unlike Pearl's, and the rest of the sequence will stand alone.

 

2. Factorizations

Before giving a definition of finite factored sets, we will recall the definition of a partition, and give some basic notation related to partitions.

We do this for two reasons. First, we will use partitions in the definition of a factored set; and second, we want to draw attention to a duality between the notion of a partition, and the notion of a factorization.

 

2.1. Partitions

We begin with a definition of disjoint union.

Definition 1 (disjoint union). Given a set $S$ of sets, let $\bigsqcup \left(S\right)$ denote the set of all ordered pairs $(T,t)$, where $T\in S$ and $t\in T$.[3]

Definition 2 (partition). A partition of a set $S$ is a set $X\subseteq P\left(S\right)$ of nonempty subsets of $S$ such that the function $\iota :\bigsqcup \left(X\right)\to S$ given by $\iota (x,s)=s$ is a bijection.[4]

Let $Part\left(S\right)$ denote the set of all partitions of $S$. The elements of a partition are called parts.

An equivalent definition of partition is often given: a partition is a set $A$ of nonempty subsets of $S$ that are pairwise disjoint and union to $S$. We choose the above definition because it will make the symmetry between partitions and factorizations more obvious.

Definition 3 (trivial partition). A partition $X$ of a set $S$ is called trivial if $|X|=1$.

Definition 4. Given a partition $X$ of a set $S$, and an element $s\in S$, let $[s{]}_X$ denote the unique $x\in X$ such that $s\in x$.

Definition 5. Given a partition $X$ of a set $S$, and elements $s_0,s_1\in S$, we say $s_0{\sim }_X{s}_1$ if $[s_0{]}_X=[s_1{]}_X$.

Proposition 1. Given a partition $X$ of a set $S$, ${\sim }_X$ is an equivalence relation on $S$.

Proof. Trivial. $\square$

Definition 6 (finer and coarser). We say that a partition $X$ of $S$ is finer than another partition $Y$ of $S$, if for all $s_0,s_1\in S$, if $s_0{\sim }_X{s}_1$, then $s_0{\sim }_Y{s}_1$.

If $X$ is finer than $Y$, we also say $Y$ is coarser than $X$, and we write $X{\ge }_{S}Y$ and $Y{\le }_{S}X$.

Definition 7 (discrete and indiscrete partitions). Given a set $S$, let ${\text{Dis}}_S=\left\{\right\{s\}\mid s\in S\}$.

If $S$ is empty, let ${\text{Ind}}_S=\left\{\right\}$, and if $S$ is nonempty, let ${\text{Ind}}_S=\left\{S\right\}$.

${\text{Dis}}_S$ is called the discrete partition, and ${\text{Ind}}_S$ is called the indiscrete partition.

Proposition 2. For any set $S$, ${\ge }_S$ is a partial order on $\text{Part}\left(S\right)$. Further, for all $X\in Part\left(S\right)$, ${\text{Dis}}_S{\ge }_{S}X$ and $X{\ge }_S{\text{Ind}}_S$.

Proof. Trivial. $\square$

While both notations are sometimes used, it is more standard to draw the symbol in the opposite direction and have $X\le Y$ when $X$ is finer than $Y$. We choose to go against that standard because we want to think of partitions in part as the ability to distinguish between elements, and finer partitions correspond to greater ability to distinguish.[5]

Definition 8 (common refinement). Given a set $C$ of partitions of a fixed set $S$, let ${\bigvee }_S\left(C\right)$ denote the partition $X\in Part\left(S\right)$ satisfying $s_0{\sim }_X{s}_1$ if and only if $s_0{\sim }_c{s}_1$ for all $c\in C$. Given $X,Y\in Part\left(S\right)$, we let $X{\vee }_{S}Y={\bigvee }_S\left(\right\{X,Y\left\}\right)$.

 

2.2. Factorizations

We start with a definition of Cartesian product.

Definition 9 (Cartesian product). Given a set $S$ of sets, let $\sqcap \left(S\right)$ denote the set of all functions $f:S\to \bigsqcup \left(S\right)$ such that for all $T\in S$, $f\left(T\right)$ is of the form $(T,t)$, for some $t\in T$.

We can now give the definition of a factorization of a set.

Definition 10 (factorization). A factorization of a set $S$ is a set $B\subseteq Part\left(S\right)$ of nontrivial partitions of $S$ such that the function $\pi :S\to \sqcap \left(B\right)$, given by $\pi \left(s\right)=(b\mapsto (b,\left[s{]}_b\right))$, is a bijection.

Let $\text{Fact}\left(S\right)$ denote the set of all factorizations of $S$. The elements of a factorization are called factors.

In other words, a set of nontrivial partitions is a factorization of $S$ if for each way of choosing one part from each factor, there exists a unique element of $S$ in the intersection of those parts.

Notice the duality between the definitions of partition and factorization. We replace subsets with partitions, nonempty with nontrivial, and disjoint union with Cartesian product, and we reverse the direction of the function. We can think of a factorization of $S$ as a way to view $S$ as a product, in the same way that a partition was a way to view $S$ as a disjoint union.

A factored set is just a set together with a factorization of that set.

Definition 11 (factored set). A factored set $F$ is an ordered pair $(S,B)$, such that $B$ is a factorization of $S$.

If $F=(S,B)$ is a factored set, we let $\text{set}\left(F\right)=S$, and let $\text{basis}\left(F\right)=B$.

An important fact about factored sets is that the factors are enough to distinguish distinct elements.

Proposition 3. Given a factored set $F=(S,B)$, and elements $s_0,s_1\in S$, if $s_0{\sim }_b{s}_1$ for all $b\in B$, then $s_0=s_1$.

Proof. Let $F=(S,B)$ be a finite factored set, and let $s_0,s_1\in S$ satisfy $s_0{\sim }_b{s}_1$ for all $b\in B$.

Let $\pi :S\to \sqcap \left(B\right)$ be given by $\pi \left(s\right)=(b\mapsto (b,\left[s{]}_b\right))$, as in the definition of factorization. Then $\pi \left(s_0\right)=(b\mapsto (b,\left[s_0{]}_b\right))=(b\mapsto (b,[s_1{]}_b\left)\right)=\pi \left(s_1\right)$. Since $\pi$ is bijective, this means $s_0=s_1$. $\square$

 

2.3. Chimera Functions

The following theorem can be viewed as an alternate characterization of factorization. We will use this alternate characterization to define chimera functions, which will be useful tools for manipulating elements of factored sets.

Theorem 1. Given a set $S$, a set $B$ of nontrivial partitions of $S$ is a factorization of $S$ if and only if for every function $g:B\to S$, there exists a unique $s\in S$ such that for all $b\in B$, $s{\sim }_{b}g\left(b\right)$.

Proof. First, we let $B$ be a factorization of $S$, and let $g:B\to S$ be any function. We want to show that there exists a unique $s\in S$ such that for all $b\in B$, $s{\sim }_{b}g\left(b\right)$. Let $\pi :S\to \sqcap \left(B\right)$ be given by $\pi \left(s\right)=(b\mapsto (b,\left[s{]}_b\right))$, as in the definition of factorization. Note that $\pi$ is bijective, and thus has an inverse.

Let $s={\pi }^{-1}(b\mapsto (b,\left[g\right(b\left){]}_b\right))$. Observe that this is well-defined, because $(b\mapsto (b,\left[g\right(b\left){]}_b\right))$ is in fact in $\sqcap \left(B\right)$. We will show that $s{\sim }_{b}g\left(b\right)$ for all $b\in B$, and the uniqueness of this $s$ will then follow directly from Proposition 3.

We have $\pi \left(s\right)=(b\mapsto [s{]}_b)$ by the definition of $\pi$. However, we also have $\pi \left(s\right)=(b\mapsto [g\left(b\right){]}_b)$ by the definition of $s$. Thus, $b\mapsto [s{]}_b$ and $b\mapsto \left[g\right(b){]}_b$ are the same function, so $[s{]}_b=[g\left(b\right){]}_b$ for all $b\in B$, so $s{\sim }_{b}g\left(b\right)$ for all $b\in B$.

Conversely, let $S$ be any set, and let $B$ be any set of nontrivial partitions of $S$. Assume that for all $g:B\to S$, there exists a unique $s\in S$ satisfying $s{\sim }_{b}g\left(b\right)$ for $b\in B$. Again, let $\pi :S\to \sqcap \left(B\right)$ be given by $\pi \left(s\right)=(b\mapsto (b,\left[s{]}_b\right))$, as in the definition of factorization. We want to show that $\pi$ is invertible.

First, we show that $\pi$ is injective. Take an arbitrary $s_0\in S$, and let $g:B\to S$ be the constant function satisfying $g\left(b\right)=s_0$ for all $b\in B$. Given another $s_1\in S$, if $\pi \left(s_0\right)=\pi \left(s_1\right)$, then $(b\mapsto [s_0{]}_b)=(b\mapsto \left[s_1{]}_b\right)$, so $[s_1{]}_b=[s_0{]}_b=\left[g\right(b){]}_b$ for all $b\in B$, so $s_0{\sim }_b{s}_1{\sim }_{b}g\left(b\right)$ for all $b\in B$. Since there is a unique $s\in S$ satisfying $s{\sim }_{b}g\left(b\right)$ for all $b\in B$, this means $s_0=s_1$. Thus $\pi$ is injective.

To see that $\pi$ is surjective, consider some arbitrary $h\in \sqcap \left(B\right)$. We want to show that there exists an $s\in S$ with $h=\pi \left(s\right)$.

For all $b\in B$, let $H_b\in b$ be given by $h\left(b\right)=(b,H_b)$, which is well-defined since $h\in \sqcap \left(B\right)$. Note that $H_b$ is a nonempty subset of $S$, so there exists a function $g:B\to S$ with $g\left(b\right)\in H_b$ for all $b\in B$. Fix any such $g$, and let $s$ satisfy $s{\sim }_{b}g\left(b\right)$ for all $b\in B$. 

We thus have that for all $b\in B$, $h\left(b\right)=(b,H_b)=(b,[g\left(b\right){]}_b)=(b,\left[s{]}_b\right)=\pi \left(s\right)\left(b\right)$, so $h=\pi \left(s\right)$. Thus $\pi$ is surjective.

Since $\pi$ is bijective, we have that $B$ is a factorization of $S$. $\square$

This also gives us that factors are disjoint from each other.

Corollary 1. Given a factored set $F=(S,B)$ and distinct factors $b_0,b_1\in B$, $b_0\cap b_1=\left\{\right\}$.

Proof. Assume by way of contradiction that $T\in b_0\cap b_1$. Since $b_0$ is nontrivial, there must be some other $T^{\prime }\in b_0$ with $T\cap T^{\prime }=\left\{\right\}$. Let $g:B\to S$ be any function such that $g\left(b_0\right)\in T^{\prime }$ and $g\left(b_1\right)\in T$. Then there can be no $s$ such that $s{\sim }_{b_0}g\left(b_0\right)$ and $s{\sim }_{b_1}g\left(b_1\right)$, since then $s$ would be in both $T$ and $T^{\prime }$. This contradicts Theorem 1. $\square$

We are now ready to define the chimera function of a factored set.

Definition 12 (chimera function). Given a factored set $F=(S,B)$, the chimera function (of $F$) is the function ${\chi }^F:(B\to S)\to S$ defined by ${\chi }^F\left(g\right){\sim }_{b}g\left(b\right)$ for all $g:B\to S$ and $b\in B$.

The name "chimera function" comes from the fact that ${\chi }^F$ can be viewed as building an element of $S$ by fusing together the properties of various different elements. Since we will often apply the chimera function to functions $g$ that only take on two values, we will give notation for this special case.

Definition 13. Given a factored set $F=(S,B)$, and a subset $C\subseteq B$, let ${\chi }_C^F:S\times S\to S$ be given by ${\chi }_C^F(s,t)={\chi }^F\left(g\right)$, where $g:B\to S$ is given by $g\left(b\right)=s$ if $b\in C$, and $g\left(b\right)=t$ otherwise.

For $T,R\subseteq S$, we will write ${\chi }_C^F(T,R)$ for $\left\{{\chi }_C^F\right(t,r)\mid t\in T,r\in R\}$.

The following is a list of properties of ${\chi }_C^F$, which will be useful in later proofs. All of these properties follow directly from the definition of ${\chi }_C^F$.

Proposition 4. Fix $F=(S,B)$, a factored set, $C,D\subseteq B$, and $s,t,r\in S$.

1. ${\chi }_C^F(s,t){\sim }_{c}s$ for all $c\in C$.
2. ${\chi }_C^F(s,t){\sim }_{b}t$ for all $b\in B\setminus C$.
3. ${\chi }_C^F(s,s)=s$.
4. ${\chi }_{B\setminus C}^F(s,t)={\chi }_C^F(t,s)$.
5. ${\chi }_{C\cup D}^F(s,t)={\chi }_C^F(s,{\chi }_D^F(s,t\left)\right)$.
6. ${\chi }_{C\cap D}^F(s,t)={\chi }_C^F\left({\chi }_D^F\right(s,t),t)$.
7. ${\chi }_C^F\left({\chi }_C^F\right(s,t),r)={\chi }_C^F(s,{\chi }_C^F(t,r\left)\right)={\chi }_C^F(s,r)$.
8. ${\chi }_C^F(s,{\chi }_D^F(t,r\left)\right)={\chi }_D^F\left({\chi }_C^F\right(s,t),{\chi }_C^F(s,r\left)\right)$.
9. ${\chi }_C^F\left({\chi }_D^F\right(s,t),r)={\chi }_D^F\left({\chi }_C^F\right(s,r),{\chi }_C^F(t,r\left)\right)$.
10. ${\chi }_B^F(s,t)=s$.
11. ${\chi }_{\left\{\right\}}^F(s,t)=t$.

Proof. Trivial. $\square$

 

2.4. Trivial Factorizations

We now define a notion of a trivial factorization of a set, and show that every set has a unique trivial factorization.

Definition 14 (trivial factorization). A factorization $B$ of a set $S$ is called trivial if $|B|\le 1$. A factored set $(S,B)$ is called trivial if $B$ is trivial.

Proposition 5. For every set $S$, there exists a unique trivial factorization $B$ of $S$. If $|S|\ne 1$, this trivial factorization is given by $B=\left\{{\text{Dis}}_S\right\}$, and if $|S|=1$, it is given by $B=\left\{\right\}$.

Proof. We start with the case where $|S|=0$. The only partition of $S$ is $\left\{\right\}$, so we only need to consider the sets of partitions $\left\{\right\{\left\}\right\}$ and $\left\{\right\}$ as potential factorizations. $\left\{\right\{\left\}\right\}$ is vacuously a factorization of $S$ by Theorem 1, since there are no functions from $\left\{\right\{\left\}\right\}$ to $S$. $\left\{\right\}$ is not a factorization by Theorem 1, since there is a function from $\left\{\right\}$ to $S$, but there is no element of $S$. Thus, when $|S|=0$, $\left\{\right\{\left\}\right\}=\left\{{\text{Dis}}_S\right\}$ is the unique trivial factorization of $S$.

Next, consider the case where $|S|=1$. First, observe that the unique $s\in S$ vacuously satisfies $s{\sim }_{b}g\left(b\right)$ for all $g:\left\{\right\}\to S$ and $b\in \left\{\right\}$, since there is no $b\in \left\{\right\}$. Thus, by Theorem 1, $\left\{\right\}$ is a factorization of $S$. Further, $\left\{\right\}$ is the only factorization of $S$, since there are no nontrivial partitions of $S$. Thus, when $|S|=1$, $\left\{\right\}$ is the unique trivial factorization of $S$.

Next, we consider the case where $|S|\ge 2$. Observe that ${\text{Dis}}_S$ is a nontrivial partition of $S$. Let $B=\left\{{\text{Dis}}_S\right\}$. We want to show that $B$ is a factorization of $S$. By Theorem 1, it suffices to show that for all $g:B\to S$, there exists a unique $s\in S$ with $s{\sim }_{{\text{Dis}}_S}g\left({\text{Dis}}_S\right)$. We can take $s=g\left({\text{Dis}}_S\right)$, which clearly satisfies $s{\sim }_{{\text{Dis}}_S}g\left({\text{Dis}}_S\right)$. This $s$ is unique, since if $s^{\prime }{\sim }_{{\text{Dis}}_S}g\left({\text{Dis}}_S\right)$, then $s^{\prime }\in \left[g\right({\text{Dis}}_S){]}_{{\text{Dis}}_S}=[s{]}_b=\left\{s\right\}$, so $s^{\prime }=s$. Thus $B$ is a factorization of $S$.

On the other hand, if $|S|\ge 2$, $\left\{\right\}$ is not a factorization of $S$, since if it were, Proposition 3 would imply that all elements of $S$ are equal. Further, for any partition $b$ of $S$, with $b\ne \left\{{\text{Dis}}_S\right\}$, there must exist $s_0,s_1\in S$, with $s_0{\sim }_b{s}_1$, but $s_0\ne s_1$. Thus $\left\{b\right\}$ cannot be a factorization of $S$ by Proposition 3. Thus when $|S|\ge 2$, ${\text{Dis}}_S$ is the unique trivial factorization of $S$. $\square$

 

2.5. Finite Factored Sets

This sequence will primarily be about finite factored sets.

Definition 15. If $F=(S,B)$ is a factored set, the size of $F$, written $\text{size}\left(F\right)$, is the cardinality of $S$. The dimension of $F$, written $\text{dim}\left(F\right)$, is the cardinality of $B$. $F$ is called finite if its size is finite, and finite-dimensional if its dimension is finite.

We suspect that the theory of infinite factored sets is both interesting and important. However, it is outside of the scope of this sequence, which will require finiteness for many of its key results.

Some of the definitions and results in this sequence will be given for finite factored sets, in spite of the fact that they could easily be extended to finite-dimensional or arbitrary factored sets. This is because they can often be extended in more than one way, and determining which extension is most natural requires further developing the theory of arbitrary factored sets.

Proposition 6. Every finite factored set is also finite-dimensional.

Proof. If $F=(S,B)$ is a factored set, $B$ is a set of sets of subsets of $S$. Thus, $|B|\le 2^{2^{|S|}}$. $\square$

This bound is horrible and will be improved in Proposition 9. First, however, we will take a look at the number of factorizations of a fixed finite set.

Proposition 7. Let $F=(S,B)$ be a finite factored set. Then $|S|={\prod }_{b\in B}|b|$.

Proof. Trivial. $\square$

Proposition 8. If $|S|$ is equal to $0$, $1$, or a prime, the trivial factorization of $S$ is the only factorization of $S$.

Proof. If $|S|=0$ or $|S|=1$, then $|Part\left(S\right)|=1$, so $B\subseteq Part\left(S\right)$ can have cardinality at most 1.

If $|S|=p$, a prime, then by Proposition 7, $|b|$ must divide $p$ for all $b\in B$. Since factorizations cannot contain trivial partitions, this means $|b|=p$ for all $b\in B$. However, $\left\{\right\{s\}\mid s\in S\}$ is the only element of $Part\left(S\right)$ of cardinality $p$, so $|B|\le 1$. $\square$

On the other hand, in the case where $|S|$ is finite and composite, the number of factorizations of $S$ grows very quickly, as seen in Table 1. Table 1 shows the number of factorizations of a set $S$ with cardinality up to 25:

$|S|$	$|Fact\left(S\right)|$		$|S|$	$|Fact\left(S\right)|$
0	1		13	1
1	1		14	8648641
2	1		15	1816214401
3	1		16	181880899201
4	4		17	1
5	1		18	45951781075201
6	61		19	1
7	1		20	3379365788198401
8	1681		21	1689515283456001
9	5041		22	14079294028801
10	15121		23	1
11	1		24	4454857103544668620801
12	13638241		25	538583682060103680001

Given the naturalness of the notion of factorization, we were surprised to discover that this sequence did not exist on the On-Line Encyclopedia of Integer Sequences (OEIS). We added the sequence, A338681, on April 30, 2021.

To give one concrete example, the four factorizations of  the set $\{0,1,2,3\}$ are:

• $\left\{\right\{\left\{0\right\},\left\{1\right\},\left\{2\right\},\left\{3\right\}\left\}\right\}$,
• $\left\{\right\{\{0,1\},\{2,3\}\},\{\{0,2\},\{1,3\}\left\}\right\}$,
• $\left\{\right\{\{0,1\},\{2,3\}\},\{\{0,3\},\{1,2\}\left\}\right\}$, and
• $\left\{\right\{\{0,2\},\{1,3\}\},\{\{0,3\},\{1,2\}\left\}\right\}$.

Proposition 9. Let $F$ be a finite factored set. 

• If $\text{size}\left(F\right)=0$, then $\text{dim}\left(F\right)=1$.
• If $\text{size}\left(F\right)=1$, then $\text{dim}\left(F\right)=0$.
• If $\text{size}\left(F\right)=p$ is prime, then $\text{dim}\left(F\right)=1$.
• If $\text{size}\left(F\right)=p_0\dots p_{k-1}$ is a product of $k\ge 2$ primes, then $1\le \text{dim}\left(F\right)\le k$.

Proof. The first three parts follow directly from Proposition 5 and Proposition 8. For the fourth part, let $F=(S,B)$, and let $|S|=p_0\dots p_{k-1}$ be a product of $k\ge 2$ primes.

By Proposition 7, $|S|={\prod }_{b\in B}|b|$. Consider an arbitrary $b\in B$. Since $b$ is a nontrivial partition of a finite set $S$, $|b|$ is finite and $|b|\ne 1$. If $|b|$ were $0$, then $|S|$ would be $0$. Thus $|b|$ is a natural number greater than or equal to $2$. $B$ cannot be empty, since $|S|\ne 1$. If $|B|$ were greater than $k$, then we would be able to express $|S|$ as a product of more than $k$ natural numbers greater than or equal to $2$, which is clearly not possible since $|S|$ is a product of $k$ primes. Thus $1\le \text{dim}\left(F\right)\le k$. $\square$

 

In the next post, we will introduce the notions of the history of a partition, orthogonality between partitions, and time.

---

Acknowledgments: My thanks to Alex Appel, Ramana Kumar, Xiaoyu He, Tsvi Benson-Tilsen, Andrew Critch, Sam Eisenstat, Rob Bensinger, and Claire Wang for discussion and feedback on this sequence.

 

Footnotes

[1] Although I say "factorize" here, note that this will not be the kind of factorization that shows up in finite factored sets, because (as we will see) disjoint factors must be independent in a finite factored set. I appeal to the same concept in both contexts because factorization is just a very general and useful concept, rather than to indicate a direct connection.

[2] At least, it lacks such causal inference tools unless we assume access to interventional data.

[3] Note that this definition and Definition 9 could have been made more general by taking $S$ to be a multiset.

[4] $P\left(S\right)$ denotes the power set of $S$.

[5] In our view, "$Y\ge X$" is also a more natural way to visually represent a mapping between a three-part partition $Y$ that is finer than a two-part partition $X$.

2 comments

Comments sorted by top scores.