1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I think that almost all the $k\in S$ in your post should be $k\notin S$. $\endgroup$ – Asaf Karagila Nov 7 '17 at 21:39
  • $\begingroup$ @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. $\endgroup$ – Demetre Saghliani Nov 7 '17 at 21:41
  • 1
    $\begingroup$ I used $k$ since in some places it has $1$ or $n+1$ and so on. $\endgroup$ – Asaf Karagila Nov 7 '17 at 21:41
  • $\begingroup$ 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.) $\endgroup$ – Andreas Blass Nov 7 '17 at 21:52
  • $\begingroup$ If a set has only one element, how can any element be bigger? $\endgroup$ – fleablood Nov 7 '17 at 21:56
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rob Arthan Nov 7 '17 at 22:28
  • $\begingroup$ @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. $\endgroup$ – Mark Nov 7 '17 at 23:01
  • 1
    $\begingroup$ To have a minimal element is not the same as satisfying the well-ordering principle. Your answer is simply incorrect. $\endgroup$ – Andrés E. Caicedo Nov 8 '17 at 23:41
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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?" $\endgroup$ – Demetre Saghliani Nov 7 '17 at 22:04
  • $\begingroup$ 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. $\endgroup$ – fleablood Nov 7 '17 at 22:11

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.