Undergrad Recursion theorem: application in proof

[member 587159]

I have read a proof but I have a question. To give some context, I first wrote down this proof as written in the book. First, I provide the recursion theorem though.

Recursion theorem:

Let H be a set. Let $e \in H$. Let $k: \mathbb{N} \rightarrow H$ be a function. Then there exists a unique function f such that $f(1) = e$ and $f \circ s = k \circ f$.

Theorem: There is a unique binary operation $+: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ that satisfies the following two properties for all $n,m \in \mathbb{N}$
1) n + 1 = s(n)
2) n + s(m) = s(n + m)

(s is the successor function as described in the Peano Postulates)

Proof: Uniqueness: I'm going to skip this here as it is not important for my question.

Existence:

For $p \in \mathbb{N}$, we can apply the recursion theorem to the set $\mathbb{N}$, the element $s(p) \in \mathbb{N}$ and the function $s: \mathbb{N} \rightarrow \mathbb{N}$ to deduce that there is a unique function $f_p: \mathbb{N} \rightarrow \mathbb{N}$ such that $f_p(1) = s(p)$ and $f_p \circ s = s \circ f_p$. Let $+: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ be defined by $c + d = f_c(d)$ for all $(c,d) \in \mathbb{N} \times \mathbb{N}$. Let $n,m \in \mathbb{N}$. Then $n + 1 = f_n(1) = s(n)$, which is part 1) and $n + s(m) = f_n(s(m)) = s(f_n(m)) = s(n + m)$, which is part 2).I'm having a hard time to understand why we can define $c + d = f_c(d)$. $f_c$ is unique by the recursion theorem, what exactly does this mean? That we can only define this function as $f_c: \mathbb{N} \rightarrow \mathbb{N}: d \mapsto c + d$ and there is no other possibility? If this is the case, how do we show that this function is indeed the unique one the recursion theorem talks about. In fact, the recursion theorem says there exists such a unique function, but how do they know that it is that function? Thank you in advance

 

[fresh_42]

I don't really understand your confusion.*) My confusion is the recursion theorem itself, but we take that for granted here. This means (for $k = s$)
$$\forall \, {p \in \mathbb{N}=H} \quad \exists ! \, {f_p} \; : \; f_p(1) = s(p) = e \in \mathbb{N}=H \; \wedge \; f_p(s(n)) = s(f_p(n))$$

Thus we may use it to define $(c,d) := c+d := f_c(d)$ because $f_c$ is unique and $f_c$ is defined on $\mathbb{N}$.
Whether there is another way to define $c+d$ isn't clear, since you left out the uniqueness part. But at least it is one possible definition and the uniqueness of every $f_c$ makes it well-defined, i.e. unambiguous.

The properties then are simply substitutions of these definitions plus the properties of the recursion theorem.

*) Edit: Maybe I got it. If it is the varying $f_c$ that concerns you, then think of it as follows:
$(c,d) \overset{1:1}\longleftrightarrow (f_c,d) := f_c(d) =: c + d$

 

[Erland]

For a thorough discussion about the recursion theorem, with two proofs and much more, see this thread:

https://www.physicsforums.com/threads/question-about-the-axiom-of-dependent-choice.716209/