Let $f:[N]\to [N]$ be an injective self-map where $[N]:= \{1, 2, …, N\}$ is a finite set of $\mathbb{N}$. Show that $f$ is bijective.
My proof:
As $f$ is injective and finite we simply count all images of $N$ which are $N$-many. As $f([N]) \subseteq [N] $, we conclude $f([N]) = [N] $ as both sets have the same cardinality. So $f$ is surjective and therefore bijective. $q.e.d.$
Is this correct?
The approach of our professor is different and I don't understand one step he did:
He took the union of all preimages $\bigcup_{k=1}^N \{f^{-1}(k)\}$, which are also $N$-many and uses injectivity to argue that all $\{f^{-1}(k)\}$ are pairwise disjoint and therefore $\bigcup_{k=1}^N \{f^{-1}(k)\} = [N]$.
Why holds $\bigcup_{k=1}^N \{f^{-1}(k)\} = [N]$?
$\bigcup_{k=1}^N \{f^{-1}(k)\} \subseteq [N]$ is certainly true but I don't understand the other subset-property $\supseteq$ which finally shows that both sets are euqal?
Can someone explain this step to me?
Best Answer
I'm going to write $[n]$ for your $[N]$.
Your proof is good, just add after "as both sets have the same cardinality" the following "and $[n]$ is the only subset of $[n]$ with cardinality $[n]$".
It sounds dumb but for sets of higher cardinalites, it may be false, i.e. $f[X]\subseteq X$ with $\lvert f[X]\rvert=\lvert X\rvert$, but $f[X]\ne X$. For example, take $X=\mathbb N$ and the map $n\mapsto n+1$.
What your professor did is essentially the same. You used that injective implies that the image of any $k\in[n]$ is singleton, then unioning $[n]$-many singleton sets gives a set of cardinality $[n]$. Your professor used that injective implies that the preimage of any $k\in[n]$ is singleton, . . . and so on.
Here's an alternative proof that I wrote earlier.