◀ ▲ ▶Branches / Set-theory / Proof

Proof

(related to Proposition: More Characterizations of Finite Sets)

By hypothesis, $X,Y$ are finite sets equal cardinalities $|X|=|Y| < \infty.$

Ad $(1)$

• Let $f:X\to Y$ be surjective.
• Assume $f$ wasn't injective. Then there would exist some $v_1,v_2\in X$ with $x_1\neq x_1$ but $f(x_1)=f(x_2).$
• Since, in this case, at least $2$ elements $x_1,x_2$ of $X$ were mapped to a single element $f(x_1)=f(x_2)$ and because $X,Y$ are finite, this would mean that there is an $y\in Y$ such that no $x\in X$ are left with $f(x)=y$. But this would contradict the surjectivity of $f$.
• Therefore, $f$ is injective.

$(2)$

• Let $f:X\to Y$ be injective.
• This means that $f(x_1)\neq f(x_2)$ if $x_1\neq x_2.$
• It follows that $f$ maps different elements of $X$ on different elements of $Y.$
• Since $X$ has the same number of elements as $Y$, every element of $x\in X$ will be mapped to a distinct value $y\in Y.$
• It follows that $f$ is surjective. Now, $X,Y$ are finite sets with unequal cardinalities.

$(3)$ By Induction

• By hypothesis, the cardinalities $|Y|=n$ and $|X|=m$ and $n < m.$
• For the sake of transparency in the notation, we write $Y_n$ for $Y$ with $|Y|=n$ and $X_m$ for $X$ with $|X|=m.$
• We will prove this lemma by induction of $m.$
• Base case: $m=1$.
  • Assume for the sake of contradiction that there is an injective function $f:X_1\to Y_n$ and $n > 1.$
  • This assumption means that there are some $a,b\in X_1$ with $a\neq b$ and $f(a)=f(b).$
  • But this is impossible, since $X_1$ has only one element.
  • Therefore, there is no injective function, and the lemma is true.
• Induction step: $m\to m+1$
  • Assume, there is no injective function $f:X_m\to Y_n$ for some $m < n.$
  • By contraposition, this is equivalent to saying that if $n > m$ for some $m\in\mathbb N$ then there is an injective function $f:X_m\to Y_n.$
  • Holding $n$ fixed and using this injective function $f$, we will now construct another injective function $f':X_{m+1}\to Y_n.$ as follows: * Without loss of generality, let $X_m=\{x_1,\ldots,x_m\}$ and $X_{m+1}:=X_m\cup \{x_{m+1}\}.$ * Since $n > m,$ and $f$ is injective, there is an element $y\in Y_n$ with $y\neq f(x_k)$ for all $k=1,\ldots,m.$ * Define the function $f':X_{m+1}\to Y_n$ by $$f'(x_k):=\begin{cases}f(x_k)\in Y_n&\text{if }k\le m\\y&\text{if }k=m+1.\end{cases}$$ * By construction $f'$ is injective.

$(4)$

• Another proof:
  • From $(3)$ it follows that if $f:X\to Y$ is injective than $|X|\le |Y|$.
  • Vice versa, if $g:Y\to X$ is injective than $|Y| \le |X|$
  • By the Schroeder-Bernstein Theorem, it follows $|X|=|Y|.$
  • By the definition of equipotent sets, this is the case if an only if $f$ and $g$ are bijective.
    ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Knauer Ulrich: "Diskrete Strukturen - kurz gefasst", Spektrum Akademischer Verlag, 2001