## Saturday, March 9, 2013

### The well ordering principle

The set of natural numbers $\mathbb{N}$ is well ordered which means that every subset of the natural numbers can be described by a monotone increasing enumeration. Consider for example the set of prime numbers:
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53)

We can convert any prime number back into a natural number $\mathbb{N}$. For example, 547 can be converted to 100. These enumerations are endofunctions $\mathbb{N} \to \mathbb{N}$ that are reversible but not surjective. With finite functions all reversible surjective operations are automorphisms. The square numbers are another enumeration of natural numbers:
(0 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225)

The set of all subsets of $\mathbb{N}$ under set union and set intersection forms a boolean algebra with $\mathbb{N} - S$ as the complement operation. The differences between elements of this enumeration form an integer sequence. Consider the sum of the totient function:
(0 1 2 4 6 10 12 18 22 28 32 42 46 58 64 72)

The additive differences of the sum of totients is the eulers totient function itself. In this sense, these monotone enumerations are related to integer sequences in general. We can generalize integer sequences by describing sequences of rational numbers $\mathbb{N} \to \mathbb{Q}$, however, an important difference is that the set of rational numbers $\mathbb{Q}$ is not well ordered.