Alphabeta Math
LemmaStatement: Literature-sourcedProof: 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.

DAG adjacency is equivalent to having no separating set

Statement

Let G be a finite DAG on V. For distinct vertices i,j∈V, the pair {i,j} is an edge of the skeleton of G if and only if there is no S⊆V∖{i,j} that d-separates i and j in G.

Facts & Assumptions

Given: A finite DAG G and distinct vertices i,j∈V.

[F1]

In a finite DAG, a path is active given S when each internal noncollider is outside S and each collider has a descendant in S, with membership in S counted as being its own descendant. Paths, active paths, and d-separation in a finite DAG

Proof

1.1givenF1

If i and j are adjacent, the one-edge path between them has no internal vertices, so it is active given every S⊆V∖{i,j} by [F1]. Hence no such S d-separates them.

1.2givenF1constructchoose

Suppose i and j are nonadjacent. Acyclicity implies that at least one of i,j is not a descendant of the other; after interchanging labels, assume j is not a descendant of i. Since i,j are nonadjacent, j is a non-descendant non-parent of i. Put S=pa⁡G(i). Then S excludes both endpoints. Consider any path i=v0,v1,…,vr=j. If its first arrow points into i, then v1∈S and the occurrence of v1 is a noncollider, because the arrow v1→i has its tail at v1; the path is blocked. If the first arrow points out of i, follow arrows that point forward along the path until the first arrow that points backward. Such a reversal must occur because j is not a descendant of i. At the reversal vertex vt, both incident arrows point into vt, so it is a collider and the initial segment is a directed path i→⋯→vt. If vt had a descendant p∈S, then i→⋯→vt→⋯→p→i would be a directed cycle. Thus this collider has no descendant in S, and the path is blocked by [F1]. Every path is blocked, so S d-separates i and j.

2.1step 1.1step 1.2algebra∎

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