Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Consider the finite algorithm A, and the real number $0<T<1$. The output of A on input T is all possible theorems and provable propositions in ZFC, and only that.

Q1. Can such an algorithm and number exist?

Q2. Can we construct such an A and prove there exist such a T?

Q3. Can we prove or disprove that T is rational, irrational, normal, trancendental, algebraic?

Q4. Can T have a closed form expression?

Q5. Is it possible to prove or disprove that no finite algorithm that takes as input A, can output T to arbitrary precision?

share|cite|improve this question
What exactly do you mean by giving a real number as input to a finite algorithm? Since the sentences of the language of set theory are enumerable, there is a real number between $0$ and $1$ that has a $1$ in each binary digit corresponding to a theorem of ZFC and a $0$ everywhere else -- if you "give this number as input" to an algorithm that examines its digits one by one, you get the desired output -- but what would that mean? – joriki Apr 7 '11 at 0:38
You can use Chaitin's constant to encode all this information, for instance. Note however that this number is necessarily noncomputable (so in particular, must be transcendental, and the answer to Q5 is no), as the halting problem (or first-order logic) is undecidable. – Akhil Mathew Apr 7 '11 at 0:43
So we know such a number exist, how can we know that for instance e/Pi does not by some magical coincidence have this property? – TROLLKILLER Apr 7 '11 at 0:59
I'm having trouble with 'exists' (I don't recognize it as a technical term here). Do you mean computable? What about $T$? DI'm guessing you intend that it 'exists'? Is it also computable? I feel like that should be part of the prerequisites to the question. – Mitch Apr 7 '11 at 2:50
up vote 3 down vote accepted

(I'm only offering hints as I presume this is homework, though it isn't tagged as such.)

A hint for Q1 and Q2: 'how many' provable theorems of ZFC can there be? What different definitions of 'a real' do you know, and do you know ways of converting back and forth between the different definitions? Once you have this, the other pieces should start to fall into place easily.

A hint for Q5: assuming you had such an algorithm, what would this imply about the provable theorems of ZFC?

Hints for Q3 and Q4: can you show a relationship between these questions and Q5?

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.