Appendix A — Graphical Intuition for Conditional Independence and \(d\)-Separation
This appendix provides a gentle introduction to the probabilistic and graphical ideas that underlie Chapters 2 and 3. Our goal is not to give a complete treatment of graphical models, but rather to develop enough intuition so that the formal machinery of \(d\)-separation, back-door adjustment, and intervention graphs does not appear abruptly.
A directed acyclic graph (DAG) is more than a picture. It is a compact language for expressing assumptions about how variables are related. Once those assumptions are represented graphically, the graph tells us which variables may be associated, which paths transmit dependence, and which variables should or should not be conditioned on. These ideas become central in Chapter 2, where we study \(d\)-separation, and in Chapter 3, where we use graph surgery to derive identification results.
The key pedagogical idea of this appendix is simple: before learning the full \(d\)-separation criterion, it is helpful to understand three elementary three-node patterns. Those local patterns explain most of what happens later in larger graphs. Chapter 2 follows the same route — the three motifs with examples, then the blocking rules, then the \(d\)-separation criterion — so this appendix can be read as a gentler first pass over the same arc.
A.1 Conditional Independence: The Probabilistic Language Behind Graphs
Before introducing graphs, we first recall the probabilistic notion that graphs are designed to encode.
Definition A.1 (Conditional Independence) Let \(X\), \(Y\), and \(Z\) be random variables. We say that \(X\) and \(Y\) are conditionally independent given \(Z\), written \(X \indep Y \mid Z\), if \[p(x, y \mid z) = p(x \mid z)\,p(y \mid z) \qquad \text{for } P_Z\text{-almost every } z.\]
Equivalently, once \(Z\) is known, learning \(X\) gives no additional information about \(Y\), and learning \(Y\) gives no additional information about \(X\).
In terms of densities (with respect to a dominating measure on \((X, Y, Z)\)), conditional independence admits the following equivalent characterizations, each interpreted almost everywhere: \[X \indep Y \mid Z \;\iff\; f(x,y,z)\,f(z) = f(x,z)\,f(y,z) \;\iff\; \exists\, a, b \colon f(x,y,z) = a(x,z)\,b(y,z).\] The last form is especially useful: it says that the joint density factors into one piece depending on \((x,z)\) and another depending on \((y,z)\), with no cross-term in \(x\) and \(y\).
Proposition A.1 (Fundamental Properties of Conditional Independence) For random variables \(X\), \(Y\), \(Z\), and \(W\), the following hold:
(C1) Symmetry. \(X \indep Y \mid Z \;\Rightarrow\; Y \indep X \mid Z\). (C2) Decomposition. \(X \indep (Y,W) \mid Z \;\Rightarrow\; X \indep Y \mid Z\). (C3) Weak Union. \(X \indep (Y,W) \mid Z \;\Rightarrow\; X \indep Y \mid (Z,W)\). (C4) Contraction. \(X \indep Y \mid Z\) and \(X \indep W \mid (Y,Z) \;\Rightarrow\; X \indep (Y,W) \mid Z\). (C5) Intersection. If \(f(x,y,z,w) > 0\) for all \((x,y,z,w)\), then \(X \indep Y \mid (Z,W)\) and \(X \indep Z \mid (Y,W) \;\Rightarrow\; X \indep (Y,Z) \mid W\).
Properties (C1)–(C4) hold for any probability distribution and are known as the semigraphoid axioms. Property (C5) additionally requires the joint density to be strictly positive; together with (C1)–(C4) it forms the graphoid axioms. These properties are used implicitly throughout the course whenever conditional independence statements are combined or simplified.
Conditional independence is not the same as marginal independence. Two variables may be dependent marginally but independent after conditioning on a third variable. Conversely, two variables may be independent marginally but become dependent after conditioning. Both phenomena occur repeatedly in causal inference.
Example A.1 (Ice Cream, Drowning, and Season) Let \(X = \text{ice cream sales}\), \(Y = \text{drowning incidents}\), and \(Z = \text{season}\). Marginally, \(X\) and \(Y\) are positively associated because both tend to be higher in summer. This does not mean that ice cream sales cause drowning. A more plausible explanation is that season is a common cause of both variables. Once season is fixed, the association largely disappears: \(X \indep Y \mid Z\).
This example illustrates a recurring theme in causal inference: an observed association may be induced by a third variable, and conditioning on that variable can remove the spurious dependence.
A.2 Three Basic Motifs: Chain, Fork, and Collider
Every path in a DAG is built from local three-node configurations. There are three fundamental types: a chain, a fork, and a collider. Their behavior under conditioning is the foundation of \(d\)-separation.
A.2.1 Chain
Consider the pattern \(X_1 \to X_2 \to X_3\), where the middle node \(X_2\) lies on a directed pathway from \(X_1\) to \(X_3\).
Example A.2 (Exercise, Body Weight, and Blood Pressure) Let \(X_1 = \text{exercise}\), \(X_2 = \text{body weight}\), and \(X_3 = \text{blood pressure}\). Exercise may affect blood pressure partly through its effect on body weight, so the path \(X_1 \to X_2 \to X_3\) transmits association from \(X_1\) to \(X_3\). Marginally, exercise and blood pressure are associated; conditioning on body weight blocks this particular pathway. In the isolated three-node DAG as drawn, this is the only pathway, so \(X_1 \indep X_3 \mid X_2\).
Once the middle variable is fixed, the chain no longer transmits additional information from \(X_1\) to \(X_3\).
A.2.2 Fork
Consider the pattern \(X_1 \leftarrow X_2 \to X_3\), where the middle node \(X_2\) is a common cause of \(X_1\) and \(X_3\).
Example A.3 (Ice Cream, Season, and Drowning) With \(X_1 = \text{ice cream sales}\), \(X_2 = \text{season}\), and \(X_3 = \text{drowning incidents}\), season affects both variables, so \(X_1\) and \(X_3\) are associated even though neither causes the other. Conditioning on season blocks this path: \(X_1 \indep X_3 \mid X_2\).
A fork is the simplest graphical form of confounding: the middle node creates association, and conditioning on it blocks the path.
A.2.3 Collider
Consider the pattern \(X_1 \to X_2 \leftarrow X_3\), where the middle node \(X_2\) is a common effect of \(X_1\) and \(X_3\).
Example A.4 (Talent, Legacy Status, and College Admission) Let \(X_1 = \text{academic talent}\), \(X_3 = \text{legacy status}\), and \(X_2 = \text{admission to an elite university}\). Talent and legacy status may be unrelated in the general applicant pool. But among admitted students they can become statistically associated: low legacy status makes unusually high talent more likely among admitted applicants, and vice versa. Symbolically, \(X_1 \indep X_3\), but conditioning on \(X_2\) opens the path between them, so \(X_1\) and \(X_3\) are typically dependent given \(X_2\).
Unlike chains and forks, a collider blocks the path by default. Conditioning on the collider opens the path and may induce association that was not present marginally.
A.2.4 Summary of the Three Motifs
The three motifs behave as follows. A chain (\(X_1 \to X_2 \to X_3\)) and a fork (\(X_1 \leftarrow X_2 \to X_3\)) are each open by default and blocked by conditioning on the middle node \(X_2\). A collider (\(X_1 \to X_2 \leftarrow X_3\)) is blocked by default and opened by conditioning on the middle node or any of its descendants. The stories here deliberately differ from those in Chapter 2 (smoking–tar–cancer, poverty–diet–exercise, accident–hospitalization–cancer), so that each motif is anchored in two contexts; the admission example reappears as the talent–wealth example in the IV-DAG section of Chapter 2.
None of these behaviors needs to be taken on faith: each is provable from the DAG factorization of Section A.4. The chain-proof example of Chapter 2 carries out the chain computation, and the blocking-derivation remark there obtains the remaining rules from the same factorization. Chapter 2 develops these three motifs into the full \(d\)-separation criterion; see in particular its sections on the blocking rules, on the criterion itself, and on the extended treatment of collider bias.
A.3 \(d\)-Separation: When Does Conditioning Block a Path?
The three-node motifs explain what happens locally on a path. The next step is to extend this logic to a general DAG, where two variables may be connected by many paths.
Definition A.2 (Path) A path between two nodes is a sequence of distinct nodes such that each consecutive pair is connected by an edge, regardless of edge direction.
Definition A.3 (Blocked Path) A path is blocked by a conditioning set \(S\) if at least one of the following holds:
- the path contains a chain or fork node that belongs to \(S\), or
- the path contains a collider such that neither the collider nor any of its descendants belongs to \(S\).
A path is open given \(S\) if it is not blocked.
Definition A.4 (\(d\)-Separation) Two nodes \(X\) and \(Y\) are \(d\)-separated by a set \(S\) if every path between \(X\) and \(Y\) is blocked by \(S\). More generally, two disjoint sets of nodes \(\mathbf{X}\) and \(\mathbf{Y}\), each disjoint from \(S\), are \(d\)-separated by \(S\) if every \(X \in \mathbf{X}\) is \(d\)-separated from every \(Y \in \mathbf{Y}\) by \(S\).
A.3.1 A Confounding Example
Consider the DAG with edges \(X \to T\), \(T \to Y\), and \(X \to Y\). Here \(T\) is the treatment, \(Y\) is the outcome, and \(X\) is a pre-treatment covariate that affects both. There are two paths from \(T\) to \(Y\): the directed causal path \(T \to Y\), and the back-door path \(T \leftarrow X \to Y\).
Without conditioning, the back-door path is open, so the observed association between \(T\) and \(Y\) mixes the causal effect with confounding. Conditioning on \(X\) blocks the fork \(T \leftarrow X \to Y\), thereby isolating the causal path.
This confounding graph anticipates the back-door criterion of Chapter 3: the graphical condition that makes adjustment valid is precisely that all back-door paths are blocked.
A.3.2 A Collider Warning
Now consider the DAG with edges \(T \to C\), \(U \to C\), and \(U \to Y\). Here \(C\) is a collider on the path \(T \to C \leftarrow U \to Y\). Without conditioning on \(C\), the path is blocked at the collider. Conditioning on \(C\) opens the path, creating a spurious association between \(T\) and \(Y\) through \(U\).
Even more subtly, conditioning on a descendant of \(C\) can also open the path. If additionally \(C \to D\), then conditioning on \(D\) may also induce association between \(T\) and \(Y\) through the collider at \(C\): observing \(D\) amounts to observing a noisy proxy of \(C\). The blocking-derivation remark of Chapter 2 derives this descendant rule from the factorization.
A.3.3 A Practical Checklist
To decide whether \(X\) and \(Y\) are \(d\)-separated by \(S\), proceed as follows. First, list all paths between \(X\) and \(Y\). On each path, classify each interior node as part of a chain, fork, or collider. Then check whether each path is blocked by \(S\). Finally, conclude that \(X\) and \(Y\) are \(d\)-separated if and only if every path is blocked.
For beginners, this path-by-path procedure is often more useful than starting with the most compact formal definition.
A.4 DAG Factorization and the Markov Property
So far the graph has served purely qualitative purposes: classifying paths as open or blocked. The same parent structure carries quantitative information as well, because it prescribes how a joint distribution can be broken into simple pieces.
Any joint distribution can be written by conditioning each variable on all of its predecessors, but that generic decomposition involves high-dimensional conditional distributions and reveals little. The graphical model earns its keep by replacing the generic decomposition with a sparse one, in which each variable is conditioned only on its parents.
Definition A.5 (DAG Factorization) Let \(\Gcal\) be a DAG with nodes \(V_1, \ldots, V_p\). A joint distribution \(p(v_1, \ldots, v_p)\) is said to factorize according to \(\Gcal\) if \[p(v_1, \ldots, v_p) = \prod_{j=1}^{p} p\!\left(v_j \mid \Pa(V_j)\right),\] where \(\Pa(V_j)\) denotes the set of parents of \(V_j\) in \(\Gcal\).
This factorization implies the local Markov property, defined below: once its parents are known, a node is conditionally independent of all variables that are neither its descendants nor its parents. In a causal DAG, drawing a parent arrow is an additional substantive claim that the parent is a direct causal input; this informally rules out exact cancellations or redundant arrows, and is connected to the notions of minimality and faithfulness discussed in Chapter 2.
Example A.5 (A Simple Confounding Graph) For the DAG with edges \(X \to T\), \(T \to Y\), and \(X \to Y\), the joint density factorizes as \[p(x, t, y) = p(x)\,p(t \mid x)\,p(y \mid t, x).\] Thus the graph determines which local conditional distributions appear in the factorization.
Definition A.6 (Local Markov Property) Let \(\Nd(V_i) = V \setminus \bigl(\{V_i\} \cup \De(V_i)\bigr)\) denote the set of non-descendants of \(V_i\), where \(\De(V_i)\) is the set of descendants of \(V_i\) in \(\Gcal\). A distribution \(P\) satisfies the local Markov property with respect to \(\Gcal\) if, for every node \(V_i \in V\), \[V_i \indep \bigl(\Nd(V_i) \setminus \Pa(V_i)\bigr) \mid \Pa(V_i).\] That is, once we condition on the direct causes of a node, that node is independent of all variables that are neither its descendants nor its parents.
Theorem A.1 (Equivalence of the Three Markov Properties (Lauritzen 1996, Theorem 3.27)) Let \(\Gcal\) be a DAG and let \(P\) admit a joint density with respect to a product dominating measure, with regular conditional distributions. Then the following are equivalent:
- \(P\) admits the recursive factorization \(p(v_1, \dots, v_k) = \prod_i p(v_i \mid \Pa(v_i))\);
- \(P\) satisfies the local Markov property;
- \(P\) satisfies the global Markov property.
Proof. We sketch the cycle (iii) \(\Rightarrow\) (ii) \(\Rightarrow\) (i) \(\Rightarrow\) (iii); full details are given by Lauritzen (1996).
Global \(\Rightarrow\) local (instantiation). Each local statement is itself a \(d\)-separation, hence one entry of the global dictionary. Take any path from \(V_i\) to a non-descendant \(W\). If the path leaves \(V_i\) through a parent, it is blocked there: the parent is a conditioned non-collider. If it leaves through a child, then reaching a non-descendant forces the path to reverse direction somewhere, and the reversal point is a collider that is a descendant of \(V_i\); by acyclicity no descendant of \(V_i\) can lie in \(\Pa(V_i)\), so the collider is unactivated and the path is blocked.
Local \(\Rightarrow\) factorization (chain rule). List the nodes in a topological ordering, so that every predecessor of \(V_i\) is a non-descendant. The chain rule gives \(p(v_1, \dots, v_k) = \prod_i p(v_i \mid v_1, \dots, v_{i-1})\), and the local statement for \(V_i\) licenses shrinking each conditioning set to the parents: \(p(v_i \mid v_1, \dots, v_{i-1}) = p(v_i \mid \Pa(v_i))\). The \(k\) local statements are thus exactly calibrated to the \(k\) factors of the chain rule: they pin the functional form of the joint density to a product.
Factorization \(\Rightarrow\) global (the substantive arrow). This is the soundness theorem of Chapter 2, and the standard proof runs through the moral-graph criterion of Section A.5: restrict to the ancestral set of \(A \cup B \cup \mathbf{S}\) (marginalizing over non-ancestors preserves the product form), moralize (each factor \(p(v_i \mid \mathrm{pa}_i)\) becomes a function on one clique of the moral graph, so the density is a product of clique functions), and observe that separation of \(A\) from \(B\) by \(\mathbf{S}\) in the moralized ancestral graph splits that product into \(g(a, \mathbf{s})\,h(b, \mathbf{s})\) — which is conditional independence. \(\square\)
Example A.6 (Education–Earnings Graph) Consider the DAG above, with edges \(N \to E\), \(B \to E\), \(E \to Y\), and \(B \to Y\). The corresponding factorization is \[p(n,b,e,y) = p(n)\,p(b)\,p(e \mid n,b)\,p(y \mid e,b).\] The parent set of \(Y\) is \(\Pa(Y) = \{E, B\}\), so the local Markov property gives \(Y \indep N \mid \{E, B\}\).
The same conclusion follows by \(d\)-separation. There are two paths from \(N\) to \(Y\): \[N \to E \to Y \qquad\text{and}\qquad N \to E \leftarrow B \to Y.\] Given \(\{E, B\}\), the first path is blocked at the non-collider \(E\). The second path is opened at the collider \(E\), but blocked at the non-collider \(B\). Thus every path from \(N\) to \(Y\) is blocked by \(\{E, B\}\).
The factorization above also implies that \(N \indep B\), since neither node has a parent or a common ancestor in the graph. This is a substantive modeling assumption: if neighborhood and family background are believed to be associated, the graph should include an edge between them, a common cause, or a different ordering.
Chapter 2 states the local and global Markov properties formally and uses them to connect \(d\)-separation to conditional independence; it then applies the same factorization to the education–earnings DAG introduced above.
A.5 Optional: Moralization as an Alternative Criterion
There is an alternative graph-theoretic way to check \(d\)-separation based on constructing an undirected graph called the moral graph. The method is elegant and useful in more advanced graphical-model theory, but it is not necessary for understanding the main causal ideas of Chapters 2 and 3. For most students, the path-by-path method using chains, forks, and colliders is more intuitive on first exposure.
To check whether \(X \indep Y \mid S\), the procedure is as follows. First, take the induced subgraph on \(\An(X \cup Y \cup S)\), the ancestors of all variables under consideration, including those in the conditioning set \(S\). Second, connect any two parents of a common child by an undirected edge. Third, drop all arrow directions. Finally, check whether \(S\) separates \(X\) and \(Y\) in the resulting undirected graph; equivalently, whether \(X\) and \(Y\) become disconnected once the nodes in \(S\) and their incident edges are removed. This procedure yields a criterion equivalent to \(d\)-separation.
Example A.7 (Moral Graph of a Collider) Consider the DAG \(A \to C \leftarrow B\). For the conditional query \(A \indep B \mid C\), the ancestral set is \(\An(\{A, B, C\}) = \{A, B, C\}\), so \(C\) is retained. Moralization connects the two parents \(A\) and \(B\), and after deleting the conditioned node \(C\) the edge \(A - B\) remains; therefore \(A\) and \(B\) are not separated, matching the fact that conditioning on a collider opens the path. By contrast, for the marginal query \(A \indep B\), the ancestral set is \(\An(\{A, B\}) = \{A, B\}\), so \(C\) is discarded before moralization and no moral edge is added; \(A\) and \(B\) are separated, as expected.
A.6 The ID Algorithm and the Hedge: A Proof Sketch of Completeness
This section collects the graph terminology behind the completeness theorem of Chapter 3 and sketches its proof. It is reference material for independent reading: the machinery below — ADMGs, districts, kernels, fixing, and the hedge — is not required elsewhere in the course.
A.6.1 ADMGs and Semi-Markovian Models
Chapters 2 and 3 represent latent common causes as explicit unobserved nodes (e.g. \(U \to T\) and \(U \to Y\)). The completeness theorem uses a more general graph class that encodes latent common causes compactly as bidirected edges: a bidirected edge \(X \leftrightarrow Y\) records latent common-cause dependence between \(X\) and \(Y\); in the canonical semi-Markovian representation, it is realized by an exogenous latent common cause \(U\) with \(U \to X\) and \(U \to Y\). A graph containing both directed and bidirected edges, with the directed part acyclic, is called an acyclic directed mixed graph (ADMG): directed edges represent causal relations among the observed variables, while bidirected edges represent latent common-cause relations. In the canonical semi-Markovian representation, every latent variable is exogenous, the exogenous variables are mutually independent, and each latent common cause has at most two observed children, so that it enters the ADMG as a bidirected edge between the pair of observed variables it affects. Causal models of this form are called semi-Markovian. (Conditional interventional distributions \(P(y \mid \doop(t), c)\) require an extension of the ID algorithm known as IDC, for which an analogous completeness result holds; Chapter 3 treats only the unconditional case.)
A.6.2 How ID Succeeds: Districts and Kernels
Shpitser and Pearl (2006) introduced the identification (ID) algorithm: a procedure that takes as input an ADMG \(\Gcal\), a target intervention distribution \(P(y \mid \doop(t))\), and the observed joint distribution \(P\), and either returns an explicit observational formula for \(P(y \mid \doop(t))\) or reports that the quantity is not identifiable from \(P\) given \(\Gcal\).
Sufficiency (do-calculus identifies whenever identification is possible): proved constructively via the ID algorithm. The key structural concept is the district (called a c-component, for confounded component, in the original ID literature): a maximal set of observed nodes connected by paths of bidirected edges. Its members are linked through a network of latent common-cause relations, though they need not all share a single latent parent. For a single node \(V\) with no bidirected edges, its district is \(\{V\}\) itself.
The ID algorithm first restricts attention to the relevant ancestral set \(Y^*\) — the vertices with a directed path to \(Y\) that avoids \(T\), together with \(Y\) itself — and decomposes the induced subgraph \(\Gcal[Y^*]\), denoted below by \(\Gcal_{Y^*}\) (not to be confused with the edge-deletion operations \(\Gcal_{\overline{X}}\) and \(\Gcal_{\underline{X}}\)), into districts. It then attempts to recover one interventional kernel for each district by a recursive reduction of the observed distribution (Tian’s Q-factorization (Tian and Pearl 2002); in modern terminology, a sequence of fixing operations). If every required district kernel is recoverable — every district is intrinsic — the kernels combine into an identifying functional; the output is best viewed as a modified nested Markov factorization of the ADMG, in the same way that the g-formula is a modified Markov factorization of a DAG. If some required district is not intrinsic, the algorithm fails and exposes a hedge (defined below). When the algorithm succeeds, it has produced an explicit identification formula, demonstrating that the do-calculus is sufficient.
A.6.3 How ID Fails: The Hedge and the Two-Model Witness
Necessity (do-calculus cannot identify nonidentifiable quantities): proved by showing that whenever the ID algorithm fails, the causal effect is genuinely nonidentifiable — not merely hard to compute. The key graphical obstruction is the hedge.
Informally, a hedge for \(P(y \mid \doop(t))\) in \(\Gcal\) is a pair of nested C-forests \(\langle F, F' \rangle\) with \(F' \subseteq F\), both rooted at the same set \(R \subseteq F'\), such that \(F\) intersects the treatment set \(T\) while \(F'\) does not, and every node of \(R\) has a directed path to \(Y\) that avoids \(T\). (A C-forest is a subgraph whose nodes form a single district — all connected through bidirected edges — and whose directed edges form a forest with root set \(R\).) Intuitively, the hedge encodes a “loop” of confounding surrounding the treatment that the do-calculus cannot break.
Shpitser and Pearl (2006) prove that whenever a hedge for \(P(y \mid \doop(t))\) exists in \(\Gcal\), the target is not identifiable. Conversely, whenever the ID algorithm fails, it exposes a hedge for the target query: the algorithm fails if and only if \(\Gcal\) contains a hedge for \(P(y \mid \doop(t))\) itself — equivalently, some district of \(\Gcal_{Y^*}\) is not intrinsic (Shpitser 2023). (An older formulation characterized identifiability by the absence of hedges for every reduced subquery \(P(y' \mid \doop(t'))\) with \(T' \subseteq T\) and \(Y' \subseteq Y\). That subset-subquery formulation is incorrect as stated: a target such as \(P(y \mid \doop(t_1, t_2))\) can be identifiable even though the reduced query \(P(y \mid \doop(t_2))\) has a hedge (Shpitser 2023). The corrected criterion concerns the target query itself.) When a hedge for the target exists, one can explicitly construct two semi-Markovian models \(\mathcal{M}_1\) and \(\mathcal{M}_2\) that:
- induce the same observed joint distribution \(P\), so no data can distinguish them; but
- assign different values to \(P(y \mid \doop(t))\), so the interventional distribution is not a function of \(P\) alone.
The construction builds \(\mathcal{M}_1\) and \(\mathcal{M}_2\) by altering the causal mechanisms of the observed variables in the relevant district (and, if needed, the distribution of the exogenous variables — which, being exogenous, have no structural equations of their own), keeping the observed joint distribution identical. Since the two models are observationally indistinguishable yet causally distinct, no method — including the do-calculus — can identify \(P(y \mid \doop(t))\) from \(P\) alone. This establishes necessity.
Combining sufficiency and necessity: the ID algorithm (and hence the do-calculus) succeeds if and only if no hedge exists for the target query, which is if and only if \(P(y \mid \doop(t))\) is identifiable. \(\square\)
A.7 Summary
This appendix introduced the graphical ideas that support Chapters 2 and 3. Conditional independence is the probabilistic language that graphs are designed to encode. The three local motifs — chain, fork, and collider — determine how conditioning affects association along a path. \(d\)-Separation extends these local rules to arbitrary graphs: two variables are \(d\)-separated by \(S\) if every path between them is blocked by \(S\). The most important application in causal inference is to distinguish confounding paths from causal paths and to identify valid adjustment sets. The Markov property gives a probabilistic interpretation to the graph by linking graphical structure to a factorization of the joint distribution. Finally, an optional last section sketches the ID algorithm and the hedge obstruction — the machinery behind the completeness theorem of Chapter 3.