Proving injection,surjection,bijection

[Physicsissuef]

Homework Statement

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)$$

Homework Equations

The Attempt at a Solution

I have not idea at all. Can somebody, please help?

 

[EnumaElish]

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

 

[quantumdude]

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?

 

[Physicsissuef]

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?

Yes sir, sorry for missing the formula.

 

[quantumdude]

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.

 

[Physicsissuef]

And what about this one?
Prove that one copying $$f:A \rightarrow B$$ is surjection, only if $$f(A)=B$$

 

[quantumdude]

Are you going to make me guess the definition again?

 

[Physicsissuef]

Are you going to make me guess the definition again?

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

 

[HallsofIvy]

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.

 

[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, let's say $$f(x_1)=f(x_2)=1, x_1=x_2$$
http://pic.mkd.net/images/638823221.JPG
Still, can't understand.

 

[steelphantom]

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

Let f(x) = x². 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.

 

[Physicsissuef]

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

Let f(x) = x². 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.

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

 

[Physicsissuef]

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.

Can you give me the whole prove, please?

 

[HallsofIvy]

Can you give me the whole prove, please?

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(x₁)= f(x₂) then x₁= x₂. Okay, for this particular f, f(x₁)= 3x<sub>1- 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)= x², 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)= x², is not injective but is surjective?

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

What about k(x)= x², from non-negative real numbers to non-negative real numbers?</sub>

 

[Physicsissuef]

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(x₁)= f(x₂) then x₁= x₂. Okay, for this particular f, f(x₁)= 3x<sub>1- 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)= x², 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)= x², is not injective but is surjective?

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

What about k(x)= x², from non-negative real numbers to non-negative real numbers?</sub>

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

 

[cristo]

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

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.

 

[Physicsissuef]

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.

But why $x_1=x_2$?

 

[cristo]

But why $x_1=x_2$?

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

 

[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$

 

[cristo]

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$

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

 

[Physicsissuef]

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

I used the definition. $f(x_1)=f(x_2), x_1=x_2$.

 

[cristo]

I used the definition. $f(x_1)=f(x_2), x_1=x_2$.

That's not the definition of a function it is the definition of an injective function. Clearly whatever function you just used is not injective! You seem to be implicitly assuming that every function is injective, which is not true. HallsofIvy has already gone through an example above; did you read that? What didn't you follow in that example?

 

[Physicsissuef]

That's not the definition of a function it is the definition of an injective function. Clearly whatever function you just used is not injective! You seem to be implicitly assuming that every function is injective, which is not true. HallsofIvy has already gone through an example above; did you read that? What didn't you follow in that example?

Because I don't understand why $f(x_1)=f(x_2)$, only if $x_1=x_2$. Can you give me example with domains and co domains?

 

[Physicsissuef]

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(x₁)= f(x₂) then x₁= x₂. Okay, for this particular f, f(x₁)= 3x<sub>1- 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)= x², 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)= x², is not injective but is surjective?

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

What about k(x)= x², from non-negative real numbers to non-negative real numbers?</sub>

<sub>The first one is not injective and is not surjective because of the fact:

$$f(x_1)=x_1^2$$

$$f(x_2)=x_2^2$$

if $$x_1=-1$$ then $$f(x_1)=1$$

$$x_2=1$$ then $$f(x_2)=1$$

but

$$x_1 \neq x_2$$

It is not surjective because:

$$f(x)=x^2$$

$$f(x)=y$$

$$x= \pm \sqrt{y}$$

So if we get $$y=-1$$, then we will get complex numbers, and we need real numbers. Right?</sub>

 

[Physicsissuef]

For the 2nd one:
i.e
$$h:R \rightarrow R^+$$, defined by $$h(x)=x^2$$ IS not injection

Because of:

$$x_1,_2= \pm 1$$

It IS surjection

$$h(x)=x^2=y$$

$$x= \pm \sqrt{y}$$

So $$y$$ can be equal only to 1 and not to negative real numbers due [0,+∞)

 

[Physicsissuef]

For the 3rd one.

$$j(x)=x^2, j:R^+ \rightarrow R$$

It is injection due to x $\in$ [0,+∞)

It isn't surjection because of

[tex]x= \pm \sqrt{y}[/itex]<br /> <br /> y $\in$[/tex][itex](-∞,+∞)<br /> <br /> if y=-1 then we get complex numbers and not real numbers.<br /> <br /> And now for the 4th one.<br /> <br /> $$k(x)=x^2 , k:R^+ \rightarrow R^+$$<br /> <br /> It is injection due x $\in$ [0,+∞)<br /> <br /> It is surjection due to y $\in$ [0,+∞)<br /> <br /> So if it is injection and surjection, it is bijection. Am I right for 4 of the examples?[/itex]

 

[Physicsissuef]

How will I prove, this:
Prove that if $$f:A \rightarrow B$$ and $$g:B \rightarrow C$$ are injections (surjections), then $$g \circ f$$ is injection (surjecton).

And also this:
prove if $$f:A \rightarrow B$$ and $$g:B \rightarrow C$$ are bijections, then $$g \circ f$$ is bijection.

 

[Physicsissuef]

For the 2nd one.
$$f:A \rightarrow B$$ and $$g:B \rightarrow C$$ are bijections then $$g \circ f$$ is bijection.
$$f(x_1)=f(x_2), x_1=x_2$$ (injection)
$$f(A)=B$$ (surjection)
So if g is bijection and f is bijection... Hmm.. But how will I prove it?

 

[HallsofIvy]

How will I prove, this:
Prove that if $$f:A \rightarrow B$$ and $$g:B \rightarrow C$$ are injections (surjections), then $$g \circ f$$ is injection (surjecton).

To prove that $g\circ f$ is an injection, you must prove: "if $g\circ f(x_1)= g\circ f(x_2)$ then $x_1= x_2$", the definition of injection. Since we are given that g is an injection, we can say, again using that definition, "since $g\circ f(x_1)= g\circ f(x_2)$ then $f(x_1)= f(x_2)$". Do you see how that works?
$g\circ f(x)$ is itself defined as [/itex]g(f(x))[/itex] so I have replaced the "$x_1$" and "$x_2$" in "If $g(x_1)= g(x_2)$ then $x_1= x_2$" by "$f(x_1)$" and "$f(x_2)$". Once I have that, knowing that f is an injection tells me that $x_1= x_2$ and I am done.
Try the same thing yourself for "surjection'. Be sure to use the precise words and formulas that are in the definitions.

And also this:
prove if $$f:A \rightarrow B$$ and $$g:B \rightarrow C$$ are bijections, then $$g \circ f$$ is bijection.

For the 2nd one.
$$f:A \rightarrow B$$ and $$g:B \rightarrow C$$ are bijections then $$g \circ f$$ is bijection.
$$f(x_1)=f(x_2), x_1=x_2$$ (injection)
$$f(A)=B$$ (surjection)
So if g is bijection and f is bijection... Hmm.. But how will I prove it?

??No, you are given that f and g are bijections. You aren't trying to prove that! You want to prove "then $$g \circ f$$ is bijection" (I copied that directly from your problem). To do that, you use the definition of "bijection". That is, of course, that the function is both an injection and a surjection so you really need to do two proofs:
1) If f and g are both injections, then $f\circ g$ is an injection.
2) If f and g are both surjections, then $f\circ g$ is a surjection.
Well, you've already done those, haven't you? So the proof is really just to state that both of those are true from the proofs above and therefore $f\circ g$ is a bijection.