I have just begun using Judson's 2018 Abstract Algebra: theory and applications. In the text, there is a Lemma with the following statement and proof:

The Principle of Mathematical Induction implies that 1 is the least positive natural number.

Proof. Let $S=\{n \in \mathbb{N} | n \ge 1\}$. Then $1 \in S$. Assume that $n \in S$. Since $0<1$, it must be the case that $n=n+0<n+1$. Therefore, $1 \le n < n+1$. Consequently, if $n \in S$, then $n+1$ must also be in $S$, and by the Principle of Mathematical Induction, and $S=\mathbb{N}$. QED.

I am having some issues with this proof.

  1. The last sentence doesn't seem coherent.
  2. S is defined as the set of natural numbers $\ge1$, but I don't understand how the proof shows that $S = \mathbb{N}$ to arrive at the conclusion that 1 is the least positive natural number.

Prior to this Lemma we are given the definition of natural numbers $\mathbb{N}=\{1,2,3,...\}$, and as propositions the First and Second Principle of Mathematical Induction, as well as the Principle of Well-Ordering.

Can anyone either help me understand why this proof is correct or otherwise help me fill in what may be missing?

  • 1
    $\begingroup$ The last sentence should be something like “... and by the Principle of Mathematical Induction, we have $S=\Bbb N$. Otherwise, the proof is completely fine. $\endgroup$ – Maximilian Janisch May 20 '19 at 19:51
  • $\begingroup$ Not sure why (1) is incoherent. In induction starting at $0$ (and hence when $0$ is considered a natural number) this same proof shows that for all natural $n,$ you either have $n=0$ or $n\geq 1.$ $\endgroup$ – Thomas Andrews May 20 '19 at 19:53
  • $\begingroup$ It is true that you don't actually need to property $n\in S$ to prove $n+1\in S$ in this case. A simpler lemma is (now assuming the natural numbers/induction start at $1$): For all $n,$ either $n=1$ or $n=m+1$ for some natural number $m.$ $\endgroup$ – Thomas Andrews May 20 '19 at 19:55

The proof showed that

  • $1\in S$ and
  • for every $n\in S$, we have $n+1\in S$.

By using Peano axiomatic (aka the principle of induction), the proof correctly concludes that $S=\Bbb N$. Thus every natural number is $\geq 1$. Hence, by definition, $1$ is a smallest number of $\Bbb N$ (it is in fact also the only smallest number of $\Bbb N$.)


You might think that since $\mathbb{N}$ is defined to be $\{1,2,\dots\}$ this proof is pointless. Although Judson doesn't make this clear, the point of this proof is that it gives us an alternative more formal way of describing the properties of $\mathbb{N}$ without using the informal ellipsis; if we take an appropriate version of induction as an axiom then we don't need to define $\mathbb{N}$ to be $\{1,2,\dots\}$.

Unfortunately, the form of induction stated by Judson does not give a correct proof of this theorem. Judson's version only proves that $n\ge1$ for all $n\ge1$. The version of induction that's needed for this theorem is something like the following:

Let $S(n$) be a statement about integers for $n \in \mathbb{N}$ and suppose $S(1)$ is true. If for all integers $k$ with $k \ge1$, $S(k)$ implies that $S(k + 1)$ is true, then $S(n)$ is true for all integers $n\in\mathbb{N}$.


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.