# 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?

-
Remark: I'm a tutor, not a freshmen. : - ) I must say I find no reasonable level of rigour to prove this. – k.stm Nov 11 '12 at 11:12
+1 for clear question statement. – akkkk Nov 11 '12 at 12:04

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:

1. If $T = A_{m+1}$, then we're done.
2. If $m+1 \notin T$, then actually $T \subseteq A_m$, and we're done by hypothesis.
3. 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.)
-
Ah, thanks. Yes. That is much simpler, I've been blind. – k.stm Nov 11 '12 at 11:44

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.

-
Why is there a $m \in \mathbb{N}$ such that $T_{m+1} = \emptyset$? – k.stm Nov 11 '12 at 11:31