[Math] troubles proving every subset of a finite set is finite with naive set theory

elementary-set-theoryinduction

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?

Best Answer

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.)
Related Question