Thread: proof with functions

So I am pretty sure this statement is false so my proof should be incorrect by I cannot see where the error is.

The statement is: If g o f is 1 -1 then g is 1 -1

Let (f(x),g[f(x)]), (f(z),g[f(z)]) be elements of g
to prove 1 -1 assume g[f(x)] = g[f(z)]
so we must prove f(x) = f(z) in order to be 1 - 1

(x, g[f(x)]), (z, g[f(z)]) are elements of g o f
since g[f(x)] = g[f(z)] and g o f is 1 - 1, x = z

(x, f(x) ), (z, f(z) ) are elements of f
since x = z and f is a function, f(x) = f(z)
therefore g is 1 - 1.

Can someone help?

Originally Posted by stuffthings

The statement is: If g o f is 1 -1 then g is 1 -1

If and you need to be surjective (onto), otherwise the statement is not true. However I see from your working that you are implicitly assuming to be surjective. Still it's always better to state everything clearly at the beginning.

I was not assuming it was onto. Thank you for the clarification.

Originally Posted by stuffthings

[FONT=Verdana,Arial,Helvetica][SIZE=2][FONT=Verdana,Arial,Helvetica][SIZE=2]So I am pretty sure this statement is false so my proof should be incorrect by I cannot see where the error is.
The statement is: If g o f is 1 -1 then g is 1 -1

. Then

would a similar proof work to prove f is 1 -1 when g o f is 1 -1.

(x, f(x) ), (z, f(z) ) are elements of f
f(x) = f(z)

(f(x), g[f(x)] ) (f(z), g[f(z)]) are elements of g
since f(x) = f(z) and g is a function g[f(x)] = g[f(z)]

(x, g[f(x)] ), (z, g[f(z)] ) are elements of g o f
since g[f(x)] = g[f(z)] and g o f is 1 -1, x = z

therefore f is 1 -1 .

this is how it works:

if gof is 1-1, then f is 1-1 (g might not be 1-1).
if gof is onto, then g is onto (f may not be onto).

here is how a proof of the two works:

suppose that f(x) = f(y), and that gof is 1-1.

then gof(x) = g(f(x)) = g(f(y)) = gof(y) (since f(x) and f(y) are the same point in the image of f).

since gof is 1-1, x = y, so f is 1-1.

***

now, suppose that we have that gof is onto. let z be any point in the image of g.

we need to find a y such that g(y) = z.

because gof is onto, there IS an x in the domain of gof, with gof(x) = z.

let y = f(x). then g(y) = g(f(x)) = gof(x) = z, as desired.

***

a counter-example, to show that even if gof is 1-1, g might not be 1-1, and even if gof is onto, f might not be onto:

let g = {(r,x),(s,y),(t,y)} that is:

g(r) = x
g(s) = y
g(t) = y

then g is not 1-1, because g(s) = g(t), but s ≠ t.

let f = {(a,r), (b,s)} that is:

f(a) = r
f(b) = s.

note that gof is well-defined, we have:

gof(a) = g(f(a)) = g(r) = x
gof(b) = g(f(b)) = g(s) = y

so gof = {(a,x), (b,y)}, which is 1-1, even though g ISN'T.

******

if X = {x,y}, then the same example shows that gof is onto X:

we have a such that gof(a) = g(f(a)) = g(r) = x,

we have b such that gof(b) = g(f(b)) = g(s) = y.

however, f is NOT onto S = {r,s,t}, because there is no element of dom(f) = {a,b} that f maps to t.