[FOM] Excluded middle & cardinality of the reals

[Michael Carroll]

John L. Kelley in his 'General Topology' gives a proof (pp. 26-27) along the
following lines, showing that "The set of all real numbers is uncountable."
He begins by defining "characteristic function" of a subset A of a set X in
the usual way. Then he defines a one-to-one correspondence between the
family F of characteristic functions on the set of non-negative integers,
and the family G of "rational dyadic expansions." Finally he uses a
diagonalization argument to show that F is uncountable, and so is G, and so
is the set of reals.

Various authors have investigated the concept of a partial subset of a given
set. (Shoenfield, 'Mathematical Logic', p. 144, for example.)

Suppose we modify Kelley's definition of "characteristic function" to allow
partial functions from X to {0, 1}, as well as total ones, to count as
characteristic functions. It would appear that his proof that the reals are
uncountable no longer goes through, since a characteristic function on the
non-negative integers may fail to be defined for one or more values, and the
diagonalization argument then fails. (This is reminiscent of Rogers'
comment, "We can avoid the diagonalization difficulty by allowing sets of
instructions for nontotal partial functions as well as for total functions",
on p. 11 of 'Theory of Recursive Functions and Effective Computability.')

ZFC and similar systems do not seem to permit "partial subsets" to exist as
sets. But when one looks to see why, the reason turns out to be logic's law
of the excluded middle, rather than a set-theoretic axiom.

So Kelley's proof, that the reals are uncountable, relies on the law of the
excluded middle's dictate that partial subsets do not exist.  I was
surprised to see this. Should I not have been?

Mike Carroll
Oro Valley, AZ