Brouwer – Heyting – Kolmogorov yorumu - Brouwer–Heyting–Kolmogorov interpretation

Olarak matematiksel mantık , Brouwer-Heyting-Kolmogorov yorumlanması veya BHK yorumlama , bir sezgisel mantığı tarafından önerilen LEJ Brouwer ve Arend Heyting göre, bağımsız bir şekilde, ve Andrey Kolmogorov . Stephen Kleene'nin gerçekleştirilebilirlik teorisi ile bağlantısı nedeniyle bazen gerçekleştirilebilirlik yorumu olarak da adlandırılır .

Yorum

Yorum, belirli bir formülün kanıtı olması amaçlanan şeyi belirtir . Bu, bu formülün yapısında tümevarım ile belirtilir :

• Bir kanıtı bir çift <olan bir ,  b > bir bir kanıtıdır ve b bir kanıtıdır . ${\ displaystyle P \ kama Q}$${\ displaystyle P}$${\ displaystyle Q}$
• Bir kanıtı, bir çift <olan bir ,  b burada> bir 0 ve b bir kanıtıdır veya bir 1 olduğu ve B bir kanıtıdır . ${\ displaystyle P \ vee Q}$${\ displaystyle P}$${\ displaystyle Q}$
• Bir kanıtı bir fonksiyondur bir kanıt dönüştüren bir kanıtı içine . ${\ displaystyle P \ ila Q}$${\ displaystyle f}$${\ displaystyle P}$${\ displaystyle Q}$
• Bir kanıtı bir < a ,  b > çiftidir ve burada a , S'nin bir elemanıdır ve b'nin bir kanıtıdır . ${\ displaystyle \ S: \ varphi (x) içinde x \ var}$${\ displaystyle \ varphi (a)}$
• Bir kanıtı bir fonksiyonu olan bir eleman dönüştürür a ait S bir kanıtı olarak . ${\ displaystyle \ forall x \ S: \ varphi (x)}$${\ displaystyle f}$${\ displaystyle \ varphi (a)}$
• Formül olarak tanımlanır bunun bir kanıtıdır bir fonksiyonu olan, böylece, f bir kanıtıdır dönüştürür bir kanıtı olarak . ${\ displaystyle \ neg P}$${\ displaystyle P \ ila \ bot}$${\ displaystyle P}$${\ displaystyle \ bot}$
• (Saçma veya alt tip (bazı programlama dillerinde sonlandırmama)) kanıtı yoktur . ${\ displaystyle \ bot}$

İlkel bir önermenin yorumunun bağlamdan bilindiği varsayılır. Aritmetik bağlamında, s = t formülünün bir kanıtı , iki terimi aynı rakama indirgeyen bir hesaplamadır.

Kolmogorov da aynı çizgileri takip etti ama yorumunu problemler ve çözümler açısından ifade etti. Bir formül ileri sürmek, o formülle temsil edilen soruna bir çözüm bildiğini iddia etmektir. Örneğin indirgeme sorunudur Q için P ; Bunu çözmek için, P problemine bir çözüm verildiğinde  Q problemini çözmek için bir yöntem gerekir . ${\ displaystyle P \ ila Q}$

Örnekler

Özdeşlik işlevi, P ne olursa olsun formülün bir kanıtıdır . ${\ displaystyle P \ ila P}$

Çelişkisizlik yasası şu şekilde genişler : ${\ displaystyle \ neg (P \ kama \ neg P)}$${\ displaystyle (P \ kama (P \ bottan \ bot)) \ bota}$

• Bir kanıtı bir fonksiyondur bir kanıt dönüştüren bir kanıtı içine . ${\ displaystyle (P \ kama (P \ bottan \ bot)) \ bota}$${\ displaystyle f}$${\ displaystyle (P \ kama (P \ den \ bot))}$${\ displaystyle \ bot}$
• Bir kanıtı, < a ,  b > ispatıdır , burada P'nin bir kanıtıdır ve bir kanıtıdır . ${\ displaystyle (P \ kama (P \ den \ bot))}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle P \ ila \ bot}$
• Bir kanıtı, bir kanıtı dönüştüren bir fonksiyonudur P bir kanıtı olarak . ${\ displaystyle P \ ila \ bot}$${\ displaystyle \ bot}$

Hep birlikte koyarak, bir kanıtıdır bir işlevdir dönüştürür bir çift <o bir ,  b > - nerede bir kanıtıdır P ve bir fonksiyondur dönüştüren bir kanıtı P bir kanıtı içine - bir kanıtı içine . Bunu yapan, P ne olursa olsun, çelişkisizlik yasasını kanıtlayan bir işlev vardır . ${\ displaystyle (P \ kama (P \ bottan \ bot)) \ bota}$${\ displaystyle f}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle \ bot}$${\ displaystyle \ bot}$${\ displaystyle f}$${\ Displaystyle f (\ langle a, b \ rangle) = b (a)}$

Nitekim, aynı düşünce çizgisi , herhangi bir önermenin nerede olduğu için de bir kanıt sağlar . ${\ displaystyle (P \ kama (P \ ila Q)) \ ila Q}$${\ displaystyle Q}$

Öte yandan, dışlanmış orta yasası genişler ve genel olarak hiçbir kanıtı yoktur. Yoruma göre, bir kanıtı < a ,  b > çiftidir ; burada a , 0 ve b , P'nin bir kanıtıdır veya a , 1 ve b'nin bir kanıtıdır . Dolayısıyla, ne P ne de kanıtlanabilir değilse , o zaman da kanıtlanamaz . ${\ displaystyle P \ vee (\ neg P)}$${\ displaystyle P \ vee (P \ bottan \ bota)}$${\ displaystyle P \ vee (\ neg P)}$${\ displaystyle P \ ila \ bot}$${\ displaystyle P \ ila \ bot}$${\ displaystyle P \ vee (\ neg P)}$

Saçma nedir?

Genel olarak, mantıksal bir sistemin resmi bir olumsuzlama operatörüne sahip olması mümkün değildir, öyle ki bir kanıtı olmadığında tam olarak "değil" kanıtı vardır ; bkz Gödel'in eksiklik teoremleri . Bunun yerine BHK yorumu , saçmalığa yol açan anlamını "değil" olarak alır , böylece bir ispatı, bir ispatı saçmalığın kanıtına dönüştüren bir işlevdir . ${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle \ bot}$${\ displaystyle \ lnot P}$${\ displaystyle P}$

Aritmetik ile uğraşırken standart bir saçmalık örneği bulunur. 0 = 1 olduğunu varsayın ve matematiksel tümevarımla devam edin : 0 = 0 eşitlik aksiyomuyla. Şimdi (tümevarım hipotezi), eğer 0 belirli bir n doğal sayıya eşit olsaydı, o zaman 1 n  + 1'e eşit olurdu , ( Peano aksiyomu : S m  =  S n eğer ve sadece m = n ise ), ancak 0 = 1'den beri , dolayısıyla 0, n  + 1'e de eşit olacaktır. Tümevarımla, 0 tüm sayılara eşittir ve bu nedenle herhangi iki doğal sayı eşit olur.

Bu nedenle, 0 = 1 ispatından herhangi bir temel aritmetik eşitliğin ispatına ve dolayısıyla herhangi bir karmaşık aritmetik önermenin ispatına gitmenin bir yolu vardır. Ayrıca, bu sonucu elde etmek için 0'ın herhangi bir doğal sayının ardılı "olmadığını" belirten Peano aksiyomunu çağırmak gerekli değildi. Bu gibi uygun 0 = 1 yapar içinde Heyting aritmetik (ve Peano aksiyomu 0 = yeniden yazılarak  S N → 0 =  S 0). Bu 0 = 1 kullanımı patlama prensibini doğrular . ${\ displaystyle \ bot}$

İşlev nedir?

BHK yorumu, bir ispatı diğerine dönüştüren veya bir alanın bir elemanını ispata dönüştüren bir işlevi neyin oluşturduğuna dair alınan görüşe bağlı olacaktır . Yapılandırmacılığın farklı versiyonları bu noktada birbirinden ayrılacaktır.

Kleene'nin gerçekleştirilebilirlik teorisi, fonksiyonları hesaplanabilir fonksiyonlarla tanımlar . Niceleme alanının doğal sayılar olduğu ve ilkel önermelerin x = y biçiminde olduğu Heyting aritmetiği ile ilgilenir . X = y'nin bir kanıtı, eğer x , y'nin yaptığı sayı ile aynı sayıyı değerlendiriyorsa (ki bu her zaman doğal sayılar için karar verilebilir) basit bir algoritmadır , aksi halde kanıt yoktur. Bunlar daha sonra tümevarımla daha karmaşık algoritmalara dönüştürülür.

Biri sürerse lambda taşı bir işlev kavramını tanımlarken, sonra BHK yorumlama açıklar yazışmaları doğal kesinti ve işlevleri arasında.

Referanslar

• Troelstra, A. (1991). "Yirminci Yüzyılda Yapılandırmacılığın Tarihi" (PDF) . Alıntı günlüğü gerektirir |journal= ( yardım )
• Troelstra, A. (2003). "Yapılandırmacılık ve İspat Teorisi (taslak)". CiteSeerX   10.1.1.10.6972 . Alıntı günlüğü gerektirir |journal= ( yardım )