Are there really infinite transcendental numbers?

[lpetrich]

Alan Turing and the Countability of Computable Numbers – Feature Column and  Computable number

A computable real number is a real number that can be approximated arbitrary closely by running a Turing machine arbitrarily long. As with algebraic numbers, the output of each Turing machine can be tagged by Turing machine to resolve repetitions, so

{Nonnegative integers} < {computable numbers} < {Turing-machine results tagged by Turing machine}

As for algebraic numbers, can show that the number of Turing machines is countable, so we find

A0 <= |computable numbers| <= |Turing machines| = A0

and thus

|computable numbers| = A0

Computable numbers include not only algebraic numbers but also every transcendental number that one will ever use. Think of root-finding algorithms, infinite-series sums and products, and numerical integration.

There is an exception: Chaitin's constant, or more properly, family of constants. It's a number between 0 and 1 where each fractional digit has a Turing machine assigned to it, and is 1 if the Turing machine halts and 0 if it does not.

Alan Turing proved that one cannot construct a Turing machine that can return whether or not a Turing machine will halt, and that means that there is no Turing machine that can generate Chaitin's constant. Thus, Chaitin's constant is uncomputable.

 

[lpetrich]

The Turing machine, general recursive functions, and the lambda calculus are three equivalent models of computation.

 Lambda calculus - essentially doing everything with functions.

Functions:
 Primitive recursive function - functions of nonnegative integers that are combinations of these functions:

• Constant function
• Successor function: add 1 to a number
• Projection function: select the arg at some position in the args to output
• Function composition: function of a function
• Primitive recursion: a function f(n) for any n that depends on f(n-1) then f(n-2) then all the way to f(0), like a loop over some variable from 0 to n in steps of 1

 General recursive function also has the minimization operator, a function that increases an integer value in steps from 0 to find the first one that makes some other function zero, like an infinite loop with some general termination condition.

Automata:

•  Combinational logic - memoryless computation - it can be expressed as a transition table, a table that takes an input value and gives an output value.
•  Finite-state machine or finite-state automaton - has an internal memory that can have a finite number of states, and a transition table that also reads from that memory and writes to it.
•  Pushdown automaton - also has an infinite pushdown stack, a memory that is accessed in last-in-first-out (LIFO) fashion, and a transition table that can read the value on the stack, push a value onto it, or pop a value off of it.
•  Turing machine - instead of a pushdown stack, it has an infinite tape, and a transition table that can read from the tape's current position, write to it, and move the tape to the next position or previous one.

 

[Jarhyn]

Alan Turing and the Countability of Computable Numbers – Feature Column and  Computable number

A computable real number is a real number that can be approximated arbitrary closely by running a Turing machine arbitrarily long. As with algebraic numbers, the output of each Turing machine can be tagged by Turing machine to resolve repetitions, so

{Nonnegative integers} < {computable numbers} < {Turing-machine results tagged by Turing machine}

As for algebraic numbers, can show that the number of Turing machines is countable, so we find

A0 <= |computable numbers| <= |Turing machines| = A0

and thus

|computable numbers| = A0

Computable numbers include not only algebraic numbers but also every transcendental number that one will ever use. Think of root-finding algorithms, infinite-series sums and products, and numerical integration.

There is an exception: Chaitin's constant, or more properly, family of constants. It's a number between 0 and 1 where each fractional digit has a Turing machine assigned to it, and is 1 if the Turing machine halts and 0 if it does not.

Alan Turing proved that one cannot construct a Turing machine that can return whether or not a Turing machine will halt, and that means that there is no Turing machine that can generate Chaitin's constant. Thus, Chaitin's constant is uncomputable.

We have used Turing machines to brute force small BB numbers, for example.

I would dare you to make the claim that a Turing machine (such as an LLM implementation by a Turing machine) is utterly unable to tell you if an algorithm (such as a simple loop) will halt. As such, I will challenge the notion that this is as set in stone quite in the way you characterize it.

I think a lot has to do with the relative "size" and "power" of the two Turing machines in question.

IOW "computability" relies on a context of what is doing the computing.

 

[barbos]

Obviously n*e is transcendental where n is any other number. Therefore at a trivial level there are infinite numbers of transcendental numbers. But I mean an infinite number of numbers that not calculated using other transcendental numbers?

I would think the answer is yes. But all the proofs I see are of multiplying some number to e or pi.

Transcendental numbers are the numbers which are not roots of the finite order rational coefficient polynomials.
There is obviously infinite number of infinite order polynomials. Some of these produce roots which are irrational or even rational. But it's obvious that infinite number is not. I would be surprised that all of them can be expressed as finite order polynomials of finite set of transcendental numbers. Not a proof but insight.

 

[lpetrich]

 BlooP and FlooP and Bloop Floop And Gloop
The first two, "bounded loop" and "free loop", are toy programming languages invented by Douglas Hofstader for his book "Goedel, Escher, Bach", and the third one, "general loop", is a completely hypothetical one.

BlooP is primitive recursive functions, and FlooP is general recursive functions ~ Turing machines ~ lambda calculus

BlooP programs are guaranteed to halt, while FlooP ones are not, and by Alan Turing's halting theorem, there is no FlooP program that can test for whether or not a FlooP one will halt.

GlooP is a hypothetical super-Turing system.

Most algorithms that we use can be expressed in BlooP-like form, with maximum numbers of loop repeats specified before entering those loops.


What hardware and software is Turing-complete? That is, what is FlooP-like to within resource limitations? It must have:

1. Arbitrary flow of control, including potentially infinite loops
2. Arbitrary array access

Charles Babbage's Analytical Engine satisfied (1) but not (2), as far as I can tell from reading descriptions of its proposed instruction set, and that was also true of some early computers that were actually built, like the  Manchester Baby of 1948.  Timeline of computing hardware before 1950

The first computer to satisfy both criteria was likely the  Manchester Mark 1 of 1949 with "index registers" for accessing arrays. All computing hardware since then has satisfied both criteria except for hardware that is limited in some way, like a Field Programmable Gate Array (FPGA).

The first commercially-available CPU on a chip was the Intel 4004 (1971), and it satisfied criterion (1) but not (2). That was apparently also true of the Intel 8008 (1972), but later ones soon satisfied both criteria, like the Intel 8080 (1974), the Motorola 6800 (1974), the MOS Technology 6502 (1975), and the Zilog Z80 (1976).

Turning to software, most programming languages that one is likely to use are Turing-complete, and the main exceptions that I know of are HTML, XML, CSS, and SQL. For a webpage, HTML and CSS aren't Turing-complete, but JavaScript is.

 

[lpetrich]

Obviously n*e is transcendental where n is any other number. Therefore at a trivial level there are infinite numbers of transcendental numbers. But I mean an infinite number of numbers that not calculated using other transcendental numbers?

I would think the answer is yes. But all the proofs I see are of multiplying some number to e or pi.

One has to restrict n in some way, like to algebraic numbers, or else one allows the likes of (1/e).

Both e and pi are computable, however.
e = sum over n from 0 to infinity of 1/n!
pi = 4 * sum over n from 0 to infinity of (-1)^n/(2n+1)

Chaitin's constant is not computable, however. Strictly speaking, it is a family of constants, one for each permutation of Turing machines. That makes its cardinality C, that of the real numbers. So there are as many of these as there are all numbers between 0 and 1 inclusive: every possible set of digit values for binary numbers (0 and 1).

 

[lpetrich]

I will now discuss algebraic extensions of sets of numbers.

For a set of numbers S with operations on them, one constructs an algebraic extension with some root or roots of a polynomial with coefficients in S, roots that are not in S. One then applies the operations of S onto these new numbers to get a complete set.

Consider integers with sqrt(2) added on: Z(sqrt(2)) or Z(x^2-2). One gets integers a0 and integers multiplying sqrt(2): a1*sqrt(2) to get all the elements: a0 + a1*sqrt(2).

Let's try sqrt(2) and sqrt(3): Z(sqrt(2),sqrt(3)) or Z(x^2-2,x^2-3). At first thought, one might expect a0 + a1*sqrt(2) + a2*sqrt(3), but multiply sqrt(2) and sqrt(3) and one gets an additional number: sqrt(6). Thus, a0 + a1*sqrt(2) + a2*sqrt(3) + a3*sqrt(6).

Let's now consider constructing familiar kinds of numbers from other familiar kinds. Start with nonnegative integers N, and do extension N({-a or x + a for all a in N}). This gives us the negative numbers, making Z, the integers. This can be simplified to

Z = N(-1) or N(x+1)

Extension only with -1, with multiplication doing the rest.

Likewise, the rational numbers are

Q = Z({a/b or b*x-a for all a in Z and all b in Z - {0}})

 

[lpetrich]

Now consider a full algebraic extension of some set of numbers S, with the roots of all non-constant polynomials with coefficients in S: FullAlgExt

The (complex) algebraic numbers A = FullAlgExt(Q) -- Q is the rational numbers. A is also algebraically closed: FullAlgExt(A) = A.

There are also algebraic integers, the algebraic extension of the integers is the integers with the roots of all non-constant monic polynomials with integer coefficients, "monic" meaning that its highest coefficient is 1.

Algebraic integers are closed over addition, subtraction, and multiplication, and algebraic numbers also over division.

|algebraic integers| = A0 also.

-

Real numbers can be defined as the limits of Cauchy sequences of rational numbers, convergent sequences with convergence defined without reference to the limit of convergence.

They are closed under addition, subtraction, multiplication and division, and complex numbers (complex real numbers) are also algebraically closed: FullAlgExt(C) = C where C is here the complex numbers. They are also Cauchy-closed, limits of every Cauchy sequence of real numbers. Cauchy(Q) = Cauchy(R) = R.

Cauchy sequences of rational numbers have cardinality A0^A0 = C, and Cauchy sequences of real numbers C^A0 = (2^A0)^A0 = 2^(A0*A0) = 2^A0 = C. So there are as many of them as there are real numbers.

 

[Swammerdami]

The History of math is a topic that interests me. Let's review the history of transcendental numbers.

Gottfried Leibniz coined the term "transcendental function"; he proved that the trigonometric functions are not algebraic; but did not consider transcendental numbers. Johann Lambert and Leonhard Euler were first to work with that concept but neither completed a proof that any number was actually non-algebraic. (Lambert, one of the greatest of polymaths, was first to prove that pi is irrational; he also proved that pi was not the square-root of any rational number; and conjectured that that proof could be extrapolated to prove pi transcendental.)

Although it is now obvious, via Georg Cantor's work in the 1870's, that almost all real numbers are transcendental, that transcendental numbers even exist was not proven until Joseph Liouville's work in the 1840's, cf  Liouville number. As shown at that Wiki page the proof has two parts: First he shows that irrational algebraic numbers cannot have a "good" rational approximation; Then he displays a number which has excellent rational approximations so must be non-algebraic:

L = 0.11000100000000000000000100000000000000000000000000......​

The 1's occur at positions 1, 2, 6, 24, 120, ... k!, ...

After the work of Liouville and Cantor, the race was on! Charles Hermite soon proved that e (Euler's number) was transcendental; Ferdinand von Lindemann extended this proof to show that pi was transcendental; Karl Weierstrass extended the result even further. In Heinrich Dörrie's excellent book 100 Great Problems of Elementary Mathematics, more pages are spent on Weierstrass's intricate proof of this transcendentality than on any of the other 99 problems.

- - - - - - - - - - - - - - - -

While transcendental numbers were almost unheard of until the 18th century, there was a sort of ancient analog. Euclid introduced the idea of constructible numbers -- ratios that could be built using compass and straightedge. (We now know that these are a subset of the algebraic numbers.) Some of the ancient puzzles could be phrased as questions about constructible numbers. Can a circle be squared? (Is pi constructible?) Can a cube be doubled? (Is the cube-root of 2 constructible?)

Two medieval mathematicians -- Omar Khayyam and Leonardo of Pisa -- are credited with discovering that the solutions to cubic equations are not in general constructible.

 

[lpetrich]

I'll now consider algebraic extensions of the computable numbers. Doing an algebraic extension is something computable, so one ends up with computable numbers again:

FullAlgExt(computable) = complex computable numbers


 Definable real number This is a step further, all the numbers that can be described using some finite-length strings of symbols with some finite number of them and with some grammar for interpreting combinations of them. I mean "grammar" in a very broad sense. Consider how we write positive integers. Here are the rules of its grammar:

(Number) = (digit: 1 to 9) -- value = (digit value)
(Number) = (Number) (digit: 0 to 9) -- value = 10*(previous number value) + (digit value)

 Backus–Naur form
<number> ::= <1 to 9> | <number> <0 to 9>

Natural-language words require more complicated rules.

 Context-free grammar -- production rules are independent of context, like how we write positive integers.

 

[lpetrich]

However one defines definable numbers, the definitions are finite in length, and the set of all of them is thus countable: cardinality A0.

Computable numbers are a subset of definable numbers, since their algorithms for computing them are definitions. But some definable numbers are not computable, like  Chaitin's constant the probability that some random Turing machine will halt. I seem to have come up with something different: a real number between 0 and 1 whose binary digits are whether the Turing machine for that digit will halt, 1 for yes and 0 for no. That also is definable but not computable.

Natural/whole numbers < Integers < Rational numbers < Real algebraic numbers < Real computable numbers < Real definable numbers < Real numbers

All of them have cardinality A0 except real numbers: cardinality C = 2^A0 = A0^A0

 

[lpetrich]

Going as far back as possible with numbers, we get Giuseppe Peano's axioms of arithmetic.  Peano axioms

Equality:

1. Closure: if a is in some set S, and a = b, then b is also in S.
2. Reflexivity: a = a.
3. Symmetry: a = b is equivalent to b = a.
4. Transitivity: a = b and b = c imply a = c.

Natural numbers N and successor function S:

1. Zero: 0 is in N
2. Closure: if a is in N, then S(a) is in N.
3. Equality: for a, b in N, a = b is equivalent to S(a) = S(b)
4. Floor: there is no a in N such that S(a) = 0
5. Mathematical induction:
   • Set theory: if 0 is in some set F and if for all a in N, a in F implies S(a) in F, then N <= F.
   • Predicate function: if for function f, f(0) is true, and if for all a in N, f(a) implies f(S(a)), then for all a in N, f(a) is true.

Addition:

1. a + 0 = a
2. a + S(b) = S(a + b)

Multiplication:

1. a*0 = a
2. a*S(b) = (a*b) + a

One can show that finite set cardinalities satisfy Peano's axioms.

 

[lpetrich]

Let's say that we only know about natural numbers. What x satisfies x + 1 = 0?
x + 1 = 0
x + S(0) = 0
S(x) = 0
Not possible from Peano's axioms.

So let us do an algebraic extension of the natural numbers. For a in N, the solution x of x + a = 0. This gives us the integers: Z. This means that subtraction is always defined for integers, even if not always for natural numbers:

a - b is x that solves x + b = a

That is, integers are closed over subtraction, even if natural numbers aren't. That is also true of every superset of the integers.

Now we only know about integers. What x satisfies 2*x = 1?
Start with 0 and 1, multiply by 2, and use ordering:
0 < 1 implies 2*0 < 2*1 giving 0 < 2
Where does 1 fit in?
0 < 1 < 2
Thus, x cannot be an integer.

We do an algebraic extension with multiplication: for a, b in Z, the solution x of b*x - a = 0. This gives us the rational numbers: Q, and division is always defined for them except for division by zero, even if not always for integers:

a/b is x that solves b*x = a

Rational numbers are closed over division, even if integers aren't. That is also true of every superset of the rational numbers.

 

[lpetrich]

Turning to irrational numbers, the first one discovered was likely the square root of 2, sometimes called Pythagoras's constant, using Pythagoras's theorem. A right triangle, a triangle with a right angle in it, has two short sides, next to the right angle, and a long side, the hypotenuse, opposite the right angle.

(Long-side length)^2 = (short-side-1 length)^2 + (short-side-2 length)^2

When the two short sides have equal length, the long side has sqrt(2) * that length.

 Square root of 2 and Square Root of 2 is Irrational - ProofWiki and Square Root of Prime is Irrational - ProofWiki

Every integer that is not a square of another integer has an irrational square root, and likewise for rational numbers. Likewise, every integer that is not an nth root of another integer has an irrational nth root, and likewise for rational numbers.

Nth Root of Integer is Integer or Irrational - ProofWiki

The nth power of a non-integer rational number is also non-integer rational. Thus, the nth root of an integer is either an integer or irrational.

One can extend this kind of proof to algebraic integers more generally. They are roots of integer-coefficient monic polynomials, those with the highest coefficient equal to 1. For example, the square root of 2 is an algebraic integer.

One finds that an integer-coefficient monic polynomial of a non-integer rational number is a non-integer rational number, and thus the polynomial's roots are integers and irrational numbers without non-integer rational numbers.

 

[lpetrich]

Proof that for positive integers n and N, N^(1/n) is irrational if it is not an integer.

As a preliminary, if N has a prime factor p with power m > n, then it has factor p^(k*n) * p^(m-k*n) where k is a positive integer and m-k*n is >= 0 and < n. (p^(k*n))^(1/n) = p^k, obviously a rational number, so it suffices to consider the case of p having a power less than n.

For some positive n > 1, consider some number N that is a product of distinct primes p, each to some power m < n. It can be proved that N^(1/n) is irrational, using a classic proof of the irrationality of sqrt(2).

Let us suppose that N^(1/n) is a/b where a and b are positive integers in lowest terms. Then,
a^n = N*b^n = (product of p^m) * b^n
This means that a must have prime factors p with powers m' satisfying n*m' > m:
a = (product of p^m') * a'
That gives us
b^n = (product of p^(n*m'-m)) * a'^n
The same argument shows that b must also have prime factors p, meaning that both a and b are divisible by the p's. They thus cannot be in lower terms, and N is thus irrational.


Now for every algebraic integer being either an integer or an irrational number. Suppose that a degree-n monic integer-coefficient polynomial has non-integer rational-number solution a/b where a and b are relatively prime (coprime), a is nonzero, and b > 1. The highest term gives (a^n)/(b^n) and the rest of the terms A/b^(n-1) for some integer A. They combine to make (a^n + A*b)/b^n. Since b does not evenly divide a, the numerator is necessarily nonzero, and a nonzero rational number cannot be a root of that polynomial.

This gives a constraint on solutions on integer-coefficient polynomials: +- a/b where a evenly divides the lowest nonzero coefficient and b evenly divides the highest nonzero coefficient. So one can use that constraint for trial-and-error solution of such polynomials.

 

[lpetrich]

 Proof that e is irrational and Euler's Number is Irrational - ProofWiki

It is also possible to prove that for all nonzero rational numbers a, e^a is irrational, and that e does not satisfy any second-degree or third-degree rational-number-coefficient polynomial.

Martin Aigner, Günter M. Ziegler Auth. Proofs From THE BOOK : Martin Aigner, Günter M. Ziegler : Free Download, Borrow, and Streaming : Internet Archive -- has a proof of e^a irrational. It starts with a proof for a a positive integer, then generalizes to reciprocals and nth roots, thus proving for a nonzero rational number.

x is rational <-> 1/x is rational
x is irrational <-> 1/x is irrational
For n an integer > 1,
x is rational -> x^n is rational
x is irrational -> x^(1/n) is irreational

 Proof that π is irrational and Pi is Irrational - ProofWiki

One of the proofs first proves that pi^2 is irrational, thus implying that pi itself is irrational.

Irrationality of Logarithm - ProofWiki

If for rational numbers a and b, there are no nonzero integers m and n satisfying a^m = b^n, then log(b,a) = log(a)/log(b) is irrational.

Proof: suppose that log(b,a) = p/q for nonzero integers p, q. Then a = b^(p/q) and a^q = b^p contrary to that condition.

 

[lpetrich]

 Transcendental number has a proof that e is transcendental. It also lists several known-transcendental and possibly-transcendental numbers.

It has a proof that e is transcendental.

It mentions the  Lindemann–Weierstrass theorem

If algebraic numbers a1, ..., an are linearly independent over the rational numbers, then e^a1, ..., e^an are algebraically independent over the rational numbers -- they do not satisfy any rational-coefficient polynomial in them.

Equivalent formulation:
If algebraic numbers a1, ..., an are distinct, then e^a1, ..., e^an are linearly independent over the algebraic numbers.

For nonzero algebraic number a, the set {1, e^a} is linearly independent over the algebraic numbers, meaning that e^a is transcendental.

Proof that pi is transcendental. It uses e^(pi*i) +1 = 0. That would not be possible if pi*i is algebraic, thus pi*i is transcendental. Since i is algebraic, pi is transcendental.

Likewise, trigonometric and hyperbolic functions of nonzero algebraic numbers are transcendental.

This implies that inverse trigonometric and hyperbolic functions of algebraic numbers are either 0 or transcendental.

 

[lpetrich]

 Gelfond–Schneider theorem

If a and b are complex algebraic numbers with a not 0 or 1 and with b irrational, then every value of a^b is a transcendental number.

Alternately, for a and b nonzero algebraic, log(a)/log(b) is either rational or transcendental.

A related result is from the Lindemann-Weierstrass theorem: for algebraic number a not 0 or 1 and for base e, log(a) is transcendental.

 Baker's theorem generalizes it, and  Schanuel's conjecture is related.

 

[lpetrich]

There are many numbers that have yet to be proven to be irrational or transcendental despite their seeming like they ought to be.

•  Irrational number
• Irrational Number -- from Wolfram MathWorld
•  Transcendental number
• Transcendental Number -- from Wolfram MathWorld

Most combinations of e and pi: pi + e, pi - e, pi*e, pi/e, e^e, e^(e^2), pi^e, pi^pi, ... Known exceptions:

• e^(a*pi*i) for rational a - is algebraic
• e^(pi*sqrt(n)) for positive integer n - is transcendental

Thus, e^pi is transcendental.

Gelfond-Schneider constant: 2^sqrt(2) is transcendental. But a further power of sqrt(2) is algebraic:
(2^sqrt(2))^sqrt(2) = 2^(sqrt(2)*sqrt(2)) = 2^2 = 4

(transcendental)^(rational) = (transcendental)
Algebraic-coefficient polynomial of (transcendental) = (transcendental)

 

[lpetrich]

There are some curious partial results. Consider the Euler  Gamma function an extension of factorials into non-integer values:

\( \displaystyle{ \Gamma(z) = \int_0^\infty t^{z-1} e^{-t} \, dt } \)
\( \displaystyle{ n! = \Gamma(n+1) } \)
\( \displaystyle{ \Gamma(z+1) = z \Gamma(z) } \)
\( \displaystyle{ \Gamma(z) \Gamma(1-z) = \frac{\pi}{\sin \pi z} } \)
\( \displaystyle{ \prod_{k=0}^{m-1} \Gamma( z + k/m ) = (2\pi)^{(m-1)/2} m^{1/2 - m z} \Gamma(m z) } \)

for n a nonnegative integer. So every value is a multiple of some value for real part between 0 and 1 or a reciprocal of some such value.

Using G for "Gamma", G(1) = 1 and G(1/2) = sqrt(pi)

• Transcendental and algebraically independent of pi: G(1/6), G(1/4), G(1/3), G(2/3), G(3/4), G(5/6)
• Transcendental: (1/pi)*G(1/4)^2 ... (1/pi)*G(1/3)^2
• Not known to be irrational, let alone transcendental: G(1/5)

They are not necessarily algebraically independent of each other, however. From that function's identities:

• G(1/3)*G(2/3) = (2/3)*pi*sqrt(3)
• G(1/4)*G(3/4) = pi*sqrt(2)
• G(1/6)*G(5/6) = 2*pi
• G(1/6)*G(2/3) = 2^(2/3)*sqrt(pi)*G(1/3)
• G(1/3)*G(5/6) = 2^(1/3)*sqrt(pi)*G(2/3)

Algebraic independence of some numbers over some set of numbers (usually integers / rational numbers / algebraic numbers): no polynomial from all these numbers will ever equal zero.