Bijective map between two finite sets is equivalent to the same cardinality

Question

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

Answer 1

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$.

Answer 2

Base Case $n=0$ so $X=\emptyset$. Can you prove that $Y=\emptyset$?

Inductive Step

Assume your statement is true for $n$ and let $|X|=n+1 > 0$. Then, pick any $x \in X$ and define $\bar{X} = X \backslash \{x\}$. Then, $f:\bar{X} \to Y$ is an injection. Can you transform range of $f$ to make it into a bijection and apply the inductive hypothesis?

Answer 3

Correct me if wrong.

Base case $n=1$. OK.

$f:X \rightarrow Y$ is a bijection.

Let $x \in X$.

${f(x)} =Y$ , since surjective $|Y|=1$.

Hypothesis :True for $n:$

$|X| =n$ , and $|Y|=m$ , and

assume a bijection $f:X \rightarrow Y$ , then $n=m$.

Step $n+1$:

Let $X_{n+1}$ have $n+1$ elements, and let $Y$ have $m$ elements

Need to show :

Assume a bijection $f:X_{n+1} \rightarrow Y$, then $n+1=m$.

$X_{n+1}= (X_{n+1}$ \ {$a$}$)\cup ${$a$}, where $a$ is an element $X_{n+1}$.

Let $X_n:= X_{n+1}$ \ {$a$}, and

consider $Y$ \ {$f(a)$}.

Then $f: X_{n} \rightarrow Y$ \ {$f(a)$} is a bijection.

By hypothesis $n = m$, where

$m=|Y$ \ {f$(a)$}$|$.

Then

$|X_{n+1}|=n+1$ ,and

$|Y|= |Y$ \ {$f(a)$}$|+|${$f(a)$}$|=n+1.$

Answer 4

$f$ is bijective, so it is injective and surjective.

Since $f$ is injective, $f(a)=f(b) \implies a=b.$ For a given value in the range, there is one and only one value in the domain. So the cardinality of the domain is less than or equal to the cardinality of the range. There could be points in the range not mapped from the domain.

Since $f$ is surjective, every element of the range has a pre image in the domain. The domain might have some elements not mapped to elements of the range. So the cardinality of the domain is greater than or equal to the cardinality of the range.

$n<=m$ and $n>=m \implies n=m$