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

Let $f$ be the function that maps the godel number of each proposition P in PA to 0 if P is provable false and 1 if P is provable true and 2 if P is independent of PA.

Then $f$ is not computable. Is it possible to prove that for every computable function $g$, $g\neq f$ ?

How, or - which known result does it follow from?

share|cite|improve this question
You are misusing terminology, instead of "P is undecidable" I think you should say "P is independent of PA". – quanta May 10 '11 at 12:27
up vote 2 down vote accepted

Given an oracle $f : \mathbb N \to \{\text{provable},\text{disprovable},\text{independent}\}$ you could simply encode an arbitrary Turing machine into an arithmetic statement and decide with one invocation whether that Turing machine halts or not. This is non-computable by a result due to Turing.

Alternatively, you could use this oracle to define an extension of PA which is sound and complete, this is impossible by a result of Godel.

Let $f$ be any non-computable function and $g$ a computable function, then I claim $f \not = g$. Supposes for a contradiction that $f = g$ then since $g$ is computable $f$ is.

share|cite|improve this answer
f is already non-computable, my question is if g!=f for all g is provable true, or independent, which theory is it provably true in? – pi_yum_yum May 10 '11 at 12:57
I proved $f$ is not computable, if $g$ is computable $f \not = g$. – quanta May 10 '11 at 12:59
Are you sure proof by contradiction works? $f\neq g$ could be independent? – pi_yum_yum May 10 '11 at 13:16
@pi_yum_yum, I think you need to re-ask your question in a much more detailed and precise way because $f\neq g$ does not make sense in the way I read it. – quanta May 10 '11 at 13:23
@pi_yum_yum, only say "independent" with respect to a theory, it's not clear by context which theory you had in mind. – quanta May 10 '11 at 13:24

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.