Cardinal Arithmetic Property Proof

Question

The following proposition is "obvious" but I am having trouble obtaining a rigorous proof of it: If the set $X$ is finite and $Y$ is a subset of $X$, then $Y$ is finite and #$(Y)\leq$#$(X)$. It is easy to show that if #$(Y)\leq$#$(X)$ then $Y$ is finite, but with regards to proving that #$(Y)\leq$#$(X)$, I have tried a whole bunch of ways to show this given the hypotheses and have come to no satisfactory proof (e.g. I tried a proof by contradiction of assuming #$(Y)>$#$(X)$, but was not able to derive any obvious contradiction).

Answer 1

Assume that the claim is false. Without loss of generality, this implies that there is some $m,n\in\mathbb N$, $m<n$, such that there is an injection $f$ from $[n]\to[m]$ ($[n]$ is notation for $\{1,...,n\}$).

Also without loss of generality, we can assume that $n$ is the smallest natural for which this property holds.

If $n=1$, the claim is clearly false (you can write out the case yourself).

If $n>2$, let $x_0=1$, and let $x_{i+1}=f(x_i)$ for all naturals $i$.

I'll leave it to you to prove that if $X=\{x_i\}_{i\in\mathbb N}$, then $f_X$, the restriction of $f$ to $X$, is a bijection $f_X:X\to X$. Also, note that $X\subset[m]\subsetneq[n]$, so this implies that $f_{[n]\setminus X}$ is an injection from $[n]\setminus X$ to $[m]\setminus X$. This implies that the property holds for $n-|X|<n$, contradicting minimality of $n$.