Alphabeta Math
LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)
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 C if each noncollider occurrence is outside C and each collider occurrence is an ancestor of C, including membership in C. If an active route joins vertices x,y∉C with x≠y, then an active distinct-vertex path joins x and y given C.

Facts & Assumptions

[F1]

The active-path criterion and finite acyclic graph conventions are those of Paths, active paths, and d-separation in a finite DAG.

Proof

technique · shorten repeated-vertex loops and check the only possible newly blocked junction

Given: An active route from x to y and the hypotheses in the statement.

1.1givenF1chooseconstruct

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 x, or the terminal segment from the earlier occurrence of y. Endpoints are outside C, 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 v. Delete the segment between two such occurrences and identify them. Only the two incidences at the joined occurrence of v change. If v∈C, its old occurrences were both colliders, so the joined occurrence is still a collider. If v∉C and the joined occurrence is a noncollider, it is allowed; if it is a collider and v is an ancestor of C, it is also allowed.

2.1F1step 1.1construct∎

The sole remaining possibility is that the join makes v a collider although v is not an ancestor of C. Both original occurrences were then noncolliders. The retained edge before the first occurrence points into v, so its deleted departure edge must point out of v; likewise the deleted arrival edge at the second occurrence points out of v, since its retained departure edge points into v. Traverse the deleted segment starting with its arrow out of v. There must be a first place where its arrows cease to point forward: the final arrow points backward, and an entirely forward return to v would also contradict acyclicity. At that first change is a collider w, reached from v by a directed segment. A directed segment in a DAG has no repetitions. Activity of the original route makes w an ancestor of C, hence v an ancestor of C, 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