Undecidability Theorem

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $T$ be the set of theorems of some consistent theory in the language of arithmetic which contains minimal arithmetic $Q$.


Then $T$ is not recursive.


Proof

Let $\Theta$ be the set of Gödel numbers of the theorems in $T$.

We have that $T$ is a consistent extension of $Q$.

By Set of Gödel Numbers of Arithmetic Theorems Not Definable in Arithmetic, $\Theta$ is not a definable set in $T$.

Since Recursive Sets are Definable in Arithmetic, this means that $\Theta$ is not recursive.


Aiming for a contradiction, suppose $T$ were recursive.

Then by Gödel Numbering is Recursive, we could recursively go from $\Theta$ to $T$.

Then using the recursivity of $T$, we could then recursively go back to $\Theta$.

Thus $\Theta$ would be recursive.

This would be a contradiction.

Thus, by Proof by Contradiction, $T$ is not recursive.

$\blacksquare$


Sources