Tarski'nin tanımlanamazlık teoremi - Tarski's undefinability theorem

1933'te Alfred Tarski tarafından belirtilen ve kanıtlanan Tarski'nin tanımlanamazlık teoremi , matematiksel mantıkta , matematiğin temellerinde ve biçimsel anlambilimde önemli bir sınırlayıcı sonuçtur . Gayri resmi olarak, teorem, aritmetik gerçeğin aritmetikte tanımlanamayacağını belirtir .

Teorem, daha genel olarak , sistemin standart modelindeki gerçeğin sistem içinde tanımlanamayacağını gösteren, yeterince güçlü herhangi bir resmi sisteme uygulanır .

Tarih

1931'de Kurt Gödel , birinci dereceden aritmetik içinde biçimsel mantığın sözdiziminin nasıl temsil edileceğini göstererek kısmen kanıtladığı eksiklik teoremlerini yayınladı . Aritmetiğin biçimsel dilinin her bir ifadesine ayrı bir sayı atanır. Bu prosedür çeşitli şekillerde Gödel numaralandırma , kodlama ve daha genel olarak aritmetizasyon olarak bilinir . Özellikle, çeşitli kümeler ifadelerin sayı kümesi olarak kodlanmıştır. (Örneğin, çeşitli sözdizimsel özellikleri için bir formül olan , bir cümle olarak , vs.), bu kümeleridir hesaplanabilir . Ayrıca, herhangi bir hesaplanabilir sayı kümesi, bazı aritmetik formüllerle tanımlanabilir. Örneğin, aritmetik dilinde, aritmetik cümleler ve kanıtlanabilir aritmetik cümleler için kod kümesini tanımlayan formüller vardır.

Tanımlanamazlık teoremi, doğruluk gibi anlamsal kavramlar için bu kodlamanın yapılamayacağını göstermektedir . Yeterince zengin bir yorumlanmış dilin kendi semantiğini temsil edemeyeceğini gösterir. Doğal bir sonucu, herhangi olmasıdır üst dildir bazı semantik ifade edebilen nesne dili nesne dili aşan ifade gücüne sahip olmalıdır. Üstdil, nesne dilinde olmayan ilkel kavramları, aksiyomları ve kuralları içerir, böylece üst dilde kanıtlanabilen teoremler, nesne dilinde kanıtlanamayan teoremler vardır.

Tanımlanamazlık teoremi geleneksel olarak Alfred Tarski'ye atfedilir . Gödel, 1931'de ve 1933'te Tarski'nin çalışmasının yayınlanmasından çok önce yayınlanan eksiklik teoremlerini kanıtlarken, 1930'da tanımlanamazlık teoremini de keşfetti (Murawski 1998). Gödel, tanımlanamazlığın bağımsız keşfiyle ilgili hiçbir şey yayınlamamış olsa da, bunu 1931'de John von Neumann'a yazdığı bir mektupta tanımladı . Tarski, 1933'te yazdığı " Pojęcie Prawdy w Językach Nauk Dedukcyjnych " (" Tümdengelimli Bilimlerin Dillerinde Hakikat Kavramı ") adlı monografisinin neredeyse tüm sonuçlarını 1929 ve 1931 yılları arasında elde etmiş ve Polonyalı dinleyicilere bu sonuçlar hakkında konuşmuştu. Ancak makalede vurguladığı gibi, daha önce elde edemediği tek sonuç tanımlanamazlık teoremiydi. 1933 monografının tanımlanamazlık teoreminin (Twierdzenie I) dipnotuna göre, teorem ve ispatın taslağı, ancak el yazması 1931'de matbaaya gönderildikten sonra monografiye eklendi. 21 Mart 1931'de Varşova Bilim Akademisi'ne yazdığı monografinin içeriğinde, burada kısmen kendi araştırmalarına ve kısmen Gödel'in eksiklik teoremleri hakkındaki kısa raporuna dayanan sadece bazı varsayımları ifade etti "Einige metamathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit ", Wien'de Akademie der Wissenschaften, 1930.

Beyan

Önce Tarski teoreminin basitleştirilmiş bir versiyonunu ifade edeceğiz, sonra bir sonraki bölümde Tarski'nin 1933'te kanıtladığı teoremi ifade edip ispatlayacağız. L birinci mertebeden aritmetiğin dili olsun ve N , L için standart yapı olsun . Böylece ( L , N ) "aritmetiğin yorumlanan birinci derece dilidir". L' deki her x formülünün bir Gödel sayısı g ( x ) vardır. Let T kümesini belirtir L -formulas doğru olarak N ve T * formüller Gödel'in numaralarının grubu T . Aşağıdaki teorem soruyu yanıtlar: T *, birinci dereceden aritmetik formülüyle tanımlanabilir mi?

Tarski'nin tanımlanamazlık teoremi : T *'yi tanımlayan bir L- formülü True ( n ) yoktur . Kendisine, orada hiçbir L -Formül doğru ( n her için bu), örneğin L -Formül A , gerçek ( g ( A )) ↔ bir tutar.

Gayri resmi olarak, teorem, belirli bir biçimsel aritmetik verildiğinde, o aritmetikteki doğruluk kavramının, o aritmetiğin sağladığı ifade araçları kullanılarak tanımlanamayacağını söyler. Bu, "öz-temsil" kapsamında büyük bir sınırlama anlamına gelir. Olduğu bir formül tanımlamak mümkündür True ( n olan uzantısıdır) T *, ama sadece çizerek üstdil olan ifade gücü ötesine geçer , L . Örneğin, birinci dereceden aritmetik için bir doğruluk yüklemi , ikinci dereceden aritmetikte tanımlanabilir . Bununla birlikte, bu formül yalnızca orijinal dilde L' deki formüller için bir doğruluk yüklemi tanımlayabilecektir . Üstdil için bir doğruluk yüklemi tanımlamak, daha da yüksek bir metametadil vb. gerektirir.

Az önce ifade edilen teorem, Post'un aritmetik hiyerarşi hakkındaki teoreminin bir sonucuydu, Tarski'den (1933) birkaç yıl sonra kanıtlandı. Post'un teoreminden Tarski teoreminin anlamsal kanıtı aşağıdaki gibi reductio ad absurdum ile elde edilir . Varsayarak , T *, bir doğal sayı olduğu, aritmetik olarak tanımlanabilir olması , n olacak şekilde , T * düzeyde bir formül ile tanımlanabilir olması ve aritmetik hiyerarşi . Ancak, T * tüm k için -zordur . Böylece aritmetik hiyerarşi , Post'un teoremiyle çelişerek n düzeyinde çöker .

Genel form

Tarski, tamamen sözdizimsel bir yöntem kullanarak, yukarıda belirtilenden daha güçlü bir teoremi kanıtladı. Ortaya çıkan teorem, olumsuzlamalı ve köşegen lemmanın sahip olduğu kendine referans için yeterli kapasiteye sahip herhangi bir resmi dile uygulanır . Birinci dereceden aritmetik bu önkoşulları karşılar, ancak teorem çok daha genel biçimsel sistemler için geçerlidir.

Tarski'nin tanımlanamazlık teoremi (genel biçim) : ( L , N ) olumsuzlamayı içeren ve g ( x ) Gödel numaralandırmasına sahip herhangi bir yorumlanmış biçimsel dil olsun, öyle ki her L- formülü A ( x ) için bir formül B vardır, öyle ki B ↔ A ( g ( B )) N'de tutar . Let T * ait Gödel sayıların kümesi L gerçek -Formül N . O zaman T *'yi tanımlayan L -formula True ( n ) yoktur . Kendisine, orada hiçbir L -Formül doğru ( n ) bu tür her için L -Formül A , gerçek ( g ( A )) ↔ bir gerçek kendisi N .

Tarski'nin tanımlanamazlık teoreminin bu formdaki kanıtı yine reductio ad absurdum iledir . Bir L formülünün True ( n ) öğesinin T * tanımladığını varsayalım . Özel olarak, bir aritmetik, daha sonra bir formül doğru ( g ( A )) içinde tutan , N , ancak ve ancak bir tutan N . Bu nedenle, tüm A için , True ( g ( A )) ↔ A formülü N'de geçerlidir . Ancak köşegen lemma , S ↔ ¬ True ( g ( S )) N'de geçerli olacak şekilde "yalancı" bir S formülü vererek bu eşdeğerliğe bir karşı örnek verir . Bu nedenle, hiçbir L formülü True ( n ) T * tanımlayamaz . QED.

Bu ispatın biçimsel mekanizması, köşegen lemmanın gerektirdiği köşegenleştirme dışında tamamen temeldir. Çapraz lemmanın ispatı da aynı şekilde şaşırtıcı derecede basittir; örneğin, özyinelemeli işlevleri hiçbir şekilde çağırmaz . Kanıt, her L formülünün bir Gödel numarasına sahip olduğunu varsayar , ancak bir kodlama yönteminin özellikleri gerekli değildir. Bu nedenle Tarski'nin teoremi, birinci dereceden aritmetiğin metamatematiksel özellikleri hakkında Gödel'in daha ünlü teoremlerinden çok daha kolay motive edilir ve kanıtlanır .

Tartışma

Smullyan (1991, 2001), Tarski'nin tanımlanamazlık teoreminin, Gödel'in eksiklik teoremlerinin topladığı ilginin çoğunu hak ettiğini güçlü bir şekilde savundu . İkinci teoremlerin tüm matematik hakkında ve daha tartışmalı olarak, bir dizi felsefi konu hakkında (örneğin, Lucas 1961) söyleyecek çok şeyi olduğu çok açık değildir. Öte yandan Tarski'nin teoremi, doğrudan matematikle ilgili değil, gerçek ilgiyi çekecek kadar ifade edici herhangi bir biçimsel dilin doğasında bulunan sınırlamalarla ilgilidir. Bu tür diller , diyagonal lemmanın kendilerine uygulanabilmesi için zorunlu olarak yeterli öz referansa sahiptir . Tarski'nin teoreminin daha geniş felsefi anlamı daha çarpıcı biçimde açıktır.

Yorumlanmış bir dil, tam olarak dil, dile özgü tüm anlamsal kavramları tanımlayan yüklemler ve işlev sembolleri içerdiğinde , güçlü bir şekilde anlamsal olarak kendini temsil eder . Bu nedenle, gerekli olan fonksiyonlar bir formül eşleme "anlam değerleme fonksiyonu" içerir A onun için gerçek değeri || A || ve bir t terimini gösterdiği nesneye eşleyen "anlamsal ifade işlevi" . Tarski'nin teoremi daha sonra şu şekilde genellenir: Yeterince güçlü hiçbir dil, güçlü bir şekilde anlamsal olarak kendini temsil etmez .

Tanımlanamazlık teoremi, bir teorideki gerçeğin daha güçlü bir teoride tanımlanmasını engellemez. Örneğin, N'de doğru olan birinci dereceden Peano aritmetiğinin formülleri (kodları) ikinci dereceden aritmetikte bir formülle tanımlanabilir . Benzer şekilde, ikinci sıra aritmetik (veya standart model gerçek formüllerin grubu , n herhangi inci sipariş aritmetik n ) birinci dereceden bir formül ile tanımlanabilir ZFC .

Ayrıca bakınız

Referanslar

  • JL Bell ve M. Machover, 1977. Matematiksel Mantıkta Bir Kurs . Kuzey Hollanda.
  • G. Boolos , J. Burgess ve R. Jeffrey , 2002. Hesaplanabilirlik ve Mantık , 4. baskı. Cambridge Üniversitesi Yayınları.
  • JR Lucas , 1961. " Zihin, Makineler ve Gödel ". Felsefe 36: 112-27.
  • R. Murawski, 1998. Gerçeğin tanımlanamazlığı. Öncelik sorunu: Tarski vs. Gödel . Mantık Tarihi ve Felsefesi 19, 153–160
  • R. Smullyan , 1991. Gödel'in Eksiklik Teoremleri . Oxford Üniv. Basın.
  • R. Smullyan , 2001. "Gödel'in Eksiklik Teoremleri". In L. Goble, ed., The Blackwell Guide to Philosophical Logic , Blackwell, 72-89.
  • A. Tarski , 1933. Pojęcie Prawdy w Językach Nauk Dedukcyjnych . Nakładem Towarzystwa Naukowego Warszawskiego.
  • A. Tarski (1936). "Der Wahrheitsbegriff in den formalisierten Sprachen" (PDF) . Studia Philosophica'nın fotoğrafı . 1 : 261-405. Arşivlenmiş orijinal (PDF) 9 Ocak 2014 tarihinde . 26 Haziran 2013 alındı .