0
$\begingroup$

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?

  • 0
    You are misusing terminology, instead of "P is undecidable" I think you should say "P is independent of PA".2011-05-10

1 Answers 1

2

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.

  • 0
    @pi_yum_yum, only say "independent" with respect to a theory, it's not clear by context which theory you had in mind.2011-05-10