ここで $\psi(\overline{x}) = \neg \varphi \left( \overline{f(x, x)} \right)$ と選ぶと,
$$
\mathrm{PA} \vdash \neg \varphi \left( \overline{f(\lceil \psi \rceil, \lceil \psi \rceil)} \right) \Longleftrightarrow \mathrm{PA} \vdash \psi \left( \overline{\lceil \psi \rceil} \right) \Longleftrightarrow \mathrm{PA} \vdash \varphi \left( \overline{f(\lceil \psi \rceil, \lceil \psi \rceil)} \right)
$$
となる.
$\Sigma^0_1$-完全集合 $A$ をとる.$\mathrm{PA} \vdash \psi(\overline{x})$ は( $\psi$ の Gödel 数と $x$ をとる述語として)$\Sigma^0_1$ なので,還元関数 $f$ があって
$$
\mathrm{PA} \vdash \psi(\overline{x}) \Longleftrightarrow f(\lceil \psi \rceil, x) \in A
$$
となる.$A$ も弱表現可能なので $x \in A \Longleftrightarrow \mathrm{PA} \vdash \varphi(\overline{x})$ となる論理式 $\varphi$ がある.
早稲田 計算機科学系 M0