Gödel'in eksiklik teoremleri: Ne söyler, ne söylemez?

“Matematikte her doğru şey kanıtlanabilir mi?” Bu soru kulağa felsefi gelir, ama 1930–1931 yıllarında henüz 24 yaşındaki Avusturyalı mantıkçı Kurt Gödel ona kesin bir matematiksel cevap verdi. Cevap, matematiğin temellerini sağlamlaştırmayı amaçlayan büyük bir projeyi sarstı ve bugün de mantığın en çok alıntılanan sonuçları arasında yer alıyor.

Aynı zamanda en çok yanlış anlaşılan sonuçlardan biridir. İnternette Gödel’in “her şeyin belirsiz olduğunu”, “matematiğin çöktüğünü” ya da “insan zihninin bilgisayardan üstün olduğunu” kanıtladığını okuyabilirsiniz. Bu yazıda teoremlerin gerçekte ne söylediğini, hangi koşullarda geçerli olduğunu ve ne söylemediğini ayırmaya çalışacağız.

Arka plan: Hilbert’in büyük planı

20. yüzyılın başında matematikçiler, kümeler kuramında ortaya çıkan paradokslar yüzünden matematiğin temellerinden kaygı duyuyordu. David Hilbert bir çıkış yolu önerdi. Matematiği, sembolleri ve kuralları açıkça belirlenmiş biçimsel sistemler olarak yazalım. Sonra bu sistemlerin iki özelliğini kanıtlayalım:

• Çelişkisizlik: Sistem hem bir önermeyi hem de onun olumsuzunu kanıtlamasın.
• Tamlık: Sistemin dilinde yazılan her önerme için ya önermenin kendisi ya da olumsuzu kanıtlanabilsin.

Hilbert ayrıca çelişkisizlik ispatının güvenilir, basit ve sonlu yöntemlerle yapılmasını istiyordu. Bu programın arka planını Hilbert’in 23 problemi yazımızda anlatıyoruz.

Gödel sonuçlarını Eylül 1930’da Königsberg’deki bir toplantıda duyurdu ve makalesi 1931’de yayımlandı. Aynı Gödel, bir yıl önce doktora tezinde birinci mertebe mantığın başka bir anlamda “tam” olduğunu kanıtlamıştı. İki sonucun adlarının benzemesi, karışıklığın kaynaklarından biridir.

Biçimsel sistem ne demek?

Biçimsel sistemi bir oyun gibi düşünebilirsiniz. Elimizde şunlar vardır:

1. Bir alfabe: 0, S (ardıl, “bir sonraki”), +, ×, =, parantezler, değişkenler, “ve”, “değil”, “her” gibi semboller.
2. Aksiyomlar: Başlangıçta doğru kabul edilen önermeler. Örneğin “her x için x + 0 = x”.
3. Çıkarım kuralları: Elimizdeki önermelerden yenilerini üretmenin mekanik kuralları.

Bir kanıt, her adımı ya aksiyom ya da önceki adımlardan kurallarla elde edilmiş sonlu bir önerme dizisidir. Önemli olan, bir dizinin kanıt olup olmadığını bir makinenin denetleyebilmesidir. Bu, aksiyomların “etkin” biçimde verilmesi koşulu olarak bilinir.

Gödel’in hilesi: Önermeleri sayılara çevirmek

Gödel’in ilk büyük fikri, sistemin kendi hakkında konuşmasını sağlamaktı. Bunun için her sembole, her önermeye ve her kanıta bir doğal sayı atadı. Bugün bu yönteme Gödel numaralandırması denir.

Kendi basit örneğimizle görelim. Sembollere şu kodları verelim: “0” → 1, “=” → 2, “S” → 3. Bir sembol dizisini, sırayla asal sayıların üsleri olarak kodlayalım: Birinci sembolün kodu 2’nin, ikincisininki 3’ün, üçüncüsününki 5’in üssü olsun.

• “0 = 0” dizisinin kodları 1, 2, 1’dir. Gödel numarası 2¹ × 3² × 5¹ = 2 × 9 × 5 = 90 olur.
• “S0 = S0” dizisinin kodları 3, 1, 2, 3, 1’dir. Numarası 2³ × 3¹ × 5² × 7³ × 11¹ = 8 × 3 × 25 × 343 × 11 = 2 263 800 olur.

Asal çarpanlara ayırmanın tek türlü olması sayesinde bu sayılardan diziyi geri okuyabiliriz: 90 = 2¹ × 3² × 5¹ olduğundan kodlar 1, 2, 1’dir; dizi “0 = 0”dır. Böylece “bu dizi bir kanıttır” gibi sistem hakkındaki ifadeler, sayılar hakkındaki ifadelere dönüşür. Aritmetiği ifade edebilen bir sistem artık kendi kanıtları hakkında da konuşabilir.

Birinci eksiklik teoremi

Gödel bu araçla, kabaca “Bu önerme sistemde kanıtlanamaz” diyen bir G önermesi kurdu. Önerme kendine doğrudan değil, kendi Gödel numarası üzerinden atıf yapar.

Şimdi akıl yürütelim:

• G kanıtlanabilseydi, sistem “G kanıtlanamaz” diyen bir önermeyi kanıtlamış olurdu. Sistem çelişkisizse bu olamaz.
• G’nin olumsuzu kanıtlanabilseydi, bu da uygun koşullar altında bir çelişkiye yol açardı.

Sonuç şudur: Temel aritmetiği ifade edebilen, aksiyomları etkin biçimde verilmiş ve çelişkisiz her biçimsel sistemde, sistemin dilinde yazılmış ama sistemde ne kanıtlanabilen ne de çürütülebilen önermeler vardır.

Gödel’in orijinal ispatı çelişkisizlikten biraz daha güçlü bir koşul kullanıyordu. J. Barkley Rosser 1936’da ispatı yalnızca çelişkisizliği varsayacak biçimde iyileştirdi.

İkinci eksiklik teoremi

İkinci teorem birincinin doğal devamıdır: Aynı koşulları sağlayan bir sistem, çelişkisiz olduğunu kendi içinde kanıtlayamaz.

Burada ince bir nokta var. Teorem, sistemin çelişkisizliğinin hiçbir şekilde kanıtlanamayacağını söylemez. Örneğin Gerhard Gentzen 1936’da aritmetiğin çelişkisizliğini kanıtladı. Ancak bunun için aritmetiğin kendi içinde bulunmayan bir ilke kullandı. Bu ilke, sonsuz sıra sayıları üzerinde tümevarım yapmaya dayanıyordu. Yani çelişkisizlik ispatı mümkündür, ama sistemin kendi araçlarından fazlasını ister. Hilbert’in umduğu türden, yalnızca basit yöntemlere dayanan bir ispat ise bu anlamda ulaşılamaz kaldı.

Gödel ne söylemez?

Şimdi en önemli bölüme gelelim. Teoremlerle ilgili yaygın yanlış yorumlar ve düzeltmeleri şunlardır:

“Kanıtlanamayan doğrular var” mutlak bir iddia değildir. Teorem, belirli bir biçimsel sistemde türetilebilirlikten söz eder. Bir sistemde kararlaştırılamayan G önermesi, daha güçlü başka bir sistemde kanıtlanabilir. O yeni sistemin de kendi kararlaştırılamayan önermeleri olur.

Her matematik kuramı eksik değildir. Teorem yalnızca temel aritmetiği içeren sistemler için geçerlidir. Örneğin yalnızca toplamanın bulunduğu, çarpmanın bulunmadığı doğal sayılar aritmetiği tamdır ve karar verilebilirdir. Gerçek sayıların belirli bir cebirsel kuramı ve Öklid geometrisinin birinci mertebe bir biçimi de tamdır. Öklid’in yaklaşımına Elemanlar yazımızda değiniyoruz.

Matematik çelişkili ya da güvenilmez değildir. Teoremler bir sistemde çelişki bulmaz. Yalnızca çelişkisizliğin nerede ve hangi araçlarla kanıtlanabileceğine sınır koyar. Okulda öğrendiğimiz teoremlerin doğruluğunu sorgulatan bir sonuç değildir.

“Her şey görecelidir” anlamına gelmez. Gödel’in teoremleri son derece kesin koşullara sahip, kendisi de kesin olarak kanıtlanmış matematiksel sonuçlardır. Hukuk, siyaset ya da gündelik tartışmalar biçimsel sistem değildir. Bu alanlara teoremi doğrudan uygulamak bir benzetmedir, kanıt değildir.

İnsan zihni hakkındaki sonuçlar tartışmalıdır. Bazı düşünürler teoremlerden insan zihninin hiçbir makineyle eşdeğer olmadığı sonucunu çıkarmaya çalışmıştır. Mantıkçıların önemli bir kısmı bu çıkarımın teoremlerin kendisinden kaynaklanmadığını, ek varsayımlara dayandığını savunur. Bu, açık bir felsefe tartışmasıdır.

Neden önemli?

• Bilgisayar bilimi: Gödel’in fikirleri, birkaç yıl sonra Alan Turing’in bazı problemlerin hiçbir algoritmayla çözülemeyeceğini göstermesine zemin hazırladı. Bu bağı Turing makinesi yazımızda görebilirsiniz.
• Kodlama fikri: Önermeleri sayılara çevirmek, bugün programların ve verilerin sayılarla temsil edilmesinin kavramsal bir öncüsüdür.
• İspatın doğası: Lisede tanıştığımız aksiyom, tanım ve ispat kavramlarının ne kadar derin sorular taşıdığını gösterir. İspatın neden önemli olduğunu ispat nedir yazımızda tartışıyoruz.

Kapanış

Gödel matematiğin sonunu getirmedi. Aksine, matematiğin kendi sınırlarını da matematikle inceleyebileceğini gösterdi. Teoremlerin gücü, iddialarının kesinliğinden gelir: Hangi sistem, hangi koşul, hangi tür kanıt? Bu soruları sormadan yapılan her “Gödel’e göre her şey belirsiz” yorumu, teoremin kendisinden çok uzağa düşer.