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

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.

Sigma_1^0 sets are exactly the computably enumerable sets

Statement

For $A \subseteq N$ , $A$ is $Σ_{1}^{0}$ if and only if $A$ is computably enumerable (recognizable).

Facts & Assumptions

Given: a subset $A$ of $N$ .

Proof

technique · direct

1.1

If $x \in A ⟺ \exists s R (x, s)$ with $R$ primitive recursive, search $s = 0, 1, \dots$ and halt on the first true value. This recognizes exactly $A$ .

givenconstruct

2.1

Conversely, a recognizer has a finite halting computation exactly on its positive inputs. Its coded history gives an existential witness whose validity is primitive recursive, so $A$ has a $Σ_{1}^{0}$ definition.

step 1.1construct∎

Depends on

Used by

Delta₁⁰ sets are exactly the decidable sets Corollary
Reading a c.e. definition as a Sigma₁⁰ formula Example
Post's theorem Theorem
The halting set is Sigma₁⁰-complete Theorem

Dependency tree · two levels

6 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

Ludovic Patey, Computability Theory, Proposition 2.1 (standard reference, not scraped)