Injective if and only if Surjective

• Feb 3rd 2010, 07:38 AM
shmounal
Injective if and only if Surjective
Hi there, I have this problem and while I think what I've put is correct I'm not sure that it is rigorous enough. Any help much appreciated!!

(a) Let A be a finite set. Show that a function f : A → A is injective if
and only if it is surjective.

(b) Show that this result is false for infinite sets by exhibiting
• An injective map f : N → N that is not surjective;
• A surjective map f : N → N that is not injective.

For a) I've put that a function is injective if each unique element x in the domain X is mapped to an element y in some co-domain Y, and a function is surjective if for every element y in the co-domain Y there is atleast one element x in the domain X such that f(x)=y. As the cardinality of the domain and co-domain are the same if the function is injective it must also be surjective.

For b) An injective map which is not surjective would be 2x=y
For a surjective map which is not injective I'm thinking something like ┌ x/2┐=y (those symbols are meant to denote the ceiling function!!)
• Feb 3rd 2010, 04:37 PM
bmp05
So the interesting thing about this function is that it is a reflexive relation on the set A.

Injective iff. surjective means:
injective $\displaystyle \Rightarrow$ surjective and surjective $\displaystyle \Rightarrow$ injective.

A function is onto if the range of $\displaystyle f$ equals the codomain of $\displaystyle f$.
A function is one-to-one if no member of the codomain is the image under $\displaystyle f$ of two distinct elements of the domain.

That is $\displaystyle (\forall a)(\exists a')(a \mapsto a')$.

if $\displaystyle f$ is onto then it follows that $\displaystyle \Vert A \Vert \geq \Vert A' \Vert$ but from $\displaystyle (f: A \mapsto A \rightarrow \Vert A \Vert = \Vert A' \Vert ) \Rightarrow (\forall a')(\forall b')(a' = b' \rightarrow f'(a) = f'(b))$ and $\displaystyle f$ is also one-to-one.

And then you have to show it the other way around.

An injective map that is not surjective is $\displaystyle f:x \mapsto 2x$.
A surjective map that is not injective is $\displaystyle f: x \mapsto \lfloor \frac{1}{2}x \rfloor$