Proof of Recursion on the Natural Numbers Starting at One

Let $0$ be as in The Class Omega of Natural Numbers with Zero §zero, let $S(x)$ denote the successor of a set $x$, and let $\omega$ be as in The Class Omega of Natural Numbers with Zero §omega. By The Set of Natural Numbers and the Number One §naturals and The Boolean Operations on Classes, Disjointness, and the Universal Class §operations, $\mathbb{N}\subseteq\omega$. By Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §successors, a set $x$ lies in $\mathbb{N}$ if and only if $x=S(k)$ for some $k\in\omega$.

The shifted step map. Let $k\in\omega$ and $u\in a$. Then $S(k)\in\mathbb{N}$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §successors, so $(S(k),u)\in\mathbb{N}\times a=\operatorname{dom}g$ by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set §membership and Functions, Values of a Function, and Functions from One Class to Another §map; hence the value $g(S(k),u)$ is defined, and it lies in $\operatorname{ran}g\subseteq a$ by Functions, Values of a Function, and Functions from One Class to Another §value, Relations, Domain, Range, Inverse and Composition §range and Functions, Values of a Function, and Functions from One Class to Another §map. Since $\omega$ is a set by Omega Is the Least Inductive Class: It Is a Set, Induction from Zero, the Peano Properties, and Transitivity §set, Maps and Relations Given by Formulas §binary, applied with the sets $\omega$, $a$ and $a$ in place of $c$, $d$ and $b$ and with the expression $g((S(k),u))$ in the variables $k$ and $u$ and the parameter $g$, gives a map $G:\omega\times a\to a$ with $G(k,u)=g(S(k),u)$ for all $k\in\omega$ and $u\in a$.

Recursion on $\omega$. By The Recursion Theorem on Omega §recursion, applied to $a$, $c$ and $G$, there is a map $h:\omega\to a$ with $h(0)=c$ and $h(S(k))=G(k,h(k))=g(S(k),h(k))$ for every $k\in\omega$.

The shifted map. Let

$$f=\{p:\exists k\,\exists u\,(p=(S(k),u)\wedge(k,u)\in h)\},$$

formed by class abstraction with the parameter $h$; its formula quantifies over set variables only, the ordered pair and $S(k)$ being defined set symbols, so it is predicative as Class Theory NBG: the Axioms, Standing Conventions and Basic Notation §comprehension requires. By Class Abstraction: the Class of All Sets Satisfying a Predicative Formula §abstraction and The Characteristic Property of Ordered Pairs and Nested Tuples of Sets §characteristic, for all sets $x$ and $u$,

$$(x,u)\in f\quad\text{if and only if}\quad\text{there is }k\text{ with }x=S(k)\text{ and }(k,u)\in h.\qquad(\ast)$$

Every element of $f$ is an ordered pair, so $f$ is a relation. If $(x,u)\in f$ and $(x,u')\in f$, then by $(\ast)$ there are $k,k'$ with $x=S(k)=S(k')$, $(k,u)\in h$ and $(k',u')\in h$; then $k=k'$ by Omega Is the Least Inductive Class: It Is a Set, Induction from Zero, the Peano Properties, and Transitivity §successor-injective, and $u=u'$ because $h$ is a function. So $f$ is a function by Functions, Values of a Function, and Functions from One Class to Another §function. If $x\in\operatorname{dom}f$, then by Relations, Domain, Range, Inverse and Composition §domain and $(\ast)$, $x=S(k)$ with $(k,u)\in h$ for some $u$, so $k\in\operatorname{dom}h=\omega$ and $x\in\mathbb{N}$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §successors. Conversely, if $x\in\mathbb{N}$, then $x=S(k)$ with $k\in\omega=\operatorname{dom}h$, and $(x,h(k))\in f$ by $(\ast)$ and Functions, Values of a Function, and Functions from One Class to Another §value, so $x\in\operatorname{dom}f$. By Class Theory NBG: the Axioms, Standing Conventions and Basic Notation §extensionality, $\operatorname{dom}f=\mathbb{N}$. If $u\in\operatorname{ran}f$, then $(k,u)\in h$ for some $k$ by Relations, Domain, Range, Inverse and Composition §range and $(\ast)$, so $u\in\operatorname{ran}h\subseteq a$ by Functions, Values of a Function, and Functions from One Class to Another §map. Hence $f:\mathbb{N}\to a$ by Functions, Values of a Function, and Functions from One Class to Another §map, and by $(\ast)$ and Functions, Values of a Function, and Functions from One Class to Another §value, $f(S(k))=h(k)$ for every $k\in\omega$. The class $f$ is moreover a set, as the lower-case letter requires under Class Theory NBG: the Axioms, Standing Conventions and Basic Notation §notation: each element $(x,u)$ of $f$ has $x\in\operatorname{dom}f=\mathbb{N}$ and $u\in\operatorname{ran}f\subseteq a$, so it lies in $\mathbb{N}\times a$ by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set §membership; thus $f\subseteq\mathbb{N}\times a$ by Subclasses and Subsets §subclass, where $\mathbb{N}\times a$ is a set by The Set of Natural Numbers and the Number One §naturals and Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set §set, and $f$ is a set by Subclasses of Sets Are Sets, the Union and Power Set of a Set Exist Uniquely, Binary Unions of Sets Are Sets, and the Universal Class Is Proper §subclass.

Existence. Since $0\in\omega$ by Omega Is the Least Inductive Class: It Is a Set, Induction from Zero, the Peano Properties, and Transitivity §inductive and $1=S(0)$ by The Set of Natural Numbers and the Number One §one, $f(1)=f(S(0))=h(0)=c$. Let $n\in\mathbb{N}$. Then $n=S(k)$ for some $k\in\omega$, and $S(k)\in\omega$ by Omega Is the Least Inductive Class: It Is a Set, Induction from Zero, the Peano Properties, and Transitivity §inductive. Since $n\in\omega$, $n+1=S(n)=S(S(k))$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §plus-one, and $S(n)\in\mathbb{N}$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §successors, so $n+1\in\operatorname{dom}f$ and $f(n+1)$ is defined. Moreover $f(n)\in\operatorname{ran}f\subseteq a$ by Functions, Values of a Function, and Functions from One Class to Another §value, Relations, Domain, Range, Inverse and Composition §range and Functions, Values of a Function, and Functions from One Class to Another §map, so $(n,f(n))\in\mathbb{N}\times a=\operatorname{dom}g$ by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set §membership and $g(n,f(n))$ is defined. Hence

$$f(n+1)=f(S(S(k)))=h(S(k))=g(S(k),h(k))=g(n,f(S(k)))=g(n,f(n)).$$

Uniqueness. Let $f':\mathbb{N}\to a$ be a map with $f'(1)=c$ and $f'(n+1)=g(n,f'(n))$ for every $n\in\mathbb{N}$. Let

$$A=\{n\in\mathbb{N}:f(n)=f'(n)\},$$

formed by restricted class abstraction with the parameters $\mathbb{N}$, $f$ and $f'$; its formula has no quantifier, the values $f(n)$ and $f'(n)$ being defined set symbols by Functions, Values of a Function, and Functions from One Class to Another §value, so it is predicative as Class Theory NBG: the Axioms, Standing Conventions and Basic Notation §comprehension requires. By Class Abstraction: the Class of All Sets Satisfying a Predicative Formula §restricted, $A\subseteq\mathbb{N}$. Since $f(1)=c=f'(1)$ and $1\in\mathbb{N}$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §one, $1\in A$. Let $n\in A$. Then $S(n)=n+1$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §plus-one, $S(n)\in\mathbb{N}$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §successors, and $f(n+1)=g(n,f(n))=g(n,f'(n))=f'(n+1)$, so $S(n)\in A$. By The Principle of Induction for the Natural Numbers Starting at One §induction, $A=\mathbb{N}$, that is, $f(n)=f'(n)$ for every $n\in\mathbb{N}$. Since $\operatorname{dom}f=\mathbb{N}=\operatorname{dom}f'$ by Functions, Values of a Function, and Functions from One Class to Another §map, Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §equality gives $f=f'$. Hence $f$ is the only map with the stated properties.