Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Proof by contradiction

  1. Sep 17, 2016 #1

    Math_QED

    User Avatar
    Homework Helper

    Hello.

    I'm currently studying about natural numbers and I encountered the theorem of definition by recursion:

    This states:

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

    I will not post the entire proof here, as it is a quite long proof, but the part where I have a question about.

    In the proof, they prove that:

    If ##(n,y) \in f## and ##(n,y) \neq (1,e)##, then there is some ##(m,u) \in f## such that ##(n,y) = (s(m), k(u))##

    They do this by deriving a contradiction. I quote the book:

    Suppose to the contrary that there is some ##(r,t) \in f## such that ##(r,t) \neq (1,e)##, and that there is no ##(m,u) \in f## such that ##(r,t) = (s(m),k(u))##

    Writing out the statement we want to proof with symbols, we get:

    ##(n,y) \in f \land (n,y) \neq (1,e) \Rightarrow \exists (m,u) \in f : (n,y) = (s(m), k(u))##

    I think, if we negate this (to start with a contradiction), we should have instead:

    ##(n,y) \in f \land (n,y) \neq (1,e) \land \forall (m,u) \in f : (n,y) \neq (s(m), k(u))##
    and thus, since the book recalls ##(n,y) = (r,t)## since ##(n, y)## was used previously:

    ##(r,t) \in f \land (r,t) \neq (1,e) \Rightarrow \forall (m,u) \in f : (r,t) \neq (s(m), k(u))##

    Is the statement in the book correct too and are both logically equivalent or...?

    Thanks in advance
     
    Last edited: Sep 17, 2016
  2. jcsd
  3. Sep 17, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    What is s?

    Something went wrong with formatting in the second part of the post.
     
  4. Sep 17, 2016 #3

    Math_QED

    User Avatar
    Homework Helper

    Trying to fix it, I don't find the mistake:

    s is a function ##\mathbb{N} \rightarrow \mathbb{N}## that is defined by the Peano Postulates.

    EDIT: fixed the Latex
     
  5. Sep 17, 2016 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Okay, so we get f(1)=e, f(2)=k(e), f(3)=k(k(e)) and so on.

    Replaying n by r and y by t doesn't change anything.
     
  6. Sep 17, 2016 #5

    Math_QED

    User Avatar
    Homework Helper

    Yes but that's not the question. They just do that because they used (n,y) previously and otherwise it could cause confusion.
     
  7. Sep 17, 2016 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You asked if they are equivalent?
    The negation looks right.
     
  8. Sep 17, 2016 #7

    Math_QED

    User Avatar
    Homework Helper

    Yes, is the book's negation correct? And mine?
     
  9. Sep 17, 2016 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That's what I said.
     
  10. Sep 17, 2016 #9

    Math_QED

    User Avatar
    Homework Helper

    So they are equivalent? How can I verify that other than just thinking about it? Are there rules for?
     
  11. Sep 17, 2016 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Again: yes.
    Wikipedia has a list of rules for negation.
     
  12. Sep 17, 2016 #11

    Math_QED

    User Avatar
    Homework Helper

    I don't see anything about negations involving quantifiers. But I guess it's obvious, although I'm somewhat curious how one should prove these things, if this is even possible. Maybe they are axioms.
     
  13. Sep 20, 2016 #12

    fresh_42

    Staff: Mentor

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: Proof by contradiction
  1. Proof by contradiction? (Replies: 12)

  2. Proof by contradiction (Replies: 1)

Loading...