How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
DAG adjacency is equivalent to having no separating set
Statement
Let be a finite DAG on . For distinct vertices , the pair is an edge of the skeleton of if and only if there is no that d-separates and in .
Statement references
Facts & Assumptions
Given: A finite DAG and distinct vertices .
In a finite DAG, a path is active given when each internal noncollider is outside and each collider has a descendant in , with membership in counted as being its own descendant. Paths, active paths, and d-separation in a finite DAG
Proof
If and are adjacent, the one-edge path between them has no internal vertices, so it is active given every by [F1]. Hence no such d-separates them.
Suppose and are nonadjacent. Acyclicity implies that at least one of is not a descendant of the other; after interchanging labels, assume is not a descendant of . Since are nonadjacent, is a non-descendant non-parent of . Put . Then excludes both endpoints. Consider any path . If its first arrow points into , then and the occurrence of is a noncollider, because the arrow has its tail at ; the path is blocked. If the first arrow points out of , follow arrows that point forward along the path until the first arrow that points backward. Such a reversal must occur because is not a descendant of . At the reversal vertex , both incident arrows point into , so it is a collider and the initial segment is a directed path . If had a descendant , then would be a directed cycle. Thus this collider has no descendant in , and the path is blocked by [F1]. Every path is blocked, so d-separates and .
The adjacent and nonadjacent cases prove both implications.
Depends on
Used by
Dependency tree · one level
1 result within one dependency step of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Kalisch and Bühlmann, Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm, §2.1 (standard reference, not scraped)
- Lauritzen, Graphical Models lecture notes, Lemma 2.57 (standard reference, not scraped)