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.
Every active finite route contains an active path
Statement
In a finite DAG, a route is a finite sequence of vertices with consecutive vertices adjacent by an arrow in either direction; repeated vertices are allowed. Collider and noncollider status is assigned to each internal occurrence using its two incident route arrows. A route is active given if each noncollider occurrence is outside and each collider occurrence is an ancestor of , including membership in . If an active route joins vertices with , then an active distinct-vertex path joins and given .
Facts & Assumptions
The active-path criterion and finite acyclic graph conventions are those of Paths, active paths, and d-separation in a finite DAG.
Proof
Given: An active route from to and the hypotheses in the statement.
Among active routes with these endpoints choose one of minimum length. If a repeated vertex occurs at an endpoint, discard the initial segment through the later occurrence of , or the terminal segment from the earlier occurrence of . Endpoints are outside , and all retained internal occurrences have their old incidences, so the shortened route is active. Consequently any repetition in a minimum route consists of two internal occurrences of a vertex . Delete the segment between two such occurrences and identify them. Only the two incidences at the joined occurrence of change. If , its old occurrences were both colliders, so the joined occurrence is still a collider. If and the joined occurrence is a noncollider, it is allowed; if it is a collider and is an ancestor of , it is also allowed.
The sole remaining possibility is that the join makes a collider although is not an ancestor of . Both original occurrences were then noncolliders. The retained edge before the first occurrence points into , so its deleted departure edge must point out of ; likewise the deleted arrival edge at the second occurrence points out of , since its retained departure edge points into . Traverse the deleted segment starting with its arrow out of . There must be a first place where its arrows cease to point forward: the final arrow points backward, and an entirely forward return to would also contradict acyclicity. At that first change is a collider , reached from by a directed segment. A directed segment in a DAG has no repetitions. Activity of the original route makes an ancestor of , hence an ancestor of , a contradiction. Thus every loop deletion above is active and strictly shorter, contradicting minimality. The minimum route is therefore a path.
Source notes
Pearl's d-separation criterion supplies the occurrence-wise activity conditions. The loop-junction argument above is supplied locally; the source's statement of the moralization test is not used in place of this proof.
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
- Judea Pearl, Causal Diagrams for Empirical Research, §2-1, pp. 671–672 (standard reference, not scraped)