1. Not finding help here? Sign up for a free 30min 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!

Logic and proof of injection

  1. Oct 2, 2016 #1
    1. The problem statement, all variables and given/known data
    Prove that ##f: \mathbb{R}\to\mathbb{R}, f(x) = x^2## is not injective.

    2. Relevant equations
    Definition of an injection: function ##f:A\to B## is an injection if and only if ##\forall a,b \in A, f(a) = f(b) \Rightarrow a = b##.

    3. The attempt at a solution
    ##f: \mathbb{R}\to\mathbb{R}##
    Let ##a,b \in \mathscr{D_f}##, suppose ##f(a) = f(b)##, then ##a^2=b^2##. By solving this equation we get ##a=b\ or \ a = -b##.

    This is where I'm stuck. How do I prove that (and is the following what I have to prove) ##\forall a,b \in \mathbb{R}, (a = b \vee a=-b) \Rightarrow (a = b) \equiv F##?

    By introducing the substitutions ##A := (a =b), B:= (a = -b)##, the proposition is reduced to ##(A \vee B) \Rightarrow A \equiv F##.

    Now, what am I looking for in the truth table? The expression is obviously not always false, but for the ##F## to hold I have to find one case where the proposition does not hold and I've proven my hypothesis. From the truth table, if ##B \equiv T, A \equiv F## we get ##T \Rightarrow F##, which is false; consequently, our problem is solved.

    Is my approach correct, and is there another approach? Thank you in advance.
     
  2. jcsd
  3. Oct 2, 2016 #2

    Math_QED

    User Avatar
    Homework Helper

    It is as simple of finding a counterexample. In this case, there are many.
     
  4. Oct 2, 2016 #3
    Thank you. Would you mind addressing my question? So far I've found one "explanation", where the author says that "it is obvious", after finding the solutions to the equation.
     
  5. Oct 2, 2016 #4

    Math_QED

    User Avatar
    Homework Helper

    For example we have:

    ##f(-1) = f(1)## but ## -1 \neq 1## thus f is not injective
     
  6. Oct 2, 2016 #5
    The explanation the book provides is: "The solution of the equation is ##|a| = |b|##, that is, we have 4 solutions in ##\mathbb{R}##, which means that the given implication does not hold because ##a## and ##b## obviously don't have to be equal; consequently, the proposition is false."

    I'm intrigued as to how the "obvious" step is performed formally and not intuitively.
     
  7. Oct 2, 2016 #6

    fresh_42

    Staff: Mentor

    @Math_QED 's answer has been formally!

    ... proves ##\exists a,b \in A \, : \, f(a) = f(b) \wedge a \neq b##, which is the negation of ##f## being injective.
     
  8. Oct 2, 2016 #7

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Another approach was to draw a graph of ##y = x^2## and look for two values of ##x## with the same value of ##y##.
     
  9. Oct 2, 2016 #8
    ...which I could've gotten without the equations obtained by the author of the book. So what is their purpose? I'm not practicing (dis)proving the injectivity, but the logic of proving "obvious" statements formally.
     
  10. Oct 2, 2016 #9

    fresh_42

    Staff: Mentor

    In this case it seems, that a feasible solution depends strongly on the rules of logical deviations and and the amount of arithmetic which you regard as being allowed to use. Neither of it is obvious to us, and assuming the usual logic and arithmetic, the given two(!) answers are enough.
    In addition we can't say what the equations obtained by the author of the book and their purpose are, since we don't know them. Maybe it is simply to practice the handling of logical terms.

    I can't see why an obvious result should be artificially complicated.

    A counterexample even holds in the case you are rejecting indirect proofs or proofs by contradiction. The negation of an all-quantifier is simply an existence-quantifier. Otherwise you should explain what "not injective" means.
     
  11. Oct 2, 2016 #10

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You're getting confused about what constitutes a proof. To prove for example that not all whole numbers are odd, you only have to find one that is not odd.

    To prove this sort of thing requires only a single counterexample, nothing more.

    To prove something positive, such as to prove there are infinitely many primes requires a logical proof.
     
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: Logic and proof of injection
  1. Logic: Proofs (Replies: 3)

Loading...