[FOM] Correction on:Who was the first to accept undefinable individuals in mathematics?
Vaughan Pratt
pratt at cs.stanford.edu
Mon Mar 16 17:34:48 EDT 2009
William Tait wrote:
> A better example is from Cantor's original paper on the non-
> denumerability of the reals. He concluded that there is a
> transcendental number between a and b (when a<b) and made a point of
> the fact that this result is significant even if it does not yield a
> definition of such a transcendental. The transcendental can in fact be
> defined in terms of an enumeration of all the algebraic numbers
> between a and b; but in Cantor's time, before Sturm's Theorem, no such
> enumeration could be defined.
Sturm proved his theorem in 1829. (Fourier had worked on this earlier
but Cantor may not have known about that.) So that proof approach would
have been available to Cantor had he so chosen.
However if the goal is simply to construct a transcendental number in
[a,b], Cantor could have chosen a much simpler and faster (time O(1))
algorithm, unlike the application of Sturm's theorem which is a
complicated algorithm that gradually homes in on the target in
infinitely many steps.
Sturm's collaborator Liouville proved that his eponymous constant was
transcendental in 1851, denote it by L. Let n be an integer in
[2L/(b-a), 2L/(b-a) + 2], and let m be an integer in [an/L, an/L + 2].
Then mL/n is easily seen to be a transcendental number in [a,b].
Intervals of width 2 are wide enough to be sure of easily finding an
integer, raising no decision problems near the boundary no matter what a
and b are, yet narrow enough not to present us with a large set to
choose from. We chose n large enough to make an/L + 2 less or equal to
bn/L.
If a and b are rationals then no decision problems arise since the four
interval boundaries are rational multiples of L and hence easily
separated from their nearest integers. It is therefore safe to choose
the least integer in each interval, making the construction deterministic.
The construction then defines a function on the upper left triangle a <=
b of Q^2 that is everywhere transcendental. The function is a countable
union of constant functions each defined on a small domain of positive
measure, decreasing as the diagonal a = b is approached. It can
therefore be extended, remaining transcendental everywhere, to all but a
set of measure zero of the upper left triangle of R^2, i.e. the
construction can safely be assumed deterministic for all but a set of
pairs (a,b) of reals of measure zero, albeit uncountable analogously to
the Cantor set.
Can the Sturm-based method be so extended?
Vaughan Pratt
More information about the FOM
mailing list