# Logic and proof of injection

1. Oct 2, 2016

### Korisnik

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. Oct 2, 2016

### Math_QED

It is as simple of finding a counterexample. In this case, there are many.

3. Oct 2, 2016

### Korisnik

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.

4. Oct 2, 2016

### Math_QED

For example we have:

$f(-1) = f(1)$ but $-1 \neq 1$ thus f is not injective

5. Oct 2, 2016

### Korisnik

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.

6. Oct 2, 2016

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

7. Oct 2, 2016

### PeroK

Another approach was to draw a graph of $y = x^2$ and look for two values of $x$ with the same value of $y$.

8. Oct 2, 2016

### Korisnik

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

9. Oct 2, 2016

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

10. Oct 2, 2016

### PeroK

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.