Could someone please verify whether my proof is okay?

Every nonempty subset of $\mathbb{N}$ has a smallest element.

Let $S$ be a nonempty subset of $\mathbb{N}$.

Base case: If $1 \in S$, then the proof is done, since $1$ is the smallest natural number.

Inductive hypothesis: If $S$ contains an integer $k$ such that $1 \leq k \leq n$, then it must be that $S$ contains a smallest element.

Inductive step: It remains to be shown that if $S$ contains an integer $k \leq n + 1$, then $S$ has a smallest element.

If there is no such $k \leq n + 1$, then $n + 1$ is the smallest element. If there is such a $k$, since $S$ is nonempty, $S$ must contain an element $k - 1$ that is less than or equal to $n$. That element would then be less than or equal to $n + 1$. By induction, $S$ has a smallest element.

I am not sure whether assuming the element is $k-1$ is correct. The last paragraph is hard for me to understand if I don't assume this...


The last paragraph should be:

Suppose $S$ contains an element $1 \leq k \leq n+1$. If $S$ does not contain an element $1 \leq l \leq n$ then that element $k$ is $n+1$ and it is the smallest element of $S$ because $S$ contains it and nothing less than it.

If $S$ does contain an element $1 \leq l \leq n$ then it meets the criteria of the inductive hypothesis and therefore has a smallest element.

Either way, any set $S$ with an element $1 \leq k \leq n+1$ has a smallest element. This concludes the induction step.

  • $\begingroup$ Thank you for taking the time to help me understand the last paragraph in a simple way. :) $\endgroup$ – numericalorange Apr 26 '18 at 23:56
  • 1
    $\begingroup$ This description makes the use of the Law of the Excluded Middle a bit clearer. That every non-empty set of natural numbers has a least element is actually equivalent to the Law of the Excluded Middle (within an otherwise constructive context). $\endgroup$ – Derek Elkins Apr 27 '18 at 0:25

Let $S$ be a set of positive integers which contains an element $k\le n+1$

If the only element of $S$ is $k=n+1$, then $n+1$ is the smallest element.

Otherwise $k<n+1$ which implies $k\le n$ , thus by induction hypotheses $S$ has a minimum element.

  • $\begingroup$ And if $k=n+1$ but $S$ is not a singleton set? $\endgroup$ – Derek Elkins Apr 26 '18 at 23:53
  • $\begingroup$ If other elements are larger than k, then k is still a minimum. and if they are smaller than k, one of them is less than or equal n. $\endgroup$ – Mohammad Riazi-Kermani Apr 26 '18 at 23:57

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.