1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Recursion theorem: application in proof

  1. Sep 21, 2016 #1

    Math_QED

    User Avatar
    Homework Helper

    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
     
  2. jcsd
  3. Sep 21, 2016 #2

    fresh_42

    Staff: Mentor

    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##
     
    Last edited: Sep 21, 2016
  4. Sep 21, 2016 #3

    Erland

    User Avatar
    Science Advisor

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Recursion theorem: application in proof
  1. Proofs of theorems (Replies: 8)

  2. Proof by contradiction (Replies: 11)

Loading...