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!

Proof by contradiction and function

  1. Aug 30, 2015 #1
    1. The problem statement, all variables and given/known data
    Problem 1
    Assuming that the people in D and C all have KTP (Citizen ID in my country) IDs, let:

    D = {x |x is the KTP ID of a student in your Basic Calculus class},

    C = {y |y is the KTP ID of the biological father/mother of a student in your Basic Calculus class},

    and f : D ->C be the function that relates a student in your Basic Calculus class to his/her

    biological father and mother.

    1. It is clear that f does not exist. Why?

    2. You can fix C such that f exists. Express your fix formally using the set-builder notation,

    and then, formally define f!

    Problem 2
    Proof by contradiction that if p^2 is an odd number, then p is an odd number too, profided
    p is an element of integer numbers

    2. Relevant equations

    3. The attempt at a solution
    Problem 1
    1. Because a case can occur when both the student's father and mother are in the list as there is no rule that say it can't, if that occur, then f is not a function as it fails the vertical line test

    2.D= {x|x is the KTP ID of a student in calculus class}
    C= {y|y is the KTP ID of either a student's father or mother}
    f(x)= KTP number of a student's father or mother

    I've submitted these answers to my lecturer and have been told that both were wrong. Number 2 is wrong my way of fixing it does not uphold the required relationship

    Problem 2
    I've followed like they did here http://proofsfromthebook.com/2014/09/28/odd-and-square/. I thought it's proof by contraposition and told by my lecturer that it was.
  2. jcsd
  3. Aug 30, 2015 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't think you have defined C clearly enough. (What does "father/mother" mean?). I'm guessing that you mean that C contains the KTP ID's of all the fathers, the KTP ID's of all the mothers, and nothing else.

    The question about f doesn't entirely make sense. It doesn't make sense to say that f is some specific function, and then say that f doesn't exist. If it doesn't exist, then it isn't a function. But I guess it's clear enough that what they're asking you to do is to explain why the statement that's supposed to define f is inadequate. I wouldn't say that your answer is wrong, but it can be improved somewhat. If Charlie's parents are Alice and Bob, then what does the definition say that f(Charlie) is? Is it an element of D?

    Your attempt to change the definitions of C and f doesn't work because you haven't made it clear what exactly the elements of C are, or what each f(x) is.

    One of the most basic results in logic is that ##A\Rightarrow B## is equivalent to ##\lnot B\Rightarrow\lnot A##. The latter statement is called the contrapositive of the former. So if you want to prove "p2 odd ⇒ p odd", you can do it by proving its contrapositive.

    An alternative approach is to start with the statement "suppose that p2 is odd", and then try to prove that p is odd. You can use a proof by contradiction to do this. It would be best to explain what you're going to do: "We're going to prove that p is odd by deriving a falsehood from the assumption that it's not. So suppose that p is not odd". This approach is more complicated, but perhaps more deserving of the label "proof by contradiction".

    Note that in this approach, we prove A ⇒ B by assuming A and proving B. It's B that's proved by contradiction, not the implication A ⇒ B. If you really want to prove the implication by contradiction, you have to assume that it's false. This is to assume that A is true and B is false. Then you derive a falsehood from those assumptions.
    Last edited: Aug 30, 2015
  4. Aug 30, 2015 #3


    User Avatar
    Science Advisor

    You start by saying "assuming the people in C and D" and then define C and D as sets of numbers, not people!
    Problem 1 follows from the definition of "function"- what is that definition?

    "Proof by contradiction" starts by assuming the conclusion is false, then finding a contradiction. Here, the conclusion is "then p is an odd number". If p in NOT an odd number, it is an even number.
  5. Aug 30, 2015 #4
    Hi, thanks for the response. For problem 1 doesn't the problem already define the elements of D and C?
  6. Aug 30, 2015 #5


    User Avatar
    Science Advisor

    Yes, but NOT as "sets of people" so you cannot talk about the "people" in sets C and D!
  7. Aug 30, 2015 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The problem statement defines D clearly, but I don't think it's clear what "father/mother" means. However, the only interpretation I see is that C is the set of all the KTP IDs of all the parents of the students whose KTP IDs are included in C. If that interpretation is correct, then I would say that the problem has defined D clearly and C sufficiently clearly.

    But you also said this:
    Doesn't this mean that you should change the definition of C before you attempt to define f?
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 and function
  1. Proof By Contradiction (Replies: 7)

  2. Proof by contradiction (Replies: 1)

  3. Proof by Contradiction (Replies: 1)

  4. Proof by contradiction (Replies: 13)

  5. Proof by contradiction (Replies: 11)