Proving injection,surjection,bijection

  • Thread starter Physicsissuef
  • Start date
In summary, the conversation discusses the concept of injections in mathematical proofs. An injection is defined as a map that assigns each element in the domain to a unique element in the codomain. It is proven that for a map f:A \rightarrow B to be an injection, for all x_1,x_2 \in A, f(x_1)=f(x_2) implies x_1=x_2. The conversation also discusses the concept of surjections and how to prove that a function is surjective by showing that the range of the function is equal to the codomain. Examples of functions that are not injective and not surjective are also provided.
  • #1
Physicsissuef
908
0

Homework Statement



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

Homework Equations





The Attempt at a Solution



I have not idea at all. Can somebody, please help?
 
Physics news on Phys.org
  • #2
What is the definition of an injection that you are working with/have been taught?
 
  • #3
I bet the definition he was taught was the contrapositive of this one. Namely, that a map [itex]f:A\rightarrow B[/itex] is an injection if for all [itex]x_1,x_2\in A[/itex], [itex]f(x_1)=f(x_2)[/itex] implies [itex]x_1=x_2[/itex].

Physicsissuef, is that the definition in your book?
 
  • #4
Tom Mattson said:
I bet the definition he was taught was the contrapositive of this one. Namely, that a map [itex]f:A\rightarrow B[/itex] is an injection if for all [itex]x_1,x_2\in A[/itex], [itex]f(x_1)=f(x_2)[/itex] implies [itex]x_1=x_2[/itex].

Physicsissuef, is that the definition in your book?

Yes sir, sorry for missing the formula.
 
  • #5
In that case, your proof need only be one line long. For any conditional statement [itex]p \Rightarrow q[/itex] (that is: if p, then q), a logically equivalent statement is [itex]\neg q \Rightarrow \neg p[/itex] (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
And what about this one?
Prove that one copying [tex]f:A \rightarrow B[/tex] is surjection, only if [tex]f(A)=B[/tex]
 
  • #7
Are you going to make me guess the definition again?
 
  • #8
Tom Mattson said:
Are you going to make me guess the definition again?

surjection is, if every element [tex]y \in B[/tex] is image of at least one element [tex]a \in A[/tex]
 
  • #9
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 [itex]f: A\rightarrow B[/itex] mean?)
To prove that B is a subset of A, start with "if [tex]y \in B[/tex]" 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
Ok, but I think I still can't understand the definition of injection. What does [tex]f(x_1)=f(x_2), x_1=x_2[/tex], mean?
If I draw a domain and codomain, let's say [tex]f(x_1)=f(x_2)=1, x_1=x_2[/tex]
http://pic.mkd.net/images/638823221.JPG
Still, can't understand.
 
Last edited by a moderator:
  • #11
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. :smile:
 
  • #12
steelphantom said:
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. :smile:

Ok, thanks. But can you draw it with domains and co domains, like my picture, please?
 
  • #13
HallsofIvy said:
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 [itex]f: A\rightarrow B[/itex] mean?)
To prove that B is a subset of A, start with "if [tex]y \in B[/tex]" 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?
 
  • #14
Physicsissuef said:
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(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
HallsofIvy said:
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?


Ok, can you explain me first, why the definition is [itex]f(x_1)=f(x_2)[/itex] , [itex]x_1=x_2[/itex]? What it means?
 
  • #16
Physicsissuef said:
Ok, can you explain me first, why the definition is [itex]f(x_1)=f(x_2)[/itex] , [itex]x_1=x_2[/itex]? 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.
 
  • #17
cristo said:
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 [itex]x_1=x_2[/itex]?
 
  • #18
Physicsissuef said:
But why [itex]x_1=x_2[/itex]?

That's the "distinct element in the domain" part.
 
  • #19
Lets say if [itex]f(x_1)=f(x_2)[/itex], [itex]f(x_1)=y[/itex] if y=3, then [itex]f(x_2)=3[/itex]
if [itex]x_2=5[/itex], so [itex]f(5)=3[/itex], then [itex]x_1=6[/itex] and [itex]f(6)=3[/itex], it doesn't necessarily [itex]x_1=x_2[/itex]
 
  • #20
Physicsissuef said:
Lets say if [itex]f(x_1)=f(x_2)[/itex], [itex]f(x_1)=y[/itex] if y=3, then [itex]f(x_2)=3[/itex]
if [itex]x_2=5[/itex], so [itex]f(5)=3[/itex], then [itex]x_1=6[/itex] and [itex]f(6)=3[/itex], it doesn't necessarily [itex]x_1=x_2[/itex]

Sorry, but what function are you using? I don't see you define f anywhere.
 
  • #21
cristo said:
Sorry, but what function are you using? I don't see you define f anywhere.

I used the definition. [itex]f(x_1)=f(x_2), x_1=x_2[/itex].
 
  • #22
Physicsissuef said:
I used the definition. [itex]f(x_1)=f(x_2), x_1=x_2[/itex].

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?
 
  • #23
cristo said:
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 [itex]f(x_1)=f(x_2)[/itex], only if [itex]x_1=x_2[/itex]. Can you give me example with domains and co domains?
 
  • #24
HallsofIvy said:
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?


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

[tex]f(x_1)=x_1^2[/tex]

[tex]f(x_2)=x_2^2[/tex]

if [tex]x_1=-1[/tex] then [tex]f(x_1)=1[/tex]

[tex]x_2=1[/tex] then [tex]f(x_2)=1[/tex]

but

[tex]x_1 \neq x_2 [/tex]

It is not surjective because:

[tex]f(x)=x^2[/tex]

[tex]f(x)=y[/tex]

[tex]x= \pm \sqrt{y}[/tex]

So if we get [tex]y=-1[/tex], then we will get complex numbers, and we need real numbers. Right?
 
  • #25
For the 2nd one:
i.e
[tex]h:R \rightarrow R^+[/tex], defined by [tex]h(x)=x^2[/tex] IS not injection

Because of:

[tex]x_1,_2= \pm 1[/tex]

It IS surjection

[tex]h(x)=x^2=y[/tex]

[tex]x= \pm \sqrt{y}[/tex]

So [tex]y[/tex] can be equal only to 1 and not to negative real numbers due [0,+∞)
 
Last edited:
  • #26
For the 3rd one.

[tex]j(x)=x^2, j:R^+ \rightarrow R[/tex]

It is injection due to x [itex]\in[/itex] [0,+∞)

It isn't surjection because of

[tex]x= \pm \sqrt{y}[/itex]

y [itex]\in[/tex] (-∞,+∞)

if y=-1 then we get complex numbers and not real numbers.

And now for the 4th one.

[tex]k(x)=x^2 , k:R^+ \rightarrow R^+[/tex]

It is injection due x [itex]\in[/itex] [0,+∞)

It is surjection due to y [itex]\in[/itex] [0,+∞)

So if it is injection and surjection, it is bijection. Am I right for 4 of the examples?
 
  • #27
How will I prove, this:
Prove that if [tex]f:A \rightarrow B[/tex] and [tex]g:B \rightarrow C[/tex] are injections (surjections), then [tex]g \circ f [/tex] is injection (surjecton).

And also this:
prove if [tex]f:A \rightarrow B[/tex] and [tex]g:B \rightarrow C[/tex] are bijections, then [tex]g \circ f[/tex] is bijection.
 
  • #28
For the 2nd one.
[tex]f:A \rightarrow B [/tex] and [tex]g:B \rightarrow C[/tex] are bijections then [tex]g \circ f[/tex] is bijection.
[tex]f(x_1)=f(x_2), x_1=x_2[/tex] (injection)
[tex]f(A)=B[/tex] (surjection)
So if g is bijection and f is bijection... Hmm.. But how will I prove it?
 
  • #29
Physicsissuef said:
How will I prove, this:
Prove that if [tex]f:A \rightarrow B[/tex] and [tex]g:B \rightarrow C[/tex] are injections (surjections), then [tex]g \circ f [/tex] is injection (surjecton).
To prove that [itex]g\circ f[/itex] is an injection, you must prove: "if [itex]g\circ f(x_1)= g\circ f(x_2)[/itex] then [itex]x_1= x_2[/itex]", the definition of injection. Since we are given that g is an injection, we can say, again using that definition, "since [itex]g\circ f(x_1)= g\circ f(x_2)[/itex] then [itex]f(x_1)= f(x_2)[/itex]". Do you see how that works?
[itex]g\circ f(x)[/itex] is itself defined as [/itex]g(f(x))[/itex] so I have replaced the "[itex]x_1[/itex]" and "[itex]x_2[/itex]" in "If [itex]g(x_1)= g(x_2)[/itex] then [itex]x_1= x_2[/itex]" by "[itex]f(x_1)[/itex]" and "[itex]f(x_2)[/itex]". Once I have that, knowing that f is an injection tells me that [itex]x_1= x_2[/itex] 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 [tex]f:A \rightarrow B[/tex] and [tex]g:B \rightarrow C[/tex] are bijections, then [tex]g \circ f[/tex] is bijection.

Physicsissuef said:
For the 2nd one.
[tex]f:A \rightarrow B [/tex] and [tex]g:B \rightarrow C[/tex] are bijections then [tex]g \circ f[/tex] is bijection.
[tex]f(x_1)=f(x_2), x_1=x_2[/tex] (injection)
[tex]f(A)=B[/tex] (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 [tex]g \circ f[/tex] 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 [itex]f\circ g[/itex] is an injection.
2) If f and g are both surjections, then [itex]f\circ g[/itex] 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 [itex]f\circ g[/itex] is a bijection.
 

Related to Proving injection,surjection,bijection

1. What is the difference between injection, surjection, and bijection?

Injection, surjection, and bijection are all types of functions in mathematics. An injection, also known as one-to-one function, is a function where each element in the domain maps to a unique element in the range. A surjection, also known as onto function, is a function where every element in the range is mapped by at least one element in the domain. A bijection is a function that is both injective and surjective, meaning each element in the domain maps to a unique element in the range and every element in the range is mapped by exactly one element in the domain.

2. Why is it important to prove whether a function is an injection, surjection, or bijection?

Proving whether a function is an injection, surjection, or bijection is important because it helps us understand the relationship between the elements in the domain and the range. It also allows us to determine whether a function has an inverse, which is essential in solving many mathematical problems.

3. How do you prove a function is an injection?

To prove a function is an injection, you need to show that for every pair of distinct elements in the domain, the corresponding elements in the range are also distinct. This can be done by assuming that two elements in the domain map to the same element in the range and then showing that this leads to a contradiction. Another way is to use the formal definition of an injection, which states that for every element in the range, there exists only one element in the domain that maps to it.

4. Can a function be both an injection and a surjection?

Yes, a function can be both an injection and a surjection. This type of function is called a bijection and is often referred to as a one-to-one correspondence. An example of a bijection is the function f(x) = x, where the domain and range are both the set of real numbers.

5. How do you prove a function is a bijection?

To prove a function is a bijection, you need to show that it is both an injection and a surjection. This can be done by using one of the methods mentioned above to prove that the function is injective and then showing that every element in the range is mapped by at least one element in the domain. Another way is to use the definition of a bijection, which states that a function is bijective if and only if it has an inverse function. Thus, you can prove a function is a bijection by showing that it has an inverse function.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
15
Views
888
  • Precalculus Mathematics Homework Help
Replies
32
Views
948
  • Precalculus Mathematics Homework Help
Replies
22
Views
2K
Replies
3
Views
845
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
  • Precalculus Mathematics Homework Help
Replies
19
Views
2K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Precalculus Mathematics Homework Help
2
Replies
57
Views
3K
  • Precalculus Mathematics Homework Help
Replies
14
Views
1K
Back
Top