Diagonal arguments

Various arguments prove extremely strong results by phrasing the result in such a way that some two-parameter thing can be used to supply a diagonal, the special case where the two-parameter thing has both parameters equal, analysis of which suffices to prove some property of the two-parameter thing which suffices to imply the desired strong result. The great grand-daddy of diagonal arguments is Cantor's, which proved that some infinities are bigger than others.

Cantor's Diagonal Argument

The classic form of the argument goes as follows: given a mapping (N| f :{mapping (N|:{0,1})}) there is a mapping g defined by; g(i) = not(f(i,i)) where ({0,1}: not :{0,1}) swaps 0 <-> 1; clearly, g isn't f(i) for any i in N, since, by construction, it is distinguishable from each.

Cantor originally applied the argument to show that there are more real numbers between 0 and 1 than there are natural (counting) numbers, 0, 1, 2, 3, ..., so he was using N = {naturals}; where the above has a mapping (N|p:{0,1}), e.g. p = f(i) for some i in N, one may read p as (the binary representation of) the number sum(N: i-> p(i)/power(1+i,2) :) to restore the above argument into Cantor's terms. [Strictly, at this point, you need to watch out for the .0111111... = .1000000... complication; if f(i) has several possible representations, you must make clear which is to be used to decide the value of f(i,i), with which g has to disagree.] The issue, for Cantor's contemporaries, was that this implied some infinities were bigger than others, which wasn't an idea with which they all felt comfortable. That set a revolution in motion which came to its resolution, via the heroics of Russel, Whitehead and their peers, in the work of Kurt Gödel. Listen closely, and you may be able to hear the first pre-echoes of Gödel's fork somewhere in the background of the saga's first breakthrough.

Another way of reading a function (N| p :{0,1}) is as (|p:{1}) = {i in N: p(i) = 1}, given which, call it yes; from yes one may obtain no = {i in N: i not in yes} and re-construct p as (no:i->0:)&unite;(yes:i->1:); so the reading is unambiguous and equivalent. Restating the construction we now have: given a mapping (N|f:{subsets of N}), there is some subset G of N which isn't in (:f|); namely, G = {i in N: i not in f(i)}. This, in turn, may be read as saying that every set has more subsets than members.

One might fairly describe this as obvious - after all, {} is a sub-set of N, so is {i} for each i in N, so we've already got one extra. This works fine when N is finite, but infinite sets are slipperier. One can map 0->{}, i+1->{i} on the naturals and cover all the sub-sets just listed. It gets harder to encode all the subsets of size two, {i,j}, but it can be done and the trick it involves generalises adequately to subsets of each finite size. Interleaving all these takes some care and attention but, none the less, one can enumerate any set of subsets of the naturals as long as there's an upper (finite) bound on the size of the subsets. One may use each natural in turn as choice of upper bound and construct an enumeration of all the subsets of the naturals smaller than this. It might seem that in the limit at infinity this process should get us at least an enumeration of all finite sub-sets of the naturals; and one might hope that some analogous trickery might enable one to get all sub-sets of the naturals. In any case the diagonal argument shows only one extra value to handle, so surely it's no more interesting than the {{},{i}: i in N} case ?

The diagonal argument can be read as an algorithm for converting a function, from a set to its power set, into a function from the set's successor to its powerset, via that of the original power set: ie diagonal(N|f:P(N)) extends f to 1+N by giving it a value on N, namely f(N) = {n in N: n not in f(n)}.

The crucial property of the diagonal argument is that f(N) is not a member of {f(n) : n in N}. Consequently, it preserves the property monic and ensures that f cannot be iso.

We can repeatedly apply our diagonal algorithm to an arbitrary function from a set to (some subset of) its power set and get a well-ordered succession. For instance, start from the empty function {} -> {} and apply the algorithm: we get

{} -> {}

ie f({}) = {x in empty: x in f(x)} = {}. From now on, use the Peano naming 0 for {}, 1 for {0}, generally 1+n for {n} union n, leading to n = {i in Natural: i < n}. The above becomes 0 -> {} (when written as a function from a set to its power set) and, as yet, 0 is the only value to which our function has given a value.

1 -> {0} = 1

as 0 not in f(0) = {} and 0 is the only candidate.

2 -> {0, 1} = 2

as 1 not in f(1) = {0} with 1 the only new candidate.

3 -> 3

as 2 not in 2

...

we can, indeed, apply n not in n to each natural number n in turn and induce, from our empty initial function (the identity on the empty set) the identity on the natural numbers:

n -> n

for all n in Naturals.

{naturals} -> successor({naturals})

and, indeed, the same argument ensures we get the set of ordinals, once we apply transfinite induction to the diagonal argument.

Consequently, the diagonal argument regenerates Peano's axioms for the natural numbers.