Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Do all known algorithms that generate infinitely many transcendental numbers like Gelfond-Schneider or Liouville only generate countably many? If uncountably many, is this set of measure zero?

share|improve this question
2  
You shouldn't write "infinite transcental numbers" if you mean infinitely many transcendental numbers. "Infinite transcendtal numbers" means transcendental numbers each one of which, by itself, is infinite. Gelfond-Schneider doesn't generate any infinite numbers. –  Michael Hardy Dec 27 '12 at 4:06
1  
If a computer can generate the numbers (in some listed order), then it is countable. –  Thomas Eding Dec 27 '12 at 5:55
2  
Title needs fixing, all the known things are countable, transcendental or not. –  Arjang Dec 27 '12 at 5:59

2 Answers 2

Here's a "method" to generate all transcendental numbers in the interval $(0,1)$. Of course such a thing can't be an actual algorithm, it must involve countably many arbitrary choices. Let $\{a_n\}_{n=1}^\infty$ be a sequence that runs through all algebraic numbers in $(0,1)$ (such things are easy enough to generate explicitly, but for brevity I'll just assume it's given). For each $n$ choose a positive integer $m_n$ such that $m_{n+1} > m_n$. Now take any sequence of positive integers $b_n$ with the restriction that if $m_j = n$ for some $j$ and the simple continued fraction representation of $a_j$ is $1/(c_1 + 1/(c_2 + \ldots ))$ (with at least $n$ elements), the n-tuples $[c_1, \ldots, c_n]$ and $[b_1, \ldots, b_n]$ are different. Thus there is at most one possible excluded value for each $b_n$. Finally, take $x$ to be the number with continued fraction representation $1/(b_1 + 1/(b_2 + \ldots)$. It is easy to see that $x$ will be a transcendental number in $(0,1)$ and that any such $x$ can be generated for an appropriate choice of the sequences $m_n$ and $b_n$.

share|improve this answer
    
Correct me if I'm wrong. This is a diagonal argument right? Can I just stick with decimal representation for my countable list of algebraic numbers and just flip the numbers digit by digit to get my transcendental number. –  user54358 Dec 28 '12 at 5:12
    
You know what feels funny... even if I did produce my transcendental number, the only information I have about my transcendental number is that it is not on my list of algebraic numbers. –  user54358 Dec 28 '12 at 5:28
    
The main reason for using continued fractions here is to avoid ambiguity with non-uniqueness of decimal representation. There are other ways to do that, of course –  Robert Israel Dec 28 '12 at 5:46
    
What sort of extra property do you want to your transcendental number to have? That may be possible to enforce by adding further restrictions in the process. –  Robert Israel Dec 28 '12 at 7:44

The Liouville procedure generates continuum-many. As long as the gaps between successive $1$'s grow fast enough, we get a transcendental number.

Take any Liouville-type transcendental number, with $1$'s at positions $p_n$, and $0$'s elsewhere. We can modify this in $2^\omega$ many ways, by deciding for every $n$ whether or not to shift the $1$ at position $p_n$ to position $p_n+1$.

In the above example, a very loose notion of "algorithm" was used. If you mean algorithm in a formal sense, as in a Turing machine algorithm, then there are only countably many Turing machines, and hence only countably many algorithmically specifiable numbers.

share|improve this answer
1  
Even in a much looser sense, there are only countably many finite strings in a given finite alphabet, so there are at most countably many numbers those strings can uniquely define (given an unambiguous way of deciding whether a string defines a unique number). –  Robert Israel Dec 27 '12 at 4:48
    
I guess I've been careless in my use of the term "algorithm." But if I may bother you. Your uncountable set of Liouville-type numbers is measure zero right? Can you give a similarly nifty reason why that should be so? –  user54358 Dec 28 '12 at 5:37
    
Yes, it is of measure $0$. Nifty reason, no, a standard calculation. Robert Israel has given something that could be called a construction of a set of transcendentals that definitely has non-zero measure. –  André Nicolas Dec 28 '12 at 6:39

Your Answer

 
discard

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.