1
$\begingroup$

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?

  • 1
    A 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 2

2

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''$).

2

@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.

  • 0
    this iteration of the bijection is much more elegant than my proof. Very nice.2012-11-17