I understand that this should be done by induction, but I have very limited knowledge on proof by induction. Could someone explain it in a way which also makes clear exactly what each stage of induction means and achieves?
Prove that if a set is Peano finite, then it is Dedekind finite.
-
1A set is Peano finite if there is a bijection between the set and a natural number. It is Dedekind finite if it is not equivalent to a proper subset of itself (the same as is in the link). – 2012-11-17
2 Answers
Definition $[N] = \{1,2,3,\ldots,N\}$ for natural $N$ including $0$.
Definition A set $S$ is Peano finite if there exists some $N$ and a bijection $S \to [N]$.
Definition A set $S$ is Dedekind infinite if there is a bijection between $S$ and a proper subset of $S$.
Lemma $[N]$ is not Dedekind infinite. proof: Suppose there was a bijection between $[N]$ and a proper subset $S \subsetneq [N]$, by composing it with the right permutation we have a bijection which is the identity in the direction $S \to [N]$ and therefore its inverse is the identity but then $[N] = S$ contradicts that $S$ is a proper subset.
Theorem A set $S$ is Peano finite iff it is not Dedekind infinite.
$(\Rightarrow)$ Let $S$ be Peano finite (so it's in bijection with some $[N]$) and Dedekind infinite, then $[N]$ is Dedekind infinite contradicting the lemma.
$(\Leftarrow)$ Let non-empty $S$ not be Peano finite, then we will show it is Dedekind infinite. Since $S$ is non-empty pick $s \in S$ and note that if $S \setminus \{s\}$ was Peano finite $S$ would be. By induction then, we can pick $N$ elements out of $S$ and it remains Peano infinite for all $N$. Let $s_n$ be a sequence of distinct elements of $S$ (so that picking $\{s_1,s_2,\ldots,s_n\}$ out of $S$ leaves it still Peano infinite) then let $S' = \bigcup_{n \in \mathbb N} \{s_n\}$ - $S'$ is Dedekind infinite because it's bijective with the naturals - and let $S''$ such that we have the disjoint union $S = S' \cup S''$, now define extend the bijection ($S'$ to a proper subset of $S'$) to a bijection ($S' \cup S''$ to a proper subset of $S' \cup S''$).
@sperners lemma's much fuller answer appeared as I was typing this. But a shorter answer might usefully highlight the key point you need to answer the original question.
Try proving the contrapositive: if $X$ is Dedekind infinite, $X$ is Peano infinite.
Hint. If $X$ is Dedekind infinite, then there is an object $a \in X$ and a bijection $f$ between $X$ and $X - \{a\}$ (by definition!). So now consider the set $A = \{a,\ f(a),\ f(f(a)),\ f(f(f(a)) \ldots \}$. Then each member of $A$ is distinct (why?) so $A$ is Peano infinite, and since $A \subseteq X$, $X$ must be Peano infinite too.
-
0this iteration of the bijection is much more elegant than my proof. Very nice. – 2012-11-17