Çapraz lemma - Diagonal lemma

Gelen matematiksel mantık , diyagonal lemma (olarak da bilinen kösegenlestirilmesi Lemma , kendinden referans lemmasının veya sabit nokta teoremi ) varlığını kurar özüne cümlelerden belli biçimsel teorilerine doğal sayılar -specifically tümünü temsil etmek yeterince güçlü olan bu teoriler hesaplanabilir fonksiyonlar . Varlığı köşegen lemma tarafından güvence altına alınan cümleler daha sonra Gödel'in eksiklik teoremleri ve Tarski'nin tanımlanamazlık teoremi gibi temel sınırlayıcı sonuçları kanıtlamak için kullanılabilir .

Arka fon

Izin vermek doğal sayılar kümesi . Bir teori T temsil hesaplanabilir fonksiyon , bir "grafik" yüklemi mevcutsa dilinde T örneğin her biri için bu , T kanıtlar ${\ displaystyle \ mathbb {N}}$ ${\ displaystyle f: \ mathbb {N} \ rightarrow \ mathbb {N}}$ ${\ displaystyle \ Gama _ {f} (x, y)}$ ${\ displaystyle x \ in \ mathbb {N}}$

{\ displaystyle \ forall y \ quad \ sol ({} ^ {\ circ} f (x) = y \ Leftrightarrow \ Gamma _ {f} ({} ^ {\ circ} x, y) \ sağ)}

.

Burada doğal sayıya karşılık gelen sayı olduğu kapalı dönem 1+ ··· + 1 (olarak tanımlanır, olanlar), ve karşılık gelen sayı olduğu . ${\ displaystyle {} ^ {\ circ} x}$ ${\ displaystyle x}$ ${\ displaystyle x}$ ${\ displaystyle {} ^ {\ circ} f (x)}$ ${\ displaystyle f (x)}$

Köşegen lemma ayrıca her formüle θ Gödel numarası olarak adlandırılan doğal bir sayı # ( θ ) atamanın sistematik bir yolunu gerektirir . Formüller daha sonra teori içinde Gödel sayılarına karşılık gelen sayılarla temsil edilebilir. Örneğin, θ , ° # ( θ ) ile temsil edilir

Köşegen lemma, tüm ilkel özyinelemeli işlevleri temsil edebilen teoriler için geçerlidir . Bu tür teoriler, Peano aritmetiğini ve daha zayıf Robinson aritmetiğini içerir . Lemmanın ortak bir ifadesi (aşağıda verildiği gibi), teorinin tüm hesaplanabilir fonksiyonları temsil edebileceğine dair daha güçlü bir varsayımda bulunur .

Lemmanın ifadesi

Let T bir olmak birinci dereceden aritmetik ve tüm temsil edebilen dilinde teorisi hesaplanabilir fonksiyonlar . F tek serbest değişkenli dilde bir formül olsun , o zaman:

Lemma - Bir cümle var böyle de kanıtlanabilir olan T . ${\ displaystyle \ psi}$ ${\ displaystyle \ psi \ iff F (^ {\ circ} \ # (\ psi))}$

Sezgisel, bir olan kendini referans söyleyerek cümle özelliğine sahiptir F . Cümle , her formüle cümleyi atayan işlemin sabit bir noktası olarak da görülebilir . İspatta inşa edilen cümle , kelimenin tam anlamıyla aynı değildir , ancak T teorisinde kanıtlanabilir bir şekilde eşdeğerdir . ${\ displaystyle \ psi}$ ${\ displaystyle \ psi}$ ${\ displaystyle \ psi}$ ${\ displaystyle \ theta}$ ${\ displaystyle F (^ {\ circ} \ # (\ theta))}$ ${\ displaystyle \ psi}$ ${\ displaystyle F (^ {\ circ} \ # (\ psi))}$

Kanıt

Let f : N → K ile tanımlanır fonksiyonu:

f (# ( θ )) = # ( θ (° # ( θ )))

her T- formülü için θ bir serbest değişkende ve f ( n ) = 0, aksi halde. Fonksiyon f hesaplanabilir, yani, bir formül Γ vardır _f temsil f içinde T . Bu nedenle, her bir formül için İçeride ISTV melerin RWMAIWi'nin , T kanıtlar

(∀ y ) [Γ _f (° # ( θ ), y ) ↔ y = ° f (# ( θ ))],

söylenmek istenen

(∀ y ) [Γ _f (° # ( θ ), y ) ↔ y = ° # ( θ (° # ( θ )))].

Şimdi β ( z ) formülünü şu şekilde tanımlayın :

β ( z ) = (∀ y ) [Γ _f ( z , y ) → F ( y )].

Sonra T ispatlar

β (° # ( θ )) ↔ (∀ y ) [ y = ° # ( θ (° # ( θ ))) → F ( y )],

söylenmek istenen

β (° # ( θ )) ↔ F (° # ( θ (° # ( θ )))).

Şimdi θ = β ve ψ = β (° # ( β )) alın ve önceki cümle , istenen sonuç olan ψ ↔ F (° # ( ψ )) olarak yeniden yazılır .

(Aynı argüman farklı terimlerle [Raatikainen (2015a)] da verilmiştir.)

Tarih

Lemma, Cantor'un köşegen argümanına bir miktar benzerlik taşıdığı için "köşegen" olarak adlandırılır . Terimleri "diyagonal lemma" veya "sabit noktası" görünmez Kurt Gödel 'in 1931 makalesinde veya Alfred Tarski ' ın 1936 makalesinde .

Rudolf Carnap (1934), genel kendini referans veren lemmayı ispatlayan ilk kişiydi ; bu, belirli koşulları sağlayan bir T teorisindeki herhangi bir F formülü için , ψ ↔ F (° # ( ψ )) olacak şekilde bir ψ formülü olduğunu söyler. T olarak kanıtlanabilir . Carnap'ın çalışması, hesaplanabilir işlevler kavramı henüz 1934'te geliştirilmediği için alternatif bir dilde ifade edildi . Mendelson (1997, s. 204), Carnap'ın çapraz lemma gibi bir şeyin Gödel'in muhakemesinde örtük olduğunu belirten ilk kişi olduğuna inanır. Gödel, 1937'de Carnap'ın çalışmalarından haberdardı.

Diyagonal lemma yakından ilişkilidir Kleene'nin tekrarlama teoremi içinde Hesaplama teorisi , ve kendi ispatlar benzerdir.

Ayrıca bakınız

Notlar

Referanslar

George Boolos ve Richard Jeffrey , 1989. Hesaplanabilirlik ve Mantık , 3. baskı. Cambridge University Press. ISBN 0-521-38026-X ISBN 0-521-38923-2
Rudolf Carnap , 1934. Logische Sözdizimi der Sprache . (İngilizce çevirisi: 2003. Mantıksal Dil Sözdizimi . Açık Mahkeme Yayınları.)
Haim Gaifman , 2006. ' Adlandırma ve Köşegenleştirme: Cantor'dan Gödel'e Kleene'ye '. IGPL'nin Mantık Dergisi, 14: 709–728.
Hinman, Peter, 2005. Temel Matematiksel Mantık . AK Peters. ISBN 1-56881-262-0
Mendelson, Elliott , 1997. Matematiksel Mantığa Giriş , 4. baskı. Chapman & Hall.
Panu Raatikainen, 2015a. Köşegenleştirme Lemması . Gelen felsefesi Stanford Ansiklopedisi , ed. Zalta. Raatikainen'e Ek (2015b).
Panu Raatikainen, 2015b. Gödel'in Eksiklik Teoremleri . Gelen felsefesi Stanford Ansiklopedisi , ed. Zalta.
Raymond Smullyan , 1991. Gödel'in Eksiklik Teoremleri . Oxford Üniv. Basın.
Raymond Smullyan, 1994. Köşegenleştirme ve Öz Referans . Oxford Üniv. Basın.
Alfred Tarski (1936). "Der Wahrheitsbegriff in formalisierten Sprachen" (PDF) . Studia Philosophica . 1 : 261–405. 9 Ocak 2014 tarihinde orjinalinden (PDF) arşivlendi . Erişim tarihi: 26 Haziran 2013 . CS1 Maint: önerilmeyen parametre ( bağlantı )
- Alfred Tarski , tr. JH Woodger, 1983. "Biçimlendirilmiş Dillerde Hakikat Kavramı". Tarski'nin 1936 tarihli makalesinin İngilizce çevirisi . A. Tarski, ed. J. Corcoran, 1983, Mantık, Anlambilim, Metamatematik , Hackett.

Languages

In other projects