# Proving injection,surjection,bijection

1. Feb 27, 2008

### Physicsissuef

1. The problem statement, all variables and given/known data

Prove that one copying $$f:A \rightarrow B$$ is injection, only if $$x_1,x_2 \in A$$ and $$x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$$

2. Relevant equations

3. The attempt at a solution

2. Feb 27, 2008

### EnumaElish

What is the definition of an injection that you are working with/have been taught?

3. Feb 27, 2008

### Tom Mattson

Staff Emeritus
I bet the definition he was taught was the contrapositive of this one. Namely, that a map $f:A\rightarrow B$ is an injection if for all $x_1,x_2\in A$, $f(x_1)=f(x_2)$ implies $x_1=x_2$.

Physicsissuef, is that the definition in your book?

4. Feb 27, 2008

### Physicsissuef

Yes sir, sorry for missing the formula.

5. Feb 27, 2008

### Tom Mattson

Staff Emeritus
In that case, your proof need only be one line long. For any conditional statement $p \Rightarrow q$ (that is: if p, then q), a logically equivalent statement is $\neg q \Rightarrow \neg p$ (that is: if not p, then not q). This latter statement is called the contrapositive of the first, and it can be immediately inferred from it.

6. Feb 27, 2008

### Physicsissuef

Prove that one copying $$f:A \rightarrow B$$ is surjection, only if $$f(A)=B$$

7. Feb 27, 2008

### Tom Mattson

Staff Emeritus
Are you going to make me guess the definition again?

8. Feb 27, 2008

### Physicsissuef

surjection is, if every element $$y \in B$$ is image of at least one element $$a \in A$$

9. Feb 27, 2008

### HallsofIvy

Staff Emeritus
Okay, you prove one set is equal to another by showing that each is a subset of the other. And you prove subset by saying "if x is in" the first set and then showing that x must be in the second.

It should be trivial to show that f(A) is a subset of B. (What does $f: A\rightarrow B$ mean?)
To prove that B is a subset of A, start with "if $$y \in B$$" and show that y is in f(A). Of course, you will also need to use the definition of "f(A)".

Do you see a basic theme in all of this? Learn the exact words of the definitions. You can use the exact statement of definitions in proofs.

10. Feb 28, 2008

### Physicsissuef

Ok, but I think I still can't understand the definition of injection. What does $$f(x_1)=f(x_2), x_1=x_2$$, mean?
If I draw a domain and codomain, lets say $$f(x_1)=f(x_2)=1, x_1=x_2$$
http://pic.mkd.net/images/638823221.JPG [Broken]
Still, can't understand.

Last edited by a moderator: May 3, 2017
11. Feb 28, 2008

### steelphantom

Here's an example of something that's not an injection:

Let f(x) = x2. If f(y) = f(z) = 4, does y = z ? Not necessarily, because you could have y = 2 and z = -2. This is not an injection.

If, for example, f(x) = 2x, then f(y) = f(z) would imply that y = z. e.g. f(y) = f(z) = 4 => y = z = 2. This is an injection.

Hope that helped you understand the concept a little better.

12. Feb 28, 2008

### Physicsissuef

Ok, thanks. But can you draw it with domains and co domains, like my picture, please?

13. Feb 29, 2008

### Physicsissuef

Can you give me the whole prove, please?

14. Feb 29, 2008

### HallsofIvy

Staff Emeritus
No, we don't want to prevent you form learning- you learn by doing, not by watching someone else do it for you .

I will do this: suppose f:R->R is defined by f(x)= 3x- 4. To prove that f is injective ("one-to-one") we need to prove "if f(x1)= f(x2) then x1= x2. Okay, for this particular f, f(x1)= 3x1- 4 and f(x2)= 3x2- 4 so f(x1)= f(x2) means 3x1- 4= 3x2- 4. Adding 4 to both sides of the equation gives 3x1= 3x2 and then dividing both sides by 3, x1= x2, exactly what we needed to prove. To prove f is surjective ("onto"), let y be any real number. We need to prove that there must exist x such that f(x)= y. f(x)= 3x- 4= y so, again adding 4 to both sides, 3x= y+ 4 and then dividing by 3, x= (y+4)/3. For any real number y, that is still a real number. Since every number in R is f(x) for some x, f is surjective.

Now, can you tell me why g: R-> R, defined by g(x)= x2, can you tell me g is not injective and is not surjective?

Can you tell me why h:R to the non-negative real numbers, defined by h(x)= x2, is not injective but is surjective?

What about j(x)= x2, from non-negative real numbers to all real numbers?

What about k(x)= x2, from non-negative real numbers to non-negative real numbers?

15. Mar 1, 2008

### Physicsissuef

Ok, can you explain me first, why the definition is $f(x_1)=f(x_2)$ , $x_1=x_2$? What it means?

16. Mar 1, 2008

### cristo

Staff Emeritus
It's just the definition. In words, it means that an injective function is one that maps a distinct element in the domain to a distinct element in the codomain.

17. Mar 1, 2008

### Physicsissuef

But why $x_1=x_2$?

18. Mar 1, 2008

### cristo

Staff Emeritus
That's the "distinct element in the domain" part.

19. Mar 1, 2008

### Physicsissuef

Lets say if $f(x_1)=f(x_2)$, $f(x_1)=y$ if y=3, then $f(x_2)=3$
if $x_2=5$, so $f(5)=3$, then $x_1=6$ and $f(6)=3$, it doesn't necessarily $x_1=x_2$

20. Mar 1, 2008

### cristo

Staff Emeritus
Sorry, but what function are you using? I don't see you define f anywhere.