Liouville vs Cantor

I do not know who is the author of this bad joke, but it is appalling that even qualified mathematicians often say that Cantor’s proof of existence of transcendental numbers is non-constructive, as opposed to Liouville’s proof.

Let me recall that Liouville proved that the infinite sum {\sum 2^{-n!}} is transcendental, while Cantor proved that the set of algebraic numbers is countable, but the set of reals is uncountable.

Dear colleagues, Cantor’s proof is less “constructive” than Liuoville’s only on emotional or aesthetic level. Mathematically, both are equally constructive.

Indeed, the only way I can imagine of defining a real number “constructively” is providing an algorithm for computing rational approximations to it of any prescribed precision. More formally, call a real number {\alpha} constructible if there exists an algorithm (a Turing machine) which, having a natural number {n} at the input, produces at the output a rational approximation to {\alpha} with precision {1/n}. I do not know another reasonable (non-equivalent) definition of a constructible real number; if anybody knows, I would be happy if he shares it with me.

Of course, the Liouville number {\sum 2^{-n!}} is constructible, the good rational approximations being the partial sums of the infinite series.

Further, call a sequence {(\alpha_n)} constructible if there exists an algorithm, which, having natural {m} and {n} at the input, produces a rational approximation to {a_n} with precision {1/m} at the output.

Now two simple exercises.

  1. Show that there exists a constructible sequence containing all algebraic numbers.
  2. Show that for any constructible sequence, there exists a constructible number not contained in this sequence.

A careful examination of Cantor’s proof reveals that its first part solves the first exercise, and the second part solves the second exercise.

I would never waste time for recalling these trivialities in my precious blog if this misunderstanding were not so widespread even among professional mathematicians.


6 Responses to “Liouville vs Cantor”

  1. Sergei Yakovenko Says:

    waist => waste.

  2. Harald Helfgott Says:

    Kantor -> Cantor

    (But then, he started his life in Cyrillic.)

  3. Dima Says:

    Do you really need rational approximations to imagine real algebraic numbers?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: