Let $S_N$ be the set of numbers $\{1, 2, 3, \dots, N\}$. Argue that if a map $f\colon S_N\to S_N$ is surjective, then $f$ is a bijection.
I know that bijection is surjective + injective then there will be a case or set where surjective will also be bijective right?
Any help appreciated.
On
Simpler answer:
There are $n$ numbers (pigeons) being mapped to $n$ values (holes). If two numbers (pigeons) are mapped to the same value (hole) then there won't be enough remaining numbers (pigeons) to map to the remaining (holes).
So if $f:X \to X$ and $|X| =|X|$ is finite. Then if $f$ is not injective than $f$ can not be surjective.
If $x_i$ and $x_j$ both map to the same value than then are $N-2$ remaining numbers to map, and there are $N-1$ remaining numbers to be mapped to. We simply won't have enough numbers to map to $N$ slots unless every number is mapped to a different slot.
===== long but thorough answer below====
Thing is $S_N$ is finite. So we are mapping from a finite set to itself. Now the following argument will only work for finite sets[1]:
Let's suppose $X$ and $Y$ are finite sets. Let $f:X\to Y$ be a function and let $Im(f) = $ the image of $f =$ all the mapped outputs for $f$, that is $\{f(x)| x\in X\}$.
Now $Im(f) \subseteq Y$ of course. And if $Im(f) \subsetneq$ then there are elements of $Y$ that are not mapped to so $f$ would not be surjective. And if $Im(f) = Y$ then $f$ is surjective because... every element of $Y$ is an element of $I(f)$ and so every element is being mapped to.
Also: Although $f:X \to Y$ might not be surjective. Then $f:X \to Im(f)$ must be surjective... by definition.
Now if we count the elements of $X = \{x_1, x_2, ....., x_k\}$ one by one and count $y_1 = f(x_1)$ and $y_2 = f(x_2)$ etc. we well find that we can't have more elements in $Im(f)$ then we have in $X$ because every element in $X$ is mapped to an element in $Im(f)$. So $X$ must be as big a set or bigger than $Im(f)$.
If $f$ is injective then each element of $X$ is mapped to a different element of $Im(f)$ and $X$ and $Im(f)$ are the same size.
But if $f$ is not injective then there is at least two $x_i, x_j$ so that $x_i$ and $x_j$ get mapped to the same value in $Im(f)$. So $X$ is bigger than $Im(f)$.
So.... recap:
If $f: X \to Y$ for finite $X, Y$.
1: $f$ is surjective if and only if $Im(f) = Y$.
2: $f$ is injective if and only if $|X| = |Im(f)|$.
3: $f$ is not injective if and only if $|X| > |Im(f)|$
4: $|X| < |Im(f)|$ NEVER happens.
......
So what if $X = Y$ and $f: X \to X$.
Then
1: $f$ is surjective if and only if $Im(f) = X$.
2: $f$ is injective if and only if $|Im(f)| = |X|$.
But if $f$ is surjective $\implies Im(f) = X \implies |Im(f)| = |X| \implies f$ is surjective.
And if $f$ is injective $\implies |Im(f)| = |X|$ but as $Im(f) \subseteq X$ then $|Im(f)| \le |X|$ with equality holding only if $X = Im(f)$ so $\implies f$ is surjective.
So for finite $X$ then $f:X \to X$ is injective if and only if $f$ is surjective.
Hmmm.... Also if $f: X \to Y$ and $|Y| > |X|$ then surjectivity is impossible. ANd if $|Y| < |X|$ injectivity is impossible.
But this is ONLY true for finite sets because:
[1] This is all based and the assumption that if $X$ is finite and $A \subsetneq X$ then $|A| < |X|$ or in other words; no proper subset of $X$ has the same cardinality as $X$.
But be careful
a) This statement is FALSE and absolutely not true for infinite sets. NOT AT ALL!!!!!! (Example the even number integers has the same cardinality as all integers) and
b) I have given this statement without proof as intuitively obvious. That was BAD of me. If I were you teacher I should be fired for this but ... seeing as no-one pays me... In actuality this is something you well have to prove. It's not hard to prove but it is obtuse and not trivial.
By definition of surjection we have that for all $y \in S_n, \exists x \in S_n$ s.t. $f(x)=y$. That is there is at least one element of $S_n$ that maps to every element of $S_n$ via $f$.
If we further assume $f$ is not injective, then there exists $f(a) = f(b)$ s.t. $a \neq b$. That is we have $a \in S_n$ and $b \in S_n$ such that $a \neq b$ and $f(a) = f(b) = y_1 \in S_n$. By finiteness of $S_n$ and the pigeonhole principle we then clearly see that $S_n$ is not surjective (as there must exist a $y_2$ not mapped to by $f$).
Comment: this seems to be the clearest way to think about this, i.e. break onto without 1-1. This is a great problem to visualize with sets and arrows, start with a few elements and see why the arrows lead you to believe this.