[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 

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