# computable function

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?

-
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

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.

-
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