# Thread: Injective if and only if Surjective

1. ## 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!!)

2. So the interesting thing about this function is that it is a reflexive relation on the set A.

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

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

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

if $f$ is onto then it follows that $\Vert A \Vert \geq \Vert A' \Vert$ but from $(f: A \mapsto A \rightarrow \Vert A \Vert = \Vert A' \Vert ) \Rightarrow (\forall a')(\forall b')(a' = b' \rightarrow f'(a) = f'(b))$ and $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 $f:x \mapsto 2x$.
A surjective map that is not injective is $f: x \mapsto \lfloor \frac{1}{2}x \rfloor$