Prove Mapping from Set to Itself: 1-1 & Not onto iff Onto & Not 1-1

[mehrts]

Prove that there is a mapping from a set to itself that is one-to one but not onto iff there is a mapping from the set to itself that is onto but not one-to -one.

Since this is a 'iff' proof, so I must prove the statementlike two 'if' statements.

Let g:S ---> S.

Assume that g is 1-1 but not onto.

==> g(x1) = g(x2), for x1,x2 E S

==> x1 = x2

Now what ? Since the mapping is not onto, there must be no y E S such that y = g(x) for some x E S. I'm stuck. Dunno what to do :-(

 

[matt grime]

Draw a picture. A map from a set to itself can be pictured as a bunch of arrows with the tail at x and the head at f(x) for each arrow.

Injective means that no two arrows meet, and surjective means every element is at the head of an arrow.

So if we draw two blobs for two copies of X and a picture of an ijective function that is not surjective can't you see how to reverse the arrows and add somemore into get a picture with a surjective map that is not injective? The dual statement follows immediately as well.

 

[mehrts]

Thxs I get it.

I might post the solution up here later.