TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedverified 2026-09-23 (gpt-6-sol)

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.

The totality set is Pi_2^0-complete

Statement

$T O T = {e : (\forall x) φ_{e} (x) ↓}$ is $Π_{2}^{0}$ -complete.

Facts & Assumptions

Given: An acceptable numbering $(φ_{e})$ and an arbitrary $Π_{2}^{0}$ set $A \subseteq N$ .

[F1]

$Π_{2}^{0}$ membership has a $\forall x \exists y$ formula with primitive-recursive matrix (The classes Sigma_n^0, Pi_n^0, and Delta_n^0).

[F2]

Completeness means membership in $Π_{2}^{0}$ and a total computable many-one reduction from every $Π_{2}^{0}$ set (Completeness at an arithmetical level).

[F3]

$T (e, x, s)$ is a primitive-recursive test for a complete halting computation (Kleene's T-predicate and output function).

[F4]

The parameter theorem makes the index of a program with one parameter fixed a total computable function of that parameter (The s-m-n theorem).

Proof

technique · direct

1.1F1F3given

By [F3], $φ_{e} (x) ↓$ is equivalent to $\exists s T (e, x, s)$ with a primitive-recursive matrix. Thus $e \in T O T$ is $\forall x \exists s T (e, x, s)$ , a $Π_{2}^{0}$ predicate.

1.2F1givenconstruct

By [F1], write $z \in A ⟺ \forall x \exists y R (z, x, y)$ with $R$ primitive recursive. Fix one program $P$ which, on coded inputs $(z, x)$ , tests $R (z, x, 0), R (z, x, 1), \dots$ in order and halts with output $0$ at the first successful test. Each test terminates, so $P (z, x)$ halts exactly when $\exists y R (z, x, y)$ .

2.1F2F4step 1.1step 1.2∎

Let $e_{P}$ be a fixed index of $P$ . The specialization map in [F4] gives a total computable $f (z) = s_{1}^{1} (e_{P}, z)$ whose program on input $x$ agrees with $P (z, x)$ . Hence $f (z) \in T O T$ exactly when $\forall x \exists y R (z, x, y)$ , equivalently $z \in A$ . Since $A$ was arbitrary, [F2] and step 1.1 prove $Π_{2}^{0}$ -completeness.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

14 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, Example 1.5 (standard reference, not scraped)