Prove that there can't exist a bijection $f: A\rightarrow I_{n}$, if $A\subset I_{n}, \ I_{n}=\{ 1,2,...,n \}$
For me this is a quite simple concept to understand, but my class book stated a longer explanation than I think was necessary, so I want to know if what I thought is valid. It follows:
Take a bijection $f: I_{n} \rightarrow I_{n}$, if we remove any element $x$ from the domain, such that $f(x)=y$, it would be impossible to still have a bijection by the pigeonhole principle, as we would have a $n$ elements set choosing $n-1$ elements from the domain. The same is applied if we remove $k<n$ elements, as $n$ elements set cannot choose $n-k$ elements without at least one element from $I_{n}$ be choosing at least twice an element from the domain, making $f$ not a well defined function.
Your proof looks fine and makes intuitive sense, but we can perhaps be more rigorous by only using principles from set theory. We can actually prove the following more general statement:
We proceed by induction on $n$. Here, we use "$\subset$" of course to denote proper inclusion and "$-$" to represent the set-theoretic difference.
Base Case
For $n = 1$, $I_n = \{ 1 \}$. Thus $A$ must be a singleton set: $A = \{ a_1 \}$. The only proper subset of a singleton set is $\emptyset$, and of course there is no bijection between $\emptyset$ and $\{ 1 \}$, which is non-empty.
Inductive Step
Suppose the statement is true for $n$; let $f: A \mapsto I_{n + 1}$ be a bijection, and $B \subset A$. The case where $B$ is empty is trivial, since there is no bijection between $\emptyset$ and $I_n$ - the same reasoning as applied for the base case. So, suppose there is some $a_k \in B \implies a_k \in A$. Also, since $B \subset A$, then there must exist some $a_m \in A - B$. Then $B - \{ a_k \} \subset A - \{ a_k \}$.
Now, we claim that there exists a bijection from $A - \{ a_k \}$ to $I_n$. To show this, take $a_{n + 1} = f^{-1} (n + 1)$. If $a_{n + 1} = a_k$, then the restriction $g = f |_{A - \{ a_k \}}: A - \{ a_k \} \mapsto I_{n + 1} - \{ n + 1 \} = I_n$ is the desired bijection. If $a_{n + 1} \neq a_k$, then define $g: A - \{ a_k \} \mapsto I_n$ as
$$g (a) = \begin{cases} f (a) & a \ne a_{n + 1} \\ f (a_k) & a = a_{n + 1} \end{cases}$$
This is a bijection, as can be checked. Now, applying the inductive hypothesis, since $g: A - \{ a_k \} \mapsto I_n$ is a bijection and $B - \{ a_k \} \subset A - \{ a_k \}$, then there is no bijection between $B - \{ a_k \}$ and $I_n$. Now, for the sake of contradiction, assume there is a bijection between $B$ and $I_{n + 1}$. By the same construction as above, there exists a bijection $g: B - \{ a_k \} \mapsto I_n$, which is a contradiction. So, there cannot exist a bijection between $B$ and $I_{n + 1}$, as desired.
Original Problem
To show the original statement, we simply note that there exists a bijection between $I_n$ and $I_n$: the identity function $i (x) = x$ is an example. Since $A \subset I_n$, then by what we just proved, there is no bijection between $A$ and $I_n$.