0
$\begingroup$

Working on proving the well ordering principle, I ran into this way to do it and I was hoping someone might read through it and tell me if I have any holes. I've looked over it a few times but I want to be sure.

Theorem — Each non-empty subset $S$ of $\Bbb N$ contains a smallest element.

Proof — Suppose that $S$ has no smallest element and define $T = \Bbb N \setminus S$. Suppose $\{1, 2, 3, ..., n\} \subset T$ and $n \in \Bbb N$. Further, suppose $\{1, 2, 3, ... , n\} \subset T \Rightarrow n + 1 \in T$. Then $n + 1 \notin S$ because it would be a least element of S. Since $1 \in T$ and $n + 1 \in T, T = \Bbb N$ by the induction axiom.

Since $T = \Bbb N \setminus S = \Bbb N, S = \varnothing$, which contradicts that $S$ is non-empty. Thus, each non-empty subset $S$ of $\Bbb N$ contains a smallest element. $\Box$

The only thing I can think of that might ruin my argument is supposing that $\{1, 2, 3, ... , n\} \subset T \Rightarrow n + 1 \in T$. I'm essentially saying that because induction works, the proof works.

But then again, this really shouldn't be a problem since the proof rests on the assumption that $S$ has no smallest element and therefore should maintain that property regardless of any subset of $\Bbb N$, including a set as fussily defined as $T$. Right?

$\endgroup$
  • $\begingroup$ Do you mean $\{1,2,3,\ldots,n\}\subset T$? Or are you using the definition $n+1=n\cup \{n\}$? $\endgroup$ – ajotatxe Sep 3 '17 at 21:42
  • $\begingroup$ Whoops, yes, I'll fix that. $\endgroup$ – Austin Sep 3 '17 at 21:45
  • $\begingroup$ >I'm essentially saying that because induction works, the proof works. $$~\\~$$ IMO, this will be a circular proof because the proof for the principle of mathematical induction uses the fact that $\Bbb N$ is well-ordered. $\endgroup$ – Prasun Biswas Sep 3 '17 at 21:48
  • 2
    $\begingroup$ You are fine. Principle of Induction implies WOP and vice versa. You need one to prove the other. $\endgroup$ – TCiur Sep 3 '17 at 21:50
  • $\begingroup$ @Tciur See I thought about that too because to prove that induction works you have to assume the WOP. $\endgroup$ – Austin Sep 3 '17 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.