Composition of Mappings, Surjective and Injective

[gbean]

Homework Statement

a) Let g: A => B, and f: B => C. Prove that f is one-to-one if f o g is one-to-one.
b) Let g: A => B, and f: B => C. Prove that f is onto if f o g is onto.

Homework Equations

a) Since f o g is onto, then (f o g)(a) = (f o g)(b) => a = b.
b) Since f o g is onto, every element in C is an image under f o g.
(f o g)(a) = f(g(a)) = f(b) = c

The Attempt at a Solution

a) Proof by contradiction. Assume that g is not one-to-one.
(f o g)(a) = (f o g)(b)
f(g(a)) = f(g(b))
I don't know where to go from here.
I'm just wondering if this explanation is rigorous enough.
b) Proof by contradiction: Assume that f is not onto.

(f o g)(a) = f(g(a)) = f(b) = c.
However, f is not onto, thus there exists a c in C that is not mapped to by f. Thus by definition, f o g is not onto if not every c in C is an image under f o g. This is a contradiction of the given, hence f must be onto.

 

[Robert1986]

Homework Statement

a) Let g: A => B, and f: B => C. Prove that f is one-to-one if f o g is one-to-one.
b) Let g: A => B, and f: B => C. Prove that f is onto if f o g is onto.

Homework Equations

a) Since f o g is onto, then (f o g)(a) = (f o g)(b) => a = b.
b) Since f o g is onto, every element in C is an image under f o g.
(f o g)(a) = f(g(a)) = f(b) = c

The Attempt at a Solution

a) Proof by contradiction. Assume that g is not one-to-one.
(f o g)(a) = (f o g)(b)
f(g(a)) = f(g(b))
I don't know where to go from here.



I'm just wondering if this explanation is rigorous enough.
b) Proof by contradiction: Assume that f is not onto.

(f o g)(a) = f(g(a)) = f(b) = c.
However, f is not onto, thus there exists a c in C that is not mapped to by f. Thus by definition, f o g is not onto if not every c in C is an image under f o g. This is a contradiction of the given, hence f must be onto.

For part a), I think you meant that you are going to assume that f is not 1-1.

Anyway, what exactly does this mean for a function to NOT be 1-1? You had it partially correct (though you seem to have been working in the "opposite" direction). It means there is an a =! b such that f(a)=f(b).

So, if f sends a and b to the same element of B, where does g send f(a) and where does g send f(b)? Can you find a contradiction there?

 

[Robert1986]

Wait, I got confused, in a) are you showing that f or g is 1-1?

 

[gbean]

Whoops, I wrote down part a wrong. It should be: a) Let g: A => B, and f: B => C. Prove that g is one-to-one if f o g is one-to-one.

 

[gbean]

a) Proof by contradiction. Assume that g is not one-to-one.
(f o g)(a) = (f o g)(a')
f(g(a)) = f(g(a'))

If g is not 1-to-1 then there exist distinct a and a' such that g(a) = g(a') = b.

Then f(b) = f(b) => c = c. But this means that (f o g)(a) = c and (f o g)(a') = c, or that there exist distinct a and a' such that (f o g)(a) = (f o g)(a') = c. This is a contradiction as f o g is not 1-to-1, hence g must be 1-to-1.