第一不完全性定理の（計算論的）証明

証明1

$ x \in K \iff T \vdash \kappa(\overline x)

$ K(x) \coloneqq \begin{cases} 1 & \text{if $T \vdash \kappa(\overline x)$} \\ 0 & \text{if $T \vdash \lnot\kappa(\overline x)$} \end{cases}

証明2

$ D \coloneqq \{\varphi\ |\ T \vdash \lnot\varphi(\ulcorner \varphi \urcorner)\}

$ T \vdash \rho(\ulcorner \varphi \urcorner) \iff \varphi \in D

したがって

$ T \vdash \rho(\ulcorner \rho \urcorner) \iff T \vdash \lnot\rho(\ulcorner \rho \urcorner)