Tamlık teoremi

Açılış sahnesi

Kerem, kataloğun en eski kayıtlarından birini okuyor: "Her nüsha için, onu kopyalayan bir müstensih vardır." Cümle sıradan görünüyor. Ama Kerem, onu bir biçimsel sisteme yazmaya çalışınca, cümlenin iki niceleyicinin iç içe geçmesinden oluştuğunu fark ediyor. "Her nüsha için" bir evrensel niceleyiciydi, "bir müstensih vardır" ise onun kapsamı içindeki bir varoluşsal niceleyici. Cümle, her nüshaya bir müstensih eşliyordu, ama hangi müstensihi eşlediğini söylemiyordu.

Tolga, tamlık teoreminin bu tür cümleler için ne söylediğini soruyor. Teorem, tutarlı her kümenin bir modeli olduğunu söylüyordu. Ama bu model nereden gelecekti? Selin, önceki çalışmalarında kayıtların kendi adlarından bir model kurduklarını hatırlıyor ve bu modelin hep sayılabilir büyüklükte olduğunu fark ediyor. Lina, bir sözlüğün sözcüklerinin sabit bir dünyayı mı yoksa değişebilen dünyaları mı betimlediğini merak ediyor. Barış, bir kayıt sisteminin iki listenin eşit uzunlukta olduğunu gösteren bir belgeye sahip olmadığında, bu listelerin sistem içinde eşit sayılıp sayılamayacağını düşünüyor. Defne ise bulgu değerlerini gerçek sayılarla ölçen bir kılavuzun, gerçek sayıların sayılamaz çokluğunu gerçekten ifade edip edemediğini soruyor. Bu ders, Mantık ve Akıl Yürütme programının Metalojik ve Hesaplanabilirlik kursunda, birinci derece mantığın tamlık teoreminin bu mantığın niceleyicilerine ve modellerine özgü içeriğini, Gödel'in kanıtının izlediği yolu ve teoremin birinci derece mantığın modelleri hakkında, özellikle sonsuz modeller hakkında, hangi sonuçlar doğurduğunu soruyor.

Bu derste ne olacak

Önce bu dersin yerini belirleyelim. Metateori modülü, nesne dili ile üst dil ayrımını, biçimsel sistem kavramını, sesliliği, tamlığı ve karar verilebilirliği inceledi. Tamlık dersi, teoremi seslilikle karşılaştırmış ve Henkin'in tanık sabitlerine dayanan kanıtını, Lindström'ün teoremini ve tıkızlık teoremini tanıtmıştı. Programın Yüklemler Mantığı kursunda ise Gödel'in 1930 tarihli makalesi, Skolem'in çoklu nicelemenin yapısını açıklayan 1920 tarihli çalışması ve Löwenheim'ın 1915 tarihli sonuçları ele alınmış, Etchemendy'nin mantıksal sonuç eleştirisi de tartışılmıştı. Bu ders, Birinci derece mantık modülünü açıyor: tamlık teoremini bu kez bir üst kuram sonucu olarak değil, birinci derece mantığın niceleyicileri ve modelleri hakkında bir teorem olarak ele alıyor.

Sonra üç kaynağa bakacağız. Kurt Gödel, 1930'da yayımladığı Mantıksal İşlevler Hesabının Aksiyomlarının Tamlığı makalesinde, tamlığı, her formülü niceleyicileri başa toplanmış bir biçime indirgeyerek ve adım adım genişleyen sonlu yaklaşımlardan bir model kurarak kanıtlar. Thoralf Skolem, 1922'de verdiği ve 1923'te yayımlanan Küme Kuramının Aksiyomatik Temellendirilmesi Üzerine Birkaç Not konferansında, küme kuramının sayılabilir bir modeli olması gerektiğini ve bunun doğurduğu tuhaflığı tartışır. Warren Goldfarb ise 1979'da yayımladığı Yirmili Yıllarda Mantık: Niceleyicinin Doğası makalesinde, tamlık sorusunun ancak niceleyicinin belirli bir anlayışıyla sorulabilir hâle geldiğini gösterir.

Ardından üç itirazı tartacağız: Gödel'in kanıtının yapıcı olmadığı, Skolem'in sonucunun birinci derece mantığın matematik için yetersiz olduğunu gösterdiği ve teoremin mantıksal doğruluğu değil, yalnızca onun biçimsel bir yorumunu yakaladığı itirazları.

Sonda, bir birinci derece kuramın modellerini değerlendirmenin dört adımını göstereceğiz: kuramın cümlelerini niceleyicileri başa toplanmış biçime getirmek, varoluşsal niceleyicilerin nasıl tanıklarla karşılanacağını belirlemek, sonlu yaklaşımların her birinin tutarlı olup olmadığını sınamak ve kurulan modelin büyüklüğünü ve amaçlanan modelle ilişkisini yazmak.

Merkez soru

Sorumuz şu: birinci derece mantığın tamlık teoremi bu mantığın niceleyicileri ve modelleri hakkında ne söyler ve teoremin kanıtından sonsuz modeller hakkında hangi sonuçlar çıkar?

Ölçülü iddiam şu: tamlık teoremi, birinci derece mantığın niceleyicilerinin, yalnızca bir nesneler alanı üzerinde dolaşan niceleyiciler olarak anlaşıldığında, kanıt kurallarıyla tam olarak yakalanabildiğini söyler. Goldfarb'ın gösterdiği gibi, bu anlayış kendiliğinden verili değildi. Niceleyicinin, değişebilen bir alan üzerinde dolaşan bir işleç olarak görülmesi, tamlık sorusunun sorulabilmesinin önkoşuluydu. Gödel'in kanıtı, her formülü, niceleyicileri başa toplanmış ve evrenselleri varoluşsallardan önce gelen bir biçime indirger. Sonra, formülün çürütülemediği varsayımından, adım adım genişleyen sonlu yaklaşımlar kurar. Her yaklaşım, önermeler mantığıyla denetlenebilir. Bu yaklaşımların hepsi tutarlıysa, onlardan doğal sayılar üzerinde bir model kurulur. Kanıtın bu yapısı, teoremin önemli bir sonucunu da verir. Tutarlı her kümenin, sayılabilir büyüklükte bir modeli vardır. Bu sonuç, Löwenheim ile Skolem'in adıyla anılır. Skolem'in gösterdiği gibi, bu sonuç, sayılamaz kümelerin varlığını kanıtlayan küme kuramının da sayılabilir bir modeli bulunduğunu söyler. Bu bir çelişki değildir, çünkü "sayılamaz" kavramı bir modelin içinden ve dışından farklı görünür. Ama birinci derece mantığın, sonsuz yapıları büyüklükleriyle birlikte tam olarak betimleyemediğini gösterir. Tamlığın bedeli, birinci derece bir kuramın amaçlanan modelini tek başına belirleyememesidir.

Sıfır noktası

Bir öğrenci tamlık teoremini öğrendiğinde, onu çoğu zaman bir güvence olarak duyar: geçerli olan her şey kanıtlanabilir. Bu doğrudur. Ama teoremin birinci derece mantığa özgü bir içeriği vardır ve bu içerik, niceleyicilerin nasıl anlaşıldığına bağlıdır.

Birinci derece mantıkta niceleyiciler, bir nesneler alanı üzerinde dolaşır. "Her şey" ve "bir şey" sözcükleri, bu alanın nesnelerini kapsar. Alan her modelde başka olabilir: bir modelde el yazmaları, başka bir modelde doğal sayılar, başka bir modelde tek bir nesne. Bir formül geçerliyse, alanı ne olursa olsun her modelde doğrudur. Tamlık teoremi, bu anlamda geçerli her formülün kanıtlanabildiğini söyler.

Teoremi kanıtlamak için, çürütülemeyen bir formülün bir modelini kurmak gerekir. Bu model bir alana ihtiyaç duyar. Gödel'in ve daha önce görülen Henkin'in kanıtlarında, bu alan formülün kendi terimlerinden ya da doğal sayılardan kurulur. Her iki durumda da alan sayılabilirdir. Tamlığın kanıtı, bu yüzden, sayılabilir modeller hakkında bir şey söylemeden tamamlanamaz.

Görüşler ve pozisyonlar

Tamlık teoreminin birinci derece mantık hakkında ne gösterdiği konusunda üç görüş var.

Birinci görüş, yeterlilik görüşüdür. Buna göre tamlık teoremi, birinci derece mantığın matematiğin ve bilimin mantığı olarak yeterli olduğunu gösterir. Bu mantıkta her geçerli çıkarım kanıtlanabilir ve bu, bir mantıktan beklenebilecek en güçlü güvencedir.

İkinci görüş, sınır görüşüdür. Buna göre tamlık teoremi, onunla birlikte gelen Löwenheim ve Skolem sonuçlarıyla, birinci derece mantığın sonsuz yapıları tam olarak betimleyemediğini gösterir. Bu mantıkla yazılmış bir kuram, amaçlanan modelinin yanında istenmeyen modellere de sahiptir ve onları dışarıda bırakamaz.

Üçüncü görüş, göreliliğe dayalı görüştür. Buna göre tamlık teoremi ve Skolem'in sonucu, küme kuramının "sayılamaz" gibi kavramlarının mutlak değil, bir modele göreli olduğunu gösterir. Bu görelilik, birinci derece mantığın bir kusuru değil, matematiksel kavramların doğası hakkında bir bilgidir.

Bu ders ikinci görüşü temel alır ve birinci görüşün, tamlığın güçlü bir güvence olduğu gözlemini kabul eder. Birinci görüş, birinci derece mantıkta kanıtlanabilirlik ile geçerliliğin örtüştüğünü doğru görür. Ama bu örtüşmenin, kuramların amaçlanan modellerini belirleme gücünün kaybıyla birlikte geldiğini hesaba katmaz. Üçüncü görüş, Skolem'in kendisinin vardığı sonucu doğru yakalar. Ama göreliliğin, matematikçilerin "sayılamaz" derken kastettikleri şeyin de göreli olduğunu gösterip göstermediği tartışmalıdır. İkinci görüş, sınırı kabul eder ve onun ne kadar derin olduğunu sorar.

Argümanın yapısı

Bir birinci derece kuramın modellerini değerlendirmek için dört adım izlenebilir.

Birinci adım, kuramın cümlelerini niceleyicileri başa toplanmış biçime getirmektir. Değerlendiren, her cümlenin niceleyicilerini başa toplar ve evrensel niceleyicilerin varoluşsallardan önce geldiği biçimi kurar.

İkinci adım, varoluşsal niceleyicilerin nasıl tanıklarla karşılanacağını belirlemektir. Değerlendiren, her varoluşsal niceleyici için, onu karşılayan nesneyi veren bir ad ya da bir işlev tanımlar.

Üçüncü adım, sonlu yaklaşımların her birinin tutarlı olup olmadığını sınamaktır. Değerlendiren, belirli sayıda ad kullanan yaklaşımları kurar ve her birini önermeler mantığıyla denetler. Bir yaklaşım tutarsızsa, kuramın modeli yoktur.

Dördüncü adım, kurulan modelin büyüklüğünü ve amaçlanan modelle ilişkisini yazmaktır. Değerlendiren, yaklaşımlardan kurulan modelin sayılabilir olduğunu not eder ve bu modelin, kuramın betimlemek istediği yapıyla aynı olup olmadığını sorar.

En güçlü itiraz

Bu yaklaşıma üç yönden ciddi itiraz yapılabilir.

Tamlık teoremini ciddiye alan düşünce şu cevabı verebilir. Tamlık teoremi, birinci derece mantığın niceleyicilerinin, bir nesneler alanı üzerinde dolaşan niceleyiciler olarak anlaşıldığında, kanıt kurallarıyla tam olarak yakalanabildiğini söyler. Goldfarb'ın gösterdiği ve Lina'nın iki sözlüğünde görülen gibi, bu anlayış evrenselci anlayıştan sonra kazanılmıştı ve tamlık sorusunun sorulabilmesinin önkoşuluydu. Gödel'in kanıtı, her formülü Skolem normal biçimine indirger ve Kerem'in müstensih cümlesinde ve Tolga'nın sonlu yaklaşımlarında görüldüğü gibi, adım adım genişleyen sonlu yaklaşımlardan doğal sayılar üzerinde bir model kurar. Bu yapı, tutarlı her kümenin sayılabilir bir modeli bulunduğunu verir. Skolem'in gösterdiği gibi, bu sonuç, sayılamaz kümelerin varlığını kanıtlayan küme kuramının da sayılabilir bir modeli olduğunu söyler. Barış'ın eşleme belgesinde görüldüğü gibi, bu bir çelişki değildir, çünkü "sayılamaz" kavramı modelin içinden ve dışından farklı görünür. Ama Selin'in sayı modelinde görüldüğü gibi, birinci derece bir kuram, sonsuz bir yapıyı betimlediğinde amaçlanan modelini tek başına belirleyemez. Tamlığın bedeli budur. Defne'nin gerçek sayı ölçütlerinde görüldüğü gibi, bu bedel, pratikte çoğu zaman ödenebilir bir bedeldir.

Açık kalan sorular

Selin'in sayı modeli, birinci derece bir kuramın amaçlanan modelini tek başına belirleyemediğini gösterdi. Öyleyse bir matematikçi, doğal sayılardan ya da gerçek sayılardan söz ederken, amaçlanan modeli nasıl belirler? Bu belirleme, bir kuramın dışında kalan bir sezgiye mi dayanır?

Barış'ın eşleme belgesi, "sayılamaz" kavramının bir modelin içinden ve dışından farklı göründüğünü gösterdi. Dışarıdan bakan biri, kendisi de başka bir modelin içinde değil midir? Mutlak olarak sayılamaz bir küme var mıdır, yoksa her sayılamazlık bir bakış açısına mı göredir?

Lina'nın iki sözlüğü, bir konuşanın bazen gerçekten her şeyi kastettiğini düşündürdü. Model kuramsal anlayış, niceleyicilerin her zaman sınırlı bir alan üzerinde dolaştığını varsayıyorsa, "her şey hakkında" konuşan bir cümle nasıl anlaşılmalıdır? Mutlak genellik, birinci derece mantıkla ifade edilebilir mi?

Yaygın hatalar

Kendin dene

Aklında kalsın

Beş cümlede dersin iskeleti.

Tamlık teoremi, birinci derece mantığın niceleyicilerinin, değişebilen bir nesneler alanı üzerinde dolaşan niceleyiciler olarak anlaşıldığında, kanıt kurallarıyla tam olarak yakalanabildiğini söyler ve bu anlayış, mantığın evrenselci anlayışından sonra kazanılmıştır.

Gödel'in 1930 tarihli makalesi tamlığı her formülü Skolem normal biçimine indirgeyip sonlu yaklaşımlardan doğal sayılar üzerinde bir model kurarak kanıtladı, Skolem'in 1922 tarihli konferansı küme kuramının sayılabilir bir modeli bulunduğunu ve bunun "sayılamaz" kavramını göreli kıldığını gösterdi, Goldfarb'ın 1979 tarihli makalesi ise tamlık sorusunun niceleyicinin model kuramsal anlayışına dayandığını gösterdi.

Bir birinci derece kuramın modelleri dört adımla değerlendirilir: cümleleri niceleyicileri başa toplanmış biçime getirmek, varoluşsal niceleyicilerin tanıklarını belirlemek, sonlu yaklaşımların tutarlılığını sınamak ve kurulan modelin büyüklüğünü ve amaçlanan modelle ilişkisini yazmak.

Gödel'in kanıtının yapıcı olmadığı, Skolem'in sonucunun birinci derece mantığı yetersiz kıldığı ve teoremin yalnızca biçimsel bir geçerliliği yakaladığı itirazları, teoremin klasik bir metateorem olarak açıkça konumlandırılabildiğini, sınırın daha güçlü mantıkların tamlığı yitirmesiyle dengelendiğini ve sıkıştırma argümanının teoremi sezgisel geçerliliğe bağladığını gördüğümüzde cevaplanabilir.

Bu yüzden tamlık teoremi, birinci derece mantığa hem kanıtlanabilirlik ile geçerliliğin örtüşmesini hem de sonsuz yapıları tam olarak belirleyememe sınırını verir ve bu iki sonuç aynı kanıttan çıkar.

Sonraki derse köprü

Tolga'nın sonlu yaklaşımları, bir kuramın her sonlu parçası tutarlıysa kuramın bütününün de bir modeli bulunduğunu gösteriyordu. Tolga, bu gözlemin kendi başına ne kadar güçlü olduğunu fark ediyor. Bir kuram sonsuz sayıda cümleden oluşsa bile, onun bir modelini bulmak için yalnızca sonlu parçalarına bakmak yetiyordu.

Defne, bu gözlemi tuhaf bir kurama uyguluyor. Kuram, "en az bir hasta vardır", "en az iki hasta vardır", "en az üç hasta vardır" diye sonsuza kadar giden cümlelere, bir de "hastaların sayısı sonludur" cümlesini eklemeye çalışıyordu. Defne, son cümlenin birinci derece mantıkta yazılıp yazılamayacağını soruyor. Kerem, doğal sayılar hakkındaki bir kurama, "bu sayı birden büyüktür", "bu sayı ikiden büyüktür" diye sonsuza kadar giden cümleler eklendiğinde ne olacağını merak ediyor. Selin, bu cümlelerin her sonlu parçasının doğal sayılarda karşılanabildiğini, ama bütününün karşılanamadığını söylüyor.

Bir sonraki ders bu soruya dönüyor. Kompaktlık dersi, sonsuz bir cümle kümesinin her sonlu parçası karşılanabilirse bütününün de karşılanabilir olmasının birinci derece mantıkta hangi beklenmedik modelleri doğurduğunu, bu özelliğin doğal sayıların standart olmayan modellerini nasıl ortaya çıkardığını ve birinci derece mantığın sonluluk gibi kavramları neden tanımlayamadığını soruyor.