Kelengkapan sistem deduktif

Dalam pembahasan sebelumnya, semua pertanyaan berbentuk Apakah x mengungu y? dapat dijawab dan dibuktikan dalam sistem Krucing. Jika setiap pernyataan dalam suatu sistem dapat dibuktikan benar (proven) atau dapat dibuktikan salah (disproven), sistem tersebut disebut sebagai sistem yang komplet.

Sistem deduktif yang komplet: Sistem deduktif yang cukup untuk membuktikan benar (prove) maupun membuktikan salah (disprove) semua pernyataan yang dapat dibuat dalam sistem tersebut.

Sekarang mari kita lihat contoh sistem deduktif sederhana berikut ini.

Domain
D = {a, b, c}
Relasi
p(x, y)
A1
p(a, b)
R1
p(x, y) => p(y,x)

Kita hanya memiliki sebuah aksioma (A1) dan sebuah aturan inferensia (R1).

Kemudian kita dapat menarik kesimpulan berdasarkan R1 dan A1 bahwa p(b, a) harus benar. Ini adalah T1.

Namun kita tidak dapat menarik kesimpulan lebih banyak. Misalnya kita tak dapat menarik kesimpulan p(a,a) maupun p(a,c). Jadi p(a,a) adalah undecidable, demikian juga dengan p(a,c).

Sistem yang seperti ini disebut sebagai sistem yang tidak komplet, karena ada pernyataan yang tak dapat dibuktikan benar maupun salah. Contohnya adalah p(a,a).

Jadi tidak semua sistem deduktif komplet. Ada sistem-sistem deduktif yang tidak mengandung beberapa informasi.

Berikutnya: Minimalitas dan independensi