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