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 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
    2017 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
    2017 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
    2017 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
    2017 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
    2017 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

    User Avatar
    2017 Award

    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...