Prove onto and one-to-one

**imind** · January 28th 2011, 01:35 PM

I've been struggling with the compositions and injection/surjection so I borrowed a book from my professor and I was using both books to teach myself. I've gotten considerably better at the application of the onto and one-to-one (i.e. actually composing two functions and determining whether it's onto, one-to-one, or both/neither) ... The next portion of the excercise has me a bit stumped, it's a more abstract concept which requires me to prove ....

Suppose f, g, and h are all mappings of a set A into itself.

(a) Prove that if g is onto and $f \circ g = h \circ g$ , then $f = h$ .

(b) Prove that if f is one-to-one and $f \circ g = f \circ h$ , then $g = h$ .

I've been memorizing the definitions for injection, surjection, and image as well as a few others but I'm having a really hard time visualizing these and I think that's why I'm not able to prove them. Thanks for any help you guys can provide!

**dwsmith** · January 28th 2011, 01:43 PM

Originally Posted by imind

I've been struggling with the compositions and injection/surjection so I borrowed a book from my professor and I was using both books to teach myself. I've gotten considerably better at the application of the onto and one-to-one (i.e. actually composing two functions and determining whether it's onto, one-to-one, or both/neither) ... The next portion of the excercise has me a bit stumped, it's a more abstract concept which requires me to prove ....

Suppose f, g, and h are all mappings of a set A into itself.

(a) Prove that if g is onto and $f \circ g = h \circ g$ , then $f = h$ .

(b) Prove that if f is one-to-one and $f \circ g = f \circ h$ , then $g = h$ .

I've been memorizing the definitions for injection, surjection, and image as well as a few others but I'm having a really hard time visualizing these and I think that's why I'm not able to prove them. Thanks for any help you guys can provide!

For a, try a proof by contradiction.

**FernandoRevilla** · January 28th 2011, 01:50 PM

(b)

For all $x\in A$ :

$f[g(x)]=f[h(x)]$

Now, apply that $f$ is one to one.

Fernando Revilla

**Plato** · January 28th 2011, 02:40 PM

I suggest part a) be done directly.
If $z\in A$ then $\left( {\exists t \in A} \right)\left[ {g(t) = z} \right]$ . WHY?

So that means that $f(z)=h(z)$ for all $z\in A$ . HOW?

**imind** · January 28th 2011, 05:38 PM

Heh, Thanks for the help .. working on part a I've got the following and I'm kind of stuck as to where to go from here ... reminder, my issue is the overall lack of knowledge of "why" things are what they are ... I'm really having issues with understanding what exactly "onto-ness" means from an abstract concept ... here is what I've got so far:

Suppose $f$ , $g$ , and $h$ are all mappings of a set $A$ into itself.

a) Prove that if $g$ is onto and $f \circ g = h \circ g$ , then $f = h$

By Contradiction:
If $g$ is onto and $f \circ g=h \circ g$ ; then $f \neq h$

Proof:

let $f:A \rightarrow A$ and $g:A \rightarrow A$

so the composition of $f \circ g : A \rightarrow A$

Suppose $\exists a \in A$

since $g$ is onto,

$\exists b \in A \mid f(b)=a$

I'm not really sure where to go next ... I think I need to show that since fog and hog are equal there exists f(b)=a but that can't work cause f doesn't equal h ... does that look right? ... If it is I'm not really sure what it's saying and if anyone could show me an example I'd greatly appreciate it....

**dwsmith** · January 28th 2011, 05:46 PM

Originally Posted by imind

Heh, Thanks for the help .. working on part a I've got the following and I'm kind of stuck as to where to go from here ... reminder, my issue is the overall lack of knowledge of "why" things are what they are ... I'm really having issues with understanding what exactly "onto-ness" means from an abstract concept ... here is what I've got so far:

Suppose $f$ , $g$ , and $h$ are all mappings of a set $A$ into itself.

a) Prove that if $g$ is onto and $f \circ g = h \circ g$ , then $f = h$

By Contradiction:
If $g$ is onto and $f \circ g=h \circ g$ ; then $f \neq h$

Proof:

let $f:A \rightarrow A$ and $g:A \rightarrow A$

so the composition of $f \circ g : A \rightarrow A$

Suppose $\exists a \in A$

since $g$ is onto,

$\exists b \in A \mid f(b)=a$

I'm not really sure where to go next ... I think I need to show that since fog and hog are equal there exists f(b)=a but that can't work cause f doesn't equal h ... does that look right? ... If it is I'm not really sure what it's saying and if anyone could show me an example I'd greatly appreciate it....

f(b) = h(b)

For all b in B, there is an a in A such that g(a) = b. Since g is surjective, there is an a in A such that,

f(g(a)) = h(g(a))

.....

**imind** · January 28th 2011, 08:12 PM

So final answer ...

Suppose $f$ , $g$ , and $h$ are all mappings of a set $A$ into itself.

a) Prove that if $g$ is onto and $f \circ g = h \circ g$ , then $f = h$

By Contradiction:
If $g$ is onto and $f \circ g=h \circ g$ ; then $f \neq h$

Proof:

let $f:A \rightarrow A$ and $g:A \rightarrow A$

so the composition of $f \circ g : A \rightarrow A$

Suppose $\exists a \in A$

since $g$ is onto,

$\exists b \in A \mid f(b)=a$

By definition $f \circ g = h \circ g$

thus $f(b) = h(b)$

therefore f = h which is a contradiction

Does that look right dwsmith or should I alter it some? Now I'm trying to understand exactly what this is saying .. since the image under f and the image under h are equal the functions f and h must be equal? I'm going to move on and work on part b now, thanks so far for the help guys ... I had no idea there was a resource as good as this website out there, I may have to stick around

**LoblawsLawBlog** · January 28th 2011, 08:43 PM

I think you mean something more like "let $a\in A$ " instead of "suppose $\exists a\in A$ " (I guess if $A$ is actually empty then the problem is vacuously true). Also, I think you mean that there exists a $b\in A$ such that $g(b)=a$ , not $f(b)=a$ , since $g$ is the only function assumed to be onto.

I'd like to reiterate Plato's suggestion to just prove (a) directly. If you look at your proof it basically contains such a direct proof, although the last couple of lines could probably use some more justification. Maybe something like:

Let $a\in A$ . Since $g$ is onto, there is some $b\in A$ such that $g(b)=a$ . Now, $f(a)=f(g(b))=$ ...

As far as what "onto-ness" means, it just says that everything in the codomain/target space, or whatever you call it (the $B$ in $f:A\rightarrow B$ ) gets hit by something from $A$ when it gets run through the function.

**imind** · January 28th 2011, 09:27 PM

Suppose $f$ , $g$ , and $h$ are all mappings of a set $A$ into itself.

a) Prove that if $g$ is onto and $f \circ g = h \circ g$ , then $f = h$

By Contradiction:
If $g$ is onto and $f \circ g=h \circ g$ ; then $f \neq h$

Proof:

let $f:A \rightarrow A$ and $g:A \rightarrow A$

so the composition of $f \circ g : A \rightarrow A$

Suppose $\exists a \in A$

since $g$ is onto,

$\exists b \in A \mid g(b)=a$

By definition $f \circ g = h \circ g$

thus $f(a)=f(g(b))=h(g(b))$

therefore f = h and we arrive at a contradiction

I corrected a few of the things you pointed out does that look better? The way our professor likes stuff is similar to the way I wrote it out here so for consistency I just try to learn it that way ... helps for regurgitation

as for part b what do you think about the following

for an arbitrary x in a .. by definition f(g(x)) = f(h(x)) and f is one-to-one then g(x) = h(x) so g must equal h

how does that look logic wise?

**LoblawsLawBlog** · January 28th 2011, 10:19 PM

Well, the only thing about saying just "suppose there exists an $a$ in $A$ " is that it isn't really supposing much. Unless $A$ is empty then there is an $a\in A$ . So what? I'm probably nitpicking, but "if $a\in A$ ", "for any $a\in A$ ", or just "suppose $a\in A$ " all seem more natural.

Your statement right before the proof is a little awkward too. The way it's worded makes it look like you're claiming to prove that $f\neq h$ . Another minor thing: you need to show that $f(a)=h(a)$ for all $a\in A$ , so your last line should end with $=h(a)$ . Of course, $g(b)=a$ so it does follow immediately, but you should still write it.

Aside from that it looks good, but if you just start with the line "Suppose $a\in A$ " and then chop off the last sentence, you have a direct proof.

The proof of part b looks good.

**imind** · January 28th 2011, 10:25 PM

Thanks a ton... I'll add the b part a bit later today. If anyone has any other onto/one-to-one problems from some of there texts I'd greatly appreciate seeing them so I can really make sure I'm understanding this stuff. Were starting inverses next week which from reading ahead means we need to be able to understand onto and one-to-one which I'm guessing he'll cover also... Hoping to stay ahead haha

**emakarov** · January 29th 2011, 11:41 AM

If anyone has any other onto/one-to-one problems from some of there texts I'd greatly appreciate seeing them so I can really make sure I'm understanding this stuff.

First, there are these relatively simple facts.

Proposition 1. If f o g is onto, then so is f.

Proposition 2. If f o g is one-to-one, then so is g.

Proposition 3. If f o g is onto and f is one-to-one, then g is onto.

Proposition 4. Let h, s be functions from natural numbers to natural numbers, and suppose that s is not onto. Then h o s o h is not an identity.

It is easy to deduce this claim from the first three. However, if we know, for example, that $s(x)\ne 0$ for all $x$ , then it is possible to explicitly provide three numbers $x_1,x_2,x_3$ such that $(h\circ s\circ h)(x_i)\ne x_i$ for some $i=1,2,3$ . This requires some ingenuity.

Next, the converse of the claims in the OP also holds.

Proposition 5. Let f : A -> B. Then the following statements are equivalent.
(1) f is onto.
(2) For any set C and any g, h : B -> C, if g o f = h o f, then g = h.

Proposition 6. Let f : A -> B where |B| > 1. Then the following statements are equivalent.
(1) f is onto.
(2) For any g : B -> B, if g o f = f, then g is an identity function.

Proposition 7. Let f : A -> B. Then the following statements are equivalent.
(1) f is one-to-one.
(2) For any set C and any g, h : C -> A, if f o g = f o h, then g = h.

Finally, if you you really want to improve your one-to-one kung fu, then here is another problem. Suppose that eq : E -> Y and g, h : Y -> Z.

Definition. The function eq is called an equalizer of f and g if the following two conditions hold.
(1) $f\circ eq = g\circ eq$ .
(2) For any $y\in Y$ , if $f(y) = g(y)$ , then there exists a unique $x\in E$ such that $eq(x) = y$ .

In other words, $f(eq(x))$ = $g(eq(x))$ for all $x\in E$ , and if $f(y) = g(y)$ , that's only because $y$ is the image of one and only one $x\in E$ .

Proposition 8. If eq is an equalizer, then it in one-to-one.

**imind** · January 29th 2011, 03:46 PM

thanks emakarov ... I'm pretty sure I can do the first 3 so I'm going to get started

**imind** · January 31st 2011, 10:00 PM

Proposition 1:

Let g: A -> B and f: B ->. Prove that f is onto if fog is onto

outline Proof:

The composition fog maps A -> C and fog is onto
Thus for c in C there exists a in A such that fog (a) = f(g(a)) = c

Do I need to move to since every element in B is an image under g there exists g(a) = b and then show that f(b) = c proving that f is onto? can I do it in that order?

I'm kinda stuck on the proposition 2 ... I think I need to use 2 elements but I'm not sure where I need to go with it ... I think I got 5-7 though ... Thanks for the help guys ... Snow day tomorrow so I think I'm going to work on tackling Left/Right inverses and permutations!

Let me know if you see any errors or better ways for me to get to my solution

**emakarov** · February 1st 2011, 12:15 AM

every element in B is an image under g

This is false; it is not assumed that g is onto. However, you don't need to consider every element of B. For a given c, you have constructed a specific element b = g(a) and showed that c = f(b). Thus, you have proved that every c in C is the image of some b in B, i.e., that f is onto.

Concerning problem 2, the intuitive idea is the following. Suppose you need to encode a message in two stages. In the first, you replace each letter by a number. If you replace two different letters with the same number, then regardless of the second stage, these letters will be indistinguishable in the resulting code. So my first idea was to use proof by contradiction. Suppose g is not injective; then there exist distinct a1, a2 such that g(a1) = g(a2). Therefore, f(g(a1)) = f(g(a2)), which contradicts the fact that f o g is one-to-one. However, there is an even easier direct proof. Suppose g(a1) = g(a2). Then f(g(a1)) = f(g(a2)) and, since f o g is one-to-one, a1 = a2.

For other problems, it is probably better to start new threads.

Thread: Prove onto and one-to-one

LinkBack

Thread Tools

Display

Prove onto and one-to-one

Problems about injections and surjections

Similar Math Help Forum Discussions

Prove that

Prove n^2<= ......

prove that if sequence (an) converges, use def of limit of sequence to prove...

prove that

prove

Search Tags