**Note:** A pointer to a reference, or a yes/no answer with a 1-2 sentence incomplete/non-rigorous justification would suffice for answers. I am just curious about whether the result is true; it is fairly unambiguous that I presently lack the means to understand it adequately. **/Note**


In 1992, Studeny gave a proof that there exists no complete finite axiomatization of countable independence ([*Conditional Independence Relations have no Finite Complete Characterization*](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51.7014&rep=rep1&type=pdf) - [alternative link](ftp://ftp.utia.cas.cz/pub/staff/studeny/ci-no-axiom-92.pdf)). (Apparently [Sullivant has shown in 2007](https://arxiv.org/abs/0704.2847) that this is true even for Gaussians.)


The proof involves giving a countable sequence of true conditional independence statements, indexed by $n$, such that the statements for $m< n$ do not imply that for $n$. (At least according to Wolfgang Spohn -- more on this later.) Sullivant uses a similar approach for his proof.


Studeny says in the abstract of his 1992 paper that:



> 
> However, under the assumption that CIRs [conditional-independence relations] are grasped the existence of a countable characterization of CIRs is shown.
> 
> 
> 


Since Studeny seems to be calling a "*complete finite axiomatization*" a "*finite characterization*", this seems to suggest that Studeny is even claiming/asserting that he has shown a complete countable axiomatization of conditional independence.


**Question:** Is this correct? Has Studeny or anyone else shown the existence of a ***complete*** countable axiomatization of conditional independence? (Soundness is not in dispute.)


Later in the introduction, Studeny seems to possibly demur, saying only:



> 
> The main result is proved in the fourth section. It is supplied by the construction of a countable characterization of CIRs by $\square$ properties (however applicable only in the case that all CIRs are grasped). The fifth description is devoted to a syntactical description of CI [conditional independence]. We show how a formal axiomatization for CI can look and show that no simple complete deductive system for CI exists.
> 
> 
> 


In particular, I don't understand the condition "all conditional independence relations are grasped", nor whether the mentioned formal axiomatization is complete, or just sound, nor what is meant by a "*simple* complete deductive system" (as opposed to more general complete deductive systems).


I tried to read the fourth and fifth sections of the paper to get answers to these questions. However, due to my almost complete ignorance of mathematical logic, I understood almost nothing. (Maybe some of Example 2 and Definition 3, but the rest is more or less completely lost on me.)


Fortunately, Wolfgang Spohn, in the 1994 paper [*On the Properties of Conditional Independence*](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.8198&rep=rep1&type=pdf) ([alternative link](http://kops.uni-konstanz.de/bitstream/handle/123456789/3473/Spohn_1994_On_the_Properties.pdf?sequence=1&isAllowed=y)) effectively did me the favor of interpreting Studeny's paper and explaining some of it in language I can better understand. Specifically, on page 14 he writes:



> 
> Studeny (1992), p. 382, presents a further, simpler family of properties applying to *all* probability measures:
> 
> 
> (S4) Let $\{X\_0, \dots, X\_{n-1}\}$ be $n$ variables $(n \ge 4)$. Then $X\_0 \perp X\_i | X\_{i+1}$ holds for all $i = 1, \dots, n-1$ if and only if $X\_0 \perp X\_{i+1} | X\_i$ holds for all $i=1,\dots, n-1$ (subscripts taken modulo $n$).
> 
> 
> 


Spohn seems to go on to say that he hopes that at least it can be shown that this axiom family can be written recursively. But Spohn does not seem to mention whether the typical conditional independence axioms (see below) become complete when one replaces the fourth axiom (which corresponds, I think, to the case that $n=4$ in the family given by Studeny above) with Studeny's countable family of axioms. (Which is the only thing I am interested in.)


Seemingly, if this did make the conditional independence axioms not only sound, but even complete, most authors discussing the topic would use these completed axioms instead, since e.g. statisticians are not likely to care very much if one has to use second-order logic. Instead, in all of the references discussing the conditional independence axioms I have seen so far, only the typical, sound but not complete, axioms are mentioned. And since both Studeny and Spohn seem to be beating around the bush about whether this countable axiom family is a complete axiomatization or not, rather than saying so explicitly in unequivocal terms, I am not sure what to think.


**Background - Axioms for Conditional Independence/Graphoids:**  

These can be found on Wikipedia, [here](https://en.wikipedia.org/wiki/Conditional_independence#Rules_of_conditional_independence) or [here](https://en.wikipedia.org/wiki/Graphoid#Definition), or for actual legitimate references one can see e.g. p. 29 of Lauritzen, [*Graphical Models*](https://rads.stackoverflow.com/amzn/click/com/0198522193) (1996), pp. 24-25 of Koller and Friedman, [*Probabilistic Graphical Models*](https://mitpress.mit.edu/books/probabilistic-graphical-models) (2009), or pp. 32-35 of Whittaker, [*Graphical Models in Applied Mathematical Multivariate Statistics*](https://rads.stackoverflow.com/amzn/click/com/0471917508) (1990). Anyway, they are as follows:


* (S1) If $X\_0 \perp X\_1 | X\_2$ then $X\_1 \perp X\_0 | X\_2$.
* (S2) If $X\_0 \perp (X\_1, X\_3) | X\_2$ then $X\_0 \perp X\_1 | X\_2$ and $X\_0 \perp X\_3 | X\_2$.
* (S3) If $X\_0 \perp (X\_1, X\_3) | X\_2$ then $X\_0 \perp X\_1 | (X\_2, X\_3)$.
* (S4) If $X\_0 \perp X\_1 | X\_2$ and $X\_0 \perp X\_3 | (X\_1, X\_2)$ then $X\_0 \perp (X\_1, X\_3) | X\_2$.


It is well known that these are sound axioms, and Studeny in 1992 disproved the conjecture that they are complete. My question is about whether, according to Studeny or someone else, the fourth axiom (or another one of the axioms) can be replaced with a countable family of axioms indexed by $n$ such that all of the axioms are not just sound but even complete.


(There is also a fifth axiom which holds for positive distributions but I'm not asking about that here for the sake of increased simplicity/brevity.)



Is there a complete countable axiomatization of conditional independence? (Graphoids)

> 
> Studeny says in the abstract of his 1992 paper that:
> 
> 
> 
> > 
> > However, under the assumption that CIRs [conditional-independence relations] are grasped the existence of a countable characterization of CIRs is shown.
> > 
> > 
> > 
> 
> 
> Since Studeny seems to be calling a "complete finite axiomatization" a "finite characterization", this seems to suggest that Studeny is even claiming/asserting that he has shown a complete countable axiomatization of conditional independence.
> 
> 
> **Question**: Is this correct? Has Studeny or anyone else shown the existence of a ***complete*** countable axiomatization of conditional independence? (Soundness is not in dispute.)
> 
> 
> 


Studený has, for discrete random variables. What has been called "CIRs" or "stochastic/probabilistic CI models" at that time was a CI relation (a set of formal triplets $\langle A,B|C\rangle$ representing conditional independence statements) realized by a discrete probability distribution. Afterwards, more specific (binary) or simply different (regular Gaussian) probabilistic realizations of CIRs have been considered as well. You already mentioned Sullivant's paper. Or around the same time, [Šimeček](https://web.archive.org/web/20070720070805/http://atrey.karlin.mff.cuni.cz/%7Esimecek/skola/ps06.pdf).


What Studený claimed to have constructed is a countable axiomatization of the collection of all CIRs which are realizable by discrete probability distributions, using only Horn clauses (which he calls "$\square$ (inference) rules").
I work more on the Gaussian side, so for my peace of mind I will allow myself to emphasize "**discrete [realizable]** CIR" where applicable below. But for consistency with the article, I will continue to use the symbol $\mathsf{CIR}(N)$ to stand for discrete realizable CIRs.



> 
> Later in the introduction, Studeny seems to possibly demur, saying only:
> 
> 
> 
> > 
> > The main result is proved in the fourth section. It is supplied by the construction of a countable characterization of CIRs by $\square$ properties (however applicable only in the case that all CIRs are grasped). The fifth description is devoted to a syntactical description of CI [conditional independence]. We show how a formal axiomatization for CI can look and show that no simple complete deductive system for CI exists.
> > 
> > 
> > 
> 
> 
> In particular, I don't understand the condition "all conditional independence relations are grasped", nor whether the mentioned formal axiomatization is complete, or just sound, nor what is meant by a "simple complete deductive system" (as opposed to more general complete deductive systems).
> 
> 
> 


Neither Studený nor I are native speakers, but I believe he meant by "only in the case that all CIRs are grasped" that he provides a procedure which converts a complete list of all discrete realizable CIRs (evidently a countable set up to relabeling of the ground sets) into a countable sound and complete axiomatization using Horn clauses. Given that the conjecture being refuted in this paper was that the semigraphoid properties are sound and complete, which would yield the holy grail of knowing all discrete CIRs, it seems sensible to me that he would stress that this countable axiomatization suffers from a chicken and egg problem: if you know all the discrete CIRs, you can derive an axiomatization, but the axiomatization was sought originally to know all the discrete CIRs.


In computational terms, the problem of writing down a complete axiomatization of discrete CIRs *Turing-reduces* to the problem of deciding when a CIR is realizable by a discrete distribution. The converse is easy to prove, so the two problems are Turing-equivalent. With respect to Spohn's hope of a **recursive** axiomatization that you quoted, I should note that, to my knowledge, this question is still open. Realizability and the implication problem are equivalent, but neither is known to be decidable.


I am not aware of any alternative reference for the claimed Turing reduction and I think the primary one is alright, so I will explain the proof in different words here.


The case of a fixed ground set
------------------------------


**Construction of the axioms.** The critical result is Proposition 2 in the aforementioned paper. Given the list $\mathsf{CIR}(N)$ of discrete realizable CIRs on a fixed ground set $N$, we can iterate through all CIRs $J$ on $N$ which are **not** discrete realizable. Because discrete CIRs are closed under intersection (Lemma 1), there is a **unique smallest** $\overline J \in \mathsf{CIR}(N)$ which extends $J$. For each CI statement $c \in \overline J \setminus J$ we add one axiom $\bigwedge\_{a \in J} a \rightarrow c$ to our list. This axiom is sound because all discrete CIRs on $N$ containing $J$ contain $c$ by the choice of $\overline J$. The axioms for $J$ we just added force $J$ to be *closed* to $\overline J$, effectively forbidding $J$. If we do this for *all* non-discrete CIRs on the given ground set, our list of axioms will surely be complete for the finite set $\mathsf{CIR}(N)$. Moreover, it consists only of Horn clauses.


**Context preservation.** Let's call this set of inference rules $\mathsf{Ax}(N)$. Due to the structure of discrete CIRs, it has a subtle property that will be important in the final step of the proof. Namely, when $\bigwedge\_i \langle A\_i,B\_i|C\_i\rangle \rightarrow \langle X,Y|Z\rangle \;\in \mathsf{Ax}(N)$, then this axiom "respects context", in that $X\cup Y\cup Z \subseteq \bigcup\_i A\_i\cup B\_i\cup C\_i$. Because if that were not the case, Lemma 4 contains a construction of a discrete CIR on $N$ which contains the antecedents but not the consequent, contradicting, by intersection-closedness, our choice of *minimal* $\overline J$ in the construction of the axiom.


**Locality of consequents.** This property means that when we consider a set of antecedents $\langle A\_i,B\_i|C\_i\rangle$, we will find all the consequents of them appearing in *any* $\mathsf{Ax}(N)$ already just by studying discrete CIRs on the "smallest possible" ground set $N' = \bigcup\_i A\_i\cup B\_i\cup C\_i$. This is because on the one hand discrete CIRs are closed under restrictions of their ground sets (by the operation of marginalization on their realizing distributions), so making the ground set smaller does not make more consequents available for a fixed set of antecedents. On the other hand we do not lose any consequents either because if that were the case, i.e. $\bigwedge \langle A\_i,B\_i|C\_i\rangle \rightarrow \langle X,Y|Z\rangle \; \in \mathsf{Ax}(N)$ and $\overline{J'} \in \mathsf{CIR}(\bigcup\_i A\_i\cup B\_i\cup C\_i)$ contained all the antecedents but not the consequent, then Lemma 3 (a) allows us to lift $\overline{J'}$ to a discrete CIR on $N$ which still contains the antecedents but not the consequent, contradicting, again by intersection-closedness, the existence of the axiom in $\mathsf{Ax}(N)$.


The case of all discrete CIRs
-----------------------------


**About ground sets.** This was the story for a fixed finite set $N$, but the objective is the collection of all discrete CIRs irrespective of their ground set. Because discrete CIRs don't care how we name and order their ground sets (they are closed under permutations), let us restrict ground sets to all finite subsets of the natural numbers. Then we can consider CIRs uniformly as finite sets of triplets $\langle A,B|C\rangle$ where $A$, $B$ and $C$ are finite, disjoint subsets of $\mathbb{N}$. Notice that there are only countably many of those. Studený accounts for this trouble of choosing ground sets in his definition of $\square$ rule on page 3.


**The proof.** For each of these countably many finite subsets $N$ of the natural numbers, we simply concatenate the "locally sound and complete" axioms $\mathsf{Ax}(N)$. I claim that this yields the desired axiomatization. Certainly it is a countable set of axioms all of which are Horn clauses. Completeness follows because every CIR that is *not discrete realizable* lives on a finite ground set $N$ and $\mathsf{Ax}(N)$ includes axioms which forbid this CIR by forcing it to close to the smallest discrete realizable CIR above it. To prove soundness, let any axiom $\bigwedge\_i \langle A\_i,B\_i|C\_i\rangle \rightarrow \langle X,Y|Z\rangle$ be given, let $N$ be an arbitrary ground set and $I \in \mathsf{CIR}(N)$ which contains all of the antecedents $\langle A\_i,B\_i|C\_i\rangle$. We argued above that the existence of this axiom implies that on the ground set $N' = \bigcup\_i A\_i\cup B\_i\cup C\_i$ there is a non-discrete CIR $J' = \{ \langle A\_i,B\_i|C\_i\rangle : i \}$ whose smallest discrete CIR extension $\overline{J'}$ contains $\langle X,Y|Z\rangle$. By restricting $I$ to $N'$ we obtain a discrete CIR $I'$ which contains the antecedents, so $\langle X,Y|Z\rangle \in \overline{J'} \subseteq I'$ by minimality, and hence $I$ must have also contained the consequent. So the axiom is valid.


Summary
-------


* Because CIRs on a fixed ground set are finitely many structures, you find a finite complete axiomatization of the property of being discrete (in the form of a general Boolean formula in CNF, the clauses of which are written as implications).
* By intersection-closedness, Horn clauses suffice.
* When all these axioms are thrown into one bowl forgetting ground sets, closedness under intersections and restrictions guarantee soundness. Completeness is clear.
* In particular the context preserving nature of the axioms is crucial as it allows us to reconstruct the smallest ground set over which this axiom was obtained.



> 
> Spohn seems to go on to say that he hopes that at least it can be shown that this axiom family can be written recursively. But Spohn does not seem to mention whether the typical conditional independence axioms (see below) become complete when one replaces the fourth axiom (which corresponds, I think, to the case that $n=4$ in the family given by Studeny above) with Studeny's countable family of axioms. (Which is the only thing I am interested in.)
> 
> 
> 


No, sometime later Studený and Matúš (later Matúš alone) compiled the list of discrete realizable CIRs on four random variables, in a very compressed form ([I](http://staff.utia.cas.cz/matus/fmmscl.ps), [II](http://staff.utia.cas.cz/matus/fmdva.ps), [III](http://staff.utia.cas.cz/matus/fmtri.ps), for a summary see Šimeček's [Short note](https://web.archive.org/web/20070720065250/http://atrey.karlin.mff.cuni.cz/%7Esimecek/skola/pgm.pdf)). The semigraphoid axioms plus this infinite familiy (of which only the $n=4$ instance applies to this situation) are not sufficient to cut out the CIRs on four discrete random variables.


If you take the semigraphoid closure of the following set of triplets, it will satisfy the semigraphoid axioms (by construction) and all instances of Studený's property (vacuously), but it is not discrete realizable:
$$
\{
 \langle 1,2|\emptyset \rangle,
 \langle 1,2|3 \rangle,
 \langle 2,4|3 \rangle,
 \langle 3,4|1 \rangle,
 \langle 3,4|1,2 \rangle
\}.
$$


This is not obvious, but you could start by recognizing that the above structure is a *local semigraphoid* in the sense of [Matúš (1997)](http://staff.utia.cas.cz/matus/fmminor.ps) and that Studený's is a property which actually takes place in the local world. There is no way to order the ground set $\{1,2,3,4\}$ such that the antecedents of Studený's property are contained in this semigraphoid, so the the property is vacuously fulfilled. As for why this local semigraphoid is not discrete realizable, I cannot give you a more profound reason than: it is not an intersection of any subset of the 91 basic discrete CIRs whose 13 orbits modulo the symmetric group on the ground set are displayed in Šimeček's Short note, reference given above.



> 
> Instead, in all of the references discussing the conditional independence axioms I have seen so far, only the typical, sound but not complete, axioms are mentioned.
> 
> 
> 


As a followup to the paper you cited, Pearl and Paz revised their conjecture to state that if the semigraphoid axioms are not complete for discrete CIRs, maybe they at least generate all sound CI inference rules with at most two antecedents, which in turn was proved by Studený. To me this is a satisfactory answer for why the semigraphoid axioms prevail. They are "complete for all the smallest valid axioms". You can read more about it in [Studený (1994)](http://ftp.utia.cas.cz/pub/staff/studeny/two-antecedental-uai-94.pdf).


