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.

  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews Feb 15 '16 at 18:53
  • $\begingroup$ @ThomasAndrews But for this result we need AC, iirc. $\endgroup$ – martini Feb 15 '16 at 18:55
  • $\begingroup$ 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 $\endgroup$ – Thomas Andrews Feb 15 '16 at 18:58
  • $\begingroup$ @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. $\endgroup$ – gustavoreche Feb 15 '16 at 21:24
  • $\begingroup$ @Thomas: Yes, you need something slightly less than countable choice to prove this equivalence. $\endgroup$ – 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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.