3
$\begingroup$

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

$\endgroup$
7
  • $\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
    Commented Mar 20, 2017 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
    Commented Mar 20, 2017 at 20:45
  • $\begingroup$ Again, but less in prose? $\endgroup$
    – mdave16
    Commented Mar 20, 2017 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
    Commented Mar 20, 2017 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$
    – Maxime Ramzi
    Commented Mar 20, 2017 at 20:55

1 Answer 1

Reset to default
2
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .