Church's Theorem

Definition

If $\Sigma$ is a set of sentences in a language $\mathcal{L}$, then $\text{Cn}(\Sigma )$ is the set of consequences of $\Sigma$.

Church's Theorem

If $PA\subseteq \Sigma$ and $\Sigma$ is a consistent set of sentences, then $\text{Cn}(\Sigma )$ is not decidable.

Proof. (Sketch) There is a p.r. listing such that ${\phi }_n(x)$ is the $n^{\text{th}}$ formula in the language of number theory having at most $x$ free.

Let $E_n=\{m:\Sigma ⊢{\phi }_n(m)\}$

Then $E\ne E_n$ for all $n$, since $n\in E$ iff $n\notin E_n$. But suppose $\text{Cn}(\Sigma )$ is decidable. Since $m\mapsto {\phi }_m(m)$ is p.r. and hence computable, it follows $E$ is decidable. By Theorem 8.13 it follows $E$ is represented in $PA$ by some formula ${\phi }_k(x)$, that is $E=E_k$ for some $k$. Contradiction. Hence $\text{Cn}(\Sigma )$ is not decidable.