# Induction, Well-Ordering, and my Failed Proof Attempt

I recognize there are posts already generally on the logical equivalence of induction and the well-ordering principle, however, I'd really appreciate some advice for finding the monster lurking underneath this marsh of poor reasoning. Thanks!

Complete induction $\implies$ well-ordering principle

Consider a statement $S$ where $S(n)$ states that a given subset of $\mathbb{N}$ with cardinality of $n$ has a least element.

Let, for a set $X \subseteq \mathbb{N}$, $|X| = 1$. By the reflexive axiom, $\forall a \in X, a \le a$ so $S(1)$ holds.

Now we assume $S(n)$ is true so $|X_{n}| = n$ and $\exists \ a\ \forall \ b\ : (a,b \in X) \implies a \le b$.

$S(n+1)$ would state that the well-ordering principle holds for a set $X_n \cup {z}$ where $z$ is a new element.

Since the well ordering principle held on $X$, there is a least element of $X$, call it $a$. Now $(z \le a)\vee (z > a)$. If the former is true than $z$ is now the least element. If the latter is true then $a$ is still the least element.

Why is this seemingly much more obvious "solution" wrong? I have a gut feeling this has something to do with considering arbitrary elements of the power-set of $\mathbb{N}$ - which is uncountably infinite - and forming a bijection from $\mathbb{N}$ to these subsets of $P(\mathbb{N})$.

• it looks good to me, why do you think it's wrong? (Actually I'd change the formulation, but the logic itself looks fine) – mdave16 Mar 20 '17 at 20:43
• when a young man such as myself sees that that status quo differs, is he not filled with self doubt? – Krpcannon Mar 20 '17 at 20:45
• Again, but less in prose? – mdave16 Mar 20 '17 at 20:46
• Did you not know that Weak Induction $\iff$ Strong Induction $\iff$ Axiom of Choice $\iff$ Zorn's Lemma $\iff$ Well Ordering Principle $\iff$ Tychonoff's theorem $\iff$ Krull's theorem $\iff$ every vector space has a basis $\iff$ Tukey's Lemma $\iff \dots$ – mdave16 Mar 20 '17 at 20:48
• Note that the only thing that you proved here is that each finite subset of $\mathbb{N}$ has a smallest element, not that each non empty subset of $\mathbb{N}$ has one. – Max Mar 20 '17 at 20:55

As Max noted in the comments, you only have proved that any finite nonempty subset of $\mathbb N$ has a minimal element.
Note that also every finite subset of $\mathbb R$ has a minimal element, and yet $\mathbb R$ is not well-ordered. Indeed, your prove works unchanged also for finite subsets of $\mathbb R$, since the only property of $\mathbb N$ as the set you're taking subsets of is the order (you are using additional properties of $\mathbb N$ as cardinality of the set, but that is independent from the set from which you're taking the subset).
• The question was why the OP's solution was wrong. You answered that, but your answer would have been much better by saying how to fix the proof. Namely that if $A\subseteq \mathbb N$ and $A$ is infinite, then you can choose any element $n\in A$, and $A\cap (n+1)$ is finite and its least element will be the least element of $A$. – martin.koeberl Mar 21 '17 at 0:02