Definition by Recursion - Need for Rigour

Question

Suppose you define the factorial $n!$ by \begin{align} \tag{1}0!&:=1,\\ \tag{2}(n+1)!&:=(n+1)n!. \end{align} Consider the following argument showing that $n!$ is a uniquely defined function.

Let $$ P(n):="n!\text{ is uniquely defined }". $$ Then $(1)$ gives $P(0)$ and $(2)$ gives $P(n)\implies P(n+1)$. So, by induction, $P(n)$ is true for every natural number $n$, that is, the factorial $n!$ has been uniquely defined.

Question: Why is this argument erroneous?

There might be some ambiguity talking about $n!$ in advance of knowing that it exists, but what if we write $$ P'(n):="\text{The symbol }n!\text{ is uniquely defined }". $$

In the end, is it the impossibility of translating $P'(n)$ in, say, the formal language of ZF that is problematic?

Answer 1

We have to distinguish between first-order arithmetic and second-order one.

The original (1889) Peano version is second-order; see Arithmetices Principia, page 1 has :

Axiomata

1) $1 ∈ N$ [...]

9) $(k∈Class \land 1∈k∧x∈N∧∀x(x∈k→(x+1)∈k)→N⊆k)$.

Also Landau express his Axiom 5 (Induction) as :

Let there be given a set $\mathfrak M$ of natural numbers, with the following properties:

I) $1$ belongs to $\mathfrak M$. [...]

In a modern treatment of second-order arithmetic (see e.g.Dirk van Dalen, Logic and Structure (5th ed - 2013), page 152), we need the following axioms :

1) $∀x¬(0=S(y))$

2) $∀xy(S(x) ∧ S(y) → x = y)$

3) $∀P(P(0)∧∀x(P(x) → P(S(x))) → ∀xP(x))$.

We can for simplicity extend the language with $+$ and $\times$, but we can define them, according to Church, as follows :

$x+y=z \leftrightarrow \forall F(F(0,x) \land \forall x \forall y (F(x,y) \to F(S(x),S(y)) \to F(y,z))$.

With this definition, and the corresponding one for $\times$, we can prove existence and uniqueness of the corresponding operations.

---

In f-o arithmetic, we cannot prove the existence of a function, because we cannot quantify neither predicate nor function letters, i.e. we cannot express in it $\exists F (F(\ldots))$.

Thus, we need the so-called rucursive axioms for sum and product :

$x+0=x$

$x+S(y)=S(x+y)$

and similar for $\times$.

The $+$ symbol is a function symbol, interpreted - according to the "standard" semantical specifications - as an operation :

$+ : N × N → N$, where $N$ is the domain of the interpretation.

With the equality axiom for function symbols :

$∀x_1 \ldots x_n y_1 \ldots y_n \ (x_1=y_1 \land \ldots x_n=y_n → f(x_1,\ldots, x_n) = f(y_1,\ldots, y_n))$,

"applied" to $+$ we get :

$\forall x_1 x_2 y_1 y_2 \ (x_1=y_1 \land x_2=y_2 \to x_1+x_2=y_1+y_2)$.

We can say that the "existence" and "uniqueness" of the $+$ and $\times$ operations are built-in into the syntax and semantics of the language.

---

---

If we are working in set theory, the arithmetical "notions" are nor more primitive : we define suitable "substitute" for $0$ and the successor operation as well as for $+$ and $\times$.

In this case, we can prove Peano axioms (Induction included) and the uniqueness of the sum and product function, via recursion; see :

• George Tourlakis, Lectures in Logic and Set Theory : Volume 2, Set Theory (2003), page 246;

• Kenneth Kunen, The Foundations of Mathematics (2009), page 43 :

On $\omega$ we already have the Principle of Ordinary Induction (Theorem 1.8.14 : For any set $X$ : if $0 \in X$ and $\forall y \in X(S(y) \in X)$, then $X$ contains all natural numbers.), whereas recursion would be used to justify the definition of the factorial ($!$) function by:

$0! = 1$

$(n + 1)! = n!(n + 1)$.