Natural Numbers

Overview

The standard way of representing the natural numbers is as follows:

• $0=\varnothing$
• $1=\{0\}=\{\varnothing \}$
• $2=\{0,1\}=\{\varnothing ,\{\varnothing \}\}$
• $\dots$

That is, each natural number corresponds to the set of natural numbers smaller than it.

Inductive Sets

For any set $a$, its successor $a^{+}$ is defined as $a^{+}=a\cup \{a\}$

A set $A$ is inductive if and only if $\varnothing \in A$ and $\forall a\in A,a^{+}\in A$.

A natural number is a set that belongs to every inductive set.

Peano System

A Peano system is a triple $⟨N,S,e⟩$ consisting of a set $N$, a function $S:N\to N$, and a member $e\in N$ such that the following three conditions are met:

• $e\notin \mathrm{ran}S$;
• $S$ is one-to-one;
• Any subset $A$ of $N$ that contains $e$ and is closed under $S$ equals $N$ itself.

Given $\sigma =\{⟨n,n^{+}⟩\mid n\in \omega \}$, $⟨\omega ,\sigma ,0⟩$ is a Peano system.

Transitivity

A set $A$ is said to be transitive iff every member of a member of $A$ is itself a member of $A$. We can equivalently express this using any of the following formulations:

• $x\in a\in A\Rightarrow x\in A$
• $\bigcup A\subseteq A$
• $a\in A\Rightarrow a\subseteq A$
• $A\subseteq \mathcal{P}A$

Recursion Theorem

The recursion theorem guarantees recursively defined functions exist. More formally, let $A$ be a set, $a\in A$, and $F:A\to A$. Then there exists a unique function $h:\omega \to A$ such that, for every $n\in \omega$, \begin{align*} h(0) & = a \\ h(n^+) & = F(h(n)) \end{align*}

\

Addition

For each $m\in \omega$, there exists (by the recursion theorem) a unique function $A_m:\omega \to \omega$ such that for all $n\in \omega$, \begin{align*} A_m(0) & = m, \\ A_m(n^+) & = A_m(n)^+ \end{align*}

Addition ($+$) is the binary operation on $\omega$ such that for any $m,n\in \omega$, $m+n=A_m(n).$

Multiplication

For each $m\in \omega$, there exists (by the recursion theorem) a unique function $M_m:\omega \to \omega$ such that for all $n\in \omega$, \begin{align*} M_m(0) & = 0, \\ M_m(n^+) & = M_m(n) + m \end{align*}

Multiplication ($\cdot$) is the binary operation on $\omega$ such that for any $m,n\in \omega$, $m\cdot n=M_m(n).$

Exponentiation

For each $m\in \omega$, there exists (by the recursion theorem) a unique function $E_m:\omega \to \omega$ such that for all $n\in \omega$, \begin{align*} E_m(0) & = 1, \\ E_m(n^+) & = E_m(n) \cdot m \end{align*}

Exponentiation is the binary operation on $\omega$ such that for any $m,n\in \omega$, $m^n=E_m(n).$

Ordering

For natural numbers $m$ and $n$, define $m$ to be less than $n$ if and only if $m\in n$. The following biconditionals hold true:

• $m\in n\iff m^{+}\in n^{+}$
• $m\in n\iff m\subset n$
• $m\underline{\in }n\iff m\subseteq n$

Well-Ordering Principle

Let $A$ be a nonempty subset of $\omega$. Then there is some $m\in A$ such that $m\underline{\in }n$ for all $n\in A$.

Strong Induction Principle

Let $A$ be a subset of $\omega$ and assume that for every $n\in \omega$, $\text{if every number less than }n\text{ is in }A,\text{then }n\in A.$ Then $A=\omega$.

Bibliography

• Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
• “Recursion,” in Wikipedia, September 23, 2024, https://en.wikipedia.org/w/index.php?title=Recursion#The_recursion_theorem.