Let $n,m\in\mathbb{N}$. Show that if there is a bijection between $\{1,..,n\}$ and $\{1,..,m\}$ then $n=m$. My try for the question:
Let $X,Y$ be subsets of $\mathbb{N}$. 
Let $f: X\rightarrow Y$ be a bijection function with $\operatorname{Card}(X)=n,\operatorname{Card}(Y)=m$ both in $\mathbb{N}$. I think that If we show Card$(X)$=Card$(Y)$ then we are done. So, how? Can you give a hint?
 A: Since $f^{-1}$ is injective, it suffices to prove that if there is an injection $f : X \to Y$ then $\mathrm{Card}(X) \le \mathrm{Card}(Y)$. This can be done by induction on $\mathrm{Card}(X)$, and is fairly tedious.
The base case is simple, since in this case $X=\varnothing$, whose cardinality is less than or equal to the cardinality of any other set.
For the induction step, fix $n \in \mathbb{N}$ and suppose that, whenever there exists an injection $f : X' \to Y'$ with $\mathrm{Card}(X') = n$, then $\mathrm{Card}(X') \le \mathrm{Card}(Y')$. Take a set $X$ of cardinality $n+1$ and suppose $f : X \to Y$ is an injection; you need to use the induction hypothesis to prove that $\mathrm{Card}(X) \le \mathrm{Card}(Y)$.
To do this, take an element $x_0 \in X$; note this exists since $\mathrm{Card}(X) > 0$. Prove that:


*

*$f$ restricts to a (well-defined!) injection $f' : X \setminus \{ x_0 \} \to Y \setminus \{ f(x_0) \}$.

*Deduce that $\mathrm{Card}(X \setminus \{ x_0 \}) \le \mathrm{Card}(Y \setminus \{ f(x_0) \})$. To do this, you will need to prove the more general fact that if $A$ is a set and $a \in A$ then $\mathrm{Card}(A \setminus \{ a \}) = \mathrm{Card}(A) - 1$.

*Deduce that $\mathrm{Card}(X) \le \mathrm{Card}(Y)$. 


This will complete the proof.
A: Note that If $f$ is injective then $Card(X) \leq Card(Y)$ as $f$ is one to one so there can be more in $Y$. Also note that $f$ is surjective, this implies that $x\in X$ maps to $y\in Y$ for all $y\in Y$. So, $Card(X) \geq Card(Y)$. Since $Card(X)=n$ and $Card(Y)=m$, we have
$$n\geq m \leq n$$
which implies
$$n=m$$ as desired.
A: We first consider a set $X$ such that there exists a bijective function $g:\{1,...,n\}\to X$.
If there exists a bijective function $f:\{1,...,m\}\to \{1,...,n\}$, then $g\circ f:{\{1,...,m\}\to X}$ is also bijective since the composition of bijection functions is a bijection (which can be easily proved by the fact that bijective functions have two side inverses.)
Finally, follows from the definition of cardinality, we can conclude that $|X|=n=m$
