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
    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?2011-05-10
  • 1
    I proved $f$ is not computable, if $g$ is computable $f \not = g$.2011-05-10
  • 1
    Are you sure proof by contradiction works? $f\neq g$ could be independent?2011-05-10
  • 0
    @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.2011-05-10
  • 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