## Definition of a bijection

Show that for a mapping $$f:X\to X$$ on a finite set $$X$$, $$f$$ is injective if and only if $$f$$ is surjective.

Does this assertion hold even for infinite sets $$X$$?

• #### Solution

We will first show by contradiction that if $$f$$ is injective, then it is surjective.

If some mapping $$f:X\to Y$$ between finite sets $$X$$ and $$Y$$ is injective but not surjective, then $$|X|=|\{x:(x,y)\in f\}|=|\{y:(x,y)\in f\}|<|Y|$$.

In the first equality we've used the nature of a mapping, in the second, the fact that $$f$$ is injective and in the third, the fact that $$f$$ is not surjective, i.e. there exists $$y\in Y\setminus \{y:(x,y)\in f\}$$ such that adding it to the finite set will increase its size.

If we let $$Y=X$$, we obtain $$|X|<|X|$$, which is a contradiction.

We can demonstrate the reverse implication by contradiction as well.

If some mapping $$f:X\to Y$$ between finite sets $$X$$ and $$Y$$ is surjective but not injective, then $$|X|=|\{x:(x,y)\in f\}|>|\{y:(x,y)\in f\}|=|Y|$$

Again, in the first equality we've used the nature of a mapping, in the second, the fact that $$f$$ is not injective and in the third, that $$f$$ is surjective.

If we let $$Y=X$$, we obtain $$|X|>|X|$$, a contradiction.

For infinite sets the assertion does not hold, since $$f(x)=x+1$$ is injective but not surjective on $$\mathbb N$$.  