Pipeline-generated

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.

✓ 3 results · all verified · 3 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 3 also cleared it.

The Arithmetical Hierarchy and Post's Theorem: Examples and Counterexamples

1 · Prerequisites

2 · Summary

These examples make the computation witness in a $Σ_{1}^{0}$ formula and the eventual, rather than effectively timed, nature of a limit approximation concrete.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-06Open item page →

Reading a c.e. definition as a Sigma_1^0 formula

Example

The halting set is expressed by $⟨ e, x ⟩ \in K ⟺ \exists s T (e, x, s),$ where $s$ encodes a complete halting computation history.

Facts & Assumptions

Given: the fixed computation-history coding for $K$ .

Verification

technique · direct

1.1

Validity of a proposed finite history is primitive recursive, so the displayed formula has one leading unbounded existential quantifier over a bounded matrix.

givenconstruct

2.1

Hence it is a $Σ_{1}^{0}$ presentation. The witness is precisely the finite accepting computation used by the recognizer of $K$ .

step 1.1∎

ExampleConstruction: Literature-sourcedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-06Open item page →

A limit approximation computed from the halting oracle

Example

For the halting set, put $h (e, s) = 1$ if the $e$ th program halts within $s$ steps and put $h (e, s) = 0$ otherwise.

Facts & Assumptions

Given: a program index $e$ .

Verification

technique · direct

1.1

Bounded simulation makes $(e, s) \mapsto h (e, s)$ computable.

givenconstruct

2.1

If $e$ never halts every value is $0$ ; if it halts at stage $r$ , every value from $r$ onward is $1$ . Thus $\lim_{s} h (e, s) = χ_{0^{'}} (e)$ , without supplying a computable stage at which this happens.

step 1.1∎

CounterexampleConstruction: Literature-sourcedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-06Open item page →

A set lying in both Sigma_n^0 and Pi_n^0

Statement refuted

The assertion that $Σ_{n}^{0} \cap Π_{n}^{0}$ is empty for positive $n$ .

Facts & Assumptions

Given: a positive finite level $n$ .

Counterexample

technique · direct

1.1

The set $E$ of even natural numbers has the decidable predicate $x = 2 q$ for some $q$ , and its complement has the decidable predicate $x = 2 q + 1$ for some $q$ .

givenconstruct

2.1

Therefore $E$ is $Δ_{1}^{0}$ and is in both $Σ_{n}^{0}$ and $Π_{n}^{0}$ after padding for every $n \geq 1$ . It witnesses overlap, not equality of the two classes.

step 1.1∎

The Arithmetical Hierarchy and Post's Theorem: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Reading a c.e. definition as a Sigma_1^0 formula

Example

Facts & Assumptions

Verification

A limit approximation computed from the halting oracle

Example

Facts & Assumptions

Verification

A set lying in both Sigma_n^0 and Pi_n^0

Statement refuted

Facts & Assumptions

Counterexample

Sources