# Does the proof of the well-ordering principle not commit the circular reasoning fallacy?

It almost certainly doesn't, since it's an old and definitely a well-tested theorem, but I don't understand why.

Begging the question, or circular reasoning, as defined in my textbook (of sorts), is:

...the author of a proof uses in his argument the fact that he is supposed to prove.

The well-ordering principle, on the other hand, is defined as:

If S is a nonempty subset of N then there is m ∈ S such that m ≤ x for all x ∈ S. That is, S has a smallest or least element.

Then, as a proof for the well-ordering principle, they write:

We will use contraposition to prove the theorem. That is, by assuming that S has no smallest element we will prove that S = ∅. We will prove that n ∉ S for all n ∈ N. We do this by induction on n. Since S has no smallest element, we have 1 ∉ S. Assume that we have proved that 1, 2, · · · , n ∉ S. We will show that n + 1 ∉ S. If n + 1 ∈ S then n + 1 would be the smallest element of S since 1, 2, 3, · · · , n ∉ S, and this contradicts the assumption that S has no smallest element. Thus, we must have n + 1 ∉ S. Hence, by the principle of mathematical induction, n ∉ S for all n ∈ N. But this leads to S = ∅. This establishes a proof of the theorem

The well-ordering principle is trying to prove that every non-empty set has a smallest element, so why does its proof assume that n + 1, the only element in the set S, would be the smallest one?

I do get that n + 1 would be the smallest element if 1, 2, 3 . . . n do not belong to the set S (obviously), but does that assumption not make use of the well-ordering principle, which it's trying to prove?

(I'm a sophomore undergrad, so, if possible, relatively simple explanations would be appreciated.)

• I think that almost all the $k\in S$ in your post should be $k\notin S$. – Asaf Karagila Nov 7 '17 at 21:39
• @AsafKaragila Do you mean n? Also, yes, it should be. I copy-pasted from my e-textbook, but it seems it wasn't as perfect as I'd thought it would be. I'll fix it now. – Demetre Saghliani Nov 7 '17 at 21:41
• I used $k$ since in some places it has $1$ or $n+1$ and so on. – Asaf Karagila Nov 7 '17 at 21:41
• Two sentences before the one you put in boldface, it says "Assume that we have proved that $1,2,\cdots,n\notin S$." Given this assumption, if $n+1$ is in $S$, then $n+1$ is the smallest element of $S$, because all the smaller natural numbers $1,2,\cdots,n$ have been assumed to not be in $S$. (And $n+1$ would not necessarily be the only element in $S$. If it were the only element, then it would be the smallest even more obviously.) – Andreas Blass Nov 7 '17 at 21:52
• If a set has only one element, how can any element be bigger? – fleablood Nov 7 '17 at 21:56

## 6 Answers

The proof isn't circular --- it does assume that $\mathbb{N}\subseteq\mathbb{N}$ satisfies the well-ordering principle though, which may be your source of confusion. This assumption is fine though, as $\mathbb{N}$ vacuously has a least element (we define it that way!). I'll assume that $\mathbb{N} = \mathbb{Z}_{\geq 1}$. If you want $\mathbb{N}_0 = \mathbb{Z}_{\geq 0}$, the change should be minor.

An (informal) sketch of the proof is as follows.

We know that $\mathbb{N}$ satisfies the well-ordering principle, and has least element $1\in \mathbb{N}$. Now, consider $S\subseteq\mathbb{N}$, an arbitrary subset.

1. Assume $S$ doesn't satisfy the well-ordering princple. This must mean that $1\not\in S$ (otherwise $1$ would be the minimum element)
2. Now, via induction, we can show that if $n\not\in S$, then $n+1\not\in S$ (as otherwise $n+1$ would be the minimum element). So, we have that $1\not\in S$, then $2\not\in S$, etc.

3. Now, we've shown that every $n\geq 1$ has $n\not\in S$. So, $S = \emptyset$ is an empty subset of $\mathbb{N}$.

• Your observation that the proof does assume that $\Bbb{N} \subseteq \Bbb{N}$ satisfies the well-ordering principle is incorrect. The sketch quoted in the question and spelled out in more detail in your points 1, 2 and 3 provides a valid proof that any non-empty $S \subseteq \Bbb{N}$ has a minimum element that doesn't make any use of that assumption. – Rob Arthan Nov 7 '17 at 22:28
• @RobArthan The proof does require $\mathbb{N}$ to have a minimal element. I referred to this as "$\mathbb{N}\subseteq\mathbb{N}$ satisfying the well-ordering principle" as I suspected this was where OP was confused. $\mathbb{N}$ having a minimum element is equivalent to it satisfying the well-ordering principle, so I saw no harm in mentioning that. – Mark Nov 7 '17 at 23:01
• To have a minimal element is not the same as satisfying the well-ordering principle. Your answer is simply incorrect. – Andrés E. Caicedo Nov 8 '17 at 23:41

The proof you've provided has many typos. It should read:

We will use contraposition to prove the theorem. That is, by assuming that $S$ has no smallest element we will prove that $S = \emptyset$. We will prove that $n \not\in S$ for all $n\in\mathbb{N}$. We do this by induction on $n$. Since $S$ has no smallest element, we have $1 \not\in S$. Assume that we have proved that $1, 2,\ldots, n \not\in S$. We will show that $n + 1 \not\in S$. If $n + 1 \in S$ then $n + 1$ would be the smallest element of $S$ since $1, 2, 3, \ldots , n \not\in S$, and this contradicts the assumption that $S$ has no smallest element. Thus, we must have $n + 1 \not\in S$. Hence, by the principle of mathematical induction, $n \not\in S$ for all $n\in \mathbb{N}$. But this leads to $S=\emptyset$. This establishes a proof of the theorem.

Now, the bolded part is true because if $S$ is a set of natural numbers that doesn't contain $1,\ldots,n$ but does contain $n+1$, then $n+1$ would be the least element of $S$. This follows because $n+1$ is the smallest natural number that isn't $1,2,\ldots,n$.

The idea is as follows: Because $1$ is the smallest natural number, if $1\in S$, then $1$ has to be the smallest element. So $1\notin S$.

Now by induction, if $1,\ldots,n\notin S$, then it has to be the case that $n+1\notin S$ as well, since $n+1$ is the smallest number which is larger than all $1,\ldots,n$. So if $n+1\in S$, then by the assumption that $1,\ldots,n\notin S$, it has to be that $n+1$ is the smallest element of $S$, which is again a contradiction to the assumption on $S$.

By the induction principle, it follows that for every $n\in\Bbb N$, $n\notin S$. But that means that $S=\varnothing$.

In other words, there is no begging of the question here. We simply prove by induction, if $1,\ldots,n\notin S$, then $n+1\notin S$ either.

Either the way you have copied the proof is wrong, or your book is wrong, since almost all of you $\in$ should be replaced with $\notin$.

The argument assumes that $S$ has no smallest element. The aim, then is to show that $S$ must be empty, by showing that no natural number is in $S$. If $1$ is in $S$, then this contradicts the fact that $S$ has no smallest element, since $1$, being the smallest natural number would have to be the smallest element in $S$. Thus, $1\notin S$. Now, proceed by induction, assuming that for some fixed $n\geq 1$, $1,\ldots, n\notin S$. Then, if $n+1$ were in $S$, it would have to be the smallest element in $S$, since none of the ones that could be smaller, namely, $1,\ldots, n$ are in $S$. But then $S$ would have a smallest element, $n+1$, which would contradict the assumption that $S$ has no smallest element. Therefore, $n+1$ cannot be in $S$. Hence, by induction, no natural number is in $S$, so $S$ must be empty.

It looks to me like you have miscopied the proof or that there was a misprint in the proof itself. Obviously, it makes no sense to say that "Assume that we have proved 1, 2, ..., n $\in$ S" and then say "if n+1 $\in$ S the n+ 1 is the smallest number in S! I suspect rather that they meant to say "Assume that we have proved 1 2, ..., n $\notin$ S". If n+ 1$\in$ S while all numbers n and less are not in S, then certainly n+ 1 is the smallest number in S.

• They did. The copy-paste didn't quite carry it all over. I've fixed it, now. – Demetre Saghliani Nov 7 '17 at 21:51

Given a set $X$, $x$ is the least element of $X$ if i) $x\in X$ and ii) for all $y\in X; x\le y$.

Claim: if $S=\{n+1\}$ then $n+1$ is the least element of $S$.

Proof.

i) $n+1\in S$. That is true.

ii) for all $y\in S$ then $y=n+1$. And $y=n+1\le n+1$.

End of Proof.

One element is one element, and the author was taking the above as self evident

• Have you read the final edit (N. 6) of the post? "I do get that n + 1 would be the smallest element if 1, 2, 3 . . . n do not belong to the set S (obviously), but does that assumption not make use of the well-ordering principle, which it's trying to prove?" – Demetre Saghliani Nov 7 '17 at 22:04
• No, he is not assuming S has a lowest element. He has demonstrated that S has no elements that are smaller than n+1, then n+1 is smaller than all others. That's definition and he has now proven that n+1 is the least. – fleablood Nov 7 '17 at 22:11