<p><em>Note:</em> This is a better-written version of an <a href="https://mathoverflow.net/questions/289658/is-there-a-complete-countable-axiomatization-of-conditional-independence-graph">unanswered question asked before on MathOverflow</a>.</p>
<blockquote>
<p><strong>Question:</strong> Is there a complete and finite axiom scheme for conditional probability?</p>
<p>If so, is there a reference stating the axiom scheme in a manner understandable to someone with knowledge of only probability theory, and without knowledge of mathematical logic?</p>
</blockquote>
<p>A complete axiomatization or axiom scheme means that every result of the theory can be shown to be a result of the axioms involved. A finite axiomatization involves only finitely many axioms. I understand a finite axiom scheme to mean possibly infinitely many axioms expressable with finitely many symbols (e.g. the axiom scheme in Tarski's axiomatization of Euclidean geometry). <span class="math-container">$ \newcommand\independent{\perp\,\!\,\!\,\!\,\!\,\!\,\!\,\!\!\!\!\perp}$</span></p>
<p><strong>Background:</strong> Judea Pearl at the Computer Science department at UCLA and co-workers <a href="https://www.sciencedirect.com/science/article/pii/089054019190077F" rel="nofollow noreferrer">found a complete and finite axiomatization of (unconditional) probabilistic independence</a> in the 1990's and then began to look for a complete and finite axiomatization of conditional independence. However, Studeny showed in 1992 <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51.7014&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">[1]</a><a href="ftp://ftp.utia.cas.cz/pub/staff/studeny/ci-no-axiom-92.pdf" rel="nofollow noreferrer">[2]</a> that no such complete and finite axiomatization exists.</p>
<p>An aspect of Studeny's 1992 paper which is less often emphasized is that it also <em>claims</em> to give a complete axiom scheme for conditional probability. Since the paper is written using very abstract mathematical logic, I don't understand what the axiom scheme is supposed to be. Wolfgang Spohn wrote <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.8198&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">[1]</a><a href="http://kops.uni-konstanz.de/bitstream/handle/123456789/3473/Spohn_1994_On_the_Properties.pdf?sequence=1&amp;isAllowed=y" rel="nofollow noreferrer">[2]</a> about the result and gives what is a somewhat more transparent description of the axiom scheme, but the organization of his paper is unclear to me, as is the notation at times. <a href="https://arxiv.org/abs/0704.2847" rel="nofollow noreferrer">Seth Sullivant appears to have written about a similar issue</a>, which may have allowed me to understand at least one part of the axiom scheme. Attempting to interpolate between those three papers, this may be what a complete and finite axiom scheme for conditional probability looks like (please note that the the <span class="math-container">$U$</span>'s, <span class="math-container">$V$</span>'s, <span class="math-container">$W$</span>'s, <span class="math-container">$X$</span>'s, <span class="math-container">$\tilde{X}$</span>'s, <span class="math-container">$Y$</span>'s, and <span class="math-container">$\tilde{Y}$</span>'s are all supposed to denote random variables):</p>
<ol>
<li><span class="math-container">$$\{X_1, \dots, X_k \} \independent \{Y_1, \dots, Y_l\} | \{W_1, \dots, W_m\}$$</span> <span class="math-container">$$\iff \{Y_1, \dots, Y_l\} \independent \{X_1, \dots, X_k\} | \{W_1 \dots W_m\}$$</span></li>
<li><span class="math-container">$$\{V_1, \dots, V_j\} \independent \emptyset | \{W_1, \dots, W_m \}$$</span></li>
<li><span class="math-container">$$\{V_1, \dots, V_j\} \independent \{X_1, \dots, X_k\} \cup \{Y_1, \dots, Y_l\} | \{W_1, \dots, W_m\}$$</span> <span class="math-container">$$\implies \{V_1, \dots, V_j\} \independent \{X_1, \dots, X_k\} | \{W_1, \dots, W_m\}$$</span></li>
<li><span class="math-container">$$\{V_1, \dots, V_j\} \independent \{X_1, \dots, X_k\} \cup \{Y_1, \dots, Y_l\} | \{W_1 ,\dots, W_m \}$$</span> <span class="math-container">$$\implies \{ V_1, \dots, V_j\} \independent \{X_1, \dots, X_k\} | \{Y_1, \dots, Y_l\} \cup \{W_1, \dots, W_m \}$$</span></li>
<li><span class="math-container">$$\{V_1, \dots, V_j\} \independent \{X_1, \dots, X_k \} | \{Y_1, \dots, Y_l\} \cup \{W_1, \dots, W_m \}$$</span> <span class="math-container">$$\text{and }\{V_1, \dots, V_j\} \independent \{Y_1, \dots, Y_l\} | \{W_1, \dots, W_m\}$$</span> <span class="math-container">$$\implies \{V_1, \dots, V_j\} \independent \{X_1, \dots, X_k\} \cup \{Y_1, \dots, Y_l\} | \{W_1, \dots, W_m\}$$</span></li>
<li>For a strictly positive probability measure, i.e. <span class="math-container">$\mathbb{P}(A) = 0 \iff A = \emptyset$</span>, we have: <span class="math-container">$$\{V_1, \dots, V_j\} \independent \{X_1, \dots, X_k \} | \{Y_1, \dots, Y_l\} \cup \{W_1, \dots, W_m \}$$</span> <span class="math-container">$$\text{and }\{V_1, \dots, V_j\} \independent \{Y_1, \dots, Y_l \} | \{X_1, \dots, X_k\} \cup \{W_1, \dots, W_m\}$$</span> <span class="math-container">$$\implies \{V_1,\dots,V_j\} \independent \{X_1, \dots, X_k\} \cup \{Y_1, \dots, Y_l\} | \{W_1, \dots, W_m\} $$</span></li>
<li>If <span class="math-container">$U$</span> is an RV taking only two values, e.g. Bernoulli or Rademacher, then <span class="math-container">$$\{X_1, \dots,X_k\} \independent \{Y_1, \dots, Y_l\} \text{ and } \{X_1,\dots, X_k\} \independent \{Y_1, \dots, Y_l\} | U $$</span> <span class="math-container">$$\implies \{X_1, \dots, X_k \} \cup U \independent \{Y_1, \dots, Y_l\} \text{ or }\{X_1, \dots, X_k\} \independent \{Y_1, \dots, Y_l\} \cup U $$</span></li>
<li><span class="math-container">$$\{X_1, \dots, X_k\} \independent \{\tilde{X}_1,\dots, \tilde{X}_{\tilde{k}} \} \,, \{Y_1, \dots, Y_l\} \independent \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}}\} | \{X_1, \dots, X_k\} \,, $$</span> <span class="math-container">$$\{Y_1, \dots, Y_l \} \independent \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}}\} | \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}}\}\,, \text{ and } $$</span> <span class="math-container">$$\{X_1, \dots, X_k\} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}} \} | \{Y_1, \dots, Y_l\} \cup \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}} \} $$</span> <span class="math-container">$$ \iff \{Y_1, \dots, Y_l \} \independent \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}} \} \,, \{X_1, \dots, X_k\} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}}\} | \{Y_1, \dots, Y_l\} \,, $$</span> <span class="math-container">$$\{X_1, \dots, X_k \} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}} \} | \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}} \} \,, \text{ and }$$</span> <span class="math-container">$$\{ Y_1, \dots, Y_l\} \independent \{\tilde{Y}_1, \dots, \tilde{Y}_l \} | \{X_1, \dots, X_k\} \cup \{ \tilde{X}_1, \dots, \tilde{X}_k \}  $$</span></li>
<li>For a strictly positive probability measure, i.e. <span class="math-container">$\mathbb{P}(A) = 0 \iff A = \emptyset$</span>, we have: <span class="math-container">$$\text{If }\{Y_1, \dots, Y_l\} \independent \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}} | \{X_1, \dots, X_k \} \cup \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}}\} \cup \{W_1, \dots, W_m\} \,,$$</span> then any three of the following implies the fourth: <span class="math-container">$$\{X_1, \dots, X_k \} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}}\} | \{W_1, \dots, W_m\}\,,  $$</span> <span class="math-container">$$\{X_1, \dots, X_k  \} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}} \} | \{Y_1, \dots, Y_l\} \cup \{W_1, \dots, W_m \} \,, $$</span> <span class="math-container">$$\{ X_1, \dots, X_k \} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}}\} | \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}} \} \cup \{W_1, \dots, W_m \} \,,  $$</span> <span class="math-container">$$\{X_1, \dots, X_k \} \independent \{\tilde{X}_1, \dots, \tilde{X}_{\tilde{k}} \} | \{Y_1, \dots, Y_l \} \cup \{\tilde{Y}_1, \dots, \tilde{Y}_{\tilde{l}}\} \cup \{W_1, \dots, W_m\} \,. $$</span></li>
<li>For every <span class="math-container">$n \ge 4$</span> (this is technically an axiom scheme and not an axiom because as Studeny showed in 1992 these are all logically independent of one another for each <span class="math-container">$n$</span>) one has that: <span class="math-container">$$X_1 \independent X_2 | X_3\,, X_2 \independent X_3 | X_4\,, \dots, X_{n-1} \independent X_n | X_1\,, X_n \independent X_1 | X_2 $$</span> <span class="math-container">$$\iff X_1 \independent X_3 | X_2\,, X_2 \independent X_4 | X_3 \,, \dots , X_{n-1} \independent X_1 | X_n \,, X_n \independent X_2 | X_1 \,.$$</span></li>
</ol>

CC BY-SA 3.0
2018-02-17T15:08:02.253Z
What are the V, X, Y, W variables? Events? Atomic events? Something else?
Joshua Grochow
CC BY-SA 3.0
2018-02-17T15:10:33.697Z
@JoshuaGrochow They are random variables (I think) -- you are right, I should clarify that.
Chill2Macht
CC BY-SA 3.0
2018-02-18T08:03:26.530Z
Is the [work](http://coalg.org/mfps-calco2017/mfps-papers/6-simpson.pdf) of @AlexSimpson relevant?
Andrej Bauer
<reference-request><lo.logic><pr.probability><conditional-results><independence>
Is there a complete and finite axiom scheme for conditional independence? (Graphoids)
Chill2Macht
# Is there a complete and finite axiom scheme for conditional independence? (Graphoids)

(Asked by: username_0 on 2018-02-17)

*Note:* This is a better-written version of an [unanswered question asked before on MathOverflow](https://mathoverflow.net/questions/289658/is-there-a-complete-countable-axiomatization-of-conditional-independence-graph).

> **Question:** Is there a complete and finite axiom scheme for conditional probability?
>
> If so, is there a reference stating the axiom scheme in a manner understandable to someone with knowledge of only probability theory, and without knowledge of mathematical logic?

A complete axiomatization or axiom scheme means that every result of the theory can be shown to be a result of the axioms involved. A finite axiomatization involves only finitely many axioms. I understand a finite axiom scheme to mean possibly infinitely many axioms expressable with finitely many symbols (e.g. the axiom scheme in Tarski's axiomatization of Euclidean geometry). $ \newcommand\independent{\perp\,\!\,\!\,\!\,\!\,\!\,\!\,\!\!\!\!\perp}$

**Background:** Judea Pearl at the Computer Science department at UCLA and co-workers [found a complete and finite axiomatization of (unconditional) probabilistic independence](https://www.sciencedirect.com/science/article/pii/089054019190077F) in the 1990's and then began to look for a complete and finite axiomatization of conditional independence. However, Studeny showed in 1992 [[1]](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51.7014&rep=rep1&type=pdf)[[2]](ftp://ftp.utia.cas.cz/pub/staff/studeny/ci-no-axiom-92.pdf) that no such complete and finite axiomatization exists.

An aspect of Studeny's 1992 paper which is less often emphasized is that it also *claims* to give a complete axiom scheme for conditional probability. Since the paper is written using very abstract mathematical logic, I don't understand what the axiom scheme is supposed to be. Wolfgang Spohn wrote [[1]](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.8198&rep=rep1&type=pdf)[[2]](http://kops.uni-konstanz.de/bitstream/handle/123456789/3473/Spohn_1994_On_the_Properties.pdf?sequence=1&isAllowed=y) about the result and gives what is a somewhat more transparent description of the axiom scheme, but the organization of his paper is unclear to me, as is the notation at times. [Seth Sullivant appears to have written about a similar issue](https://arxiv.org/abs/0704.2847), which may have allowed me to understand at least one part of the axiom scheme. Attempting to interpolate between those three papers, this may be what a complete and finite axiom scheme for conditional probability looks like (please note that the the $U$'s, $V$'s, $W$'s, $X$'s, $\tilde{X}$'s, $Y$'s, and $\tilde{Y}$'s are all supposed to denote random variables):

1. $$\{X\_1, \dots, X\_k \} \independent \{Y\_1, \dots, Y\_l\} | \{W\_1, \dots, W\_m\}$$ $$\iff \{Y\_1, \dots, Y\_l\} \independent \{X\_1, \dots, X\_k\} | \{W\_1 \dots W\_m\}$$
2. $$\{V\_1, \dots, V\_j\} \independent \emptyset | \{W\_1, \dots, W\_m \}$$
3. $$\{V\_1, \dots, V\_j\} \independent \{X\_1, \dots, X\_k\} \cup \{Y\_1, \dots, Y\_l\} | \{W\_1, \dots, W\_m\}$$ $$\implies \{V\_1, \dots, V\_j\} \independent \{X\_1, \dots, X\_k\} | \{W\_1, \dots, W\_m\}$$
4. $$\{V\_1, \dots, V\_j\} \independent \{X\_1, \dots, X\_k\} \cup \{Y\_1, \dots, Y\_l\} | \{W\_1 ,\dots, W\_m \}$$ $$\implies \{ V\_1, \dots, V\_j\} \independent \{X\_1, \dots, X\_k\} | \{Y\_1, \dots, Y\_l\} \cup \{W\_1, \dots, W\_m \}$$
5. $$\{V\_1, \dots, V\_j\} \independent \{X\_1, \dots, X\_k \} | \{Y\_1, \dots, Y\_l\} \cup \{W\_1, \dots, W\_m \}$$ $$\text{and }\{V\_1, \dots, V\_j\} \independent \{Y\_1, \dots, Y\_l\} | \{W\_1, \dots, W\_m\}$$ $$\implies \{V\_1, \dots, V\_j\} \independent \{X\_1, \dots, X\_k\} \cup \{Y\_1, \dots, Y\_l\} | \{W\_1, \dots, W\_m\}$$
6. For a strictly positive probability measure, i.e. $\mathbb{P}(A) = 0 \iff A = \emptyset$, we have: $$\{V\_1, \dots, V\_j\} \independent \{X\_1, \dots, X\_k \} | \{Y\_1, \dots, Y\_l\} \cup \{W\_1, \dots, W\_m \}$$ $$\text{and }\{V\_1, \dots, V\_j\} \independent \{Y\_1, \dots, Y\_l \} | \{X\_1, \dots, X\_k\} \cup \{W\_1, \dots, W\_m\}$$ $$\implies \{V\_1,\dots,V\_j\} \independent \{X\_1, \dots, X\_k\} \cup \{Y\_1, \dots, Y\_l\} | \{W\_1, \dots, W\_m\} $$
7. If $U$ is an RV taking only two values, e.g. Bernoulli or Rademacher, then $$\{X\_1, \dots,X\_k\} \independent \{Y\_1, \dots, Y\_l\} \text{ and } \{X\_1,\dots, X\_k\} \independent \{Y\_1, \dots, Y\_l\} | U $$ $$\implies \{X\_1, \dots, X\_k \} \cup U \independent \{Y\_1, \dots, Y\_l\} \text{ or }\{X\_1, \dots, X\_k\} \independent \{Y\_1, \dots, Y\_l\} \cup U $$
8. $$\{X\_1, \dots, X\_k\} \independent \{\tilde{X}\_1,\dots, \tilde{X}\_{\tilde{k}} \} \,, \{Y\_1, \dots, Y\_l\} \independent \{\tilde{Y}\_1, \dots, \tilde{Y}\_{\tilde{l}}\} | \{X\_1, \dots, X\_k\} \,, $$ $$\{Y\_1, \dots, Y\_l \} \independent \{\tilde{Y}\_1, \dots, \tilde{Y}\_{\tilde{l}}\} | \{\tilde{X}\_1, \dots, \tilde{X}\_{\tilde{k}}\}\,, \text{ and } $$ $$\{X\_1, \dots, X\_k\} \independent \{\tilde{X}\_1, \dots, \tilde{X}\_{\tilde{k}} \} | \{Y\_1, \dots, Y\_l\} \cup \{\tilde{Y}\_1, \dots, \tilde{Y}\_{\tilde{l}} \} $$ $$ \iff \{Y\_1, \dots, Y\_l \} \independent \{\tilde{Y}\_1, \dots, \tilde{Y}\_{\tilde{l}} \} \,, \{X\_1, \dots, X\_k\} \independent \{\tilde{X}\_1, \dots, \tilde{X}\_{\tilde{k}}\} | \{Y\_1, \dots, Y\_l\} \,, $$ $$\{X\_1, \dots, X\_k \} \independent \{\tilde{X}\_1, \dots, \tilde{X}\_{\tilde{k}} \} | \{\tilde{Y}\_1, \dots, \tilde{Y}\_{\tilde{l}} \} \,, \text{ and }$$ $$\{ Y\_1, \dots, Y\_l\} \independent \{\tilde{Y}\_1, \dots, \tilde{Y}\_l \} | \{X\_1, \dots, X\_k\} \cup \{ \tilde{X}\_1, \dots, \tilde{X}\_k \} $$
9. For a strictly positive probability measure, i.e. $\mathbb{P}(A) = 0 \iff A = \emptyset$, we have: $$\text{If }\{Y\_1, \dots, Y\_l\} \independent \{\tilde{Y}\_1, \dots, \tilde{Y}\_{\tilde{l}} | \{X\_1, \dots, X\_k \} \cup \{\tilde{X}\_1, \dots, \tilde{X}\_{\tilde{k}}\} \cup \{W\_1, \dots, W\_m\} \,,$$ then any three of the following implies the fourth: $$\{X\_1, \dots, X\_k \} \independent \{\tilde{X}\_1, \dots, \tilde{X}\_{\tilde{k}}\} | \{W\_1, \dots, W\_m\}\,, $$ $$\{X\_1, \dots, X\_k \} \independent \{\tilde{X}\_1, \dots, \tilde{X}\_{\tilde{k}} \} | \{Y\_1, \dots, Y\_l\} \cup \{W\_1, \dots, W\_m \} \,, $$ $$\{ X\_1, \dots, X\_k \} \independent \{\tilde{X}\_1, \dots, \tilde{X}\_{\tilde{k}}\} | \{\tilde{Y}\_1, \dots, \tilde{Y}\_{\tilde{l}} \} \cup \{W\_1, \dots, W\_m \} \,, $$ $$\{X\_1, \dots, X\_k \} \independent \{\tilde{X}\_1, \dots, \tilde{X}\_{\tilde{k}} \} | \{Y\_1, \dots, Y\_l \} \cup \{\tilde{Y}\_1, \dots, \tilde{Y}\_{\tilde{l}}\} \cup \{W\_1, \dots, W\_m\} \,. $$
10. For every $n \ge 4$ (this is technically an axiom scheme and not an axiom because as Studeny showed in 1992 these are all logically independent of one another for each $n$) one has that: $$X\_1 \independent X\_2 | X\_3\,, X\_2 \independent X\_3 | X\_4\,, \dots, X\_{n-1} \independent X\_n | X\_1\,, X\_n \independent X\_1 | X\_2 $$ $$\iff X\_1 \independent X\_3 | X\_2\,, X\_2 \independent X\_4 | X\_3 \,, \dots , X\_{n-1} \independent X\_1 | X\_n \,, X\_n \independent X\_2 | X\_1 \,.$$

**Tags:** reference-request, lo.logic, pr.probability, conditional-results, independence
> **Comments:**
> **username_1**: What are the V, X, Y, W variables? Events? Atomic events? Something else?  
> **username_0**: @JoshuaGrochow They are random variables (I think) -- you are right, I should clarify that.  
> **username_2**: Is the [work](http://coalg.org/mfps-calco2017/mfps-papers/6-simpson.pdf) of @AlexSimpson relevant?  

---

## 0 answers

