TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 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 recursion theorem

Statement

Let $(N, 0, σ)$ be a Peano system (Peano system), in particular the natural numbers $N$ (The natural numbers $N$ (von Neumann)). For any set $A$ , any element $a \in A$ , and any function $f : A \to A$ , there is a unique function $g : N \to A$ such that $g (0) = a$ and $g (σ (n)) = f (g (n))$ for all $n \in N$ .

Facts & Assumptions

Given: a Peano system $(N, 0, σ)$ , a set $A$ , an element $a \in A$ , and a function $f : A \to A$ . Call a set $R \subseteq N \times A$ closed when $(0, a) \in R$ and, for all $n \in N$ and $x \in A$ , $(n, x) \in R$ implies $(σ (n), f (x)) \in R$ .

[L1]

Induction holds in every Peano system $N$ : any $S \subseteq N$ with $0 \in S$ that is closed under $σ$ equals $N$ (axiom P3 in Peano system).

[L2]

In a Peano system $σ (n) \neq 0$ (P1) and $σ$ is injective (P2) (Peano system).

Proof

technique · direct

1.1givenconstruct

The set $N \times A$ is closed, so the collection of closed subsets of $N \times A$ is nonempty; let $g : = ⋂ {R : R \subseteq N \times A closed}$ , which is itself closed, since if every closed $R$ contains $(0, a)$ then so does $g$ , and if $(n, x) \in g$ then $(n, x) \in R$ for each closed $R$ , whence $(σ (n), f (x)) \in R$ for each such $R$ , so $(σ (n), f (x)) \in g$ .

2.1L1step 1.1

Let $D = {n \in N : \exists x \in A, (n, x) \in g}$ ; then $0 \in D$ since $(0, a) \in g$ , and if $n \in D$ with $(n, x) \in g$ then $(σ (n), f (x)) \in g$ by closure, so $σ (n) \in D$ ; by induction $D = N$ , hence $g$ relates every $n$ to at least one $x$ .

2.2L2step 1.1

Suppose $(0, b) \in g$ with $b \neq a$ ; then $g ∖ {(0, b)}$ still contains $(0, a)$ and is closed, since any generated pair $(σ (m), f (z))$ has $σ (m) \neq 0$ by P1 and so is never equal to $(0, b)$ ; this contradicts the minimality of $g$ , so $a$ is the unique second coordinate paired with $0$ .

3.1step 2.2

Let $U = {n \in N : there is exactly one x with (n, x) \in g}$ ; then $0 \in U$ by step 2.2.

4.1L2step 3.1step 1.1

Assume $n \in U$ with unique value $x$ , so $(n, x) \in g$ and $(σ (n), f (x)) \in g$ by closure; if $(σ (n), c) \in g$ with $c \neq f (x)$ , then $g ∖ {(σ (n), c)}$ contains $(0, a)$ because $σ (n) \neq 0$ , and is closed, because a generated pair $(σ (m), f (z))$ with $(m, z) \in g ∖ {(σ (n), c)}$ can equal $(σ (n), c)$ only if $σ (m) = σ (n)$ and $f (z) = c$ , but $σ (m) = σ (n)$ forces $m = n$ by injectivity, then $z = x$ by uniqueness at $n$ , giving $f (z) = f (x) \neq c$ , a contradiction; hence $g ∖ {(σ (n), c)}$ is closed and smaller than $g$ , contradicting minimality, so $f (x)$ is the unique value at $σ (n)$ and $σ (n) \in U$ .

5.1L1step 2.1step 3.1step 4.1

By induction $U = N$ , so together with the totality from step 2.1 the relation $g$ is a function $g : N \to A$ ; it satisfies $g (0) = a$ , and closure with uniqueness gives $g (σ (n)) = f (g (n))$ for all $n$ .

6.1L1step 5.1∎

If $h : N \to A$ also satisfies $h (0) = a$ and $h (σ (n)) = f (h (n))$ , then the set ${n : g (n) = h (n)}$ contains $0$ and is closed under $σ$ , since $g (n) = h (n)$ implies $g (σ (n)) = f (g (n)) = f (h (n)) = h (σ (n))$ , so by induction it equals $N$ , that is $h = g$ .

The recursion theorem

Statement

Facts & Assumptions

Proof

Depends on

Dependency tree · 2 levels

Sources