# Reducing Causality to Functions with Structural Models

Tianyi Miao
University of Pennsylvania
<EMAIL_ADDRESS>
###### Abstract

The precise definition of causality is currently an open problem in philosophy
and statistics. We believe causality should be defined as functions (in
mathematics) that map causes to effects. We propose a reductive definition of
causality based on Structural Functional Model (SFM). Using delta compression
and contrastive forward inference, SFM can produce causal utterances like ”X
causes Y” and ”X is the cause of Y” that match our intuitions. We compile a
dataset of causal scenarios and use SFM in all of them. SFM is compatible with
but not reducible to probability theory. We also compare SFM with other
theories of causation and apply SFM to downstream problems like free will,
causal explanation, and mental causation.

Keywords: Causal Modeling, Causation, Actual Causality

##  1 Introduction

What is causation? What does it mean to say one thing causes another? Is it
possible to define causation in non-causal terms?

We can easily find examples where ”correlation doesn’t imply causation.” Ice
cream sales are positively correlated with deaths by drowning, but ice cream
doesn’t cause drowning. However, this doesn’t tell us what causation really
is. While probabilistic independence and correlation coefficients have clear
mathematical definitions, the precise definition of causality remains a
subject of ongoing debate.

Embracing a functional theory of causation, we argue that causality
essentially is functions that map causes to effects. While functions are
distinct from probability theory and sufficiently general for scientific
purposes, we can place additional constraints and formalize Structural
Functional Model (SFM), which better fit intuitions in causal utterances:

  1. 1.

Forward inference from causes to effects:

     * •

What if X? Y.

     * •

Had it been X, it would have been Y.

  2. 2.

Actual causality (separating ”actual causes” from background conditions):

     * •

X causes/doesn’t cause Y.

     * •

X is/isn’t the cause of Y.

     * •

What is the cause of Y? X.

Throughout this paper, the word ”function” exclusively denotes a mathematical
function (Appendix A). We’ll never use it to mean ”intended purpose or task”
as in ”the functions of cellphones include texting.” The word ”functional” is
only used as the adjective form of ”function.”

For SFM, we’ll explicitly separate its representation, inference, and learning
[Koller and Friedman, 2009]:

  * •

Representation is the declarative model of ”what the world is like.”

  * •

Inference assumes the representation is correct and answers queries regarding
particular instances, such as computing values of unknown variables given
known variables.

  * •

Learning inductively constructs a representation from empirical data.

Such decoupling allows us to design general-purpose inference and learning
algorithms that work for different task-specific representations.

##  2 Representation: A Roadmap

In this section, we build the representation of SFM by incrementally adding
functions, directed graphs, composition, contrast, and delta compression into
a unified model. Each additional component will help SFM better fit intuitions
about causal utterances, sometimes at the cost of generality.

Motivated by theoretical and pragmatic benefits like simplicity,
expressiveness, and computational efficiency, the definition of SFM is
unambiguous, mathematical, and reductive. It contains no circular definition
because it doesn’t rely on causal concepts like intervention and agency.

###  2.1 Causal Relata

When we say ”$X$ causes $Y$”, what kinds of things are $X$ and $Y$? How do we
represent a world? Classifying by causal relata, there are 4 kinds of causal
relationships [Gallow, 2022]:

  * •

Token causation: I frequently water my flower in my garden, causing it to grow
tall.

  * •

Type causation: Watering a plant frequently causes it to grow tall.

  * •

Token influence: How much I water my flower in my garden influences how tall
it grows.

  * •

Type influence: How much a plant is watered influences how tall it grows.

Influence relates variables (a variable can have one of many values);
causation relates values of variables.

Tokens are specific; types are general. Since this type-token distinction
applies to non-causal models too, it’s not central to causality. SFM doesn’t
endorse any particular theory of physics or metaphysics, so it’s up to the
user to specify how variables correspond to real-world things.

Formally, let $\mathcal{V}$ be a set of nodes (we use ”nodes” instead of
”variables” to avoid confusion with random variables) and $\mathcal{D}$ be a
function that maps nodes to their domains. For node $u\in\mathcal{V}$, its
domain $\mathcal{D}[u]$ is the set of values it can take on. An assignment is
a function that maps each node to a value in its domain.

  * •

A complete assignment
$\mathbf{w}:\mathcal{V}\to\bigcup_{u\in\mathcal{V}}\mathcal{D}[u]$ assigns
values to all nodes, satisfying $\forall
u\in\mathcal{V}:\mathbf{w}(u)\in\mathcal{D}[u]$.

  * •

A partial assignment
$\mathbf{w}_{|\mathcal{X}}:\mathcal{X}\to\bigcup_{u\in\mathcal{X}}\mathcal{D}[u]$
assigns values to a subset $\mathcal{X}\subseteq\mathcal{V}$ of nodes,
satisfying $\forall
u\in\mathcal{X}:\mathbf{w}_{|\mathcal{X}}(u)\in\mathcal{D}[u]$.

  * •

$\mathbf{w}_{|\mathcal{X}}\subseteq\mathbf{w}$ iff $\forall
u\in\mathcal{X}:\mathbf{w}_{|\mathcal{X}}(u)=\mathbf{w}(u)$.

We use dictionary notations {node1:value1, node2:value2, …} for assignments
(and discrete finite functions in general). Nodes, values, and assignments are
different things. Influence relates nodes (Water influences Growth), while
causation relates assignments ({Water:High} causes {Growth:Tall}).

  1. 1.

The set of all complete assignments forms the Cartesian product
$\prod_{u\in\mathcal{V}}\mathcal{D}[u]$.

  2. 2.

A team $R$ is a set of complete assignments [Väänänen, 2007], so
$R\subseteq\prod_{u\in\mathcal{V}}\mathcal{D}[u]$. $R$ is a relation.

  3. 3.

For a modal/counterfactual/possible-world interpretation, each complete
assignment $\mathbf{w}$ is a world. Each node is a
feature/property/aspect/variable of the world. $R$ is the set of possible
worlds; $(\prod_{u\in\mathcal{V}}\mathcal{D}[u])\setminus R$ is the set of
impossible worlds.

  4. 4.

For a database interpretation, each $\mathbf{w}$ is an
individual/person/record/item. $R$ is a population containing many
individuals. Each node is a property/attribute/feature of that individual.

  5. 5.

A complete assignment $\mathbf{w}$ satisfies team $R$ iff $\mathbf{w}\in R$.

  6. 6.

A team $R$ is satisfiable iff $R$ is nonempty. $R$ is unsatisfiable iff
$R=\emptyset$.

  7. 7.

If any domain $\mathcal{D}[u]$ is empty, the Cartesian product
$\prod_{u\in\mathcal{V}}\mathcal{D}[u]$ is empty and there’s no satisfiable
$R$, so we’ll only consider nonempty domains.

  8. 8.

An assignment $\mathbf{w}_{|\mathcal{X}}$ is permitted by $R$ iff
$\exists\mathbf{w}\in R:\mathbf{w}\supseteq\mathbf{w}_{|\mathcal{X}}$. We call
this $\mathbf{w}$ an induced complete assignment of
$\mathbf{w}_{|\mathcal{X}}$.

  9. 9.

Partial assignments
$\mathbf{w}_{|\mathcal{X}_{1}},\mathbf{w}_{|\mathcal{X}_{2}},\dots,\mathbf{w}_{|\mathcal{X}_{k}}$
are compatible with each other iff $\exists\mathbf{w}\in R:\forall
i\in\\{1,2,\dots,k\\}:\mathbf{w}\supseteq\mathbf{w}_{|\mathcal{X}_{i}}$.

We will say ”$\mathcal{X}$ influences $\mathcal{Y}$” and
”$\mathbf{w}_{|\mathcal{X}}$ causes $\mathbf{w}_{|\mathcal{Y}}$,” where
$\mathcal{X}$ and $\mathcal{Y}$ are sets of nodes; $\mathbf{w}_{|\mathcal{X}}$
and $\mathbf{w}_{|\mathcal{Y}}$ are partial assignments.

###  2.2 A Functional Theory of Causation

Many causal scenarios are not reducible to probability theory. For example,
flipping the light switch turns on the light, but doesn’t affect the TV. This
system of electric circuits is deterministic and fully-specified. We can
consistently predict the ”independence” between light switch and TV and what
would happen given the switches’ status, using functions alone without
probabilities.

According to the functional theory of causality, causality essentially is
mathematical functions (left-total, right-unique relations) that map causes to
effects. Russell [1912] briefly mentions that the cause (functionally)
determines the effect. Simon and Rescher [1966] explicitly defend that
causation is ”a function of one variable (the cause) on to another (the
effect).” Structural Causal Model (SCM) [Pearl, 2009a] uses multi-input
single-output functions in structural equations to represent ”laws” or
”mechanisms” of the world.

”Causality as functions” becomes immediately obvious once it’s pointed out.
For example,

  1. 1.

In $y=f(x)$, we call $x$ the independent variable and $y$ the dependent
variable, like how effects depend on causes.

  2. 2.

Describing ”rain influences wheat growth” with
$\texttt{WheatGrowth}=f(\texttt{Rain})$, the input-output mappings are:

     * •

With no rain, wheat doesn’t grow.

     * •

With moderate rain, wheat grows moderately.

     * •

With heavy rain, wheat grows very well.

  3. 3.

The light-switch-and-TV example can be described by
$\texttt{Light}=f_{1}(\texttt{LightSwitch})$ and
$\texttt{TV}=f_{2}(\texttt{TVSwitch})$.

Two key properties distinguish functions from other kinds of relations:

  1. 1.

Right-uniqueness: 1 input value cannot simultaneously associate with 2 or more
different output values. Functions can only be many-to-one or one-to-one,
never one-to-many. This explains why causes ”necessitate” or ”are sufficient
for” their effects (given the underlying function).

  2. 2.

(Possible) non-injectiveness: Some functions can map different input values to
the same output value, like $y=x^{2}$ over real numbers. Non-injective
functions cannot be inverted. This explains the asymmetry of causation:
different causes can lead to the same effect.

Functional dependencies are properties of a team
$R\subseteq\prod_{u\in\mathcal{V}}\mathcal{D}[u]$: For
$\mathcal{X},\mathcal{Y}\subseteq\mathcal{V}$,

  1. 1.

Value-level dependency: We say ”$\mathcal{Y}$ functionally depends on
$\mathbf{w}_{|\mathcal{X}}$”
($\mathbf{w}_{|\mathcal{X}}\xrightarrow{.}\mathcal{Y}$) or
”$\mathbf{w}_{|\mathcal{Y}}$ functionally depends on
$\mathbf{w}_{|\mathcal{X}}$”
($\mathbf{w}_{|\mathcal{X}}\xrightarrow{.}\mathbf{w}_{|\mathcal{Y}}$) when
given $\mathbf{w}_{|\mathcal{X}}$, there exists exactly one
$\mathbf{w}_{|\mathcal{Y}}$ that’s compatible with
$\mathbf{w}_{|\mathcal{X}}$.

  2. 2.

Node-level dependency: We say ”$\mathcal{Y}$ functionally depends on
$\mathcal{X}$” ($\mathcal{X}\xrightarrow{.}\mathcal{Y}$) when
$\mathbf{w}_{|\mathcal{X}}\xrightarrow{.}\mathcal{Y}$ for every permitted
$\mathbf{w}_{|\mathcal{X}}$.

  3. 3.

Value-level and node-level dependencies can be different. In
$\mathbf{w}(Y)=\mathbf{w}(X_{1})\lor\mathbf{w}(X_{2})\lor\mathbf{w}(X_{3})$,
value-level $\\{X_{1}:1\\}\xrightarrow{.}\\{Y:1\\}$ is true; node-level
$\\{X_{1}\\}\xrightarrow{.}\\{Y\\}$ is false; node-level
$\\{X_{1},X_{2},X_{3}\\}\xrightarrow{.}\\{Y\\}$ is true.

Node-level functional dependency $\mathcal{X}\xrightarrow{.}\mathcal{Y}$
satisfies right-uniqueness: $\forall\mathbf{w}_{1},\mathbf{w}_{2}\in
R:(\mathbf{w}_{1|\mathcal{X}}=\mathbf{w}_{2|\mathcal{X}})\Rightarrow(\mathbf{w}_{1|\mathcal{Y}}=\mathbf{w}_{2|\mathcal{Y}})$.
So there’s a function $f:\\{\mathbf{w}_{|\mathcal{X}}\ |\exists\mathbf{w}\in
R:\mathbf{w}\supseteq\mathbf{w}_{|\mathcal{X}}\\}\to\\{\mathbf{w}_{|\mathcal{Y}}\
|\exists\mathbf{w}\in R:\mathbf{w}\supseteq\mathbf{w}_{|\mathcal{Y}}\\}$ such
that $\forall\mathbf{w}\in
R:\mathbf{w}_{|\mathcal{Y}}=f(\mathbf{w}_{|\mathcal{X}})$. We thus define
functional determination:

  1. 1.

Node-level determination: We say ”$\mathcal{X}$ functionally determines
$\mathcal{Y}$ via $f$” ($\mathcal{X}\xrightarrow{f}\mathcal{Y}$) when
$\forall\mathbf{w}\in
R:\mathbf{w}_{|\mathcal{Y}}=f(\mathbf{w}_{|\mathcal{X}})$.

  2. 2.

Value-level determination: We say ”$\mathbf{w}_{|\mathcal{X}}$ functionally
determines $\mathbf{w}_{|\mathcal{Y}}$ via $f$”
($\mathbf{w}_{|\mathcal{X}}\xrightarrow{f}\mathbf{w}_{|\mathcal{Y}}$) when
$\mathcal{X}\xrightarrow{f}\mathcal{Y}$ and
$\mathbf{w}_{|\mathcal{Y}}=f(\mathbf{w}_{|\mathcal{X}})$.

In compliance with conventions from dependence logic [Galliani, 2021] and
relational databases [Silberschatz et al., 2020], functional dependency
$\mathcal{X}\xrightarrow{.}\mathcal{Y}$ doesn’t contain $f$, while our
functional determination $\mathcal{X}\xrightarrow{f}\mathcal{Y}$ does.

Influence is node-level functional determination; causation is value-level
functional determination. In
$\mathbf{w}_{|\mathcal{Y}}=f(\mathbf{w}_{|\mathcal{X}})$,
$\mathbf{w}_{|\mathcal{X}}$ is the cause, $\mathbf{w}_{|\mathcal{Y}}$ is the
effect, and $f$ is an underlying mechanism/law-of-nature (since
$\mathbf{w}_{|\mathcal{Y}}=f(\mathbf{w}_{|\mathcal{X}})$ is true in every
possible world $\mathbf{w}\in R$).

Generally, causality is the study of functional dependency (e.g. Armstrong’s
Axioms), functional determination, and relational independence [Grädel and
Väänänen, 2013]. It’s nontrivial because these concepts cannot be reduced to
probability theory.

We say ”$\mathbf{w}_{|\mathcal{X}}$ causes $\mathbf{w}_{|\mathcal{Y}}$” when
$\mathcal{X}\xrightarrow{f}\mathcal{Y}$ and
$\mathbf{w}_{|\mathcal{Y}}=f(\mathbf{w}_{|\mathcal{X}})$. We say
”$\mathcal{X}$ influences $\mathcal{Y}$” when
$\mathcal{X}\xrightarrow{.}\mathcal{Y}$.

###  2.3 Directed Graphs

Previously, we first have a team $R$ and then find functional determinations
as properties of $R$. Now we take the opposite direction. We start with a set
of functional determinations
$\textbf{FDet}=\\{\mathcal{X}_{1}\xrightarrow{f_{1}}\mathcal{Y}_{1},\mathcal{X}_{2}\xrightarrow{f_{2}}\mathcal{Y}_{2},\dots\mathcal{X}_{n}\xrightarrow{f_{n}}\mathcal{Y}_{n}\\}$,
which then select
$R_{\textbf{FDet}}\subseteq\prod_{u\in\mathcal{V}}\mathcal{D}[u]$ as all
$\mathbf{w}$ that satisfies FDet. Here ”all” is necessary for defining a
unique $R_{\textbf{FDet}}$, because functional dependencies and determinations
are downward-closed (if $R_{1}$ satisfies FDet, then any subset
$R_{2}\subseteq R_{1}$ also satisfies FDet [Galliani, 2021]).

When we draw diagrams to illustrate causal relationships, we want arrows to
point from causes to effects. Structural Causal Model (SCM) [Pearl, 2009a, b,
Halpern and Pearl, 2005] generalizes this intuition, subsumes the graphical
and potential-outcome frameworks, and is the most popular causal model in
statistics, econometrics, and epidemiology. Our SFM inherits the following
ideas from SCM:

  1. 1.

A causal system is represented as a (usually finite and acyclic) directed
graph.

  2. 2.

One mechanism’s effect can be another mechanism’s cause. One function’s output
can be another function’s input.

  3. 3.

A node’s value is functionally determined by the values of its parents.

  4. 4.

Unlike SCM, our SFM doesn’t use ”intervention” in its definition at all
(Section 8.4).

Besides nodes $\mathcal{V}$ and domains $\mathcal{D}$, an SFM
$\mathcal{M}=(\mathcal{V},\mathcal{E},\mathcal{D},\mathcal{F})$ also has:

  1. 1.

$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is a set of directed edges.

  2. 2.

In a directed graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, a node $u$ is
exogenous (exo-node $u\in\mathcal{V}_{exo}$) iff it’s a root node; otherwise,
it’s endogenous (endo-node $u\in\mathcal{V}_{endo}$).

  3. 3.

We write exo-assignment $\mathbf{w}_{|\mathcal{V}_{exo}}$ as
$\mathbf{w}_{exo}$ and endo-assignment $\mathbf{w}_{|\mathcal{V}_{endo}}$ as
$\mathbf{w}_{endo}$.

  4. 4.

$\mathcal{F}$ maps every endo-node $u\in\mathcal{V}_{endo}$ to exactly one
structural function
$\mathcal{F}[u]:(\prod_{p\in\mathrm{Pa}(u)}\mathcal{D}[p])\to\mathcal{D}[u]$.

  5. 5.

$\mathcal{F}[u]:\mathbf{w}_{|\mathrm{Pa}(u)}\mapsto\mathbf{w}(u)$ maps an
assignment over $u$’s parents to a value of $u$.

  6. 6.

$R_{\mathcal{M}}=\\{\mathbf{w}\in\prod_{u\in\mathcal{V}}\mathcal{D}[u]\ |\
\forall
u\in\mathcal{V}_{endo}:\mathbf{w}(u)=\mathcal{F}[u](\mathbf{w}_{|\mathrm{Pa}(u)})\\}$
is the set of all complete assignments satisfying $\mathcal{M}$.

Equivalently, $\mathcal{M}$ specifies functional determinations
$\textbf{FDet}_{\mathcal{M}}=\\{\mathrm{Pa}(u)\xrightarrow{f_{u}}\\{u\\}\\}_{u\in\mathcal{V}_{endo}}$,
where
$f_{u}(\mathbf{w}_{|\mathrm{Pa}(u)})=\\{u:\mathcal{F}[u](\mathbf{w}_{|\mathrm{Pa}(u)})\\}$.

######  Example 2.1.

Consider SFM $\mathcal{M}=(\mathcal{V},\mathcal{E},\mathcal{D},\mathcal{F})$:

  * •

$\mathcal{V}=\\{A,B,C,D,E\\}$

  * •

$\mathcal{E}=\\{(A,B),(B,D),(C,D),(C,E)\\}$

  * •

$\mathcal{D}=\\{A:\mathbb{R},B:\mathbb{R},C:\mathbb{R},D:\mathbb{R},E:\mathbb{R}\\}$

  * •

For simplicity, we’ll abuse notations and write
$\mathcal{F}[u](\mathbf{w}_{|\mathrm{Pa}(u)})$ as
$\mathcal{F}[u](\mathbf{w})$:

$\mathcal{F}[B](\mathbf{w})=\mathbf{w}(A)^{2}\\\
\mathcal{F}[D](\mathbf{w})=\mathbf{w}(B)+\mathbf{w}(C)\\\
\mathcal{F}[E](\mathbf{w})=\mathbf{w}(C)\times 7$

ABCDE$\mathcal{F}[B](\mathbf{w})=\mathbf{w}(A)^{2}$$\mathcal{F}[D](\mathbf{w})=\mathbf{w}(B)+\mathbf{w}(C)$$\mathcal{F}[E](\mathbf{w})=\mathbf{w}(C)\times
7$ Figure 1: A simple finite acyclic SFM.

  * •

$A,C\in\mathcal{V}_{exo}$ are exo-nodes; $B,D,E\in\mathcal{V}_{endo}$ are
endo-nodes.

  * •

$A\to B\to D$ forms a causal chain, $B\to D\leftarrow C$ forms a ”common
effect” structure, and $D\leftarrow C\to E$ forms a ”common cause” structure.

  * •

$\\{A:i,B:-1,C:10,D:9,E:70\\}$ isn’t an assignment over
$(\mathcal{V},\mathcal{D})$, because the complex number $i\notin\mathbb{R}$ is
outside of $A$’s domain.

  * •

$\\{A:2,B:2,C:2,D:2,E:2\\}$ is a complete assignment over
$(\mathcal{V},\mathcal{D})$, but it doesn’t satisfy $\mathcal{M}$.

  * •

$\\{A:3,B:9,C:-\pi,D:9-\pi,E:-7\pi\\}$ is a complete assignment that satisfies
$\mathcal{F}$, so $\mathcal{M}$ is satisfiable.

  * •

Therefore, partial assignments $\\{A:3,B:9\\}$ and $\\{D:9-\pi,E:-7\pi\\}$ are
permitted and compatible with each other.

  * •

$\\{D:-10,E:7\\}$ isn’t permitted because no $\mathbf{w}\in R_{\mathcal{M}}$
extends it.

Some design choices of SFM inevitably restrict the kinds of functional
dependencies that we can talk about:

  1. 1.

For simplicity, we only consider finite nodes because no important application
requires an infinite SFM.

  2. 2.

Not every set of functional determinations be covered (entailed) by an SFM,
even if we allow cycles.

Consider $\mathcal{V}=\\{X,Y,Z\\}$ with real-valued domains, the team
$R_{1}=\\{\mathbf{w}|\ \mathbf{w}(X)^{2}=\mathbf{w}(Y)=\mathbf{w}(Z)^{2}\\}$
has functional determinations
$\\{X\\}\xrightarrow{\mathbf{w}(Y)=\mathbf{w}(X)^{2}}\\{Y\\}$ and
$\\{Z\\}\xrightarrow{\mathbf{w}(Y)=\mathbf{w}(Z)^{2}}\\{Y\\}$. There’s no SFM
$\mathcal{M}$ with $R_{\mathcal{M}}=R_{1}$.

Generally, SFM cannot represent one node being functionally determined by
multiple ”separate” functions/mechanisms, each individually sufficient for its
value. This differs from symmetric overdetermination (Section 5.7), which is
just multi-input Boolean OR.

  3. 3.

The intersection of SFMs, however, can cover any set of functional
determinations.

We say $\mathbf{w}$ satisfies the SFM-intersection over
$(\mathcal{M}_{1},\mathcal{M}_{2},\dots,\mathcal{M}_{n})$ if
$\mathbf{w}\in\bigcap_{i=1}^{n}R_{\mathcal{M}_{i}}$ ($\mathbf{w}$ satisfies
every individual $\mathcal{M}_{i}$).

######  Theorem 2.1.

For any set of functional determinations FDet over finite $\mathcal{V}$, there
exists a finite SFM-intersection that covers it.

###### Proof.

Since $\mathcal{V}$ is finite, FDet is finite. For every
$\mathcal{X}_{i}\xrightarrow{f_{i}}\mathcal{Y}_{i}$ in FDet, we construct
$\mathcal{M}_{i}=(\mathcal{V},\mathcal{E}_{i},\mathcal{D},\mathcal{F}_{i})$
with edges $\mathcal{E}_{i}=\mathcal{X}_{i}\times\mathcal{Y}_{i}$ and
structural functions $\mathcal{F}_{i}[y]:\mathbf{w}_{|\mathcal{X}_{i}}\mapsto
f_{i}(\mathbf{w}_{|\mathcal{X}_{i}})(y)$ for $y\in\mathcal{Y}_{i}$. The SFM-
intersection over all $\mathcal{M}_{i}$ entails FDet. ∎

An SFM-intersection-proper is an SFM-intersection that cannot be entailed by
an SFM.

Besides $\mathbf{w}(X)^{2}=\mathbf{w}(Y)=\mathbf{w}(Z)^{2}$, SFM-intersection-
proper can express autonomous differential equations like
$\frac{d}{dt}x(t)=f(x(t))$ while SFM cannot. The differential operator
$\frac{d}{dt}$ is also a function, so we derive 2 functional determinations:
$A\xrightarrow{\frac{d}{dt}}B$ and $A\xrightarrow{f}B$. Here
$\\{A:x(t),B:x^{\prime}(t)\\}$ is permitted iff $x^{\prime}(t)=f(x(t))$.

  4. 4.

Why do people dislike SFM-intersection?

It’s nearly impossible to find an uncontrived, everyday causal system that’s
only describable by SFM-intersection-proper. Kim [2005] even explicitly
formulates the Principle of Causal Exclusion against ”more than one sufficient
cause” in this spirit. This intuitive dislike is unjustified, but when taken
as a primitive desideratum, it entails people’s preference of some SFMs over
others for modeling reality.

We suggest 2 possible reasons for disliking SFM-intersection-proper:

    1. (a)

Intersection of multiple SFMs creates too much mental computational burden and
people prefer simpler models.

In many cases (Section 4.2, 9.7), people dislike the very form of SFM-
intersection, even though the underlying $R=R_{\mathcal{M}}$ can be modeled by
some SFM $\mathcal{M}$.

    2. (b)

SFM-intersection-proper suffers from the possibly-unsatisfiable-laws objection
(PULO), which applies to any set of functional dependencies
$\textbf{FDep}=\\{\mathcal{X}_{i}\xrightarrow{.}\mathcal{Y}_{i}\\}_{i=1}^{n}$
such that some $\\{f_{i}\\}_{i=1}^{n}$ makes
$\textbf{FDet}=\\{\mathcal{X}_{i}\xrightarrow{f_{i}}\mathcal{Y}_{i}\\}_{i=1}^{n}$
unsatisfiable.

No world satisfies FDet, but our actual world exists, so we must reject FDet.
PULO takes one unjustified step further, suggesting that FDep should also be
rejected, even if some other $\\{g_{i}\\}_{i=1}^{n}$ makes
$\\{\mathcal{X}_{i}\xrightarrow{g_{i}}\mathcal{Y}_{i}\\}_{i=1}^{n}$
satisfiable, because FDep ”opens the gate” to unsatisfiable laws. From another
perspective, PULO expresses a desire for guaranteed satisfiability under any
function set.

For example,
$\textbf{FDep}=\\{\\{X\\}\xrightarrow{.}\\{Y\\},\\{Z\\}\xrightarrow{.}\\{Y\\}\\}$
suffers from PULO because
$\textbf{FDet}=\\{\\{X\\}\xrightarrow{\mathbf{w}(Y)=\mathbf{w}(X)^{2}}\\{Y\\},\\{Z\\}\xrightarrow{\mathbf{w}(Y)=-\mathbf{w}(Z)^{2}-1}\\{Y\\}\\}$
is unsatisfiable over real-valued domains.

  5. 5.

Why do we make SFM acyclic?

PULO strikes again: When there are self-loops or cycles in the graph, there
exist function sets that make the SFM unsatisfiable, such as $A=A+1$ and
$\\{A=B+1;B=A+1\\}$:

A$\mathcal{F}[A](\mathbf{w})=\mathbf{w}(A)+1$

AB$\mathcal{F}[B](\mathbf{w})=\mathbf{w}(A)+1$$\mathcal{F}[A](\mathbf{w})=\mathbf{w}(B)+1$

Figure 2: SFM with a self-loop (left) and SFM with a cycle (right); their
structural functions are not satisfiable over real-valued domains.

  6. 6.

Besides simplicity and intuitive appeals, finite acyclic SFM $\mathcal{M}$ has
other nice properties (Section 3.2):

     * •

$\mathcal{M}$ is satisfiable for any $\mathcal{F}$.

     * •

$\mathcal{V}_{exo}$ functionally determines $\mathcal{V}_{endo}$ via
$\mathbf{w}_{endo}\subseteq\mathbf{w}=\texttt{VFI}(\mathcal{M},\mathbf{w}_{exo})$.

Are they worth the price of rejecting many (possibly satisfiable) sets of
functional dependencies? We’re unsure.

  7. 7.

Different SFMs $\mathcal{M}_{1}\neq\mathcal{M}_{2}$ over the same
$(\mathcal{V},\mathcal{D})$ can be ”semantically equivalent”
$R_{\mathcal{M}_{1}}=R_{\mathcal{M}_{2}}$, which entails
”$\mathbf{w}_{|\mathcal{Y}}=f(\mathbf{w}_{|\mathcal{X}})$ in $\mathcal{M}_{1}$
iff $\mathbf{w}_{|\mathcal{Y}}=f(\mathbf{w}_{|\mathcal{X}})$ in
$\mathcal{M}_{2}$”, including
$\texttt{VFI}(\mathcal{M}_{1},\mathbf{w}_{exo})=\texttt{VFI}(\mathcal{M}_{2},\mathbf{w}_{exo})$
for all $\mathbf{w}_{exo}$.

We’ll only consider functional determinations that can be modeled by finite
acyclic SFMs, where an endo-node is functionally determined by its parents.

###  2.4 Composition and Decomposition

Since $\mathbf{w}_{exo}$ functionally determines $\mathbf{w}_{endo}$ via
$\mathbf{w}_{endo}\subseteq\texttt{VFI}(\mathcal{M},\mathbf{w}_{exo})$
(Section 3.2), we produce all causal utterances as ”$\mathbf{w}_{exo}$ causes
$\mathbf{w}_{endo}$.”

This syntax is simple, but an ostensible flaw is that only exo-assignments can
be causes. In $A\to B\to C$, we cannot say ”$\\{B:b\\}$ causes $\\{C:c\\}$”
because $B$ is an endo-node. This problem is solved by considering the sub-SFM
$B\to C$, where $B$ becomes an exo-node. Sub-SFM generalizes Pearl [2009a]’s
surgical intervention, which cuts off all incoming edges to the nodes under
intervention.

$\mathcal{M}_{sub}=(\mathcal{V}_{sub},\mathcal{E}_{sub},\mathcal{D}_{sub},\mathcal{F}_{sub})$
is a sub-SFM of
$\mathcal{M}=(\mathcal{V},\mathcal{E},\mathcal{D},\mathcal{F})$ when:

  1. 1.

$(\mathcal{V}_{sub},\mathcal{E}_{sub})$ is a subgraph of
$(\mathcal{V},\mathcal{E})$, i.e. $\mathcal{V}_{sub}\subseteq\mathcal{V}$,
$\mathcal{E}_{sub}\subseteq\mathcal{E}$, and
$(u,v)\in\mathcal{E}_{sub}\Rightarrow(u\in\mathcal{V}_{sub})\land(v\in\mathcal{V}_{sub})$.

  2. 2.

$\forall u\in\mathcal{V}_{sub|endo}:\mathrm{Pa}_{sub}(u)=\mathrm{Pa}(u)$.

  3. 3.

$\forall u\in\mathcal{V}_{sub}:\mathcal{D}_{sub}[u]=\mathcal{D}[u]$

  4. 4.

$\forall u\in\mathcal{V}_{sub|endo}:\mathcal{F}_{sub}[u]=\mathcal{F}[u]$

An exo-node in $\mathcal{M}$ can be nonexistent or exogenous in
$\mathcal{M}_{sub}$; an endo-node in $\mathcal{M}$ can be nonexistent,
exogenous, or endogenous (with the same parents and structural function) in
$\mathcal{M}_{sub}$, so the mechanisms-of-nature are preserved.

We can compose a set of smaller SFMs
$\\{\mathcal{M}_{1},\mathcal{M}_{2},\dots,\mathcal{M}_{m}\\}$ into a bigger
SFM $\mathcal{M}$ without altering any structural function, if the following
prerequisites are met for any pair of $(\mathcal{M}_{i},\mathcal{M}_{j})$:

  1. 1.

$\forall
u\in\mathcal{V}_{i}\cap\mathcal{V}_{j}:\mathcal{D}_{i}[u]=\mathcal{D}_{j}[u]$

  2. 2.

$\forall
u\in\mathcal{V}_{i|endo}\cap\mathcal{V}_{j|endo}:\mathrm{Pa}_{i}(u)=\mathrm{Pa}_{j}(u)$

  3. 3.

$\forall
u\in\mathcal{V}_{i|endo}\cap\mathcal{V}_{j|endo}:\mathcal{F}_{i}(u)=\mathcal{F}_{j}(u)$

These prerequisites ensure that the composition
$\mathcal{M}=(\bigcup_{i=1}^{m}\mathcal{V}_{i},\bigcup_{i=1}^{m}\mathcal{E}_{i},\bigcup_{i=1}^{m}\mathcal{D}_{i},\bigcup_{i=1}^{m}\mathcal{F}_{i})$
is well-defined. For $\bigcup_{i=1}^{m}\mathcal{D}_{i}$ and
$\bigcup_{i=1}^{m}\mathcal{F}_{i}$,

  1. 1.

$\mathcal{D}_{i}$ maps nodes to domains.

  2. 2.

$\mathcal{F}_{i}$ maps nodes to structural functions.

  3. 3.

Functions (including $\mathcal{D}$ and $\mathcal{F}$) are binary relations.

  4. 4.

The union of sets/relations/functions is well defined.

  5. 5.

The prerequisites ensure that each node $u$ has exactly one unique
$\mathcal{D}[u]$ and at most one unique $\mathcal{F}[u]$ across all $i$, so
$\bigcup_{i=1}^{m}\mathcal{D}_{i}$ and $\bigcup_{i=1}^{m}\mathcal{F}_{i}$ are
right-unique and thus functions.

The decomposition of SFM $\mathcal{M}$ is a set of sub-SFMs
$\\{\mathcal{M}_{1},\mathcal{M}_{2},\dots,\mathcal{M}_{m}\\}$ that can compose
into $\mathcal{M}$. While composition of sub-SFMs (when allowed) is unique,
there can be multiple different decompositions of an SFM, the most trivial
being ”keeping the original SFM itself” and the most fragmented being ”one
sub-SFM for each endo-node and its parents.”

Composition shows how small, local, and simple sub-mechanisms can be pieced
together into one big, global, and complex system, while decomposition breaks
down a large system into small sub-mechanisms. Therefore, we can deductively
reason about a big, unrepeatable event using its components and their
interconnections.

With composition-decomposition, we can say ”$\mathbf{w}_{exo}$ causes
$\mathbf{w}_{endo}$” relative to some sub-SFM.

###  2.5 Contrastive Causation

Currently, SFM can already perfectly express a causal system by correctly
answering all ”what’s $\mathbf{w}_{endo}$ if $\mathbf{w}_{exo}$” questions.
But in causal utterances, people only say ”the actual causes” and omit
background conditions (Section 5.11). The selection of actual causes takes 2
steps: contrast and omission. We’ll discuss contrast in this section.

Schaffer [2005] believes causation is contrastive. Besides the 2-argument
surface form (cause, effect), the 4-argument underlying form includes contrast
on both sides:

  * •

Surface form: Pam’s throwing the rock caused the window to shatter.

  * •

Contrastive form 1: Throwing the rock (rather than the pebble) caused the
window to shatter (rather than crack).

  * •

Contrastive form 2: Throwing the rock (rather than not throwing it) caused the
window to shatter (rather than remain intact).

We specify 2 assignments $\mathbf{w}_{a},\mathbf{w}_{c}$ for contrastive
causal utterance ”$\mathbf{w}_{a|exo}$ (rather than $\mathbf{w}_{c|exo}$)
causes $\mathbf{w}_{a|endo}$ (rather than $\mathbf{w}_{c|endo}$)”:

  1. 1.

Actual assignment $\mathbf{w}_{a}$ corresponds to the actual world (i.e. what
actually happens).

  2. 2.

Contrastive assignment $\mathbf{w}_{c}$ is selected using one of two
heuristics:

    1. (a)

$\mathbf{w}_{c}$ is a default/expected/normal/typical world; $\mathbf{w}_{a}$
is an anomalous/unexpected deviation from the default.

Normality inevitably comes with value judgments, but contrast reduces ”finding
the actual causes” to ”finding a default world,” which is a nontrivial
simplification.

    2. (b)

With $\mathbf{w}_{a}$ available first, we tweak $\mathbf{w}_{a|exo}$ into
$\mathbf{w}_{c|exo}$ by changing the values of a few exo-nodes of interest. We
then obtain
$\mathbf{w}_{c}=\texttt{VFI}(\mathcal{M},\mathbf{w}_{c|exo})=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|exo})$
through forward inference (Section 3.2).

This is common when too many nodes in $\mathbf{w}_{a}$ have non-default
values, or when there’s no appropriate default world.

Our contrastive causation is slightly simpler than Schaffer [2005]’s and
Halpern and Hitchcock [2015]’s, because we only need to specify one
contrastive world $\mathbf{w}_{c}$ (rather than many).

Contrast is common in our causal intuition:

  1. 1.

People often characterize causality as ”changing the cause will also change
the effect” or ”making a difference.” Ignoring the manipulation aspect of an
agent changing an object, change is inherently contrastive - there’s an old
state that changes to a new state.

  2. 2.

Some philosophers try to define ”event $X$ causes event $Y$” as ”$X$ raises
the probability of $Y$ ($\Pr[Y|X]>\Pr[Y|\lnot X]$).” This definition fails to
address causal asymmetry and spurious correlations [Hitchcock, 2021], so it’s
never popular among statisticians. However, the very idea of ”raising”
contains a contrast between a world with $X$ and a world with $\lnot X$.

  3. 3.

The contrast of treatment effects is formalized in statistical causal
inference. Using the potential outcome notations in Hernan and Robins [2020],

     * •

causal risk difference: $\Pr[Y^{a=1}=1]-\Pr[Y^{a=0}=1]$

     * •

causal risk ratio: $\frac{\Pr[Y^{a=1}=1]}{\Pr[Y^{a=0}=1]}$

     * •

causal odds ratio:
$\frac{\Pr[Y^{a=1}=1]/\Pr[Y^{a=1}=0]}{\Pr[Y^{a=0}=1]/\Pr[Y^{a=0}=0]}$

These measurements all involve a contrast between random variables $Y^{a=0}$
(effect under treatment 0) and $Y^{a=1}$ (effect under treatment 1).

  4. 4.

To understand a function $y=f(x)$, we often record an initial input value
$x_{0}$ and its corresponding output value $y_{0}=f(x_{0})$; we then change
$x_{0}$ to $x_{1}$ and see how the output value $y$ changes in response. For
example, derivatives in calculus help quantify how ”sensitive” the output is
with respect to the input.

With actual assignment $\mathbf{w}_{a}$ and contrastive assignment
$\mathbf{w}_{c}$, we say ”$\mathbf{w}_{a|exo}$ (rather than
$\mathbf{w}_{c|exo}$) causes $\mathbf{w}_{a|endo}$ (rather than
$\mathbf{w}_{c|endo}$).”

###  2.6 Delta Compression

To characterize omission in causal utterances, we consider
$\mathcal{C}=\\{u\in\mathcal{V}|\mathbf{w}_{a}(u)\neq\mathbf{w}_{c}(u)\\}$:
the nodes that have different values in $\mathbf{w}_{a}$ and $\mathbf{w}_{c}$.
$|\mathcal{C}|$ is the Hamming distance between $\mathbf{w}_{a}$ and
$\mathbf{w}_{c}$. With $\mathcal{C}_{exo}=\mathcal{C}\cap\mathcal{V}_{exo}$
and $\mathcal{C}_{endo}=\mathcal{C}\cap\mathcal{V}_{endo}$, the final causal
utterance is ”$\mathbf{w}_{a|\mathcal{C}_{exo}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}$.”

If something doesn’t change, we don’t mention it. We only mention the new
values of changed nodes. This is an example of delta compression [Suel, 2019]:

Encoder wants to transmit a target file to Decoder. Encoder and Decoder can
both access a reference file. The target file is only slightly different from
the reference file, so their delta (change/difference) is much smaller than
the target file itself. To reduce the amount of transferred data, Encoder
computes the delta (using target and reference files) and sends it to Decoder;
Decoder reconstructs the target file by adding the delta to the reference
file.

Delta compression is widely used in version control, where we want to store
many successive versions of the same file, but any 2 consecutive versions
differ only slightly.

######  Example 2.2.

Consider nodes $\\{A,B,C,D\\}$ with integer domains and assignments
$\mathbf{w}_{0},\mathbf{w}_{1}$:

  1. 1.

$\mathbf{w}_{0}=\\{A:1,B:2,C:3,D:4\\}$

  2. 2.

$\mathbf{w}_{1}=\\{A:1,B:7,C:3,D:5\\}$

  3. 3.

$\mathcal{C}=\\{B,D\\}$

  4. 4.

$\mathbf{w}_{0|\mathcal{C}}=\\{B:2,D:4\\}$

  5. 5.

$\mathbf{w}_{1|\mathcal{C}}=\\{B:7,D:5\\}$

People may prefer delta compression because it shortens causal utterances
without losing information or introducing ambiguities. This saving of ”mental
bandwidth” is especially prominent when:

  1. 1.

We want to represent many $\mathbf{w}_{1}$ relative to one $\mathbf{w}_{0}$.

  2. 2.

Each $\mathbf{w}_{1}$ differs only slightly from $\mathbf{w}_{0}$, i.e.
$|\mathcal{C}|$ is small relative to $|\mathcal{V}|$.

In default-actual contrasts, the default $\mathbf{w}_{c}$ is kept constant for
reference; in actual-tweaked contrasts, $\mathbf{w}_{a}$ is held for
reference.

We say $\mathbf{w}_{a|\mathcal{C}_{exo}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}$, where
$\mathcal{C}=\\{u\in\mathcal{V}|\mathbf{w}_{a}(u)\neq\mathbf{w}_{c}(u)\\}$ is
the set of changed nodes.

##  3 Inference

###  3.1 Constraint Satisfaction

During inference, we assume the SFM $\mathcal{M}$ is true. An inference
algorithm takes in assignment $\mathbf{w}_{|\mathcal{X}}$ over known nodes
$\mathcal{X}\subseteq\mathcal{V}$ and a set of target nodes $\mathcal{Y}$,
whose values we’re interested in inferring. It then checks whether
$\mathbf{w}_{|\mathcal{X}}$ is permitted and if so, returns one or more
$\mathbf{w}_{|\mathcal{Y}}$ that’s compatible with
$\mathbf{w}_{|\mathcal{X}}$.

If all domains are finite, we can formulate SFM inference as a constraint
satisfaction problem (CSP) [Russell, 2010] and use off-the-shelf CSP solvers
for inference:

  1. 1.

The domain of node $u\in\mathcal{V}$ is $\mathcal{D}[u]$.

  2. 2.

For each $u\in\mathcal{V}_{endo}$, its structural equation gives a
$(|\mathrm{Pa}(u)|+1)$-ary constraint
$\mathbf{w}(u)=\mathcal{F}[u](\mathbf{w}_{|\mathrm{Pa}(u)})$ over scope
$\mathrm{Pa}(u)\cup\\{u\\}$.

  3. 3.

Each known value $w_{u}=\mathbf{w}_{|\mathcal{X}}(u)$ for $u\in\mathcal{X}$ is
a unary constraint $\mathbf{w}(u)=w_{u}$ over scope $\\{u\\}$.

CSP does have a few drawbacks:

  1. 1.

It’s NP-complete in general.

  2. 2.

It’s unnecessary for most thought experiments, where the SFMs are small and
solvable by hand.

  3. 3.

It offers no guarantee for the existence or uniqueness of
$\mathbf{w}_{|\mathcal{Y}}$. For example, if $y=f(x)$ is non-injective,
different $x$ can be compatible with the same $y$.

Thanks to right-uniqueness, inferring effects from causes is much easier.

###  3.2 Forward Inference

Forward inference infers effects from causes. Given SFM $\mathcal{M}$, vanilla
forward inference (VFI) computes
$\mathbf{w}=\texttt{VFI}(\mathcal{M},\mathbf{w}_{exo})$, where
$\mathbf{w}\supseteq\mathbf{w}_{exo}$ and of $\mathbf{w}\in R_{\mathcal{M}}$.

When $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is finite and acyclic (and
$\forall u\in\mathcal{V}:\mathcal{D}[u]\neq\emptyset$),

  * •

$\mathcal{M}=(\mathcal{V},\mathcal{E},\mathcal{D},\mathcal{F})$ is satisfiable
for any $\mathcal{F}$;

  * •

$\mathbf{w}_{exo}$ functionally determines $\mathbf{w}_{endo}$; VFI itself is
a function.

Intuitively, VFI deterministically infers all effects given the root causes
and mechanisms-of-nature.

######  Theorem 3.1.

(Forward Inference) In a finite acyclic SFM $\mathcal{M}$ (with nonempty
domains), for any exo-assignment $\mathbf{w}_{exo}$, there exists a unique
complete assignment $\mathbf{w}$ satisfying
$\mathbf{w}\supseteq\mathbf{w}_{exo}$ and $\mathbf{w}\in R_{\mathcal{M}}$.

###### Proof.

  * •

Existence: Because $\mathcal{G}$ is finite, $\mathcal{V}$ is finite. Because
$\mathcal{G}$ is acyclic, there exists a topological order $L$ of nodes: an
ordered list of all nodes such that
$[(L[i],L[j])\in\mathcal{E}]\Rightarrow[i<j]$. Using topological sort
algorithms like depth-first-search and Kahn’s algorithm, we can compute $L$ in
$\Theta(|\mathcal{V}|+|\mathcal{E}|)$ time; cycle detection is done
simultaneously [Cormen et al., 2022].

Given $\mathbf{w}_{exo}$, we compute $\mathbf{w}_{1}$ sequentially from $i=1$
to $i=|\mathcal{V}|$ inclusive:

    1. 1.

If $L[i]\in\mathcal{V}_{exo}$, we assign
$\mathbf{w}_{1}(L[i])\leftarrow\mathbf{w}_{exo}(L[i])$.

    2. 2.

If $L[i]\in\mathcal{V}_{endo}$, we assign
$\mathbf{w}_{1}(L[i])\leftarrow\mathcal{F}[L[i]](\mathbf{w}_{1|\mathrm{Pa}(L[i])})$.

    3. 3.

Any parent $L[j]\in\mathrm{Pa}(L[i])$ must appear earlier ($j<i$) than its
child $L[i]$ because $L$ is a topological order. $\mathbf{w}_{1}(L[j])$ must
have already been assigned, so $\mathbf{w}_{1|\mathrm{Pa}(L[i])}$ is well-
defined.

Because $\mathbf{w}_{1}(L[i])$ isn’t modified after iteration $i$:

    1. 1.

If $L[i]\in\mathcal{V}_{exo}$, $\mathbf{w}_{1}(L[i])=\mathbf{w}_{exo}(L[i])$
is always satisfied.

    2. 2.

If $L[i]\in\mathcal{V}_{endo}$,
$\mathbf{w}_{1}(L[i])=\mathcal{F}[L[i]](\mathbf{w}_{1|\mathrm{Pa}(L[i])})$ is
always satisfied.

Therefore, $\mathbf{w}_{1}\supseteq\mathbf{w}_{exo}$ and $\mathbf{w}_{1}$
satisfies $\mathcal{M}$.

This constructive proof also specifies the algorithm
$\mathbf{w}=\texttt{VFI}(\mathcal{M},\mathbf{w}_{exo})$, assuming every
structural function $\mathcal{F}[u]$ is computable.

  * •

Uniqueness: Proving by contradiction, suppose instead that there’s another
$\mathbf{w}_{2}\neq\mathbf{w}_{1}$ satisfying
$\mathbf{w}_{2}\supseteq\mathbf{w}_{exo}$ and $\mathbf{w}_{2}\in
R_{\mathcal{M}}$. With topological order $L$, there exists a smallest integer
$i$ such that $\mathbf{w}_{1}(L[i])\neq\mathbf{w}_{2}(L[i])$.

Because $L$ is a topological order, every parent $L[j]\in\mathrm{Pa}(L[i])$
appears earlier ($j<i$). Since $L[i]$ is the earliest node with different
values, $\forall
L[j]\in\mathrm{Pa}(L[i]):\mathbf{w}_{1}(L[j])=\mathbf{w}_{2}(L[j])$ and
$\mathbf{w}_{1|\mathrm{Pa}(L[i])}=\mathbf{w}_{2|\mathrm{Pa}(L[j])}$.

Because functions are right-unique,
$\mathcal{F}[L[i]](\mathbf{w}_{1|\mathrm{Pa}(L[i])})=\mathcal{F}[L[i]](\mathbf{w}_{2|\mathrm{Pa}(L[i])})$.
Because $\mathbf{w}(L[i])$ is only modified at iteration $i$,
$\mathbf{w}_{1}(L[i])=\mathbf{w}_{2}(L[i])$, which contradicts
$\mathbf{w}_{1}(L[i])\neq\mathbf{w}_{2}(L[i])$. Therefore,
$\mathbf{w}_{1}=\mathbf{w}_{2}$; the induced complete assignment from an exo-
assignment is unique.

∎

Existence entails left-totality; uniqueness entails right-uniqueness, so
$\texttt{VFI}(\mathcal{M},\mathbf{w}_{exo})$ itself is a function of
$\mathbf{w}_{exo}$. Since $\mathbf{w}_{exo}$ functionally determines
$\mathbf{w}$ and $\mathbf{w}_{endo}\subseteq\mathbf{w}$, Armstrong’s Axioms
entail ”$\mathbf{w}_{exo}$ functionally determines $\mathbf{w}_{endo}$.”

During forward inference, $\mathcal{G}$ is also a computational graph, where
edges indicate the order of computation. We start with exo-nodes and the
computation ”flows down” to endo-nodes, computing their values based on the
previously computed values of their parents. Topological sort and graph
traversal both take $\Theta(|\mathcal{V}|+|\mathcal{E}|)$ time under
adjacency-list representation of graphs. For each $u\in\mathcal{V}_{endo}$,
$\mathcal{F}[u]$ is computed exactly once.

######  Corollary 3.1.1.

In a finite acyclic SFM $\mathcal{M}$ with nonempty domains, any partial
assignment $\mathbf{w}_{|\mathcal{X}}$ over any subset of exo-nodes
$\mathcal{X}\subseteq\mathcal{V}_{exo}$ is permitted.

###### Proof.

For every $u\in\mathcal{V}_{exo}\setminus\mathcal{X}$, we assign an arbitrary
$\mathbf{w}_{exo}(u)\in\mathcal{D}[u]$ since $\mathcal{D}[u]\neq\emptyset$;
for every $u\in\mathcal{X}$, we assign
$\mathbf{w}_{exo}(u)\leftarrow\mathbf{w}_{|\mathcal{X}}(u)$, so
$\mathbf{w}_{exo}\supseteq\mathbf{w}_{|\mathcal{X}}$. By Theorem 3.1,
$\mathbf{w}=\texttt{VFI}(\mathcal{M},\mathbf{w}_{exo})$ satisfies
$\mathbf{w}_{exo}\subseteq\mathbf{w}\in R_{\mathcal{M}}$, so
$\mathbf{w}_{|\mathcal{X}}\subseteq\mathbf{w}_{exo}\subseteq\mathbf{w}\in
R_{\mathcal{M}}$ and $\mathbf{w}_{|\mathcal{X}}$ is permitted. ∎

######  Corollary 3.1.2.

A finite acyclic SFM $\mathcal{M}$ with nonempty domains is always
satisfiable, regardless of its structural functions $\mathcal{F}$.

###### Proof.

Because $\mathcal{G}$ is finite (no infinite regress) and acyclic, there
exists at least one root node $u$ (Appendix B). Because
$\mathcal{D}[u]\neq\emptyset$, we select an arbitrary value
$\mathbf{w}_{|\\{u\\}}(u)\in\mathcal{D}[u]$. Corollary 3.1.1 says
$\mathbf{w}_{|\\{u\\}}$ is permitted, so $\exists\mathbf{w}\in
R_{\mathcal{M}}:\mathbf{w}\supseteq\mathbf{w}_{|\\{u\\}}$ and $\mathcal{M}$ is
satisfiable. ∎

###  3.3 Functional Invariance

We use functional invariance to describe how a multi-input function’s output
doesn’t change when some inputs have changed: TVs aren’t affected by light
switches; the output of $f(x,y)=2x$ is invariant to $y$ given $x$. Notice that
ceteris paribus (holding other input values constant) is well-defined only if
there’s a clear input-output distinction given by an underlying function.

In SFM, changing an exo-node’s value cannot influence its non-descendants.
This is deduced from $\mathcal{G}$ alone. With non-injective functions, new
parent values may map to the old child value, resulting in even fewer changed
nodes. Equivalently, for $\mathcal{X}\subseteq\mathcal{V}_{exo}$,
$\mathbf{w}_{|\mathcal{V}_{exo}\setminus\mathcal{X}}$) functionally determines
$\mathcal{X}$’s non-descendants.

######  Theorem 3.2.

(Invariance in SFM) In a finite acyclic SFM $\mathcal{M}$ with
$\mathbf{w}_{1},\mathbf{w}_{2}\in R_{\mathcal{M}}$ and changed nodes
$\mathcal{C}=\\{u\in\mathcal{V}|\mathbf{w}_{0}(u)\neq\mathbf{w}_{1}(u)\\}$:

If $\mathbf{w}_{0}(u)\neq\mathbf{w}_{1}(u)$, then
$u\in\bigcup_{v\in\mathcal{C}_{exo}}\mathrm{De}(v)$. ($u$’s value differs in
$\mathbf{w}_{0}$ and $\mathbf{w}_{1}$ only if it’s the descendant of some node
in $\mathcal{C}_{exo}$.)

###### Proof.

Let $u\in\mathcal{C}$ be any node such that
$\mathbf{w}_{0}(u)\neq\mathbf{w}_{1}(u)$. If $u\in\mathcal{V}_{exo}$, then
$u\in\mathcal{C}_{exo}$ and we’re done. If $u\in\mathcal{V}_{endo}$, then
because functions are right-unique, at least one parent $p\in\mathrm{Pa}(u)$
must have a different value ($\mathbf{w}_{0}(p)\neq\mathbf{w}_{1}(p)$). We
consider $p$ as the new $u$ and repeat this process recursively. Because the
SFM graph is finite (no infinite regress) and acyclic, this path $u\leftarrow
p_{1}\leftarrow p_{2}\leftarrow\dots$ must terminate at some exo-node
$s\in\mathcal{V}_{exo}$ (Appendix B) such that
$\mathbf{w}_{0}(s)\neq\mathbf{w}_{1}(s)$, which means $s\in\mathcal{C}_{exo}$.
The path shows $u$ is a descendant of $s$. ∎

###  3.4 Contrastive Forward Inference

Suppose we already have $\mathcal{M}$ and $\mathbf{w}_{0}\in R_{\mathcal{M}}$.
To compute $\texttt{VFI}(\mathcal{M},\mathbf{w}_{1|exo})$, we still need to
compute every $\mathcal{F}[u]$. Given all the unchanged nodes from functional
invariance, can the graph structure help us reduce $\mathcal{F}[u]$
evaluations?

Yes. With
$\mathcal{C}_{exo}=\\{u\in\mathcal{V}_{exo}|\mathbf{w}_{0|exo}(u)\neq\mathbf{w}_{1|exo}(u)\\}$,
the contrastive forward inference (CFI) algorithm
$\mathbf{w}_{1}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{0},\mathbf{w}_{1|\mathcal{C}_{exo}})$
evaluates $\mathcal{F}[u]$ only when at least one parent of $u$ has a changed
value, so we don’t recompute non-descendants of $\mathcal{C}_{exo}$. CFI
evaluates usually fewer (and always no more) structural functions than VFI,
especially when $\mathcal{C}$ is small relative to $\mathcal{V}$, when there
are many $\mathbf{w}_{i|exo}$ queries relative to one reference
$\mathbf{w}_{0}$, or when many structural functions are non-injective.

Input:

  * •

$\mathcal{M}=(\mathcal{V},\mathcal{E},\mathcal{D},\mathcal{F})$, the SFM.

  * •

$L=[u_{1},u_{2},\dots,u_{n}]$, list of all nodes in topological order
(cached).

  * •

$\mathbf{w}_{0}$, reference assignment.

  * •

$\mathbf{w}_{1|\mathcal{X}}$, exo-assignment over
$\mathcal{X}\subseteq\mathcal{V}_{exo}$ for the new forward inference query.

Output:

  * •

$\mathbf{w}_{1}$, the induced complete assignment from
$\mathbf{w}_{1|\mathcal{C}_{exo}}\cup\mathbf{w}_{0|\mathcal{V}_{exo}\setminus\mathcal{C}_{exo}}$.

$\mathbf{w}_{1}\leftarrow$ empty dictionary;

$\mathbf{c}\leftarrow$ empty dictionary; // whether a node’s value changed

foreach  _$u\in\mathcal{V}$_ do

if  _$u\in\mathcal{X}$ and
$\mathbf{w}_{1|\mathcal{X}}[u]\neq\mathbf{w}_{0}[u]$_ then

$\mathbf{c}[u]\leftarrow 1$

else

$\mathbf{c}[u]\leftarrow 0$

end if

end foreach

// traverse the nodes in topological order

for  _$i\leftarrow 1$ to $|\mathcal{V}|$_ do

$u_{i}\leftarrow L[i]$

$r\leftarrow\mathbf{c}[u_{i}]$ // 1 if $u_{i}$ needs re-computation, else 0

foreach  _parent $p\in\mathrm{Pa}(u_{i})$_ do

$r\leftarrow r\lor\mathbf{c}[p]$

end foreach

if  _$r=1$_ then

if  _$u_{i}\in V_{exo}$_ then

$\mathbf{w}_{1}[u_{i}]\leftarrow\mathbf{w}_{1|\mathcal{S}}[u_{i}]$

else

$f\leftarrow\mathcal{F}[u_{i}]$

$\mathbf{w}_{\mathrm{Pa}(u_{i})}\leftarrow$ {$p$: $\mathbf{w}_{1}(p)$ for
$p\in\mathrm{Pa}(u_{i})$}

$val\leftarrow f(\mathbf{w}_{\mathrm{Pa}(u_{i})})$ // compute new value for
$u_{i}$

if  _$val\neq\mathbf{w}_{0}[u_{i}]$_ then

$\mathbf{w}_{1}[u_{i}]\leftarrow val$

$\mathbf{c}[u_{i}]\leftarrow 1$

else

$\mathbf{w}_{1}[u_{i}]\leftarrow\mathbf{w}_{0}[u_{i}]$

end if

end if

else

$\mathbf{w}_{1}[u_{i}]\leftarrow\mathbf{w}_{0}[u_{i}]$ // copy from reference
assignment

end if

end for

Algorithm 1 Contrastive forward inference algorithm

If we draw an SFM with all arrows pointing downwards, we visually cache a
topological order of nodes. We can easily identify the descendants of changed
nodes and only evaluate their structural functions, without recomputing the
complete assignment.

Unlike functions, contrast isn’t a fundamental and irreducible part of
causality. It’s just a popular heuristic with pragmatic benefits:

  1. 1.

Delta compression reduces the length of causal utterances.

  2. 2.

CFI recomputes (usually) fewer structural functions than VFI during forward
inference.

###  3.5 Partial Forward Inference

By modifying depth-first search, we can also design partial forward inference
algorithms, where we’re only interested in a subset of endo-nodes
$\mathcal{Y}\subseteq\mathcal{V}_{endo}$, so we don’t have to compute values
for all endo-nodes. Combined with CFI, it further reduces the number of
function evaluations, especially when $\mathcal{Y}$ is much smaller than
$\mathcal{V}_{endo}$.

###  3.6 Inference in Practice

  1. 1.

VFI in Boolean circuits: A combinational logic circuit [Patt and Patel, 2020]
is a finite acyclic SFM with $\\{0,1\\}$ domains and Boolean functions. Each
wire’s value is 0 (no electrical current) or 1 (has current). A logic gate
receives input wires and returns an output wire, like a structural function.
The output wire of one gate can be the input wire of another gate. To infer
the values of all wires given all input wires, we use VFI and produce causal
utterances like ”setting this input wire to 1 causes the output wire to be 0.”

  2. 2.

CFI in GNU Make: GNU make is a popular open-source software that automatically
determines which pieces of a large program need to be recompiled [gnu, 2023].
Especially in C and C++, the source code needs to be compiled or linked into a
target file, before the target file can be executed by the computer. In a
Makefile, there are many rules. Each rule has a target file, a list of source
files, and a recipe for compilation. The target file functionally depends on
the source files. The target file of one rule can be a source file in another
rule. This forms a finite SFM where files are nodes and rules specify edges
and structural functions.

VFI compiles all files, but software development is a dynamic process: We
don’t compile the files just once. We modify some files, see the results, and
repeat. Because compilation is time-consuming, it’s costly to recompile all
files after a modification. Instead, we only need to recompile the descendants
of modified files. Just like CFI, make only recompiles the target file if any
of its source files (parents) has been modified since the previous
compilation, saving lots of time. We can produce causal utterances like
”modifying this file causes the final compiled program to crash.”

##  4 Learning

Learning causal models from statistical data is covered in depth by Pearl
[2009a], Hernan and Robins [2020], Peters et al. [2017], so we only discuss
some philosophical cases where people prefer some SFM over others, given
fully-specified possible worlds and laws-of-nature.

###  4.1 Thermometer and Temperature

We think high room temperature causes high thermometer reading, but not the
other way round. Why?

It’s common to introduce new nodes and see whether the small model remains
true as a sub-SFM of a bigger model. Consider a new node ”immersing
thermometer in cold water” and all possible worlds are listed below:

Node | HighReading | HighTemperature | ColdWater
---|---|---|---
$\mathbf{w}_{1}$ | 0 | 0 | 0
$\mathbf{w}_{2}$ | 1 | 1 | 0
$\mathbf{w}_{3}$ | 0 | 0 | 1
$\mathbf{w}_{4}$ | 0 | 1 | 1

Without granting ”intervention” any special status, we see that
$\texttt{\\{HighReading\\}}\xrightarrow{.}\texttt{\\{HighTemperature\\}}$ and
$\texttt{\\{HighReading,
ColdWater\\}}\xrightarrow{.}\texttt{\\{HighTemperature\\}}$ aren’t true in
general, so the edge should point from HighTemperature to HighReading. People
prefer simple SFMs that compose well with other SFMs that model the same
world.

###  4.2 Light, Object, and Shadow

In a symmetric equation involving {Light, Object, Shadow}, any 2 nodes
functionally determine the 1 remaining node. Why do we think the shadow is the
effect? This asymmetric preference is entailed by people’s general dislike of
SFM-intersection:

  * •

With multiple objects, $\texttt{\\{Light,
Shadow\\}}\xrightarrow{.}\texttt{\\{Object\\}}$ isn’t true in general. When we
add another object whose shadow rests entirely in another object’s shadow, the
system’s light and shadow remain the same, thus violating right-uniqueness.

  * •

$\texttt{\\{Light, Shadow\\}}\xrightarrow{.}\texttt{\\{Object\\}}$ cannot SFM-
compose with $\texttt{\\{Factory\\}}\xrightarrow{.}\texttt{\\{Object\\}}$
(objects determined by their production processes). Explicitly encoding both
functional dependencies requires SFM-intersection.

  * •

With one light source and multiple objects, $\texttt{\\{Object(i),
Shadow(i)\\}}\xrightarrow{.}\texttt{\\{Light\\}}$ holds for every Object(i),
resulting in SFM-intersection.

  * •

$\texttt{\\{Object, Shadow\\}}\xrightarrow{.}\texttt{\\{Light\\}}$ cannot SFM-
compose with $\texttt{\\{Hand\\}}\xrightarrow{.}\texttt{\\{Light\\}}$
(flashlight direction determined by hand movement) or
$\texttt{\\{TimeOfDay\\}}\xrightarrow{.}\texttt{\\{Light\\}}$ (the Sun’s
position determined by time of the day), unless we use SFM-intersection.

  * •

$\texttt{\\{Object, Light\\}}\xrightarrow{.}\texttt{\\{Shadow\\}}$ can
seamlessly compose with upstream and downstream SFMs without SFM-intersection.

##  5 Benchmark

Taking a data-centric approach, we compile a collection of thought experiments
about causality and apply SFM to all of them. A good definition of causality
should have no trouble fitting these causal scenarios. Unless otherwise
mentioned, all domains are binary $\\{0,1\\}$.

###  5.1 Sensitive to Default

  * •

The assassin shoots the victim, causing the victim’s death.

    1. 1.

$\texttt{Assassin}\to\texttt{Death}$

    2. 2.

$\mathcal{F}[\texttt{Death}](\mathbf{w})=\mathbf{w}(\texttt{Assassin})$

    3. 3.

Default $\mathbf{w}_{c}=\texttt{\\{Assassin:0, Death:0\\}}$

    4. 4.

Actual $\mathbf{w}_{a}=\texttt{\\{Assassin:1, Death:1\\}}$

    5. 5.

$\mathcal{C}_{exo}=\texttt{\\{Assassin\\}},\mathcal{C}_{endo}=\texttt{\\{Death\\}}$

    6. 6.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Assassin:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Death:1\\}}$.

  * •

At the last moment, the assassin changes his mind and doesn’t shoot, causing
the victim’s survival.

    1. 1.

Same $\mathcal{M}$ as above.

    2. 2.

Default $\mathbf{w}_{c}=\texttt{\\{Assassin:1, Death:1\\}}$

    3. 3.

Actual $\mathbf{w}_{a}=\texttt{\\{Assassin:0, Death:0\\}}$

    4. 4.

$\mathcal{C}_{exo}=\texttt{\\{Assassin\\}},\mathcal{C}_{endo}=\texttt{\\{Death\\}}$

    5. 5.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Assassin:0\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Death:0\\}}$.

###  5.2 Causal Chain

The assassin shoots a bullet, which kills the victim.

  * •

The assassin causes both the bullet and the death.

    1. 1.

$\texttt{Assassin}\to\texttt{Bullet}\to\texttt{Death}$

    2. 2.

$\mathcal{F}[\texttt{Bullet}](\mathbf{w})=\mathbf{w}(\texttt{Assassin})\\\
\mathcal{F}[\texttt{Death}](\mathbf{w})=\mathbf{w}(\texttt{Bullet})$

    3. 3.

Default $\mathbf{w}_{c}=\texttt{\\{Assassin:0, Bullet:0, Death:0\\}}$

    4. 4.

Actual $\mathbf{w}_{a}=\texttt{\\{Assassin:1, Bullet:1, Death:1\\}}$

    5. 5.

$\mathcal{C}_{exo}=\texttt{\\{Assassin\\}},\mathcal{C}_{endo}=\texttt{\\{Bullet,
Death\\}}$

    6. 6.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Assassin:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Bullet:1, Death:1\\}}$.

  * •

(Sub-SFM) The bullet causes the death.

    1. 1.

$\texttt{Bullet}\to\texttt{Death}$

    2. 2.

$\mathcal{F}[\texttt{Death}](\mathbf{w})=\mathbf{w}(\texttt{Bullet})$

    3. 3.

Default $\mathbf{w}_{c}=\texttt{\\{Bullet:0, Death:0\\}}$

    4. 4.

Actual $\mathbf{w}_{a}=\texttt{\\{Bullet:1, Death:1\\}}$

    5. 5.

$\mathcal{C}_{exo}=\texttt{\\{Bullet\\}},\mathcal{C}_{endo}=\texttt{\\{Death\\}}$

    6. 6.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Bullet:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Death:1\\}}$.

###  5.3 Connected Double Prevention

A bodyguard shoots the assassin before the assassin could shoot the victim.
The victim survives.

  * •

The bodyguard causes the assassin’s death and the victim’s survival.

    1. 1.

$\texttt{Bodyguard}\to\texttt{Assassin}\to\texttt{Survive}$

    2. 2.

$\mathcal{F}[\texttt{Assassin}](\mathbf{w})=\neg\mathbf{w}(\texttt{Bodyguard})\\\
\mathcal{F}[\texttt{Survive}](\mathbf{w})=\neg\mathbf{w}(\texttt{Assassin})$

    3. 3.

Actual $\mathbf{w}_{a}=\texttt{\\{Bodyguard:1, Assassin:0, Survive:1\\}}$

    4. 4.

$\mathcal{C}_{exo}=\texttt{\\{Bodyguard\\}}$

    5. 5.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{Bodyguard:0\\}}$

    6. 6.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})=\texttt{\\{Bodyguard:0,
Assassin:1, Survive:0\\}}$

    7. 7.

$\mathcal{C}_{endo}=\texttt{\\{Assassin, Survive\\}}$

    8. 8.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Bodyguard:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Assassin:0, Survive:1\\}}$.

###  5.4 Disconnected Double Prevention

The assassin puts poison in the victim’s cup. The bodyguard puts antidote in
the cup. The victim survives.

  * •

Antidote causes the victim’s survival.

    1. 1.

PoisonAntidoteSurvive

    2. 2.

$\mathcal{F}[\texttt{Survive}](\mathbf{w})=\neg\mathbf{w}(\texttt{Poison})\lor\mathbf{w}(\texttt{Antidote})$

    3. 3.

Actual $\mathbf{w}_{a}=\texttt{\\{Poison:1, Antidote:1, Survive:1\\}}$

    4. 4.

$\mathcal{C}_{exo}=\texttt{\\{Antidote\\}}$

    5. 5.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{Antidote:0\\}}$

    6. 6.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})=\texttt{\\{Poison:1,
Antidote:0, Survive:0\\}}$

    7. 7.

$\mathcal{C}_{endo}=\texttt{\\{Survive\\}}$

    8. 8.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Antidote:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Survive:1\\}}$.

###  5.5 No Appropriate Default

Two chess players use a coin flip to decide who moves first. If the coin lands
on head, the Player 1 moves first; otherwise, Player 2 moves first. It’s
difficult to identify a ”default” world [Blanchard and Schaffer, 2017].

  * •

Coin landing on head causes Player 1 to move first.

    1. 1.

$\texttt{Head}\to\texttt{Player1}$

    2. 2.

$\mathcal{F}[\texttt{Player1}](\mathbf{w})=\mathbf{w}(\texttt{Head})$

    3. 3.

Actual $\mathbf{w}_{a}=\texttt{\\{Head:1, Player1:1\\}}$

    4. 4.

$\mathcal{C}_{exo}=\texttt{\\{Head\\}}$

    5. 5.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{Head:0\\}}$

    6. 6.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})=\texttt{\\{Head:0,
Player1:0\\}}$

    7. 7.

$\mathcal{C}_{endo}=\texttt{\\{Player1\\}}$

    8. 8.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Head:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Player1:1\\}}$.

  * •

Coin landing on tail causes Player 2 to move first.

    1. 1.

Same $\mathcal{M}$ as above.

    2. 2.

Actual $\mathbf{w}_{a}=\texttt{\\{Head:0, Player1:0\\}}$

    3. 3.

$\mathcal{C}_{exo}=\texttt{\\{Head\\}}$

    4. 4.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{Head:1\\}}$

    5. 5.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})=\texttt{\\{Head:1,
Player1:1\\}}$

    6. 6.

$\mathcal{C}_{endo}=\texttt{\\{Player1\\}}$

    7. 7.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Head:0\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Player1:0\\}}$.

###  5.6 Gardener and Queen

The flower lives iff at least one person waters it. The gardener is
responsible for watering the flower, but the queen isn’t [Hart and Honoré,
1985].

  * •

The gardener’s not watering the flower causes the flower’s death; the queen’s
not watering it doesn’t cause the flower’s death.

    1. 1.

GardenerQueenFlower

    2. 2.

$\mathcal{F}[\texttt{Flower}](\mathbf{w})=\mathbf{w}(\texttt{Gardener})\lor\mathbf{w}(\texttt{Queen})$

    3. 3.

Default $\mathbf{w}_{c}=\texttt{\\{Gardener:1, Queen:0, Flower:1\\}}$

    4. 4.

Actual $\mathbf{w}_{a}=\texttt{\\{Gardener:0, Queen:0, Flower:0\\}}$

    5. 5.

$\mathcal{C}_{exo}=\texttt{\\{Gardener\\}},\mathcal{C}_{endo}=\texttt{\\{Flower\\}}$

    6. 6.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Gardener:0\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Flower:0\\}}$.

###  5.7 OR Firing Squad (Symmetric Overdetermination)

Two assassins simultaneously shoot the victim. It takes only 1 bullet to kill
the victim.

  * •

Both assassins are responsible because ”not killing” is default.

    1. 1.

Assassin1Assassin2Death

    2. 2.

$\mathcal{F}[\texttt{Death}](\mathbf{w})=\mathbf{w}(\texttt{Assassin1})\lor\mathbf{w}(\texttt{Assassin2})$

    3. 3.

Default $\mathbf{w}_{c}=\texttt{\\{Assassin1:0, Assassin2:0, Death:0\\}}$

    4. 4.

Actual $\mathbf{w}_{a}=\texttt{\\{Assassin1:1, Assassin2:1, Death:1\\}}$

    5. 5.

$\mathcal{C}_{exo}=\texttt{\\{Assassin1,
Assassin2\\}},\mathcal{C}_{endo}=\texttt{\\{Death\\}}$

    6. 6.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Assassin1:1, Assassin2:1\\}}$
causes $\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Death:1\\}}$.

  * •

Assassin 1 causes nothing because had he not shot, Assassin 2 would’ve still
killed the victim.

    1. 1.

Same $\mathcal{M}$ as above.

    2. 2.

Actual $\mathbf{w}_{a}=\texttt{\\{Assassin1:1, Assassin2:1, Death:1\\}}$

    3. 3.

$\mathcal{C}_{exo}=\texttt{\\{Assassin1\\}}$

    4. 4.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{Assassin1:0\\}}$

    5. 5.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})=\texttt{\\{Assassin1:0,
Assassin2:1, Death:1\\}}$

    6. 6.

$\mathcal{C}_{endo}=\emptyset$

    7. 7.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Assassin1:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\emptyset$.

###  5.8 AND Firing Squad

2 assassins simultaneously shoot the victim. It takes at least 2 bullets to
kill the victim.

  * •

Both assassins are responsible because ”not killing” is default.

    1. 1.

Assassin1Assassin2Death

    2. 2.

$\mathcal{F}[\texttt{Death}](\mathbf{w})=\mathbf{w}(\texttt{Assassin1})\land\mathbf{w}(\texttt{Assassin2})$

    3. 3.

Default $\mathbf{w}_{c}=\texttt{\\{Assassin1:0, Assassin2:0, Death:0\\}}$

    4. 4.

Actual $\mathbf{w}_{a}=\texttt{\\{Assassin1:1, Assassin2:1, Death:1\\}}$

    5. 5.

$\mathcal{C}_{exo}=\texttt{\\{Assassin1,
Assassin2\\}},\mathcal{C}_{endo}=\texttt{\\{Death\\}}$

    6. 6.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Assassin1:1, Assassin2:1\\}}$
causes $\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Death:1\\}}$.

  * •

Assassin 1 is individually responsible because had he not shot, the victim
would’ve survived.

    1. 1.

Same $\mathcal{M}$ as above.

    2. 2.

Actual $\mathbf{w}_{a}=\texttt{\\{Assassin1:1, Assassin2:1, Death:1\\}}$

    3. 3.

$\mathcal{C}_{exo}=\texttt{\\{Assassin1\\}}$

    4. 4.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{Assassin1:0\\}}$

    5. 5.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})=\texttt{\\{Assassin1:0,
Assassin2:1, Death:0\\}}$

    6. 6.

$\mathcal{C}_{endo}=\texttt{\\{Death\\}}$

    7. 7.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Assassin1:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Death:1\\}}$.

###  5.9 Connected Preemption

Assassin 1 shoots the victim first. If the victim doesn’t die, Assassin 2 will
shoot. Had Assassin 1 not shot, the victim still would’ve died.

  * •

Assassin 1 causes the victim’s death and Assassin 2’s not-shooting.

    1. 1.

Assassin1Assassin2EarlyDeathLateDeath

    2. 2.

$\mathcal{F}[\texttt{EarlyDeath}](\mathbf{w})=\mathbf{w}(\texttt{Assassin1})\\\
\mathcal{F}[\texttt{Assassin2}](\mathbf{w})=\neg\mathbf{w}(\texttt{EarlyDeath})\\\
\mathcal{F}[\texttt{LateDeath}](\mathbf{w})=\mathbf{w}(\texttt{EarlyDeath})\lor\mathbf{w}(\texttt{Assassin2})$

    3. 3.

Actual $\mathbf{w}_{a}=\texttt{\\{Assassin1:1, EarlyDeath:1, Assassin2:0,
LateDeath:1\\}}$

    4. 4.

$\mathcal{C}_{exo}=\texttt{\\{Assassin1\\}}$

    5. 5.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{Assassin1:0\\}}$

    6. 6.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})\\\
=\texttt{\\{Assassin1:0, EarlyDeath:0, Assassin2:1, LateDeath:1\\}}$

    7. 7.

$\mathcal{C}_{endo}=\texttt{\\{EarlyDeath, Assassin2\\}}$

    8. 8.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Assassin1:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{EarlyDeath:1, Assassin2:0\\}}$.

    9. 9.

We cannot say {Assassin1:1} causes {LateDeath:1} because
$\texttt{Latedeath}\notin\mathcal{C}_{endo}$.

###  5.10 Disconnected Preemption

Assassin 1 shoots the victim first. Several moments later, Assassin 2 shoots
unconditionally.

  * •

Assassin 1 causes the victim’s death.

    1. 1.

Assassin1Assassin2EarlyDeathLateDeath

    2. 2.

$\mathcal{F}[\texttt{EarlyDeath}](\mathbf{w})=\mathbf{w}(\texttt{Assassin1})\\\
\mathcal{F}[\texttt{LateDeath}](\mathbf{w})=\mathbf{w}(\texttt{EarlyDeath})\lor\mathbf{w}(\texttt{Assassin2})$

    3. 3.

Actual $\mathbf{w}_{a}=\texttt{\\{Assassin1:1, Assassin2:1, EarlyDeath:1,
LateDeath:1\\}}$

    4. 4.

$\mathcal{C}_{exo}=\texttt{\\{Assassin1\\}}$

    5. 5.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{Assassin1:0\\}}$

    6. 6.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})\\\
=\texttt{\\{Assassin1:0, Assassin2:1, EarlyDeath:0, LateDeath:1\\}}$

    7. 7.

$\mathcal{C}_{endo}=\texttt{\\{EarlyDeath\\}}$

    8. 8.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Assassin1:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{EarlyDeath:1\\}}$.

Time difference distinguishes preemption from symmetric overdetermination: To
an extreme, we wouldn’t regard immediate death and death in 100 years as the
same event.

###  5.11 Relevant Background Conditions

Ignition requires both striking the match and oxygen present, but we only
mention striking the match as the cause of fire.

  * •

Striking the match causes ignition.

    1. 1.

StrikeOxygenFire

    2. 2.

$\mathcal{F}[\texttt{Fire}](\mathbf{w})=\mathbf{w}(\texttt{Strike})\land\mathbf{w}(\texttt{Oxygen})$

    3. 3.

Default $\mathbf{w}_{c}=\texttt{\\{Strike:0, Oxygen:1, Fire:0\\}}$

    4. 4.

Actual $\mathbf{w}_{a}=\texttt{\\{Strike:1, Oxygen:1, Fire:1\\}}$

    5. 5.

$\mathcal{C}_{exo}=\texttt{\\{Strike\\}},\mathcal{C}_{endo}=\texttt{\\{Fire\\}}$

    6. 6.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Strike:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Fire:1\\}}$.

  * •

While repeatedly striking a match in an oxygen-deprived container, there’s no
ignition. Pumping in oxygen causes the match to ignite.

    1. 1.

Same $\mathcal{M}$ as above.

    2. 2.

Default $\mathbf{w}_{c}=\texttt{\\{Strike:1, Oxygen:0, Fire:0\\}}$

    3. 3.

Actual $\mathbf{w}_{a}=\texttt{\\{Strike:1, Oxygen:1, Fire:1\\}}$

    4. 4.

$\mathcal{C}_{exo}=\texttt{\\{Oxygen\\}},\mathcal{C}_{endo}=\texttt{\\{Fire\\}}$

    5. 5.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Oxygen:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Fire:1\\}}$.

Similarly, a criminal wouldn’t have committed the crime had the universe not
existed/had he never been born, but we don’t consider those as causes of the
crime.

###  5.12 Irrelevant Background Conditions

The assassin simultaneously shoots the victim and whispers.

  * •

Whispering doesn’t cause anything.

    1. 1.

WhisperShootDeath

    2. 2.

$\mathcal{F}[\texttt{Death}](\mathbf{w})=\mathbf{w}(\texttt{Shoot})$

    3. 3.

Actual $\mathbf{w}_{a}=\texttt{\\{Whisper:1, Shoot:1, Death:1\\}}$

    4. 4.

$\mathcal{C}_{exo}=\texttt{\\{Whisper\\}}$

    5. 5.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{Whisper:0\\}}$

    6. 6.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})=\texttt{\\{Whisper:0,
Shoot:1, Death:1\\}}$

    7. 7.

$\mathcal{C}_{endo}=\emptyset$

    8. 8.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Whisper:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\emptyset$.

  * •

Shooting causes death.

    1. 1.

Same $\mathcal{M},\mathbf{w}_{a}$ as above.

    2. 2.

$\mathcal{C}_{exo}=\texttt{\\{Shoot\\}}$

    3. 3.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{Shoot:0\\}}$

    4. 4.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})=\texttt{\\{Whisper:1,
Shoot:0, Death:0\\}}$

    5. 5.

$\mathcal{C}_{endo}=\texttt{\\{Death\\}}$

    6. 6.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Shoot:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Death:1\\}}$.

Similarly, Socrates drinks hemlock at dusk and dies. Hemlock causes death, but
dusk doesn’t cause anything [Achinstein, 1975].

###  5.13 Boulder and Hiker

A hiker sees a boulder rolling towards him, so he dodges and survives. Had he
not dodged, he wouldn’t have survived [Hitchcock, 2001]. This is an ostensible
counterexample to the transitivity of causation (boulder causes dodge, dodge
causes survival, but boulder doesn’t cause survival). ”Transitivity” is better
understood as SFM-composition.

  * •

Boulder causes dodge and doesn’t cause survival.

    1. 1.

BoulderDodgeSurvive

    2. 2.

$\mathcal{F}[\texttt{Dodge}](\mathbf{w})=\mathbf{w}(\texttt{Boulder})\\\
\mathcal{F}[\texttt{Survive}](\mathbf{w})=\neg\mathbf{w}(\texttt{Boulder})\lor\mathbf{w}(\texttt{Dodge})$

    3. 3.

Actual $\mathbf{w}_{a}=\texttt{\\{Boulder:1, Dodge:1, Survive:1\\}}$

    4. 4.

$\mathcal{C}_{exo}=\texttt{\\{Boulder\\}}$

    5. 5.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{Boulder:0\\}}$

    6. 6.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})=\texttt{\\{Boulder:0,
Dodge:0, Survive:1\\}}$

    7. 7.

$\mathcal{C}_{endo}=\texttt{\\{Dodge\\}}$

    8. 8.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Boulder:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Dodge:1\\}}$, but
$\texttt{Survive}\notin\mathcal{C}_{endo}$.

  * •

(Sub-SFM) Dodge causes survival.

    1. 1.

BoulderDodgeSurvive

    2. 2.

$\mathcal{F}[\texttt{Survive}](\mathbf{w})=\neg\mathbf{w}(\texttt{Boulder})\lor\mathbf{w}(\texttt{Dodge})$

    3. 3.

Actual $\mathbf{w}_{a}=\texttt{\\{Boulder:1, Dodge:1, Survive:1\\}}$

    4. 4.

$\mathcal{C}_{exo}=\texttt{\\{Dodge\\}}$

    5. 5.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{Dodge:0\\}}$

    6. 6.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})=\texttt{\\{Boulder:1,
Dodge:0, Survive:0\\}}$

    7. 7.

$\mathcal{C}_{endo}=\texttt{\\{Survive\\}}$

    8. 8.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{Dodge:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{Survive:1\\}}$.

###  5.14 Bogus Prevention

Taking birth control pills is the cause of a woman not getting pregnant, but
not the cause of a man not getting pregnant, although ”birth control prevents
pregnancy” is always true [Salmon, 1971].

  * •

Birth control causes a woman to be unable to get pregnant.

    1. 1.

IsWomanBirthControlCanPregnant

    2. 2.

$\mathcal{F}[\texttt{CanPregnant}](\mathbf{w})=\mathbf{w}(\texttt{IsWoman})\land\neg\mathbf{w}(\texttt{BirthControl})$

    3. 3.

Actual $\mathbf{w}_{a}=\texttt{\\{IsWoman:1, BirthControl:1,
CanPregnant:0\\}}$

    4. 4.

$\mathcal{C}_{exo}=\texttt{\\{BirthControl\\}}$

    5. 5.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{BirthControl:0\\}}$

    6. 6.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})=\texttt{\\{IsWoman:1,
BirthControl:0, CanPregnant:1\\}}$

    7. 7.

$\mathcal{C}_{endo}=\texttt{\\{CanPregnant\\}}$

    8. 8.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{BirthControl:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\texttt{\\{CanPregnant:0\\}}$.

  * •

Birth control doesn’t cause anything for a man.

    1. 1.

Same $\mathcal{M}$ as above.

    2. 2.

Actual $\mathbf{w}_{a}=\texttt{\\{IsWoman:0, BirthControl:1,
CanPregnant:0\\}}$

    3. 3.

$\mathcal{C}_{exo}=\texttt{\\{BirthControl\\}}$

    4. 4.

Tweak $\mathbf{w}_{c|\mathcal{C}_{exo}}=\texttt{\\{BirthControl:0\\}}$

    5. 5.

Tweaked
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})=\texttt{\\{IsWoman:0,
BirthControl:0, CanPregnant:0\\}}$

    6. 6.

$\mathcal{C}_{endo}=\emptyset$

    7. 7.

$\mathbf{w}_{a|\mathcal{C}_{exo}}=\texttt{\\{BirthControl:1\\}}$ causes
$\mathbf{w}_{a|\mathcal{C}_{endo}}=\emptyset$.

###  5.15 Backtracking Counterfactuals

Subjunctive conditionals [Starr, 2022] use forward inference, while
indicative/backtracking/non-causal conditionals don’t.

  * •

(Subjunctive) If Shakespeare didn’t write Hamlet, someone else would have.

    1. 1.

ShakespeareWriter2Hamlet

    2. 2.

$\mathcal{F}[\texttt{Writer2}](\mathbf{w})=\neg\mathbf{w}(\texttt{Shakespeare})\\\
\mathcal{F}[\texttt{Hamlet}](\mathbf{w})=\mathbf{w}(\texttt{Shakespeare})\lor\mathbf{w}(\texttt{Writer2})$

    3. 3.

Actual $\mathbf{w}_{a}=\texttt{\\{Shakespeare:1, Writer2:0, Hamlet:1\\}}$.

    4. 4.

Query $\mathbf{w}_{exo}=\texttt{\\{Shakespeare:0\\}}$

    5. 5.

Queried
$\mathbf{w}=\texttt{VFI}(\mathcal{M},\mathbf{w}_{exo})=\texttt{\\{Shakespeare:0,
Writer2:1, Hamlet:1\\}}$.

  * •

(Indicative) If Shakespeare didn’t write Hamlet, someone else did.

    1. 1.

ShakespeareWriter2Hamlet

    2. 2.

$\mathcal{F}[\texttt{Hamlet}](\mathbf{w})=\mathbf{w}(\texttt{Shakespeare})\lor\mathbf{w}(\texttt{Writer2})$

    3. 3.

Given $\mathcal{M}$, the only $\mathbf{w}_{|\texttt{\\{Writer2\\}}}$
compatible with {Shakespeare:0, Hamlet:1} is {Writer2:1}.

###  5.16 Impossible Interventions

Unlike $\texttt{Assassin}\to\texttt{Death}$, some functional dependencies
contain all parents due to how the child is
logically/conceptually/metaphysically defined, so it’s impossible to add
surgical interventions:

  1. 1.

The string ”hello” is functionally determined by its first character being
”h”, second character being ”e”, …

  2. 2.

The average height of students in the class is functionally determined by the
individual height of each student.

  3. 3.

Winning 2 out of 3 rounds is functionally determined by the result of each
round.

They’re often known as supervenience (Section 9.6).

##  6 Discussion

###  6.1 Is SFM Insufficient?

Some may argue that since SFM and functions can have non-causal
interpretations, they are insufficient for defining causality. We respond with
3 counterarguments:

  1. 1.

Some examples of insufficiency are results of misinterpretation. For example,
student ID functionally determines all attributes (name, age, course
registration, etc.) of a student in a database, but changing a student’s ID
won’t cause changes in those attributes. This example doesn’t hold because if
we allow arbitrary changes to ID, there could be repeated IDs in different
rows and ID no longer functionally determines other attributes.

  2. 2.

Incorrect causal models (e.g. ”cancer causes smoking”) are still causal,
unlike non-causal models (e.g. correlations, symmetric equations), which don’t
use functions at all. Since SFM comes from the conceptual analysis of what
”causation” should mean, its definition cannot include all empirical facts
about our world.

  3. 3.

People often use causal interpretations to understand purely mathematical
functions. When we say ”changing the independent variable $x$ causes the
dependent variable $y$ to change,” we’re using CFI.

###  6.2 A Case Against Actual Causality

Delta compression and CFI are slightly useful heuristics that also fit our
intuitions. However, the assumption that there exists a fixed set of ”actual
causes” is questionable in complex systems.

######  Example 6.1.

A circuit has $n$ binary switches
$\mathcal{V}_{exo}=\\{X_{1},X_{2},\dots,X_{n}\\}$ and 1 light bulb
$\mathcal{V}_{endo}=\\{Y\\}$, where the $n$ switches functionally determine
the light via a Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$.

Given the state of all switches and the light, which switches are the ”actual
causes” of the light being on/off?

There are $2^{2^{n}}$ different $n$-input $1$-output Boolean functions $f$.
For each $f$, there are $2^{n}$ different possible worlds. Proponents of
actual causality must accept one of the following:

  1. 1.

Provide an algorithm that can identify actual causes in $2^{2^{n}}\times
2^{n}=2^{(2^{n}+n)}$ situations. Case-by-case analyses won’t scale.

  2. 2.

Admit that contrast, default, and actual causality belong to an imperfect
mental heuristic that would fail in complex systems.

Graphical models don’t help because there’s only one Boolean function and we
shouldn’t insert hypothetical intermediate nodes. For
$\mathcal{X}\subseteq\mathcal{V}_{exo}$, SFM can answer ”is
$\mathbf{w}_{0|\mathcal{X}}$ the cause of $\mathbf{w}_{0|endo}$?” by tweaking
$\mathbf{w}_{0|\mathcal{X}}$ into $\mathbf{w}_{1|\mathcal{X}}$, inferring
$\mathbf{w}_{1}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{0},\mathbf{w}_{1|\mathcal{X}})$,
and contrasting $\mathbf{w}_{1}(Y)$ against $\mathbf{w}_{0}(Y)$ . But ”a fixed
set of actual causes” given $\mathcal{M}$ and $\mathbf{w}_{0}$ remains ill-
defined. People’s intuitions may not give consistent answers and even if they
do, such answers provide less information about $f$ than the input-output
mappings of $f$ itself.

This example generalizes all ”difficult causal scenarios” with binary
variables and following features:

  1. 1.

Causal: We can manipulate the switches to control the light.

  2. 2.

Deterministic: It has no probabilistic component.

  3. 3.

Fully-specified: Epistemological skepticism like ”how do we know these laws-
of-nature are true” doesn’t apply.

  4. 4.

Clear input-output distinction: There’s no ambiguity in the direction of
causal arrows.

Therefore, proposing and solving a few cases wouldn’t dissolve our objection.

Intuitions are often unreliable for modeling reality. Outside simple, everyday
causal utterances, there’s no real downside in abandoning actual causality.
$\mathcal{M}$ itself perfectly describes the causal system and answers all
”what if” inference queries like $\texttt{VFI}(\mathcal{M},\mathbf{w}_{exo})$.
Instead of listing ”actual causes,” a scientist should try modeling the
functional determinations in a system.

Actual causality is almost only used in normative theories (e.g.
responsibility, blame, proximate causes, ethics, law [Moore, 2019]), which
handle disagreements when everyone agrees on $\mathcal{M}$ (laws-of-nature)
and $\mathbf{w}_{a}$ (what actually happens). Working with full SFMs instead
of actual causality allows us to consider strictly more normative theories.

##  7 Probabilistic SFM

To incorporate probability theory, we don’t need to modify the definition of
SFM. We just extend domains $\mathcal{D}[u]$ to include random variables and
modify structural functions $\mathcal{F}[u]$ accordingly. Probability isn’t
required for most thought experiments on causality, but we’ll provide a
rigorous mathematical foundation for probabilistic SFM. Notably, nodes and
random variables are not the same. We avoid calling nodes ”variables”
precisely for this reason.

###  7.1 Probabilistic Extension

Think of a node $u$ as a name or index. Its value $\mathbf{w}(u)$ can be a
random variable: $\mathbf{w}(u)=X$. A random variable $X:\Omega\to\mathbb{R}$
maps an outcome $\omega$ (in sample space $\Omega$) to a real number
$X(\omega)\in\mathbb{R}$. ”$X=x$” is a shorthand for event
$\\{\omega\in\Omega|X(\omega)=x\\}$, so we can compute its probability
$\Pr[X=x]$. $X=x$ isn’t an actual equation because $X$ is a function and $x$
is a real number. Again, ”node $u$ has value $X$; $X$ is a random variable”
and ”random variable $X$ takes on value $x$; $x$ is a real number” are
different things.

Most basically, functions of random variables are actually function
compositions [Blitzstein and Hwang, 2015]. Consider real-valued function
$f(x)=2x$ and random variable $X:\Omega\to\mathbb{R}$. We want a new random
variable $Y$ that always ”takes twice the value” of $X$:

$\displaystyle Y(\omega)$ $\displaystyle=2X(\omega)$
$\displaystyle=f(X(\omega))$ $\displaystyle=(f\circ X)(\omega)$ $\displaystyle
Y$ $\displaystyle=f\circ X$

The expression ”$Y=f(X)$” is wrong by a rigorous standard, because random
variable $X$ isn’t in $f$’s domain of real numbers.

Formally, the probabilistic extension of SFM
$\mathcal{M}_{old}=(\mathcal{V},\mathcal{E},\mathcal{D}_{old},\mathcal{F}_{old})$
returns a new SFM
$\mathcal{M}_{new}=(\mathcal{V},\mathcal{E},\mathcal{D}_{new},\mathcal{F}_{new})$:

  1. 1.

Specify the sample space $\Omega$.

  2. 2.

Specify a set of nodes $\mathcal{S}\subseteq\mathcal{V}$ for probabilistic
extension. Other nodes $\mathcal{V}\setminus\mathcal{S}$ still don’t have
random variables in their domains.

The set $\mathcal{S}$ must be downward closed: if $u\in\mathcal{S}$, then
every descendant of $u$ must also be in $\mathcal{S}$, as if randomness is
”contagious” and flows down the computational graph.

For random variables to be well-defined, we also require
$\mathcal{D}_{old}[u]$ (e.g. real numbers, vectors, graphs, functions) to be
measurable for all $u\in\mathcal{S}$.

  3. 3.

Let $RV[u]$ denote the set of random variables
$\Omega\to\mathcal{D}_{old}[u]$. If $u\in\mathcal{S}$,
$\mathcal{D}_{new}[u]=\mathcal{D}_{old}[u]\cup RV[u]$; otherwise,
$\mathcal{D}_{new}[u]=\mathcal{D}_{old}[u]$.

  4. 4.

Recall that a random variable $X$ has realization $X(\omega)$ given outcome
$\omega\in\Omega$.

For nodes $\mathcal{X}\subseteq\mathcal{V}$, we define the realization of
assignment $\mathbf{w}_{|\mathcal{X}}$ given outcome $\omega$ as:

$\texttt{Realize}(\mathbf{w}_{|\mathcal{X}},\omega)=\\{u:\mathbf{w}_{|\mathcal{X}}(u)\textbf{
if }\mathbf{w}_{|\mathcal{X}}(u)\in\mathcal{D}_{old}[u]\textbf{ else
}(\mathbf{w}_{|\mathcal{X}}(u))(\omega)\\}_{u\in\mathcal{X}}$

By realizing every random variable with $\omega$ and keeping other values as
is, $\texttt{Realize}(\mathbf{w}_{|\mathcal{X}},\omega)$ is an assignment of
both $\mathcal{M}_{old}$ and $\mathcal{M}_{new}$ because $\forall
u\in\mathcal{V}:\texttt{Realize}(\mathbf{w}_{|\mathcal{X}},\omega)(u)\in\mathcal{D}_{old}[u]$.

  5. 5.

For $\mathcal{F}_{new}$ and endo-node $u\in\mathcal{V}_{endo}$:

     * •

If $\forall
p\in\mathrm{Pa}(u):\mathbf{w}_{|\mathrm{Pa}(u)}(p)\in\mathcal{D}_{old}[p]$ (no
parent value is a random variable), then
$\mathcal{F}_{new}[u](\mathbf{w}_{|\mathrm{Pa}(u)})=\mathcal{F}_{old}[u](\mathbf{w}_{|\mathrm{Pa}(u)})\in\mathcal{D}_{old}[u]$.

     * •

Otherwise (at least one parent value is a random variable),
$\mathcal{F}_{new}[u](\mathbf{w}_{|\mathrm{Pa}(u)})$ is a random variable
$\Omega\to\mathcal{D}_{old}[u]$ in $RV[u]$. For outcome $\omega\in\Omega$, we
compute
$\mathcal{F}_{new}[u](\mathbf{w}_{|\mathrm{Pa}(u)})(\omega)=\mathcal{F}_{old}[u](\texttt{Realize}(\mathbf{w}_{|\mathrm{Pa}(u)},\omega))$.

Some corollaries about probabilistic extension:

  1. 1.

For every $u\in\mathcal{V}$,
$\mathcal{F}_{new}[u]\supseteq\mathcal{F}_{old}[u]$ because both the domain
and the codomain are strictly extended, hence the name ”probabilistic
extension.”

  2. 2.

If $\mathbf{w}$ satisfies $\mathcal{M}_{old}$, then it also satisfies
$\mathcal{M}_{new}$. For $\mathcal{X}\subseteq\mathcal{V}$, if
$\mathbf{w}_{|\mathcal{X}}$ is permitted by $\mathcal{M}_{old}$, then it’s
also permitted by $\mathcal{M}_{new}$.

  3. 3.

If $\mathbf{w}$ satisfies $\mathcal{M}_{new}$, then its realization
$\texttt{Realize}(\mathbf{w},\omega)$ also satisfies $\mathcal{M}_{old}$ for
every $\omega\in\Omega$.

Intuitively, random variables express uncertainty about which realization is
actual. Each realization is a possible world in $\mathcal{M}_{old}$.
Probability merely adds ”weights” to these possible worlds, so causal
mechanisms are deterministic and true in every realization. This is unlike
Bayesian networks, where the mechanisms are inherently random.

We can now formalize ”correlation doesn’t imply causation” using SFM: The same
”observational distribution” $\mathbf{w}_{|\mathcal{X}}$ (where some nodes
have random variables as values; $\mathcal{X}\subseteq\mathcal{V}$) might be
permitted by different SFMs $\mathcal{M}_{1}\neq\mathcal{M}_{2}$ with
$R_{\mathcal{M}_{1}}\neq R_{\mathcal{M}_{2}}$, which cannot be treated as
equal.

###  7.2 Bayesian Networks

With probabilistic extension, SFM generalizes Bayesian networks, which also
use directed acyclic graphs. In a Bayesian network [Koller and Friedman,
2009], each node corresponds to a random variable, each exo-node stores a
marginal distribution, and each endo-node stores a conditional distribution
given the node’s parents.

Bayesian networks require the exogenous random variables to be
probabilistically independent, while we don’t enforce that requirement (you
may enforce it explicitly).

It’s difficult for Bayesian networks to represent SFM. To encode functional
determination (right-uniqueness), the conditional distributions must be
degenerate. When input distributions cannot be assumed (e.g. light switch
doesn’t affect TV) and we only have specific input values, the marginal
distributions are degenerate too. This sacrifices nearly all expressiveness of
a Bayesian network.

Any Bayesian network can be expressed by an SFM. We’ll use probability
integral transform (PIT) to represent conditional probability distributions
with deterministic functions:

  1. 1.

For simplicity, consider real-valued ($\Omega\to\mathbb{R}$) random variables
$Y,X_{1},X_{2},\dots,X_{n}$ and conditional distribution
$\Pr[Y|X_{1}=x_{1},X_{2}=x_{2},\dots,X_{n}=x_{n}]$.

  2. 2.

Create continuous uniform random variable $U\sim\mathrm{Unif}(0,1)$ in range
$[0,1]$, independent from all $X_{i}$.

  3. 3.

Let $F_{Y|X_{i}=x_{i}}(y):\mathbb{R}\to[0,1]$ be the conditional CDF
(cumulative distribution function) of $Y$, such that it has an inverse
$F_{Y|X_{i}=x_{i}}^{-1}:[0,1]\to\mathbb{R}$.

  4. 4.

By PIT [Blitzstein and Hwang, 2015], random variable
$F_{Y|X_{i}=x_{i}}^{-1}\circ U$ has exactly the same CDF as
$F_{Y|X_{i}=x_{i}}$.

  5. 5.

We’ve created a deterministic function $f(x_{1},x_{2},\dots,x_{n},U)$ that
returns a random variable $F_{Y|X_{i}=x_{i}}^{-1}\circ U$, given real-valued
$x_{i}$ and random variable $U$.

Essentially, we can enforce ”all mechanisms are deterministic” without
sacrificing expressiveness. The inherent randomness of a mechanism is
”injected” by an unobservable ”noise” parent whose value is a random variable.
This practice is fairly common:

  1. 1.

To sample values from $\mathcal{N}(\mu,\sigma^{2})$, the reparameterization
trick uses deterministic function
$f(\mu,\sigma,\epsilon)=\mu+\sigma\times\epsilon$, where $\epsilon$ is sampled
from an auxiliary ”noise” distribution $\mathcal{N}(0,1)$ [Kingma and Welling,
2013].

  2. 2.

Additive noise model $Y=f_{Y}(X)+N_{Y}$ has random variables $X,Y,N_{Y}$,
deterministic function $f_{Y}$, and additive noise $N_{Y}\perp X$ [Peters et
al., 2017].

  3. 3.

Randomness in computer programs often comes from built-in random number
generators, while the main program is deterministic.

##  8 Comparison

###  8.1 Symmetric Laws and Causal Eliminativism

In a symmetric equation of $n$ variables, the values of any $n-1$ variables
functionally determine the value of the 1 remaining variable. Newton’s second
law of motion $F=ma$, the ideal gas law $pV=nRT$, and Ohm’s law $V=IR$ are
symmetric laws. This differs from the non-injective asymmetry of functions. We
usually view symmetric equations as non-causal, because 1 equation is simpler
than $n$ functional determinations.

As a causal eliminativist, Russell [1912] argues that causality doesn’t appear
in physics and should be removed from philosophy altogether. However, we’ve
shown that functions and SFM are useful. We only consider Russell’s attack on
the functional theory of causation, since we don’t agree with other
definitions either.

  1. 1.

Plurality of causes: Multiple alternative causes like gunshot, arsenic, etc.
can map to the same effect - the person’s death. (Some functions are non-
injective.)

  2. 2.

Plurality of effects: The effect can be defined as the whole state of the
world, which contains many variables. (The ”cause” node has multiple
descendants.)

Russell incorrectly dismisses functional asymmetry (non-injectiveness) as
”illusory,” as if the plurality of effects makes both sides symmetric. But
these ”pluralities” aren’t the same. Non-injectiveness cannot be eliminated
without changing the function itself.

SFM also addresses other eliminativist challenges on causality [Frisch, 2022].
SFM-causality isn’t vague; actual causality, while not appearing in physics,
is a slightly useful heuristic that can be abandoned when necessary;
probabilistic extension handles inherently random mechanisms; functions are
compatible with different theories of space (e.g. action at a distance) and
time (Section 9.8).

###  8.2 Hume, Regularity, and Problem of Induction

Hume [1896] challenges causality as follows. We say ”striking a match causes
it to ignite.” But empirically, we only observe constant conjunctions of
events like ”match struck” followed by ”match igniting.” We don’t directly
observe the link/connection between cause and effect. So any causal ”law” is
an inductive generalization from particular events, with no necessary
guarantee to remain true in the future [Morris and Brown, 2022].

Hume conflates 2 distinct problems:

  1. 1.

Conceptual: What’s the definition of causality?

Claiming ”causality is just a special kind of regularity” is true but non-
reductive: What is that ”special kind”? All inductive models (e.g.
correlations, symmetric equations) model ”regular connections,” but only
functional determination captures our causal intuition.

Besides relying on unspecified physical/metaphysical models (e.g. time, space,
contiguity), regularity conditions like ”all events of type $X$ are followed
by an event of type $Y$” [Andreas and Guenther, 2021] cannot produce causal
utterances in background condition cases (Section 5.11), which are
deterministic and fully-specified.

  2. 2.

Epistemological: How to ensure the correctness of a causal model?

Non-probabilistic SFM (due to right-uniqueness) and symmetric laws make
exceptionless claims about reality, while correlation doesn’t. Perhaps that’s
why Hume attacks causality first. However, all inductive generalizations from
empirical data are equally susceptible to the Problem of Induction (PoI)
[Henderson, 2022]. Causality isn’t somehow ”more unreliable” than symmetric
laws or correlations.

We formulate PoI as follows. Consider a normal world $W_{1}(t)$ and a
piecewise world $W_{2}(t)$. $W_{2}(t)$ is exactly the same as $W_{1}(t)$ for
all time $t$ before $t_{0}$, but is drastically different after $t_{0}$. Given
a world $W$ and all its information before $t_{0}$, there’s no way of
distinguishing whether $W$ is $W_{1}$ or $W_{2}$.

By enumerating different ways of $W_{2}$ being ”drastically different”, such
as ”the world exploding after $t_{0}$” or ”the gravitational constant doubling
after $t_{0}$”, we can construct worlds where symmetric laws and correlations
break down under PoI. Therefore, PoI isn’t an attack against causality alone.
Similarly, a conceptual definition of causation won’t solve PoI.

###  8.3 Logic and Counterfactuals

In retrospect, ”if-then” material conditionals cannot replace causality
because it violates right-uniqueness: both $\\{p:0,q:0\\}$ and $\\{p:0,q:1\\}$
satisfy $p\Rightarrow q$. It allows vacuously true propositions like ”if I
don’t eat anything today, then I am a billionaire,” which feels wrong
causally/counterfactually. By adding the laws-of-nature ($\mathcal{M}$) to the
antecedents, we can perform rigorous deduction
$\mathbf{w}=\texttt{VFI}(\mathcal{M},\mathbf{w}_{exo})$ without sacrificing
causal intuitions. The underlying causal formula is $q=f(p,\dots)$ instead of
$p\Rightarrow q$, though functions and background conditions are often omitted
in causal utterances.

Like the but-for test, many counterfactual definitions of causation are
variations of ”if $x$, then $y$; if not-$x$, then not-$y$” [Menzies and
Beebee, 2020]. They’re usually imperfect because they don’t have the full
expressiveness of functions. For example, Mackie [1965]’s INUS condition is
equivalent to disjunctive normal form [Kim, 1971], which any Boolean function
can be converted to, so it’s just a circuitous way of stating ”causality is
functions.”

Lewis [1973] defines counterfactual conditional ”if not-$x$, then not-$y$” as
”in the closest possible world with not-$x$, there’s not-$y$.” However,
without defining a distance metric and an algorithm to find the closest
possible world, this definition cannot even describe a deterministic, fully-
specified causal system. Using actual-tweaked contrast, SFM unambiguously
computes the contrastive world as
$\mathbf{w}_{c}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{a},\mathbf{w}_{c|\mathcal{C}_{exo}})$.

###  8.4 Intervention and SCM

The definition of SCM [Pearl, 2009a] relies on intervention, a causal concept,
so it’s often criticized for being circular and non-reductive. We develop SFM
as an equally-expressive reformulation of SCM that only relies on functions,
thus eliminating circularity and providing a philosophical foundation for SCM.
The generality of functions also avoids anthropocentric objections that
manipulation requires human agency [Woodward, 2016].

Although SCM’s surgical intervention $do(Y=y)$ is generalized by sub-SFM, we
can also define it as a parent of $Y$, making intervention just a type of
functional determination.

Given $\mathrm{Pa}(Y)=\\{X_{1},X_{2},\dots,X_{n},DoY\\}$, $DoY$ is a surgical
intervention on $Y$ when:

  1. 1.

$\mathcal{D}[DoY]=\mathcal{D}[Y]\cup\\{\texttt{None}\\}$.
$\texttt{None}\notin\mathcal{D}[Y]$ means ”no intervention,” like in option
types and nullable types.

  2. 2.

There exists an ”ordinary mechanism” function
$g:\prod_{i=1}^{n}\mathcal{D}[X_{i}]\to\mathcal{D}[Y]$, such that

$\mathcal{F}[Y](\mathbf{w}_{|\mathrm{Pa}(Y)})=\begin{cases}g(\mathbf{w}_{|\\{X_{1},X_{2},\dots,X_{n}\\}})\textbf{
if }\mathbf{w}_{|\mathrm{Pa}(Y)}(DoY)=\texttt{None},\\\
\mathbf{w}_{|\mathrm{Pa}(Y)}(DoY)\textbf{ otherwise}\end{cases}$

”Conditionally overriding an ordinary mechanism” is the key intuition behind
interventions. For example, barometer reading is ordinarily determined by
atmospheric pressure, but it can also be manipulated by human intervention.
SFM can also express more complicated interventions, like when intervention
has a failure probability or when only some intervention options are possible
for humans.

##  9 Philosophical Applications

Many philosophical discussions take ”causation” as given without
mathematically defining what it is, so our functional definition of causality
may help clarify some downstream concepts.

###  9.1 Desires for SFM Learning

Several alleged ”metaphysical doctrines” about causality can now be seen as
epistemological desires for learning new SFMs:

  1. 1.

The Principle of Sufficient Reason (PSR): ”Everything has a cause” or
”anything is an effect caused by earlier events” [Melamed and Lin, 2021].

PSR desires to add parents to exo-nodes that ”have no causes” in old models.

  2. 2.

The Eleatic Principle (EP): For something to ”exist” in an ontology, it must
be able to cause changes in other things [Colyvan, 1998].

EP desires to add descendants to sink nodes that ”affect nothing” in old
models.

  3. 3.

Causal Nexus (CN): ”Any causal relation requires a nexus, some interface by
means of which cause and effect are connected” [Robb et al., 2023].

CN desires to insert intermediate nodes between old parent-child edges.

Strictly speaking, these desires are not satisfiable if we only allow finite
acyclic SFM (Appendix B), but they do encourage us to learn bigger SFMs to
model the world.

###  9.2 The Uncaused

Since exo-nodes can never appear in the ”effect” part of causal utterances, we
define node $u$ is uncaused relative to $\mathcal{M}$ iff
$u\in\mathcal{V}_{exo}$. Being uncaused/exogenous is not a metaphysical fact,
but a modeling choice we make: We don’t want to model $u$ as being determined
by a mechanism and other nodes in $\mathcal{M}$.

If $\mathcal{M}_{uni}$ is the SFM of the full world, we often only use some
sub-SFM $\mathcal{M}_{sub}$ for specific tasks. Because a node can be uncaused
(exo-node) in one sub-SFM and caused (endo-node) in another, regarding
”uncaused” as a node’s metaphysical property without specifying
$\mathcal{M}_{sub}$ is ill-defined. This is the source of many confusions.

For something with no causal parent anywhere, we say $u$ is strongly-uncaused
iff $u$ isn’t an endo-node in any sub-SFM $\mathcal{M}_{sub}$ (i.e. it’s an
exo-node in $\mathcal{M}_{uni}$).

###  9.3 Free Will

Free will loosely describes an agent’s ability to ”freely” choose between
different possible actions [O’Connor and Franklin, 2022]. We often face
seemingly conflicting intuitions:

  1. 1.

People have free will.

  2. 2.

The world’s past and laws-of-nature functionally determine the world’s future,
making people’s decisions unfree.

If we accept that something is free if it’s ”uncaused or not deterministically
caused” [Woodward, 2016], then SFM offers a mathematical definition of freedom
that resolves this conflict:

  1. 1.

Node $u$ is free relative to $\mathcal{M}$ iff $u$ is exogenous in
$\mathcal{M}$.

  2. 2.

Node $u$ is unfree relative to $\mathcal{M}$ iff $u$ is endogenous in
$\mathcal{M}$.

  3. 3.

Node $u$ is strongly-free iff $u$ is exogenous in every $\mathcal{M}$ of
interest that contains $u$.

  4. 4.

Node $u$ is strongly-unfree iff $u$ is endogenous in every $\mathcal{M}$ of
interest that contains $u$.

Whether an action is free depends on the model of interest. When actions have
consequences, we want to model the utility function $Q(s,a)$ for taking action
$a\in A$ at state $s\in S$. This makes action free relative to $Q(s,a)$, so
any action with consequences is not strongly-unfree. Meanwhile, the best
action $a^{*}=\pi(s,Q)=\arg_{a\in A}\max Q(s,a)$ is determined/unfree relative
to $\pi(s,Q)$. But for discrete $S,A$ without additional assumptions, finding
the best action requires computing $Q(s,a)$ for all $a\in A$, so modeling $a$
as a ”free” input is inevitable and useful: The agent evaluates the utility of
each action before taking the best action.

Besides reinforcement learning [Sutton and Barto, 2018], this best-action-
selection framework also applies to minimax search [Russell, 2010] and
decision-making in general. Although we don’t define causality using agency
like Menzies and Price [1993], we suggest that modeling ”actions functionally
determine consequences” could be an origin of human causal intuitions.

Generally, the freedom/arbitrariness/uncertainty of function inputs is closer
to the universal quantifier ”for all/any.” It’s not determined because we
don’t model it as another function’s output; it’s not random because we cannot
reasonably specify its marginal distribution and even if we do, the
distribution isn’t helpful for the downstream task.

  1. 1.

The light switch is free to vary, while the light is determined.

  2. 2.

To maximize $f(x)$, we freely vary $x$ and record the maximum $f(x)$.

  3. 3.

We freely change causes $\mathbf{w}_{1|\mathcal{C}_{exo}}$ and infer effects
$\mathbf{w}_{1|\mathcal{C}_{endo}}\subseteq\texttt{CFI}(\mathcal{M},\mathbf{w}_{0},\mathbf{w}_{1|\mathcal{C}_{exo}})$.

  4. 4.

A sorting algorithm works for an arbitrary input list.

###  9.4 Causal Explanation

We use explanans to explain explanandum. A causal explanation uses causes (and
underlying mechanisms/laws-of-nature) to explain effects. There are also non-
causal explanations that appeal to symmetric equations, correlation, or
backtracking (using effects to explain causes).

With SFM, causal explanations become a subset of Deductive-Nomological (DN)
explanations, where (1) explanans contains general laws and particular
conditions; (2) explanandum is entailed by explanans [Woodward and Ross,
2021].

Using $\mathbf{w}_{a|\mathcal{C}_{exo}}$ to explain
$\mathbf{w}_{a|\mathcal{C}_{endo}}$, we use general laws $\mathcal{M}$ and
particular conditions $\mathbf{w}_{c},\mathbf{w}_{a|exo}$; entailment comes
from
$\mathbf{w}_{a|\mathcal{C}_{endo}}\subseteq\mathbf{w}_{a}=\texttt{CFI}(\mathcal{M},\mathbf{w}_{c},\mathbf{w}_{a|\mathcal{C}_{exo}})$.
In practice, $\mathcal{M}$ can be learned from empirical data (inductive);
some nodes’ values can be random variables (probabilistic).

SFM solves many alleged counterexamples where DN model appears insufficient
for defining explanation:

  1. 1.

In the symmetric equation involving shadow length, the Sun’s position, and
flagpole height, why is shadow the explanandum? Because we prefer causal
explanations over non-causal explanations and shadow should be modeled as a
child node (Section 4.2).

  2. 2.

Why do people omit irrelevant background conditions in explanations? Because
we use delta compression in causal utterances (Section 5.14, 5.12).

The asymmetry of causal explanation comes from the asymmetry of causality,
which comes from functions being right-unique and often non-injective.

###  9.5 Disposition

Glass is fragile because it has a disposition to shatter. Dispositions like
fragility resemble properties of objects, but they describe possible (not
necessarily actual) behaviors under certain conditions: Glass may not actually
shatter [Choi and Fara, 2021]. We analyze dispositions with functions.

For a deterministic and fully-specified example, minerals higher on Mohs
hardness scale (e.g. diamond) will scratch softer minerals (e.g. talc). Let
function $f(m_{1},m_{2})$ take in 2 minerals and return the mineral that gets
scratched, so $\texttt{Talc}=f(\texttt{Diamond},\texttt{Talc})$. Talc has the
disposition to be scratched because $\forall
m:\texttt{Talc}=f(m,\texttt{Talc})$; diamond has the ”power” to scratch
because $\forall m:m=f(m,\texttt{Diamond})$.

Therefore, dispositions are properties of a downstream function $f$, but
people colloquially associate them with input nodes (scratch-hardness of
minerals) or input values (scratch-hardness of diamond).

###  9.6 Supervenience

”$Y$ supervenes on $X$” is equivalent to ”$Y$ functionally depends on $X$,”
because the formal definition of supervenience (”there cannot be an
$Y$-difference without a $X$-difference” [McLaughlin and Bennett, 2021]) is
the same as right-uniqueness: Consider team $R$,

$\displaystyle\ \quad\neg([(x,y_{1})\in R]\land[(x,y_{2})\in R]\land[y_{1}\neq
y_{2}])$ $\displaystyle=\neg([(x,y_{1})\in R]\land[(x,y_{2})\in
R])\lor\neg[y_{1}\neq y_{2}]$ $\displaystyle=\neg([(x,y_{1})\in
R]\land[(x,y_{2})\in R])\lor[y_{1}=y_{2}]$ $\displaystyle=([(x,y_{1})\in
R]\land[(x,y_{2})\in R])\Rightarrow[y_{1}=y_{2}]$

###  9.7 Mental Causation

Can mental kinds (property, state, event) cause physical kinds? Mental
causation faces 2 conflicting intuitions:

  1. 1.

It’s common in everyday experiences: I want to raise my hand (mental state),
so I raise my hand (body state).

  2. 2.

The Exclusion Problem: Physical effects like body movements are already
determined by physical causes like brain activities, so there’s no room for a
mental cause, which is also sufficient for the physical effect [Robb et al.,
2023].

The Exclusion Problem arises whenever a functional determination entailed by
$(\mathcal{V},\mathcal{E},\mathcal{D},\mathcal{F})$ cannot be deduced from the
graph structure $\mathcal{G}=(\mathcal{V},\mathcal{E})$ (and Armstrong’s
Axioms) alone. People feel uneasy because they cannot find such dependency as
a path in $\mathcal{G}$.

  1. 1.

(Assumption) On the lowest physical level, brain state functionally determines
body state: $\texttt{BrainState}\xrightarrow{f_{1}}\texttt{BodyState}$.

  2. 2.

(Assumption) Mental state supervenes on brain state:
$\texttt{BrainState}\xrightarrow{f_{2}}\texttt{MentalState}$. Mental state is
an abstract/aggregate description of physical brain state.

Multiple realizability (a single mental kind can be realized by many distinct
physical kinds) [Bickle, 2020] is true when $f_{2}$ is non-injective.

It’s a coincidence that functionalism (name unrelated to mathematical
functions) uses causality to define mental states [Levin, 2023] and we reduce
causality to functions.

  3. 3.

So we have an SFM $\mathcal{M}$ with graph
$\texttt{BodyState}\leftarrow\texttt{BrainState}\to\texttt{MentalState}$ and
functions
$\mathcal{F}=\\{\texttt{BodyState}:f_{1},\texttt{MentalState}:f_{2}\\}$.

  4. 4.

(Fact) There exists a function $f_{3}$ such that
$\texttt{MentalState}\xrightarrow{f_{3}}\texttt{BodyState}$ is true in every
$\mathbf{w}\in R_{\mathcal{M}}$. Mental state does functionally determine body
state.

$\texttt{MentalState}\xrightarrow{f_{3}}\texttt{BodyState}$ cannot be deduced
from $\mathcal{G}$ alone. It’s entailed by the specific functional mappings
$f_{1},f_{2}$ (and $(\mathcal{V},\mathcal{E},\mathcal{D})$). Although it
cannot appear as a path in $\mathcal{G}$, we see no reason to dismiss it as
”excluded.” We may use SFM-intersection to explicitly/graphically encode this
functional dependency, although $R_{\mathcal{M}}$ is entailed by a single SFM
$\mathcal{M}$ (SFM-intersection-proper isn’t required).

The Exclusion Problem appears in any system with hierarchical levels of
abstraction, since supervenience is just functional dependency. In fully-
specified and deterministic computers, what causes a video to play on screen,
the low-level chip activities or the high-level video-player program? The same
reasoning applies. The only empirical question is whether higher-level
functional determinations like $f_{3}$ are true. If not, we simply say the
abstraction is broken.

###  9.8 Time

SFM doesn’t endorse any particular theory of time, but we can define
$T:\mathcal{V}\to\mathbb{R}$ that maps each node $u$ to a real-valued
timestamp $T(u)$. If $\forall(u,v)\in\mathcal{E}:T(u)\leq T(v)$, then causes
always temporally precede their effects. But without additional assumptions,
$T$ might as well violate this condition.

Backward causation occurs when an effect temporally precedes its cause [Faye,
2021]. If most SFM edges $(u,v)\in\mathcal{E}$ still point from past to future
($T(u)\leq T(v)$), a backward edge can create cycles, resulting in PULO or
actually unsatisfiable laws. That’s why people intuitively dislike backward
causation. But if the specific SFM is satisfiable or satisfied by empirical
data, we cannot dismiss it a priori.

Are there fundamental properties of our physical world that make causal and
temporal orders agree? Could it be the asymmetry of thermodynamics, radiation
[Frisch, 2022], or our mental habit of ”actions determining consequences”
(Section 9.3)? Further research is required.

In a causal feedback loop $A\to A$, node $A$ influences its own next state.
With discrete time, we can unroll it to an acyclic time-indexed causal chain
$A(0)\xrightarrow{\mathcal{F}[A(1)]}A(1)\xrightarrow{\mathcal{F}[A(2)]}A(2)\xrightarrow{\mathcal{F}[A(3)]}\dots$,
which may be countably infinite. When every $\mathcal{F}[A(t)]$ is invertible,
the system has time-symmetry and another equivalent SFM
$A(0)\xleftarrow{\mathcal{F}[A(1)]^{-1}}A(1)\xleftarrow{\mathcal{F}[A(2)]^{-1}}A(2)\xleftarrow{\mathcal{F}[A(3)]^{-1}}\dots$.

Decreasing the interval between 2 consecutive timestamps towards the
infinitesimal, we eventually get an uncountable number of nodes and cannot
properly define an edge, because there are no 2 ”consecutive” real numbers. In
this case, it would make more sense for $A(t)$ to determine its instantaneous
rate of change $\frac{d}{dt}A(t)$, like the exponential/logistic growth rate
of bacteria population size and the predator-prey dynamics in Lotka-Volterra
equations. SFM-intersection-proper can represent autonomous differential
equations, which include causal loop diagrams [Haraldsson, 2004]. However,
differential equation in general are better tools for modeling continuous-time
causality.

##  10 Conclusion

After our conceptual analysis that reduces causality to functions, there
should be nothing mysterious about the definition of causality. Using forward
inference, contrast, and delta compression, Structural Functional Model (SFM)
correctly produces intuitive causal utterances. We’ve also supported intuitive
practices from an algorithmic perspective: contrast saves space and time;
finite acyclic SFM is required for guaranteed satisfiability (at the cost of
expressiveness). Distinct from but compatible with probability theory,
”causality as functions” allows for interesting downstream applications.

## References

  * Koller and Friedman [2009] Daphne Koller and Nir Friedman.  _Probabilistic graphical models: principles and techniques_.  MIT press, 2009.
  * Gallow [2022] J. Dmitri Gallow.  The Metaphysics of Causation.  In Edward N. Zalta and Uri Nodelman, editors, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Fall 2022 edition, 2022.
  * Väänänen [2007] Jouko Väänänen.  _Dependence logic: A new approach to independence friendly logic_ , volume 70.  Cambridge University Press, 2007.
  * Russell [1912] Bertrand Russell.  On the notion of cause.  In _Proceedings of the Aristotelian society_ , volume 13, pages 1–26. JSTOR, 1912.
  * Simon and Rescher [1966] Herbert A Simon and Nicholas Rescher.  Cause and counterfactual.  _Philosophy of science_ , 33(4):323–340, 1966\.
  * Pearl [2009a] Judea Pearl.  _Causality_.  Cambridge university press, 2009a.
  * Galliani [2021] Pietro Galliani.  Dependence Logic.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Summer 2021 edition, 2021.
  * Silberschatz et al. [2020] Abraham Silberschatz, Henry F. Korth, and S. Sudarshan.  _Database system concepts_.  McGraw-Hill, 2020.
  * Grädel and Väänänen [2013] Erich Grädel and Jouko Väänänen.  Dependence and independence.  _Studia Logica_ , 101(2):399–410, 2013.
  * Pearl [2009b] Judea Pearl.  Causal inference in statistics: An overview.  2009b.
  * Halpern and Pearl [2005] Joseph Y Halpern and Judea Pearl.  Causes and explanations: A structural-model approach. part i: Causes.  _The British journal for the philosophy of science_ , 2005.
  * Kim [2005] Jaegwon Kim.  _Physicalism, or Something Near Enough_.  Princeton University Press, 2005.  ISBN 9780691133850.  URL http://www.jstor.org/stable/j.ctt7snrs.
  * Schaffer [2005] Jonathan Schaffer.  Contrastive causation.  _The Philosophical Review_ , 114(3):327–358, 2005\.
  * Halpern and Hitchcock [2015] Joseph Y Halpern and Christopher Hitchcock.  Graded causation and defaults.  _The British Journal for the Philosophy of Science_ , 2015.
  * Hitchcock [2021] Christopher Hitchcock.  Probabilistic Causation.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Spring 2021 edition, 2021.
  * Hernan and Robins [2020] MA Hernan and J Robins.  Causal inference: What if. boca raton: Chapman & hill/crc.  2020\.
  * Suel [2019] Torsten Suel.  Delta compression techniques.  _Encyclopedia of Big Data Technologies_ , 63, 2019.
  * Russell [2010] Stuart J Russell.  _Artificial intelligence a modern approach_.  Pearson Education, Inc., 2010.
  * Cormen et al. [2022] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  _Introduction to algorithms_.  MIT press, 2022.
  * Patt and Patel [2020] Yale N Patt and Sanjay J Patel.  _Introduction to Computing Systems; Bits & Gates to C C++ and Beyond_.  McGraw-Hill, 2020.
  * gnu [2023] Gnu make manual, Feb 2023.  URL https://www.gnu.org/software/make/manual/make.html.
  * Peters et al. [2017] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf.  _Elements of causal inference: foundations and learning algorithms_.  The MIT Press, 2017.
  * Blanchard and Schaffer [2017] Thomas Blanchard and Jonathan Schaffer.  Cause without default.  _Making a difference_ , pages 175–214, 2017.
  * Hart and Honoré [1985] Herbert Lionel Adolphus Hart and Tony Honoré.  _Causation in the Law_.  OUP Oxford, 1985.
  * Achinstein [1975] Peter Achinstein.  Causation, transparency, and emphasis.  _Canadian Journal of Philosophy_ , 5(1):1–23, 1975.
  * Hitchcock [2001] Christopher Hitchcock.  The intransitivity of causation revealed in equations and graphs.  _The Journal of Philosophy_ , 98(6):273–299, 2001\.
  * Salmon [1971] Wesley C Salmon.  _Statistical explanation and statistical relevance_ , volume 69.  University of Pittsburgh Pre, 1971.
  * Starr [2022] W. Starr.  Counterfactuals.  In Edward N. Zalta and Uri Nodelman, editors, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Winter 2022 edition, 2022.
  * Moore [2019] Michael Moore.  Causation in the Law.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Winter 2019 edition, 2019.
  * Blitzstein and Hwang [2015] Joseph K Blitzstein and Jessica Hwang.  _Introduction to probability_.  CRC Press/Taylor & Francis Group Boca Raton, FL, USA, 2015.
  * Kingma and Welling [2013] Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ , 2013.
  * Frisch [2022] Mathias Frisch.  Causation in Physics.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Spring 2022 edition, 2022.
  * Hume [1896] David Hume.  _A treatise of human nature_.  Clarendon Press, 1896.
  * Morris and Brown [2022] William Edward Morris and Charlotte R. Brown.  David Hume.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Summer 2022 edition, 2022.
  * Andreas and Guenther [2021] Holger Andreas and Mario Guenther.  Regularity and Inferential Theories of Causation.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Fall 2021 edition, 2021.
  * Henderson [2022] Leah Henderson.  The Problem of Induction.  In Edward N. Zalta and Uri Nodelman, editors, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Winter 2022 edition, 2022.
  * Menzies and Beebee [2020] Peter Menzies and Helen Beebee.  Counterfactual Theories of Causation.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Winter 2020 edition, 2020.
  * Mackie [1965] John L Mackie.  Causes and conditions.  _American philosophical quarterly_ , 2(4):245–264, 1965.
  * Kim [1971] Jaegwon Kim.  Causes and events: Mackie on causation.  _The Journal of Philosophy_ , 68(14):426–441, 1971.
  * Lewis [1973] David K. Lewis.  _Counterfactuals_.  Malden, Mass.: Blackwell, 1973.
  * Woodward [2016] James Woodward.  Causation and Manipulability.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Winter 2016 edition, 2016.
  * Melamed and Lin [2021] Yitzhak Y. Melamed and Martin Lin.  Principle of Sufficient Reason.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Summer 2021 edition, 2021.
  * Colyvan [1998] Mark Colyvan.  Can the eleatic principle be justified?  _Canadian journal of philosophy_ , 28(3):313–335, 1998.
  * Robb et al. [2023] David Robb, John Heil, and Sophie Gibb.  Mental Causation.  In Edward N. Zalta and Uri Nodelman, editors, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Spring 2023 edition, 2023.
  * O’Connor and Franklin [2022] Timothy O’Connor and Christopher Franklin.  Free Will.  In Edward N. Zalta and Uri Nodelman, editors, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Winter 2022 edition, 2022.
  * Sutton and Barto [2018] Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Menzies and Price [1993] Peter Menzies and Huw Price.  Causation as a secondary quality.  _The British Journal for the Philosophy of Science_ , 44(2):187–203, 1993.
  * Woodward and Ross [2021] James Woodward and Lauren Ross.  Scientific Explanation.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Summer 2021 edition, 2021.
  * Choi and Fara [2021] Sungho Choi and Michael Fara.  Dispositions.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Spring 2021 edition, 2021.
  * McLaughlin and Bennett [2021] Brian McLaughlin and Karen Bennett.  Supervenience.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Summer 2021 edition, 2021.
  * Bickle [2020] John Bickle.  Multiple Realizability.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Summer 2020 edition, 2020.
  * Levin [2023] Janet Levin.  Functionalism.  In Edward N. Zalta and Uri Nodelman, editors, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Summer 2023 edition, 2023.
  * Faye [2021] Jan Faye.  Backward Causation.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Spring 2021 edition, 2021.
  * Haraldsson [2004] Hördur V Haraldsson.  _Introduction to system thinking and causal loop diagrams_.  Department of chemical engineering, Lund University Lund, Sweden, 2004\.
  * Weisberg [2021] Jonathan Weisberg.  Formal Epistemology.  In Edward N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Spring 2021 edition, 2021.

##  Appendix A Mathematics Review

Under ZFC set theory, a set is roughly an unordered collection of distinct
elements. The binary Cartesian product between two sets $X$ and $Y$ is
$X\times Y=\\{(x,y)|x\in X\land y\in Y\\}$. A binary relation $R$ over $X$ and
$Y$ is $R\subseteq X\times Y$. A relation $R$ may have properties:

  1. 1.

Left-total: $\forall x\in X\exists y\in Y:(x,y)\in R$

  2. 2.

Right-total: $\forall y\in Y\exists x\in X:(x,y)\in R$

  3. 3.

Left-unique: $\forall x_{1}\in X,x_{2}\in X,y\in Y:((x_{1},y)\in
R)\land((x_{2},y)\in R)\Rightarrow x_{1}=x_{2}$

  4. 4.

Right-unique: $\forall x\in X,y_{1}\in Y,y_{2}\in Y:((x,y_{1})\in
R)\land((x,y_{2})\in R)\Rightarrow y_{1}=y_{2}$

  5. 5.

Function (total function): left-total and right-unique.

  6. 6.

Partial function: right-unique.

  7. 7.

Injective function: left-unique function.

  8. 8.

Surjective function: right-total function.

  9. 9.

Bijective function: injective and surjective function.

Because of right-uniqueness, a function can be written as $f:X\to Y$ such that
$f(x)\in Y$ is unique for every $x\in X$. For functions $f:X\to Y$ and $g:S\to
Y$ satisfying $S\subseteq X$, if $\forall x\in S:f(x)=g(x)$, we say $g$ is a
restriction of $f$ and $f$ is an extension of $g$ (or $f$ extends $g$).
Because functions are relations, we write $g\subseteq f$ or $g=f_{|S}$.

An indexed collection of sets is a 3-tuple $(I,\mathcal{A},A)$ written as
$\\{A_{i}\\}_{i\in I}$, where $I$ is the index set, $\mathcal{A}$ is a
collection of sets, and $A$ is a function $A:I\to\mathcal{A}$. Every
$A_{i}=A(i)\in\mathcal{A}$ is a set. Now we can define Cartesian product over
any (possibly infinite-sized) indexed collection of sets: $\prod_{i\in
I}A_{i}$ is the set of all functions $f:I\to\bigcup_{i\in I}A_{i}$ such that
$\forall i\in I:f(i)\in A_{i}$. Similarly, a relation over an indexed
collection of sets is a subset of its Cartesian product.

A directed graph is an ordered pair $\mathcal{G}=(\mathcal{V},\mathcal{E})$,
where $\mathcal{V}$ is a set of nodes and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is a set of directed edges.
A directed edge is an ordered pair $(u,v)$ such that $u\in\mathcal{V}$ and
$v\in\mathcal{V}$.

  * •

If $(u,v)\in\mathcal{E}$, $u$ is a parent of $v$ and $v$ is a child of $u$.

  * •

$\mathrm{Pa}(u)$ denotes the set of parents of $u$; $\mathrm{Ch}(u)$ denotes
the set of children of $u$.

  * •

The indegree of $u$ is the number of its parents
($\mathrm{deg}^{-}(u)=|\mathrm{Pa}(u)|$); the outdegree of $u$ is the number
of its children ($\mathrm{deg}^{+}(u)=|\mathrm{Ch}(u)|$); the degree of $u$ is
the sum of its indegree and outdegree
($\mathrm{deg}(u)=\mathrm{deg}^{-}(u)+\mathrm{deg}^{+}(u)$).

  * •

A root node $u$ has indegree $\mathrm{deg}^{-}(u)=0$. A sink node $u$ has
outdegree $\mathrm{deg}^{+}(u)=0$.

  * •

A path is a sequence of nodes $v_{1},v_{2},\dots,v_{n}$ such that
$(v_{i},v_{i+1})\in\mathcal{E}$ for any $i\in\\{1,2,\dots,n-1\\}$; a path is a
cycle if $v_{1}=v_{n}$.

  * •

Node $u$ is an ancestor of node $v$ ($u\in\mathrm{An}(v)$) if there’s a path
from $u$ to $v$. Otherwise, $u$ is a non-ancestor of $v$.

  * •

Node $u$ is a descendant of node $v$ ($u\in\mathrm{De}(v)$) if there’s a path
from $v$ to $u$. Otherwise, $u$ is a non-descendant of $v$.

  * •

Under our convention, a node is the ancestor/descendant of itself.

##  Appendix B Generalized Münchhaussen Trilemma

We formalize a theorem that generalizes Münchhaussen Trilemma [Weisberg, 2021]
in epistemology:

######  Theorem B.1 (Generalized Münchhaussen Trilemma (GMT)).

Any directed graph $G=(V,E)$ contains at least one of the following:

  * •

A root.

  * •

A cycle.

  * •

An infinite regress: An infinite path of distinct nodes
$(\dots,u_{2},u_{1},u_{0})$ ending at $u_{0}$, such that for any integer
$i\geq 1$, there exists $u_{i}\in V$ satisfying $(u_{i},u_{i-1})\in E$ and
$u_{i}\notin\\{u_{j}\\}_{j=0}^{i-1}$

###### Proof.

Proving by contradiction, suppose instead that a graph has no root, no cycle,
and no infinite regress. Since there’s no infinite regress, there exists a
nonnegative integer $n$ that is the maximum length of a path of distinct nodes
ending at some $u\in V$. Let $(u_{n},u_{n-1},\dots,u_{1},u_{0})$ be that
maximum-length path.

Because $G$ doesn’t have a root, $\mathrm{deg}^{-}(u)\geq 1$ for all $u\in V$
and thus $\mathrm{deg}^{-}(u_{n})\geq 1$, so there exists a node $v\in V$ such
that $(v,u_{n})\in E$ is an edge.

If $v\in\\{u_{i}\\}_{i=0}^{n}$, then $v=u_{i}$ for some integer $0\leq i\leq
n$. We can construct a new path $(u_{n},u_{n-1},\dots,u_{i},u_{n})$. It’s a
path because $(u_{i},u_{n})=(v,u_{n})\in E$ and $(u_{i},u_{i-1})\in E$ for all
$1\leq i\leq n$; it’s a cycle because it starts and ends at $u_{n}$. This
violates the acyclic assumption, so $v\notin\\{u_{i}\\}_{i=0}^{n}$ is distinct
from all nodes in the path.

We can thus construct a new path $(v,u_{n},u_{n-1},\dots,u_{1},u_{0})$ of
length $n+1$, where all nodes have been shown to be distinct. However, this
contradicts the condition that the maximum length of distinct-node paths is
$n$. Therefore, it’s impossible for a directed graph to have no root, no
cycle, and no infinite regress at the same time. ∎

GMT is a general theorem about directed graphs, proven mathematically. It
applies to all problems characterized by objects and directed binary relations
between them (i.e. describable by a directed graph), such as ”$X$ causes $Y$”
and ”$X$ justifies $Y$.”

If we define a directed graph where nodes are propositions and edge $(u,v)$
means ”$u$ justifies $v$” or ”$u$ is a part of the justification for $v$”,
then GMT entails that we either settle with foundationalism (root that isn’t
justified), coherentism (cycle that justifies itself), or infinitism (infinite
regress of justification chain) - we cannot simultaneously eliminate all 3 of
them. Notice how we never used the meaning of ”justification” in our proof,
only the directed binary form of ”$A$ justifies $B$.”