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

Question

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

Answer 1

The proof isn't circular --- it does however assume that $\mathbb{N}\subseteq\mathbb{N}$ has a least element, 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}$ has least element $1\in \mathbb{N}$. Now, consider $S\subseteq\mathbb{N}$, an arbitrary subset.

1. Assume $S$ doesn't have a least element. This must mean that $1\not\in S$ (otherwise $1$ would be the least 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}$.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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