Sunday, January 26, 2014

Notes on well-ordering

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