# Proving that an injective function is bijective

I am having a lot of trouble starting this proof. I would greatly appreciate any help I can get here. Thanks.

Let $n\in \mathbb{N}$. Prove that any injective function from $\{1,2,\ldots,n\}$ to $\{1,2,\ldots,n\}$ is bijective.

-
This is often taken to be the definition of a finite set. –  Baby Dragon Mar 27 '13 at 17:37
@BabyDragon: That defines a so-called Dedekind-finite set. This concept is equivalent to finiteness in the presence of the Axiom of Choice, but not otherwise. –  Henning Makholm Mar 27 '13 at 18:44
@HenningMakholm Thank you. That is interesting. –  Baby Dragon Mar 27 '13 at 18:45
@BabyDragon: There are several different ways of characterizing finiteness, and many of them are not equivalent without (some of) the axiom of choice –  Asaf Karagila Mar 27 '13 at 18:49
@AsafKaragila HenningMakholm This means that their are models of ZF such that their are sets that are Dedekind finite but fail to be finite in some other (obvious) way? –  Baby Dragon Mar 27 '13 at 18:56

define a new function

$$g: \operatorname{Im}{f} \rightarrow \{1, \cdots, n\}$$

by setting $g(y)$ as that $x$ such that $f(x)=y$ (well-defined because each $y$ is an image and $f$ is injective). note that $f\circ g$ is the identity on $\operatorname{Im}{f}$, hence g must be injective; likewise, $g\circ f$ is the identity on $\{1, \cdots, n\}$, hence g must be surjective. we have just proved that g is a bijection, i.e. a permutation of $1, \cdots, n$.

the concept of cardinality is just shorthand for 'there exists a bijection'...

-

Another hint: Prove it by induction. It’s clear for $n=1$. Otherwise if the statement holds for some $n$, take an injective map $σ \colon \{1, …, n+1\} → \{1, …, n+1\}$. Assume $σ(n+1) = n+1$ – why can you do this? What follows?

-

Hint: Let $f : [n] \to [n]$ be injective. What is the cardinality of the image of $f$?

-

Hint: If $f:[n]\rightarrow [n]$ is injective (where $[n]= \{1,2,\dots,n\}$), all that remains to be shown is that $f$ is surjective. So, suppose it's not. How does the size of the image compare to the size of the domain, and what does this say about injectivity?

-

What if $f$ would not be bijective? Then one number would not be in the image of $f$. How can that be?

-

Suppose $f : \{1,\ldots, n\}\to\{1,\ldots, n\}$ is injective. Then $a\neq b\implies f(a)\neq f(b)$, so $\left|\,\operatorname{Im}f\,\right| = \left|\{1,\ldots, n\}\right| = n$. As $\{1,\ldots,n\}$ is the codomain, what can we say?

Since $\{1,\ldots, n\}$ is the codomain and $\left|\{1,\ldots, n\}\right| = n$, everything in the codomain must be hit.

-
Is there a way to do this without referenece to cardinality? I ask this since here [in this section] I have not yet read/introduced the concept and the source I am using (Analysis I - Escher) has this proof before discussing cardinality. Thanks. –  Michael Dykes Mar 27 '13 at 16:33
I think if you try to avoid it, you'll just work with it in a roundabout way. You can just use the pidgeonhole principle to show that the claims made about cardinality are true. –  Stahl Mar 27 '13 at 18:18