- #1
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
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