İspat teorisi - Proof theory

İspat teorisi büyük bir dal^[1] nın-nin matematiksel mantık temsil eden kanıtlar resmi olarak matematiksel nesneler matematiksel tekniklerle analizlerini kolaylaştırmak. Kanıtlar tipik olarak tümevarımsal tanımlanmış olarak sunulur veri yapıları düz listeler, kutulu listeler veya ağaçlar göre inşa edilen aksiyomlar ve çıkarım kuralları mantıksal sistemin. Bu nedenle, kanıt teorisi sözdizimsel doğada, aksine model teorisi, hangisi anlamsal doğada.

İspat teorisinin başlıca alanlarından bazıları şunlardır: yapısal kanıt teorisi, sıra analizi, kanıtlanabilirlik mantığı, ters matematik, kanıt madenciliği, otomatik teorem kanıtlama, ve kanıt karmaşıklığı. Çoğu araştırma, bilgisayar bilimi, dilbilim ve felsefe alanındaki uygulamalara da odaklanmaktadır.

Tarih

Mantığın resmileştirilmesi, aşağıdaki gibi figürlerin çalışmasıyla çok ilerlemiş olsa da Gottlob Frege, Giuseppe Peano, Bertrand Russell, ve Richard Dedekind, modern kanıt teorisinin hikayesi genellikle David Hilbert, denilen şeyi başlatan Hilbert'in programı içinde matematiğin temelleri. Bu programın ana fikri, verebilsek finiter Matematikçilerin ihtiyaç duyduğu tüm sofistike biçimsel teoriler için tutarlılık kanıtları, o zaman bu teorileri, tüm saf evrensel iddialarının (daha teknik olarak ispatlanabilir olduğunu gösteren metamatematik bir argüman aracılığıyla temellendirebiliriz. ${ displaystyle Pi _ {1} ^ {0}}$ cümleler ) son derece doğrudur; Böyle bir temele oturduktan sonra onların varoluşsal teoremlerinin sonlu olmayan anlamını umursamıyoruz, bunları ideal varlıkların varlığının sözde anlamlı hükümleri olarak görüyoruz.

Programın başarısızlığı neden oldu Kurt Gödel 's eksiklik teoremleri herhangi bir ω tutarlı teori bazı basit aritmetik gerçekleri ifade etmek için yeterince güçlü olan, kendi tutarlılığını kanıtlayamayan, Gödel'in formülasyonuna göre bir ${ displaystyle Pi _ {1} ^ {0}}$ cümle. Ancak, Hilbert'in programının değiştirilmiş versiyonları ortaya çıktı ve ilgili konularda araştırmalar yapıldı. Bu, özellikle şunlara yol açmıştır:

• Özellikle Gödel'in sonucunun iyileştirilmesi J. Barkley Rosser Yukarıdaki ω tutarlılık gerekliliğini basit tutarlılığa indirgeyen iyileştirme;
• Gödel'in sonucunun özünün modal bir dil açısından aksiyomizasyonu, kanıtlanabilirlik mantığı;
• Teorilerin transfinite yinelemesi, Alan Turing ve Solomon Feferman;
• Keşfi kendini doğrulayan teoriler, sistemler kendileri hakkında konuşacak kadar güçlü, ancak çapraz argüman Gödel'in kanıtlanamazlık argümanının anahtarı budur.

Hilbert'in programının yükseliş ve düşüşüne paralel olarak, yapısal kanıt teorisi kuruluyordu. Jan Łukasiewicz 1926'da birinin geliştirilebileceğini önerdi Hilbert sistemleri mantığın çıkarsama kurallarındaki varsayımlardan sonuçların çıkarılmasına izin veriliyorsa, mantığın aksiyomatik sunumunun temeli olarak. Buna yanıt olarak, Stanisław Jaśkowski (1929) ve Gerhard Gentzen (1934) bağımsız olarak bu tür sistemleri sağladı. doğal kesinti Gentzen'in yaklaşımı, önerme gerekçeleri arasında simetri fikrini ortaya koyarken, giriş kuralları ve önerileri kabul etmenin sonuçları eleme kuralları ispat teorisinde çok önemli olduğu kanıtlanmış bir fikir.^[2] Gentzen (1934), ardışık hesap mantıksal bağlaçların dualitesini daha iyi ifade eden benzer bir ruhla ilerlemiş bir hesap,^[3] ve sezgisel mantığın resmileştirilmesinde temel ilerlemeler kaydetti ve ilkini sağladı. kombinatoryal kanıt tutarlılığının Peano aritmetiği. Birlikte, doğal tümdengelim ve ardışık analizin sunumu, analitik kanıt teoriyi kanıtlamak için.

Yapısal kanıt teorisi

Yapısal ispat teorisi, ispat teorisinin özelliklerini inceleyen alt disiplintir. kanıt taşı. En iyi bilinen üç ispat taşı stili şunlardır:

• Hilbert taşı
• doğal kesinti taşı
• sıralı taş

Bunların her biri, tam ve aksiyomatik bir biçimlendirmeyi verebilir önerme veya yüklem mantığı ya klasik veya sezgisel lezzet, hemen hemen her modal mantık ve birçok alt yapısal mantık, gibi alaka mantığı veya doğrusal mantık. Aslında, bu taşlardan birinde temsil edilmeye direnen bir mantık bulmak alışılmadık bir durumdur.

İspat teorisyenleri tipik olarak bir kavramını destekleyen ispat taşlarıyla ilgilenirler. analitik kanıt. Analitik kanıt kavramı, Gentzen tarafından ardışık hesap için tanıtıldı; analitik kanıtlar, kesiksiz. Kesiksiz ispatlara olan ilginin çoğu alt formül özelliğinden gelir: Kesiksiz ispatın son sırasındaki her formül, öncüllerden birinin alt formülüdür. Bu, bir kişinin ardışık analizin tutarlılığını kolayca göstermesini sağlar; eğer boş dizi türetilebilir olsaydı, bazı öncüllerin bir alt formülü olması gerekirdi, öyle değil. Gentzen'in sıradaki teoremi, Craig interpolasyon teoremi ve Herbrand teoremi de kesme-eliminasyon teoreminin doğal sonucu olarak takip eder.

Gentzen'in doğal tümdengelim hesabı aynı zamanda bir analitik kanıt kavramını destekler. Dag Prawitz. Tanım biraz daha karmaşık: analitik kanıtların, normal formlar, terim yeniden yazmada normal biçim kavramı ile ilgili. Daha egzotik kanıt taşı gibi Jean-Yves Girard 's geçirmez ağlar aynı zamanda analitik kanıt kavramını da destekler.

Belirli bir analitik ispat ailesi indirgeyici mantık vardır odaklanmış ispatlar Bu, amaca yönelik kanıt arama prosedürlerinin geniş bir ailesini karakterize eder. Bir ispat sistemini odaklanmış bir forma dönüştürme yeteneği, kesmenin kabul edilebilirliğinin bir ispat sisteminin sözdizimsel olarak tutarlı olduğunu göstermesine benzer bir şekilde, sözdizimsel kalitesinin iyi bir göstergesidir.^[4]

Yapısal kanıt teorisi ile bağlantılıdır tip teorisi vasıtasıyla Curry-Howard yazışmaları Doğal tümdengelim hesaplamasındaki normalleştirme süreci ile hesaplamadaki beta indirgeme arasında yapısal bir analoji gözlemleyen yazılan lambda hesabı. Bu, sezgisel tip teorisi tarafından geliştirilmiş Martin-Löf için ve genellikle üçüncü ayağı olan üç yönlü bir yazışmaya genişletilir. kartezyen kapalı kategoriler.

Yapısal teorideki diğer araştırma konuları arasında, geniş bir mantık yelpazesi için karar prosedürleri ve yarı-karar prosedürleri sağlamak için yapısal ispat teorisinden analitik ispatın merkezi fikrini ve alt yapı mantığının ispat teorisini uygulayan analitik tablo bulunmaktadır.

Sıra analizi

Sıralı analiz, aritmetik, analiz ve küme teorisi alt sistemleri için kombinatoryal tutarlılık kanıtları sağlamak için güçlü bir tekniktir. Gödel'in ikinci eksiklik teoremi genellikle yeterli güce sahip teoriler için sonsal tutarlılık kanıtlarının imkansız olduğunu gösterdiği şeklinde yorumlanır. Sıralı analiz, kişinin teorilerin tutarlılığının sonsuz içeriğini tam olarak ölçmesine izin verir. Tutarlı bir yinelemeli aksiyomatize teori T için, sonlu aritmetikte, belirli bir sonsuzluk ordinalinin sağlam temellerinin T.Gödel'in ikinci eksiklik teoreminin tutarlılığını ima ettiği kanıtlanabilir, böyle bir ordinalin sağlam temellerinin teoride kanıtlanamayacağını ima eder. T.

Sıralı analizin sonuçları, (1) klasik ikinci dereceden aritmetik ve küme teorisinin alt sistemlerinin yapıcı teorilere göre tutarlılığını, (2) kombinatoryal bağımsızlık sonuçlarını ve (3) kanıtlanabilir toplam özyinelemeli fonksiyonların ve kanıtlanabilir şekilde iyi kurulmuş sıra sayılarının sınıflandırılmasını içerir.

Sıra analizi, Peano Aritmetiğinin tutarlılığını kanıtlayan Gentzen tarafından oluşturulmuştur. sonsuz indüksiyon sıraya kadar ε₀. Sıralı analiz, birinci ve ikinci dereceden aritmetik ve küme teorisinin birçok parçasına genişletilmiştir. En büyük zorluklardan biri, empredikatif teorilerin sıralı analizi olmuştur. Bu yöndeki ilk atılım, Takeuti'nin Π tutarlılığının kanıtıydı.¹
₁-CA₀ Sıralı diyagramlar yöntemini kullanarak.

Sağlanabilirlik mantığı

Sağlanabilirlik mantığı bir modal mantık, kutu operatörü 'bu kanıtlanabilir' olarak yorumlanır. Buradaki mesele, makul derecede zengin bir kanıtın kanıt şartı kavramını yakalamaktır. biçimsel teori. İspatlanabilirlik mantığının temel aksiyomları olarak GL (Gödel -Lob ), kanıtlanabilir yakalar Peano Aritmetiği Hilbert-Bernays türetilebilirlik koşullarının modal analoglarını alır ve Löb teoremi (A'nın ispatlanabilirliğinin A'yı ima ettiği kanıtlanabilirse, o zaman A kanıtlanabilirdir).

Peano Aritmetiğinin eksikliğine ilişkin temel sonuçlardan bazıları ve ilgili teoriler, kanıtlanabilirlik mantığında analoglara sahiptir. Örneğin, GL'deki bir teoremdir, eğer bir çelişki kanıtlanamazsa, o zaman bir çelişkinin kanıtlanamayacağı kanıtlanamaz (Gödel'in ikinci eksiklik teoremi). Sabit nokta teoreminin modal analogları da vardır. Robert Solovay GL modal mantığının Peano Aritmetiğine göre tamamlandığını kanıtladı. Yani, Peano Aritmetiğinde önermesel kanıtlanabilirlik teorisi tamamen modal mantık GL ile temsil edilir. Bu, Peano Aritmetiğinde kanıtlanabilirlik hakkında önermeye dayalı muhakemenin tam ve karar verilebilir olduğu anlamına gelir.

İspatlanabilirlik mantığındaki diğer araştırmalar, birinci dereceden kanıtlanabilirlik mantığına odaklanmıştır. çok modlu kanıtlanabilirlik mantığı (nesne teorisinde kanıtlanabilirliği temsil eden bir modalite ve meta-teoride kanıtlanabilirliği temsil eden bir başka modalite ile) ve yorumlanabilirlik mantığı kanıtlanabilirlik ve yorumlanabilirlik arasındaki etkileşimi yakalamaya yöneliktir. Son zamanlarda yapılan bazı araştırmalar, dereceli kanıtlanabilirlik cebirlerinin aritmetik teorilerin sıralı analizine uygulamalarını içermektedir.

Ters matematik

Ters matematik içinde bir program matematiksel mantık matematik teoremlerini kanıtlamak için hangi aksiyomların gerekli olduğunu belirlemeye çalışır.^[5] Saha tarafından kuruldu Harvey Friedman. Tanımlama yöntemi, "geriye doğru gitmek" olarak tanımlanabilir. teoremler için aksiyomlar ", teoremleri aksiyomlardan türetmenin sıradan matematiksel uygulamasının aksine. Ters matematik programı, klasik teorem gibi küme teorisindeki sonuçların habercisiydi. seçim aksiyomu ve Zorn lemması eşittir ZF küme teorisi. Bununla birlikte, ters matematiğin amacı, küme teorisi için olası aksiyomlardan ziyade sıradan matematik teoremlerinin olası aksiyomlarını incelemektir.

Ters matematikte, ilgi duyulabilecek teoremlerin çoğunu kanıtlamak için çok zayıf, ancak yine de bu teoremleri belirtmek için gerekli tanımları geliştirmek için yeterince güçlü olan bir çerçeve dili ve temel bir aksiyom sistemi olan temel bir teori ile başlar. Örneğin, teoremi incelemek için "Her sınırlı dizi gerçek sayılar var üstünlük "Gerçek sayılardan ve gerçek sayı dizilerinden söz edebilen bir temel sistem kullanmak gerekiyor.

Temel sistemde ifade edilebilen ancak temel sistemde kanıtlanamayan her teorem için amaç, bu teoremi kanıtlamak için gerekli olan belirli aksiyom sistemini (temel sistemden daha güçlü) belirlemektir. Bir sistem olduğunu göstermek için S bir teoremi kanıtlamak için gereklidir T, iki kanıt gereklidir. İlk kanıt gösterir T kanıtlanabilir S; bu, sistemde yürütülebileceğine dair bir gerekçeyle birlikte sıradan bir matematiksel kanıttır. S. Olarak bilinen ikinci kanıt ters çevirme, gösterir ki T kendisi ima eder S; bu kanıt temel sistemde gerçekleştirilir. Tersine çevirme, aksiyom sisteminin S ′ temel sistemi genişleten, daha zayıf olabilir S Hala kanıtlarkenT.

Ters matematikte çarpıcı bir fenomen, Büyük beş aksiyom sistemleri. Gücü arttırmak için, bu sistemler RCA baş harfleriyle adlandırılır.₀, WKL₀, ACA₀, ATR₀ve Π¹
₁-CA₀. Ters matematiksel olarak analiz edilen hemen hemen her sıradan matematik teoreminin bu beş sistemden birine eşdeğer olduğu kanıtlanmıştır. Son zamanlarda yapılan araştırmaların çoğu, RT gibi bu çerçeveye tam olarak uymayan kombinatoryal ilkelere odaklanmıştır.²
₂ (Ramsey teoremi çiftler için).

Ters matematikte araştırma genellikle aşağıdaki yöntem ve teknikleri içerir: özyineleme teorisi yanı sıra kanıt teorisi.

Fonksiyonel yorumlar

İşlevsel yorumlar, işlevsel olanlarda yapıcı olmayan teorilerin yorumlarıdır. İşlevsel yorumlar genellikle iki aşamada ilerler. Birincisi, klasik bir C teorisini sezgisel olana "indirgemek" I. Yani, biri C teoremlerini I teoremlerine çeviren yapıcı bir haritalama sağlar. İkincisi, sezgisel teori I'i niceleyici olmayan bir teoriye indirger. İşlevseller F. Bu yorumlar, klasik teorilerin yapıcı olanlara göre tutarlılığını kanıtladıkları için Hilbert'in programına katkıda bulunur. Başarılı işlevsel yorumlar, sonsuz teorilerin sonlu teorilere ve impredikatif teorilerin tahmin edici teorilere indirgenmesini sağladı.

İşlevsel yorumlar, indirgenmiş teorideki ispatlardan yapıcı bilgiyi çıkarmanın bir yolunu da sağlar. Yorumun doğrudan bir sonucu olarak, genellikle toplamı I veya C'de kanıtlanabilen herhangi bir özyinelemeli fonksiyonun bir F terimiyle temsil edildiği sonucu elde edilir.Birisi I'de F'nin ek bir yorumunu sağlayabilirse, ki bu bazen mümkün, bu karakterizasyon aslında genellikle kesin olarak gösterilmektedir. Genellikle, F terimlerinin, ilkel özyinelemeli veya çok terimli zaman hesaplanabilir işlevler gibi doğal bir işlev sınıfıyla çakıştığı ortaya çıkar. Fonksiyonel yorumlar, teorilerin sıralı analizlerini sağlamak ve kanıtlanabilir şekilde yinelemeli fonksiyonlarını sınıflandırmak için de kullanılmıştır.

Fonksiyonel yorumların incelenmesi, Kurt Gödel'in sezgisel aritmetiği, niceleyici içermeyen sonlu tip fonksiyoneller teorisinde yorumlamasıyla başladı. Bu yorum genel olarak şu şekilde bilinir: Dialectica yorumu. Klasik mantığın sezgisel mantıkta çifte olumsuz yorumuyla birlikte, klasik aritmetiğin sezgisel aritmetiğe indirgenmesini sağlar.

Resmi ve gayri resmi kanıt

gayri resmi günlük matematiksel uygulamanın kanıtları, resmi kanıt teorisinin kanıtları. Daha ziyade, bir uzmanın resmi bir kanıtı en azından prensipte, yeterli zaman ve sabırla yeniden oluşturmasına izin veren üst düzey eskizler gibidirler. Çoğu matematikçi için, tamamen resmi bir kanıt yazmak, ortak kullanım için fazla bilgiçlik ve uzun solukludur.

Biçimsel kanıtlar, bilgisayarların yardımıyla oluşturulur. etkileşimli teorem kanıtlama. Önemli bir şekilde, bu kanıtlar bilgisayar tarafından da otomatik olarak kontrol edilebilir. Resmi kanıtları kontrol etmek genellikle basittir, oysa bulma kanıtlar (otomatik teorem kanıtlama ) genellikle zordur. Matematik literatüründe gayri resmi bir kanıt, aksine, haftalarca akran değerlendirmesi kontrol edilmelidir ve hala hatalar içerebilir.

İspat-teorik anlambilim

İçinde dilbilim, tür mantıksal gramer, kategori dilbilgisi ve Montague dilbilgisi resmi vermek için yapısal kanıt teorisine dayalı formalizmler uygulayın doğal dil anlambilim.

Ayrıca bakınız

• Ara mantık
• Model teorisi
• Kanıt (gerçek)
• İspat teknikleri

Notlar

Referanslar

• J. Avigad ve E.H. Reck (2001). "'Sonsuzun doğasını açıklığa kavuşturmak': metamatematik ve ispat teorisinin gelişimi ". Carnegie-Mellon Teknik Raporu CMU-PHIL-120.
• J. Barwise, ed. (1978). Matematiksel Mantık El Kitabı. Kuzey-Hollanda.
• S. Buss, ed. (1998) İspat Teorisi El Kitabı. Elsevier.
• A. S. Troelstra ve H. Schwichtenberg (1996). Temel İspat Teorisi, Teorik Bilgisayar Bilimlerinde Cambridge Tracts, Cambridge University Press, ISBN  0-521-77911-1.
• G. Gentzen (1935/1969). "Mantıksal kesintiye yönelik araştırmalar ". M. E. Szabo, ed. Gerhard Gentzen'in Toplanan Makaleleri. Kuzey-Hollanda. Szabo tarafından "Untersuchungen über das logische Schliessen" den çevrilmiştir, Mathematisches Zeitschrift v. 39, s. 176–210, 405 431.
• D. Prawitz (1965). Doğal çıkarım: Kanıt-teorik bir çalışmaDover Yayınları, ISBN  978-0-486-44655-4
• SG Simpson (2010). İkinci Derece Aritmetiğin Alt Sistemleri, ikinci baskı. Cambridge University Press, ISBN  978-0521150149.
• H. Wang (1981). Matematiksel Mantık Üzerine Popüler Dersler, Van Nostrand Reinhold Şirketi, ISBN  0-442-23109-1.

Dış bağlantılar

• "Kanıt teorisi", Matematik Ansiklopedisi, EMS Basın, 2001 [1994]
• J. von Plato (2008). İspat Teorisinin Gelişimi. Stanford Felsefe Ansiklopedisi.