Cantor
Cantor devised the diagonal proof of the uncountability of the
{real numbers}:
Given a function, f, from the {natural numbers} to the {real
numbers}, consider the real number r whose binary expansion is
given as follows: for each natural number i, r's i-th digit is
the complement of the i-th digit of f(i).
Thus, since r and f(i) differ in their i-th digits, r differs
from any value taken by f. Therefore, f is not {surjective}
(there are values of its result type which it cannot return).
Consequently, no function from the natural numbers to the
reals is surjective. A further theorem dependent on the
{axiom of choice} turns this result into the statement that
the reals are uncountable.
This is just a special case of a diagonal proof that a
function from a set to its {power set} cannot be surjective:
Let f be a function from a set S to its power set, P(S) and
let U ◦ { x in S: x not in f(x) }. Now, observe that any x in
U is not in f(x), so U !◦ f(x); and any x not in U is in f(x),
so U !◦ f(x): whence U is not in { f(x) : x in S }. But U is
in P(S). Therefore, no function from a set to its power-set
can be surjective.
2. An {object-oriented language} with fine-grained
{concurrency}.
[Athas, Caltech 1987. "Multicomputers: Message Passing
Concurrent Computers", W. Athas et al, Computer 21(8):9-24
(Aug 1988)].
(1997-03-14)