(Content warning: maths. This was written as an exercise in approaching the underlying ideas with rigour and understanding. If it's of any help to other people, this is a happy side effect.)
In discrete mathematics, the Well-Ordering Principle for natural numbers states that any non-empty set of natural
numbers contains a least element of itself
.
Slightly more formally: \[\forall S \subseteq \mathbb{N} : \; S = \emptyset \lor \exists x \in S (\forall y \in S (x \leq y))\]
Example: Let \(S = \{12,3,189,40,25\}\). Then the least element of \(S\) is \(3\).
Example: Let \(S = \{\}\). The Well-Ordering Principle doesn't apply because \(S\) is empty.
Example: Let \(S = \mathbb{N}\). Then the least element of \(S\) is \(0\).
Example: Let \(S = \{n \in \mathbb{N} \;|\; n\textrm{ odd}\} = \{1,3,5,\ldots\}\). Then the least element of \(S\) is \(1\).
The interesting thing here is that this applies to every subset of \(\mathbb{N}\), of which there are uncountably many. Some of them we can't compute membership for, e.g. the image of the busy beaver function. Most of them we can't even give a finite description for.
