# Do all non-empty sets of natural numbers contain a smallest number?

I'm currently self-studying a book in real analysis and in it the authors wrote that all non-empty sets of natural numbers contain a smallest number. While that statement initially seemed intuitive i quickly thought of an example that this does not necessarally apply for. Consider a set of natural numbers, whose elements are so large that there exists no notation for describing their size as of now, there ought to be such numbers no? How can we be so sure that such a set has a smallest number? Is my example perhaps too vague to be considered a set? If that is the case, then why?

• We have notation for describing any natural number. We can do it all with the symbols '0,1,2,3,4,5,7,8,9'! Nov 4 '16 at 12:47
• Nov 4 '16 at 12:50

This is referred to as the Well-Ordering Principle. You might think of it this way. Given a set $A\subset\mathbb{N}$, ask yourself the following:

Is $1\in A$? If so, then $1$ is the smallest element in $A$.

Otherwise, is $2\in A$? If so, ...

If you continue in this way and find that $n\notin A$ for any $n\in\mathbb{N}$, it must be that $A$ has no elements at all. Thus, every $A\not=\emptyset$ should have a smallest element.

Intuitive explanation ...

If the principle does not hold, this means that :

(*) there exists a non-empty sets of natural numbers $A$ without a smallest element.

This in turn implies that, for every $n \in A$ ($A$ is not empty: thus we have it) we may find in $A$ a smaller number, i.e. a number, call it $m_0$, such that :

$m_0 < n$.

But now we may repeat the argument above, finding an $m_1 < m_0 < n$, and so on.

If the above principle holds, we can go on ad infinitum producing an infinite "descending sequence" of natural numbers belonging to $A$ :

$\ldots < m_2 < m_1 < m_0 < n$.

But $n$ is a natural number and - however large it is - from $0$ to $n$ we have only a finite "number" of numbers : contradiction !

Thus, the above principle (*) is false, and thus - by contradiction - we have proved its negation :

every non-empty sets of natural numbers has a smallest element.

See Proof by infinite descent, a method of proof by contradiction used in Euclid's Elements and much later developed by Fermat : based on Mathematical induction or equivalently on the Least integer principle.

The problem with your example is that there is no number for which "there exists no notation for describing their size as of now". The decimal representation of that number is such a notation.

Note 1: If a set is finite it has a minimum.

Note 2: If a set $A$ is non-empty, then it has some element $n \in A$. Then, since all numbers are positive integers, the subset $$B:= \{ m| m \in A, m \leq n \}$$ is finite.

I think it's worth writing a proof that tries to minimize appeals to intuition since personally I doubt anyone has very good intuition when it comes to large numbers. Already at numbers the size of Graham's number our intuition tends to fail us (just try and decide how much bigger $G_{64}$ is than $G_{63}$. Also the appeal to the fact that there are no infinite descending sequences is quite confusing when you consider you can have models of Peano arithmetic of order type $\omega+(\omega^\star+\omega)\times \mathbb{Q}$. Obviously the model doesn't know about the broken sets but this is far from intuitive.

All we really need for a reasonably rigorous proof of the fact that all subsets of the natural numbers have a least element is the induction axiom.

Consider a set $K\subset\mathbb{N}$ such that $K$ has no least element and $K\neq\emptyset$. Thus $\exists\; m\in K$. Now let us define $\phi(n)$ to be true if $\forall\; (i\leq n)$ $i\notin K$. Since $0$ is the least element of $\mathbb{N}$, $\phi(0)$ must hold, otherwise $0$ is the least element of $K$. Now suppose $\phi(n)$ holds for $n$. If $n+1\in K$ then $n+1$ is the least element of $K$ ($\phi(n)$ holds) so $n+1\not\in K$. Thus by induction $\{n|\phi(n)\}=\mathbb{N}$ and $\phi(m)$ holds giving us a contradiction since $m\in K$ and thus $\exists\; (i\leq m) (i\in K)$ namely $m$.

It doesn't matter whether or not you can write the numbers down, there'll always be a smallest element. This is the principle of well ordering.

The base-10 system is sufficient to denote any natural number, given a sufficiently large amount of space in which to do it. So the set you've specified is simply nonempty.

You could specify, for example, the set of all natural numbers $n$ so that $n$ has no notation expressible in base 10 using fewer than (say) $10^{100}$ symbols. Since there are finitely many symbols, there are only finitely many numbers that can be expressed in only that many symbols; therefore this set is nonempty. On the other hand, it does have a least element; that least element is $10^{10^{100} + 1}$.

Another common variation is a paradox: consider the set of natural numbers not describable in English using fewer than ten thousand symbols. This is nonempty for the same reason: there's only finitely many English symbols, so only finitely many combinations of ten thousand of them. On the other hand, its least element $N$ could be described as "the least number not describable in English using fewer than ten thousand symbols", which is a description that takes a whole lot less than ten thousand symbols. This isn't a contradiction, though - the secret is that my condition "describable in English" wasn't well-formed. In order to completely specify what I mean, I would have to completely describe English and unambiguously explain the meaning of English words, which is not possible to do in English.