Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
what is the def. of peano finite? I assume dedekind finite is what's said here en.wikipedia.org/wiki/Dedekind-infinite_set –  sperners lemma Nov 17 '12 at 15:03
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). –  David Hall Nov 17 '12 at 15:14

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

share|improve this answer

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

share|improve this answer
    
this iteration of the bijection is much more elegant than my proof. Very nice. –  sperners lemma Nov 17 '12 at 15:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.