Thread: Another functions proof

Hello, I have a question that I not sure how to proceed on:

Let X be a nonempty set and let be a function such that .
Show that if f is onto then .

I started by saying:

Suppose f is onto. Then for each there exists at least one such that .

And then I can't think what to do next. The previous question which was where I got to suppose f was one-to-one seemed much easier!

Hint:

Maybe it is better to start with a contradiction.

Let . Then there exists a x1 such that f(x1) = x2 and x1<>x2

fof(x1) = f(x1) ---- by your definition of f
also fof(x1) = f(f(x1)) = f(x2)
thus f(x1) = f(x2) => f is not one-to-one

Can you try to complete?

Also if you could please confirm that set X is finite - else I'm running into some cotradictions. If anyone else can also please confirm to us that X has to be finite for this result to hold. Thanks

I'll just leave this blank...

Sorry for all the sutipidity above. You do not need the condition that X is finite.

Let x be in the range of f. We will prove that f(x) = x for fof = f to hold true.

Assume otherwise. i.e. f(x) = y where y <> x for some x in the range of f.

As x is in the range of f, so there exists z such that f(z) = x; z<> x

consider fof(z) = f(z) = x; also fof(z) = f(f(z)) = f(x) = y; but we assumed y <> x so contradiction !!

hence every element in the range of f get mapped to itself. as f is onto thus f is identify function.

No Swlabr - I do not think we need the assumtion that X should be finite. Please see my re-worked proof below. fof = f is a much stronger condition I guess.

Originally Posted by aman_cc

No Swlabr - I do not think we need the assumtion that X should be finite. Please see my re-worked proof below. fof = f is a much stronger condition I guess.

yeah - I realised my counter-example wasn't a counter-example...it wasn't a surjection!

mistake, nvm

Here is direct proof.
If then by the given .
Because we have .