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.
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
Consequently, the diagonal argument regenerates Peano's axioms for the natural numbers.
Maintained by: Eddy.