Pembuktian

Pembuktian adalah rangkaian simbol-simbol yang menunjukkan urutan perubahan. Masing-masing kalimat dalam pembuktian dipisahkan oleh tanda titik koma.

Contoh

Buktikan bahwa \forall x:x + SSS0 = SSSx dalam bahasa first order.

Kita memiliki dua aksioma yang dapat digunakan:

\forall x:x + 0 = x, dan
\forall x:\forall x':x + Sx' = S(x + x')\

Karena itu pembuktiannya dapat disusun dari aksioma-aksioma tersebut:

\begin{aligned} \forall x&:x + 0 = x \\ \forall x&:x + S0 = S(x + 0) \\ \forall x&:x + S0 = Sx \\ \forall x&:x + SS0 = S(x + S0) \\ \forall x&:x + SS0 = SSx \\ \forall x&:x + SSS0 = S(x + SS0) \\ \forall x&:x + SSS0 = SSSx \end{aligned}

Bukti tersebut sebenarnya adalah satu rangkaian simbol yang sangat panjang.

\forall x:x + 0 = x; \forall x:x + S0 = S(x + 0); \forall x:x + S0 = Sx; \forall x:x + SS0 = S(x + S0); \forall x:x + SS0 = SSx; \forall x:x + SSS0 = S(x + SS0); \forall x:x + SSS0 = SSSx

Kita dapat mengatakan bahwa sebuah kalimat aritmetika terbukti jika dan hanya jika terdapat rangkaian simbol yang menunjukkan proses perubahan dari aksioma menuju ke kalimat yang hendak dibuktikan.

Berikutnya: Bilangan Gödel