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

  • $\begingroup$ it looks good to me, why do you think it's wrong? (Actually I'd change the formulation, but the logic itself looks fine) $\endgroup$ – mdave16 Mar 20 '17 at 20:43
  • $\begingroup$ when a young man such as myself sees that that status quo differs, is he not filled with self doubt? $\endgroup$ – Krpcannon Mar 20 '17 at 20:45
  • $\begingroup$ Again, but less in prose? $\endgroup$ – mdave16 Mar 20 '17 at 20:46
  • $\begingroup$ 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$ $\endgroup$ – mdave16 Mar 20 '17 at 20:48
  • 4
    $\begingroup$ 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. $\endgroup$ – 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).

  • $\begingroup$ But that's not a problem where induction or the well ordering principle play a role. $\endgroup$ – martin.koeberl Mar 20 '17 at 21:35
  • $\begingroup$ @martin.koeberl: I don't understand what you are trying to tell me. $\endgroup$ – celtschk Mar 20 '17 at 21:37
  • 1
    $\begingroup$ 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$. $\endgroup$ – martin.koeberl Mar 21 '17 at 0:02

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.