troubles proving every subset of a finite set is finite with naive set theory In a first undergraduate course in analysis, they have established a model of the natural numbers (without zero), proof by induction, recursive definition, injectivity, surjectivity, bijectivity of maps and elementary properties and the following definitions and facts:


*

*for every $m \in \mathbb{N}$ the set $A_m := \{k \in \mathbb{N};\ 1 \leq k \leq m\}$,

*two sets $M$ and $N$ are equipotent if there is a bijection $f \colon M \to N$, written $M \sim N$, 

*a set $M$ is finite if it is empty or equipotent to $A_m$ for some $m \in \mathbb{N}$,

*$\forall m, n \in \mathbb{N}\colon A_m \sim A_n \Leftrightarrow m = n$,

*the cardinality of a finite nonempty set $M$ is $\#M = m$, where $M \sim A_m$, and

*every nonempty subset of the natural numbers has a minimal element.


Now they have to prove that a subset of a nonempty finite set is again finite.
I have to present a solution to them.
It's clear that one can restrict this problem to:
For $m \in \mathbb{N}$ if $T \subseteq A_m$, then there is a $n \in \mathbb{N},\ n \leq m: T \sim A_n$.
I tried to define $T_1 = T$ and for $k \in \mathbb{N}$ $T_{k+1} := T_k \setminus \{\min T_k\}$ if $T_k \neq \emptyset$ and $T_{k+1} := \emptyset$ if $T_k = \emptyset$. Now I want to prove that there is a $n \in \mathbb{N} \colon T_{n+1} = \emptyset$. This would make $A_n \to T, k \mapsto \min T_k$ a bijection.
How can I proceed? I thought maybe one can use induction on the cardinality of the $T_k$, but I don't see it immediately and I have little time. One can try to show that for any $k \in \mathbb{N}$ the set $T_k$ is finite and if $T_k \neq \emptyset$, then $\# T_{k+1} + 1 = \#T_k$, but then what?
 A: To show that there is an $n$ such that $T_{n+1} = \emptyset$, just note that $\min ( T_k ) \geq k$ (actually, $T_k \cap A_{k-1} = \emptyset$; an easy proof by induction), and so $T_{m+1}$ must be empty (if $T \subseteq A_m$).

I would personally proceed in a different fashion, and not bother so much in trying to exhibit a bijection.  Instead, by induction show that for each $m$ every nonempty $T \subseteq A_m$ is finite.  The base case $m = 1$ is trivial.  Suppose it is known for $m$, and let $T \subseteq A_{m+1}$ be nonempty.  There are three cases:


*

*If $T = A_{m+1}$, then we're done.

*If $m+1 \notin T$, then actually $T \subseteq A_m$, and we're done by hypothesis.

*If $T \neq A_{m+1}$ and $m+1 \in T$, we can swap $m+1 \in T$ out for something not in $T$ to get a subset $S \subseteq A_m$ equipotent with $T$.  (And so $T$ is equipotent with a finite set.)

A: Let $f : k \mapsto \min T_k$.
Use the fact that $b \notin A \setminus \{b\}$ and induction to prove that $\min T_i = \min T_j \implies \min T_j \in T_i \implies i = j$ (assuming $i \geq j$) and thus that $f$ is an injection.
Use the fact that $(A \setminus \{b\}) \cup \{b\} = A$ (assuming $b \in A$) to prove that $\bigcup \{\min T_i \} = T$ and thus  $f$ is a surjection.
