ExampleConstruction: AI-generatedVerification: AI-generatedprecheck pass

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.

A four-vertex digraph where the bounded reachability recursion finds a path via a midpoint

Example

Let $G$ have vertices ${s, a, b, t}$ and arcs $s \to a$ , $a \to b$ , and $b \to t$ . Then ${Reach}_{1}^{G} (s, t)$ is false but ${Reach}_{2}^{G} (s, t)$ is true, witnessed by the midpoint $b$ .

Facts & Assumptions

Given: the digraph $G$ above.

[L1]

The recursion ${Reach}_{i}^{G}$ is defined by splitting at a midpoint (The bounded reachability recursion for directed paths of length at most $2^{i}$ ).

[L2]

${Reach}_{i}^{G} (u, v)$ holds exactly when there is a path of length at most $2^{i}$ from $u$ to $v$ (The bounded reachability recursion is correct).

Verification

technique · direct

1.1L2given

The only directed path from $s$ to $t$ is $s \to a \to b \to t$ , which has length $3$ . Therefore [L2] gives ${Reach}_{1}^{G} (s, t)$ false, because $2^{1} = 2 < 3$ .

2.1L1L2step 1.1

Using midpoint $b$ , [L1] reduces ${Reach}_{2}^{G} (s, t)$ to ${Reach}_{1}^{G} (s, b)$ and ${Reach}_{1}^{G} (b, t)$ . By [L2], the first holds because $s \to a \to b$ has length $2$ , and the second holds because $b \to t$ has length $1$ . Hence ${Reach}_{2}^{G} (s, t)$ is true.

3.1step 2.1∎

This makes the divide-and-conquer structure concrete: one midpoint splits the length- $3$ path into two shorter subproblems, exactly as the recursion predicts.

Remarks

The diagram displays exactly the three arcs of $G$ ; $b$ is the chosen recursive midpoint, not a new vertex. The two subpaths have lengths $2$ and $1$ , each at most $2^{1}$ , whereas the full path has length $3 > 2^{1}$ . Thus they witness ${Reach}_{2}^{G} (s, t)$ through ${Reach}_{1}^{G} (s, b)$ and ${Reach}_{1}^{G} (b, t)$ . The verification above is independent of the illustration.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

3 results within two dependency steps 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

Eric Blais, Models of Computation, 17. Space Complexity (standard reference, not scraped)