TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-07

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.

Relative halting is oracle-c.e.-complete

Statement

For every oracle $A$ , $A^{'}$ is $A$ -c.e.-complete under $\leq_{m}^{A}$ .

Facts & Assumptions

Given: an oracle $A$ and an $A$ -c.e. set $W$ , recognized by program $e$ .

Proof

technique · direct

1.1

Dovetailing the computations $Φ_{i}^{A} (i)$ enumerates exactly $A^{'}$ , so $A^{'}$ is $A$ -c.e.

givenconstruct

1.2

Insert the numerals $e, n$ into the fixed oracle-program template which ignores its own input and simulates $Φ_{e}^{A} (n)$ . The hardwiring compiler of The Turing jump gives its index $s (e, n)$ by a total computable map, uniformly in $e, n$ and independently of $A$ . Therefore $n \in W ⟺ Φ_{e}^{A} (n) ↓ ⟺ Φ_{s (e, n)}^{A} (s (e, n)) ↓ ⟺ s (e, n) \in A^{'} .$

givenconstruct

2.1

Thus $n \mapsto s (e, n)$ is a total $A$ -computable many-one reduction $W \leq_{m}^{A} A^{'}$ . Since $W$ was arbitrary, the definition of completeness applies.

step 1.1step 1.2∎

Depends on

Used by

Finite jumps match arithmetical levels Corollary

Dependency tree · two levels

4 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

Sebastiaan Terwijn, Computability Theory, §5.2 (standard reference, not scraped)