0
$\begingroup$

Could someone please walk me through line by line what is going on in this proof.

The proof for a finite set having a finite subset has been shown to me as follows

Proposition: If $S$ is a nonempty finite set and $A \subseteq S$ then $A$ is also finite.

Proof: If $A = \emptyset$ there is nothing to prove (since the $A$ would be finite).

Since $S$ is finite there exists a bijection $f: S \to [n] $ for some $n \in \mathbb{N}$ consider the restriction of $f$ to $A$, $f|_A : A \to [n] $. This is injective since $f$ is injective. Let $S =\{k\in[n] : f(a) = k \text{ for some }a \in A\}$. Write $S$ in increasing order $s_1 , s_2 , s_3 , s_4 , \dots , s_m $. Let $a_1 ,\dots,a_m $ be elements of $A$ where $f(a_1) = s_1$ , $ f(a_2) = s_2$, $\dots$ , $f(a_m) = s_m$. Since $f$ is 1-1 these elements are unique and since $f$ is surjective, $A = \{ a_1 ,a_2 ,\dots,a_m\}$. Define $g:A\to [m]$ by $g(a_k) = k$ from above we see that $g$ is a bijection, so $A$ is finite.

$\endgroup$
  • 1
    $\begingroup$ What exactly don't you understand? What's the first bit that trips you up? $\endgroup$ – Noah Schweber Mar 18 '17 at 21:43
  • $\begingroup$ @NoahSchweber I understand that the bijection exists from $S \to \mathbb{N}$ I think Im getting tripped up when S is redefined and it appears to me that we are using the same mapping from $S \to \mathbb{N}$ as from $A \to \mathbb{N}$. I guess Im lost from how we show that $A$ is finite by using the same subscripts that we had in the S sequence in the A sequence. Thank you for your help. $\endgroup$ – user372382 Mar 18 '17 at 21:52
  • $\begingroup$ Also this: math.stackexchange.com/questions/239566/… $\endgroup$ – Asaf Karagila Mar 19 '17 at 4:13
1
$\begingroup$

The proof is indeed confusing.

I assume your definition of finite set is “having a bijection with $[n]$, for some natural number $n$”, where $[n]=\{1,2,\dots,n\}$ (and $[0]=\emptyset$).

We'll do induction over $n$. The case $n=1$ is obvious, as $S=\{f^{-1}(1)\}$ and its subsets are $\emptyset$ and $S$.

Assume $n>1$ and that the statement is true for sets in bijection with $n-1$.

Suppose $f\colon S\to[n]$ is a bijection and that $A\subseteq S$. Set $s_n=f^{-1}(n)$ and $S'=S\setminus\{s_n\}$.

If $A=\emptyset$, there is nothing to prove. If $s_n\notin A$, then $A$ is a subset of $S'$ and the map $f$ induces a bijection $f'\colon S'\to[n-1]$. By the induction hypothesis, we are done.

Suppose $s_n\in A$. Then $A'=A\setminus\{s_n\}$ is a subset of $S'$. If $A'=\emptyset$, we have $A=\{s_n\}$ and we can find a bijection $h\colon A\to[1]$. Suppose $A'\ne\emptyset$. Again, $f$ induces a bijection $f'\colon S'\to[n-1]$ so, by the induction hypothesis, there exists $m$ and a bijection $g\colon A'\to[m]$. Then, defining $h\colon A\to[m+1]$ by $$ h(a)=\begin{cases} g(a) & \text{if $a\ne s_n$}\\[4px] m+1 & \text{if $a=s_n$} \end{cases} $$ we obtain a bijection.

$\endgroup$
  • $\begingroup$ Thank you for your answer, So in essence what the proof is saying lets assume that for any $[n] \in \bbmath{N}$ there exists an element back in S which we will map to. S' is the set of us removing these elements which we map back to through the inverse one at a time from S. From there we create two scenarios where either A is the subset of S' or A' is the subset of S'. By removing those elements from S we don't want because they aren't in A. And since in these two scenarios we can make a bijection either back to the original set or [m] the set is countable. $\endgroup$ – user372382 Mar 18 '17 at 22:53
  • $\begingroup$ @user372382 Yes, the idea is to reduce to a set $S'$ having one element less than $S$, so the induction hypothesis can be applied. The proof you have goes to some length into avoiding induction (but uses it implicitly). They basically “order” $A$ using as indices afforded by $f$, but do so in a disputable way: at some point. $\endgroup$ – egreg Mar 18 '17 at 23:03
  • $\begingroup$ I think thats where I got confused originally where the indices are changing between steps but with induction it seems much simpler as the induction moves through the set in a sequential order. Its very interesting so by removing one element we arrive at two cases where either this element we choose to remove is in A or not in A but in any case they are finite. Its interesting how such a simple concept of taking finitely many things from a finite collection has such a complicated argument. Thank you for your help you have really cleared things up for me a lot. $\endgroup$ – user372382 Mar 18 '17 at 23:09

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.