MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question may be naive. Take an infinite set of distinct algebraic numbers (hence countable). List them out in a table (randomly) by picking a choice of ordering and change the diagonal numbers.

1) Is it possible to decide if this Cantor type diagonal number is algebraic or transcendental?

2) For some choice of ordering the table, can one prove there exists a Cantor type algebraic or transcendental number?

3) Can we have infinitely many Cantor type transcendental numbers from an infinite subset of choice of orderings?

share|cite|improve this question
Regarding your edit, I'm not quite clear on what you mean by "randomly". You haven't specified a probability distribution, and there can be no uniform distribution here. And are we to interpret the decision question as probabilistic in nature? Clarification would be helpful. – Joel David Hamkins Mar 30 '12 at 16:39
It is an infinite set with no ordering. Say we pick an order from the infinite choice of ordering the infinite set. I will also state another question. – Turbo Mar 30 '12 at 18:17
The decision question does seem to be probabilistic since we cannot say anything until you fix the ordering. – Turbo Mar 30 '12 at 18:25
The following article may be of interest to you: Robert Gray, Georg Cantor and Transcendental Numbers, American Mathematical Monthly 101 #9 (November 1994), 819-832. – Dave L Renfro Mar 30 '12 at 20:05
Unknown (google) seems to be of two different minds on the matter. – Cam McLeman Mar 14 '13 at 15:16
up vote 19 down vote accepted

If one uses binary representation (so that changing the digit means swapping 0 and 1), then every real arises as a diagonal real. If you want the diagonal to be $d$, start with any list of algebraic numbers, and first change the diagonal digits on the list to be the dual to $d$. This is a finite change to each of the reals on the list, so they remain algebraic, but now diagonalizing the new list will produce $d$.

(One should say a bit more about how the diagonal procedure handles the integer part, the sign and the binary point, but there are reasonable procedures that allow this argument to go through.)

Meanwhile, of course, one of the main points of Cantor's construction was that if you put all algebraic reals on the list, then the diagonal is definitely transcendental.

Finally, you use the word "decide" in the question, which suggests that you might be proposing it as a problem of computational decidability. That is, the question would be: given a program that enumerates a list of algebraic reals, by giving more and more of their digits, can one compute yes-or-no whether the diagonal real for this list is algebraic? The answer to this is no, this is not computable. The reason is that we can design devious enumeration programs. Namely, suppose that $f$ was a computable function that decided the nature of the diagonal of any given c.e. enumeration of algebraic numbers. By the recursion theorem (which enables this kind of circular-seeming argument), we may design a program $p$ such that at first, the program $p$ appears to be enumerating a list with all $1$s on the diagonal, so that the diagonal number would be $0$. It does this until $f(p)$ gives its output, which must say that the number is algebraic (since otherwise we would refute it by continuing with our pattern). But after we see this output given for $f(p)$, then program $p$ deviously shifts to a mode where it forces the diagonal real to be transcendental, thereby refuting $f$. So there can be no such computable procedure $f$ to determine whether the diagonal is algebraic.

The question of whether a given c.e. listing of algebraic reals has an algebraic diagonal seems to have complexity $\Pi^0_2$ in the index of the list, and I believe it is complete at this level of complexity.

share|cite|improve this answer
I think this is a great answer – Turbo Mar 30 '12 at 18:22
It's not clear that the modification to a list proposed in the first paragraph will preserve the property that the elements of the list are distinct. – Felipe Voloch Mar 30 '12 at 20:03
Felipe, yes, one may have to make finitely many additional changes (off the diagonal) to ensure distinctness. – Joel David Hamkins Mar 30 '12 at 20:54
How can we (or the machine) find out in what mode the machine is, unless the result has been determined from the beginning? In other words: How can a program that never ends output a transcendental unless the result has been fixed before? – Rhett Butler Mar 14 '13 at 7:47
The recursion theorem enables this kind of argument. The point is that the program $p$ waits until $f$ gives its answer for program $p$, and then $p$ uses that information to do something that contradicts this answer. Technically, the way it works is this: we design a function $p\mapsto q_p$ such that $q_p$ operates like that for program $p$; then, by the recursion theorem there is a program $p$ such that $q_p$ and $p$ compute the same function. And so we might as well have been using $p$ instead of $q_p$, as in the argument. – Joel David Hamkins Mar 14 '13 at 10:48

To answer the third question in the affirmative, consider a list containing all algebraic numbers enumerated according to Dedekind for instance. Then the diagonal is transcendental. (Therefore we can use binaries without excluding certain periodic representations.) Each of the permutations of the list will also result in a transcendental diagonal. However, these diagonals need not all be different. But in order to obtain infinitely many transcendentals, we can bolster the list by inserting some algebraic numbers repeatedly. This will result in infinitely many transcendental diagonals.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.