# If $X$ is a finite set and $Y \subset X$. Prove that $Y$ is finite.

I am having trouble solving a question of section 3.6 (cardinality of sets) from Tao's Analysis I book. I have to prove the following statement:

My attempt (the boldline's refers to the points where I need help):

Since $X$ is a finite set, let $\#X=n$ and let $N_n:=\{i \in N:\forall 1\leq i \leq n\}$. Since $\#X=n$, $\exists$ a bijection $f:X \mapsto N_n$. Now, let $G:=\{f(x):x \in Y\}$. Since $G \subset N_n$ $\exists g_1 \in G$ s.t $g_1=min(G)$ ( I am not bothering with proving this). Now, consider $G_2:=G-\{g_1\}$, if $G_2\ne \emptyset$, there exists $g_2 \in G_2$ s.t $g_2=min(G_2)$.

And now I need help: Going on like this I will get to a point where $G_m=\emptyset$. I don't know how to technically write this argument, can someone help me?

Carrying on...

Now, let the set $G':=\{g_i: \forall 1\leq i \leq n'\}$. Note that $n'=m-1$. So (maybe I have to write some other steps here, please help), $\exists$ a bijection $g:Y \mapsto N_n'$, then Y is finite and $\#Y=n'$.

And now, I have to proof that $n' \leq n$.

Did I already prove this? If don't, I can prove this by contradiction, right?

So, that's it. I appreciate any help.

• This is more fun if you know the result: A set is finite $F$ if and only if any one-to-one function $F\to F$ is also onto. – Thomas Andrews Feb 15 '16 at 18:53
• @ThomasAndrews But for this result we need AC, iirc. – martini Feb 15 '16 at 18:55
• Not sure if it requires AC, but Dedekind used the result as the definition of infinite, so if you used that definition, you wouldn't need AC. :) @martini – Thomas Andrews Feb 15 '16 at 18:58
• @sigmabe, I dont know how many elements has G, because G is a subset of a finite set. So, if I use the fact that G is finite (thus it has n elements), I will run into a circularity. – gustavoreche Feb 15 '16 at 21:24
• @Thomas: Yes, you need something slightly less than countable choice to prove this equivalence. – Asaf Karagila Feb 15 '16 at 23:19

What is a function? In set theory it is a set $f$ of ordered pairs such that if $(x,y)$ and $(x,y')$ belong to $f$ then $y=y'.$

Now $f:N_n\to X$ is a bijection iff $f^{-1}:X\to N_n$ is a bijection. So for $Y\subset X,$ the set $\{(y,f^{-1}(y):y\in Y\}$ is a bijection from $Y$ to$M=\{f^{-1}(y):y\in Y\}.$

So, for $Y\ne \phi,$(because $Y=\phi$ is a trivial case), if you can show there is a bijection $g:M\to N_m$ for some natural number $m$ then the composite function $f g^{-1}$ is a bijection from $N_m to Y.$

So you have only the problem of showing that any subset of $N_n$ is finite. For this,you can employ induction on $n.$

The case $n=1$ is obviously true.

Suppose $n>1$ and it is true for $n-1.$ Now for $Y\subset N_n,$ let $Y'=Y\backslash \{n\}.$ Then $Y'\subset N_{n-1}$ so there is a bijection $f':Y'\to N_m$ for some $m.$

If $n\not \in Y$ then $Y'=Y$ and you are done, because f' is then a bijection from $Y$ to $N_m.$

Or if $n\in Y,$ then $f=f'\cup \{(n,m+1)\}$ is a bijection from $Y$ to $N_{m+1}.$

I recommend checking out Enderton's Elements of Set Theory (page 133) and/or Halmos' Naive Set Theory (page 53)