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?

  • $\begingroup$ Remark: I'm a tutor, not a freshmen. : - ) I must say I find no reasonable level of rigour to prove this. $\endgroup$ – k.stm Nov 11 '12 at 11:12

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.)
  • $\begingroup$ Ah, thanks. Yes. That is much simpler, I've been blind. $\endgroup$ – 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.

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

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.