Minimalitas dan independensi

Bagaimana ya, seandainya kita malas membuktikan semua teorema, lalu kita membuat semua teorema menjadi aksioma? Bukankah grafnya akan sama? Mari kita coba. Aslinya, sistem deduktif Krucing adalah seperti ini:

K = {Amburegul, Bahrelway, Emeseyu, Titanigo}

ng(x, y) = x mengungu y.
dengan x, y ∈ K

A1

ng(Amburegul, Bahrelway)

A2

ng(Bahrelway, Emeseyu)

A3

¬ ng(Bahrelway, Titanigo)

R1

x∈K: ng(x, x)

R2

x∈K: ∀y∈K: ng(x, y) ⇒ ng(y, x)

R3

x∈K: ∀y∈K: ∀z∈K: ng(x, y) ∧ ng(y, z) ⇒ ng(x, z)

Mari kita ganti menjadi sistem deduktif Krucing 2.0:

K = {Amburegul, Bahrelway, Emeseyu, Titanigo}

ng(x, y) = x mengungu y.
Dengan x, y ∈ K

A1

ng(Amburegul, Bahrelway)

A2

ng(Bahrelway, Emeseyu)

A3

¬ ng(Bahrelway, Titanigo)

A4

ng(Amburegul, Amburegul)

A5

ng(Bahrelway, Bahrelway)

A6

ng(Emeseyu, Emeseyu)

A7

ng(Titanigo, Titanigo)

A8

ng(Emeseyu, Bahrelway)

A9

ng(Bahrelway, Amburegul)

A10

ng(Amburegul, Emeseyu)

A11

ng(Emeseyu, Amburegul)

A12

¬ ng(Amburegul, Titanigo)

A13

¬ ng(Titanigo, Amburegul)

A14

¬ ng(Emeseyu, Titanigo)

A15

¬ ng(Titanigo, Emeseyu)

A16

¬ ng(Titanigo, Bahrelway)

R1

x∈K: ng(x, x)

R2

x∈K: ∀y∈K: ng(x, y) ⇒ ng(y, x)

R3

x∈K: ∀y∈K: ∀z∈K:\ ng(x, y) ∧ ng(y, z) ⇒ ng(x, z)

Graf yang dihasilkan juga akan sama.

Graf berarah yang lengkap.

Tabelnya juga sama.

AmburegulBahrelwayEmeseyuTitanigo
AmburegulA4A1A10A12
BahrelwayA9A5A2A3
EmeseyuA11A8A6A16
TitanigoA13A14A15A7

Jadi apa masalahnya? Masalahnya adalah aksiomanya banyak sekali! Padahal salah satu prinsip dalam matematika adalah suatu sistem harus tereduksi menjadi aturan yang lebih sederhana.

Aksioma 4 dapat dihasilkan dari aturan 1. Aksioma 8 bisa diperoleh dengan menggabungkan aksioma 2 dengan aturan 2.

Sistem deduktif Krucing ternyata lebih ringkas dari Krucing 2.0. Pertanyaannya, apakah aksioma dalam sistem deduktif Krucing masih bisa direduksi lagi? Jawabannya tidak. Tidak satupun aksioma A1, A2, dan A3 bisa diperoleh dari aksioma yang lain. Kita mengatakan bahwa ketiga aksioma ini independen atau tidak bergantung satu sama lain. Sistem dengan aksioma-aksioma yang independen disebut sebagai sistem yang minimal, karena kita tak dapat lagi mengurangi aksioma-aksioma tanpa mengubah teorema yang mungkin dihasilkan.

Berikutnya: Pernyataan-pernyataan yang tak dapat dibuktikan benar maupun salah

Ditulis oleh
Pak Ari
Ditulis pada
Terakhir diupdate
Dipublikasikan
Frase kunci
logika sistem deduktif relasi biner