Let $X$ and $Y$ be two finite sets with cardinalities $|X| = n, |Y | = m$ respectively, where$ n,m \in \mathbb{N}$. Further assume $f : X \to Y$ to be bijective. Show that $n = m$.
Hint: Induction for $n$ (or $m$).
So this is basically what I have to prove. I started but I didn't get far and I have no idea how to proceed or even how to perform an usefull induction for this problem. Can somebody help me please?
So this is what I have:
Since f is bijective,
$|Range (f)| = |Y|$ and $\left|f^{−1}\left(\{y\}\right)\right|= 1, \forall y \in Y$
Thank you Guys
Best Answer
Okay, So $|X| = n$ means the $X$ can be expressed as $X=\{x_1, ...., x_n\}$ and $|Y|=m$ means that $Y$ can be expressed as $Y= \{y_1,...,y_m\}$.
And $f:X\to Y$ is a bijection means that for every $y\in Y$ there is an $x \in X$ so that $f(x) = y$ and furthermore that $x$ is unique. (So $f(x) = f(w)=y \iff x=w$ and $f(x)=y$.)
If $n=0$ then $X$ is the empty set. For every $y\in Y$ there is an $x \in X$ so that $f(x) = y$ but that can't be true as there are no $x \in X$ so there can't be any $y \in Y$. So $Y$ is the empty set and $m =0$.
If that's vague we can do $n=1$ and $X=\{x_1\}$. There is an $y=f(x_1)$. Let's call that $y_1$ so $|Y| = m \ge 1$. And if there is a second $w\ne y$ then there is an $x \ne x_1\in X$. But there isn't. So $Y = \{y_1\} = \{f(y_1)\}$ and $|Y| = m = 1$.
Suppose $|X| = n$ and there being a bijection to $Y$ means $|Y| = n$.
Then suppose $|X| = n+1$ and $X= \{x_1, .....,x_{n+1}\}$ the $f:X\to Y$ is a bijection. Define $\overline X = \{x_1,...., x_n\}$ and let $\overline Y = \{f(x_1),..... f(x_n)\}$. Let $\overline f: \overline X \to \overline Y$ be defined as $\overline f(x)= f(x)$.
$f$ is bijection. (For every $y=f(x_i)\in \overline Y$ then $x_i\in \overline X$ and is distinct.) So $|\overline Y| = n$.
Now let consider the set $Y' = Y\setminus \overline Y = \{y\in Y|y \not \in \overline Y\}$. Now maybe $Y'$ has one element. Maybe $Y'$ is empty. Maybe $Y'$ has a thousand elements.
Well $f(x_{n+1}) \in Y'$ so $Y'$ is not empty. And if $y \in Y'$ then there is an $x \in X$ so that $f(x) = y$ but $x\not \in \overline X$ because if $x \in \overline X$ then $f(x) \in \overline Y$. But the only $x\in X$ but not in $\overline X$ is $x_{n+1}$. So $y = f(x_{n+1})$ and $Y' = \{f(x_{n+1})\}$ and $Y = \{f(x_1), f(x_2)...., f(x_{n+1})$ and $|Y| = n+1$.