Neden yalnızca Peano aritmetiği yeterli: PA hesaplamayı kodlayabiliyor
(math.stackexchange.com)- PA, Goodstein teoreminin tamamını
∀n G(n)kanıtlayamaz; ancak her standart doğal sayıniçinG(n)ifadesinin PA içinde bir kanıtının var olduğunu PA içinde gösterebilir - Temel fikir,
niçin gereken sonlu yüksekliktekiωüs kulelerine kadar ilerlemek ve bu aralık için transfinit tümevarım kanıtını mekanik olarak üretmektir - Gerekli yükseklik
m,n'nin hereditary base notation yüksekliğine karşılık gelir veO(log*(n))düzeyindedir; kısaltılmışω^[m]gösterimi kullanılırsa kanıt uzunluğuO(m log m)seviyesine iner - Bu sonuç, “her bir örnek için bir kanıt üretilebilir” demektir; PA'nın Goodstein teoreminin tamamını kanıtladığı anlamına gelmez
- PA, tek bir doğal sayının içine sayı, çift, liste, program durumu ve biçimsel mantık kanıtını kodlayabilir; böylece üretilen kanıtın gerçekten PA kanıtı olup olmadığı da PA içinde doğrulanabilir
Sorunun matematiksel biçimi
-
İlgilenilen nesne, Goodstein dizisinin sonunda 0'a ulaştığını söyleyen
G(n)önermesidir -
Bilinen ayrım şöyledir
- PA,
G(15),G(268)gibi standart doğal sayıların her somut örneğini kanıtlayabilir - PA, tüm önerme olan
∀n ∈ N: G(n)ifadesini kanıtlayamaz
- PA,
-
Soru, PA'nın aşağıdaki biçimdeki önermeyi kanıtlayıp kanıtlayamayacağıdır
∀n ∈ N: ∃p ∈ N: P_PA(p, ⌜G(n)⌝) -
P_PA(p, ⌜φ⌝),p'nin PA içindeφiçin bir kanıt kodu olduğu anlamına gelir -
Sonuç, bu düzeyde yalnızca PA'nın yeterli olduğudur
PA'nın kanıtlaması gereken şey
- PA'nın her
niçin göstermesi gereken üç nokta şunlardırG(n)'yi kanıtlamak için gereken kanıt uzunluğu hesaplanabilir- Bu kanıtı kuran prosedür sonlanır
- Kurulan kanıtın son cümlesi
G(n)'nin sonlandığını söyler
- Her
G(n)için uzunluğuO(log*(n) log(log*(n)))olan bir PA kanıtı kurulabilir log*, iterated logarithm olup son derece yavaş büyüyen bir fonksiyondurnbüyüdükçe gereken kanıt da uzar; bu nedenle yalnızca bu bilgiyle PA'nın Goodstein teoreminin tamamını kanıtladığı söylenemez
Goodstein dizileri ve ordinal gösterimi
-
Goodstein dizileri hereditary base notation kullanır; bu, Cantor normal form ile yazılmış ordinal gösterimleriyle bağlantılıdır
-
John von Neumann tarzı kurulumda ordinal'ler kümeler olarak inşa edilir
0, boş kümedir- Bir ordinal
ordvarsaord ∪ {ord}da bir ordinal'dir - Ordinal'lerden oluşan bir küme
XvarsaX'in birleşimi de bir ordinal'dir
-
Cantor normal form, ordinal'i şu biçimde gösterir
((n1, ord1), (n2, ord2), ..., (nk, ordk))- Her
nipozitif bir doğal sayıdır - Her
ordibir ordinal'dir ord1 > ord2 > ... > ordk
- Her
-
Bu gösterim şu ordinal'i ifade eder
n1·ω^ord1 + n2·ω^ord2 + ... + nk·ω^ordk -
Karşılaştırma,
ord1,n1,ord2,n2sırasındaki leksikografik karşılaştırma ile yapılır; taraflardan biri önce biterse daha kısa olan küçüktür
Tümevarımdan transfinit tümevarıma
- PA'nın beşinci aksiyomu, doğal sayılar üzerinde tümevarım sağlar
S(0)doğrudurS(n)iseS(s n)de doğrudur- O hâlde
S, tüm doğal sayılar için doğrudur
- PA, buradan
<ilişkisini özyinelemeli olarak tanımlayabilir ve güçlü tümevarımı da kanıtlayabilir- Her
niçin,n'den küçük tüm sayılardaSdoğruysaS(n)de doğrudur gösterilebiliyorsa,Stüm doğal sayılar için doğrudur
- Her
- ZFC'de, tüm ordinal'ler üzerinde güçlü tümevarım olan transfinit tümevarım kanıtlanabilir
- Cantor normal form ile yazılmış nesneler için şu iki özellik kullanılır
- Cantor normal form ile yazılmış azalan diziler mutlaka sonludur
- Cantor normal form nesneleri üzerinde transfinit tümevarım uygulanabilir
PA içinde mümkün olan transfinit tümevarım aralığı
- PA, tüm ordinal'ler için transfinit tümevarımı kanıtlayamaz
- Bunun yerine, belirli sonlu yükseklikteki ordinal aralıkları PA içinde ele alınabilir
- PA güçlü tümevarımı kanıtlayabildiği için
ω'ya kadar transfinit tümevarımı ele alabilir - Aynı mantıkla
ω^ωiçin transfinit tümevarım da kanıtlanabilir - Yine aynı yöntemle
ω^(ω^ω),ω^(ω^(ω^ω))gibi sonlu yükseklikte kuleler için bu işlem tekrarlanabilir
- PA güçlü tümevarımı kanıtlayabildiği için
- Her aşamadaki kanıt, yalnızca kulenin yüksekliği değiştirilerek mekanik olarak üretilir
m'inci kule doğrudan yazılırsa toplam kanıt uzunluğuO(m^2)olurω^[m]gibi kısaltılmış gösterim kullanılırsamyazmak için yalnızcaO(log m)uzunluk gerekir; böylece toplam kanıtO(m log m)olurε₀altındaki her ordinal için PA içinde bir transfinit tümevarım kanıtı vardır; ancak bunları tek bir kanıtta birleştirmek için sonsuz uzunlukta bir kanıt gerekir- PA,
ε₀için transfinit tümevarımı kanıtlayabilseydi PA'nın tutarlılığını da kanıtlayabilirdi; bu da Gödel'in ikinci eksiklik teoremiyle çelişirdi
Her G(n) için kanıt üretme prosedürü
- Belirli bir
niçin yalnızca hereditary base notation içindeki kule yüksekliği kadarına ihtiyaç vardır - Bu yükseklik
O(log*(n))düzeyindedir ve PA'nın kolayca hesaplayabildiği bir fonksiyon olarak ele alınır - Program, girdi olarak
nverildiğinde şunları çıktılayabilir- PA hakkında ortak olguların kanıtları
G(n)'nin bazımiçinω^[m]içindeki bir azalan diziyi izlediğine dair kanıt- Bu
m'yi hesaplama süreci vemdeğerine ilişkin kanıt ω^[0]için transfinit tümevarım kanıtıω^[i]üzerindeki transfinit tümevarımınω^[i+1]üzerindeki transfinit tümevarımı gerektirdiğine dair kanıti = 0ilem-2arasındaki her adım için transfinit tümevarım kanıtıω^[m-1]üzerindeki transfinit tümevarımın,ω^[m]içindeki tüm azalan dizilerin sonlu olduğunu gerektirdiğine dair kanıtG(n)'nin sonlandığı sonucunu
- PA, bu prosedür için şunları kanıtlayabilir
- Prosedür sonlanır
- Prosedür cümlelerden oluşan bir liste üretir
- Liste Peano aksiyomlarıyla başlar
- Her cümle önceki cümlelerden mantıksal olarak çıkar
- Tümevarımla tüm cümleler kanıtlanır
- Son cümle “
G(n)sonlanır” ifadesidir
- Dolayısıyla PA, keyfi bir doğal sayı
niçin PA'nınG(n)'nin sonlandığını kanıtladığı gerçeğini kanıtlar
PA'nın hesaplamayı kodlama biçimi
- “Kodlama”, bir doğal sayının belirli bir yapıyı temsil edecek şekilde belirlenmesi demektir
- PA'nın temel malzemeleri şunlardır
0- artçı fonksiyon
(s n) - eşitlik
0olmayan sayılar için önceleyici(p n)- tümevarımla meşrulaştırılan özyinelemeli tanımlar
0veya1'e göre dallanan koşullu ifade
- PA içinde aşağıdaki temel aritmetik fonksiyonlar özyinelemeli olarak tanımlanabilir
<min,max+*- üs alma
- kalan
% - tam sayı bölmesi
//
- Bu fonksiyonların temel özellikleri, PA içinde tümevarımla kanıtlanabilir
Tek bir doğal sayı ile veri yapıları kurmak
- İki doğal sayıyı tek bir doğal sayıya kodlamak için ikili gösterimde bitleri dönüşümlü yerleştirme yöntemi kullanılabilir
- tek konumdaki bitler
head - çift konumdaki bitler
tail
- tek konumdaki bitler
- Bu şekilde oluşturulan çiftten tekrar
headvetailçıkarılabilir - Çift oluşturulabiliyorsa bağlı liste de ifade edilebilir
0,nilolarak kullanılır- boş liste
- başa öğe ekleme
- baş ve kuyruğu okuma
- uzunluk hesaplama
- istenen konuma erişim
- ekleme ve silme
- Sayılar, çiftler ve listeler varsa yığın, kuyruk, ağaç, metin belgesi ve sanal makine gibi yapılar da tek bir doğal sayı ile gösterilebilir
Lisp ve hesaplama prosedürlerinin kodlanması
- Lisp, parantezli yapısı ve
command and argumentsbiçimi sayesinde ayrıştırma ve yorumlamayı anlatması kolay bir dil olarak kullanılır - PA içindeki doğal sayılar
(type, value)çifti olarak yorumlanabilir- sayı
- boolean
- çift
- liste
- metin vb.
- Bazı doğal sayılar belirli türler için geçerli değer olmayabilir; ancak geçerli değerler tekil olarak belirli bir yapıyı temsil edebilir
- Bu kodlama üzerinde Lisp veri yapıları, Lisp sanal makinesi ve Lisp yorumlayıcısı kurulabilir
- Lisp, Turing complete olduğundan bu yol üzerinden herhangi bir hesaplanabilir prosedür ve bu prosedürün durumu PA içinde kodlanabilir
- Belirli sayıda adımdan sonraki hesaplama durumu da PA içinde ifade edilip izlenebilir
PA, PA'nın kanıtlarını da kodlar
- Birinci dereceden mantıkta kanıt, cümlelerden oluşan bir liste olarak görülebilir
- Her cümle bir çıkarım adımıdır
- Hatalı cümleler veya hatalı çıkarımlar da yazılabilir; ancak doğrulama prosedürü bunları ayıklar
- PA içinde
type-proofbenzeri bir tür tanımlanabilir ve kanıtlar cümle listesi olarak kodlanabilir - Şu doğrulama prosedürleri de PA içinde kodlanabilir
- Kanıtın iyi biçimlenmiş olup olmadığını kontrol etme
- Her kanıt adımının geçerli olup olmadığını kontrol etme
- Hangi aksiyomların varsayıldığını kontrol etme
- Son sonucun istenen cümle olup olmadığını kontrol etme
- Belirli aksiyomlardan belirli bir cümlenin bir kanıtı varsa, bu kanıtı temsil eden belirli bir PA doğal sayısı da vardır
- PA, bu sayının gerçekten bir kanıt kodu olup olmadığını denetleyen hesaplamayı ifade edebilir; dolayısıyla “PA içindeki kanıt” kavramının kendisi de PA içinde ele alınabilir
- Gödel, tüm hesaplamayı kodlamadan da PA içinde mantığı kodlamıştı; ancak programcı bakış açısından, hesaplama kodlaması üzerinden anlamak daha doğal bir yol olur
1 yorum
Hacker News yorumları
Stack Overflow’daki bir sorunun blog yazısına genişletilmiş hâli
Peano aksiyomları ile nelerin kanıtlanabileceğinin sınırlarını ve bunun içinde Lisp’i bootstrap etmeye nasıl başlanacağını ele alıyor.
Kötü şakaların hepsi ikinci bölümde; düzeltmeler ve takip soruları memnuniyetle karşılanır.
(defun not (x) ...)örneğinde parantez eşleşmesi hatalı olan bir yer gördüm.Daha sonra “bilgisayarın dengeli parantezleri bulmasını sağlamak gerçekten kolay” diye yazdığı kısımla birleşince epey komik olmuş; “Basic Number Theory” bölümündeki “kapanış parantezi yığını görünmez hâle gelir” yorumu da eğlenceliydi.
Uzun süredir Lisp kullanmamış olmama rağmen yeniden takip edip ana fikri yakalayabildim; yazı bu yüzden iyiydi.
Peano aksiyomlarıyla hesaplamanın kodlanabilmesi de tuhaf derecede şaşırtıcı; sanki bir öz-gönderim katmanı daha oluşmuş gibi.
Son dönemde küme kuramını daha fazla çalışmaya başlayıp Goodstein dizilerine kadar geldim; bir sonraki seviye için ileri küme kuramı kitabı ya da Peano aritmetiğini derinlemesine ele alan kaynak önerilerini merak ediyorum.
https://t3x.org üzerindeki çeşitli Lisp’ler de sayıları ve geri kalanını cons hücreleri ile apply/eval üzerinden gerçekleştiriyor.
John McCarthy’nin metadöngüsel değerlendiricisi, Alan Kay’in “yazılımın Maxwell denklemleri” dediği koddur; SectorLISP’te
ASSOC EVAL EVCON APPLY EVLIS PAIRLISgibi öğelerle uygulanır.Bazı Forth’lar da benzer; T3X’in Zenlisp’i, eval/apply’nin karşılıklı olarak özyinelemeli çağrılması etrafında açıklanır: http://t3x.org/zsp/index.html
\omegaolarak yazılmalı.Hem matematik hem programlama yapmış biri olarak, hesaplamanın kodlanmasının kendisinden ziyade Goodstein teoreminin bağımsızlığının böyle bir öz-gönderim yöntemiyle aşılabilmesi daha ilginç geliyor.
Bu, PA + “PA ω-tutarlıdır” sisteminin Goodstein teoremini kanıtlayabildiği anlamına geliyor gibi; belki ε₀’a kadar olan transfinit indüksiyon da genel olarak mümkün olabilir.
Düzeltme: PA + “PA tutarlıdır” bile yeterli olabilir mi diye düşünüyorum.
Temelde “PA tutarlıdır” tek başına yeterli değil; “PA bir şeyi kanıtlarsa o doğrudur” diyen tekbiçimli yansıma ilkesi varsa yeterli.
Bu ilkenin ω-tutarlılıkla eşdeğer olup olmadığından %100 emin değilim, ama şuna bakınca öyle okunuyor: https://en.wikipedia.org/wiki/%CE%A9-consistent_theory#Relation_to_other_consistency_principles
Wikipedia, T’nin ω-tutarlı olmasını “T + RFN_T + tüm doğru cümlelerin kümesi tutarlıdır” diye açıklıyor; bu da “T + RFN_T doğrudur” ile aynı anlama geliyor gibi görünüyor.
Esasen PA’nın neyi kanıtladığına dair bir meta kanıt oluşturuyorsun; PA’ya güveniyorsan o meta kanıta da güveniyorsun.
Yine de PA + “PA tutarlıdır”ın nasıl yeterli olduğunu pek bilmiyorum.
Bu sistem, standart doğal sayılarda Goodstein teoreminin doğru olduğu ama standart olmayan bir N tamsayısında Goodstein teoreminin yanlış olduğu modelleri kabul edecek gibi; daha güçlü ω-tutarlılığın tam da bu durumu dışladığı görülüyor.
Yani bu Con(PA)’ye özgü bir sorun değil, daha genel bir olgu: https://math.stackexchange.com/questions/5003237/can-goodsteins-theorem-be-proven-in-mathrmpa-conpa
İlk soruyla bağlantılı olarak, ω-tutarlılığın PA’nın bir formülü olarak nasıl kodlandığını merak ediyorum.
Bu yüzden PA + “PA tutarlıdır”ın ε₀ için transfinit indüksiyonu kanıtlayabileceği izlenimi doğuyor.
ChatGPT, yalnızca PA + “PA tutarlıdır”ın yeterli olmadığını söyledi; mantık kitaplarını yeterince özümsemiş olmalı, bu yüzden bu iddiaya inanılabilir gibi.
Peano aritmetiğini ilk kullandığımda ifade gücü beni epey şaşırtmıştı.
İlk bakışta temel bir sistem gibi görünüyor; ama hesaplamanın kendisini PA içinde kodlayabildiğini ve çeşitli hesaplama türlerini taklit edebildiğini fark edince, karmaşık görünen şeyler yerine oturmaya başlıyor.
Bu tür kodlama tekniklerini yeni başlayanlara anlaşılır biçimde açıklayan kaynak önerilerini merak ediyorum.
Bu, Boyer-Moore teorisine çok benziyor. Bu teori de matematiği Peano aksiyomları düzeyinden başlayarak inşa eder.
Boyer ve Moore bu teoriye göre uyarlanmış otomatik teorem kanıtlayıcılar da yaptılar; GNU Common Lisp’te çalışan bir kopyası https://github.com/John-Nagle/nqthm/tree/master adresinde duruyor.
Onların açıklamasına göre, programı oldukça iyi bir matematik öğrencisi gibi düşünmek işi kolaylaştırır. Yalnızca Peano aksiyomlarını verirseniz asal çarpanlara ayırma teoremini kanıtlamasını ya da keşfetmesini beklemek zordur; ama Peano aksiyomlarıyla birlikte “toplamanın değişme özelliğini kanıtla”, “çarpmanın toplama üzerinde dağılma özelliğini kanıtla”, “GCD fonksiyonunun sonucunun iki argümanı da böldüğünü kanıtla” gibi bir teorem listesi verirseniz bunları iyi biçimde ele alabilir.
Makale: https://www.cs.utexas.edu/~boyer/acl.pdf
Math StackExchange’de JoJoModding’e yazılan yorum yanlış.
“PA kendisinin bir kanıt ürettiğini kanıtlayabilir, ama o kanıtın sonlu uzunlukta olduğunu kanıtlayamayabilir” açıklaması asıl noktayı yanlış yakalıyor.
PA, “PA X’i kanıtlar”ı kanıtlarsa PA X’i kanıtlayabilir.
Önemli olan standart dışı modellerin varlığı değil, standart doğal sayılar modelinin PA’nın bir modeli olmasıdır.
Dolayısıyla PA, “PA X’i kanıtlar”ı kanıtlarsa, gerçekten de “PA X’i kanıtlar”ın kodlanmış kanıtına karşılık gelen standart, sonlu bir doğal sayı vardır ve bu doğal sayıyla PA içindeki X kanıtı kurulabilir.
Gösterilen şey “PA
Provable(forall n, G(n))ifadesini kanıtlar” değil, “PAforall n, Provable(G(n))ifadesini kanıtlar” yönündedir.İlki olsaydı gerçekten “PA
forall n, G(n)ifadesini kanıtlar” sonucu çıkardı; ama ikincisi farklıdır.Goodstein dizilerine başvurmadan, genel bir
Pönermesi içinforall n, Provable(P(n))kanıtlanıyor diyeProvable(forall n, P(n))kanıtlanamayacağını gösteren bir argüman görmek isterim.PA içinde, PA’nın üretebildiği tüm kanıtları arayan bir fonksiyon kurulabilir; buna dayanarak belli bir fonksiyonun ve girdinin dönüp dönmeyeceğini analiz eden bir
will-returnfonksiyonu yapılabilir.Bu, durma problemini çözme girişimine benzer; bu yüzden her zaman çalışmaz ama birçok durumda çalışır.
Burada
opposite-returnoluşturulursa, verilen fonksiyon ve girdi dönmediğinde dönmeye çalışacak, döndüğünde ise dönmeyecek şekilde kurgulanabilir.Standart durma problemi kanıtındakiyle aynı biçimde
(opposite-return opposite-return opposite-return)ele alındığında PA şunları kanıtlayabilir: “PA,opposite-return’ün döndüğünü kanıtlayabiliyorsa aslında dönmez”, “PA dönmediğini kanıtlayabiliyorsa aslında döner”, “PA, kendisinin kanıtladığını kanıtladığı her şeyi gerçekten kanıtlayabiliyorsa önceki iki önermeden birinin kanıtına sahip olmalıdır”, “dolayısıyla böyle bir durumda PA tutarsızdır”.Bu, Gödel’in ikinci eksiklik teoreminin bir biçimidir; bu yüzden “PA kanıtlar” ile “PA kendisinin kanıtladığını kanıtlar” ayrılmalıdır.
Bu yüzden önerilen kanıt PA’nın içinde işlemez; o yorumun ana fikri de tam olarak bu gibi görünüyor.
https://math.stackexchange.com/questions/4408124/what-does-the-kirby-paris-theorem-mean
Biriyle tümevarımsal veri tipleri hakkında konuşurken Lean ya da Rocq’taki
Natgibizero/succtanımını göstermiştim.Karşımdaki kişi “Hepsi bu mu? Peano aksiyomları nerede? Tümevarımsal veri tiplerinden daha ilkel bir şey var mı?” diye sordu; ilginçti.
Peano aksiyomlarını kendiliğinden içkin kabul etmek yerine, onları birden çok tasarımdan biri olarak görmenin daha iyi olduğunu hatırlattı.
Çünkü tüm tümevarımsal veri tipleri, doğal sayılar ve küçük bir grup ilkel tip oluşturucu, örneğin Π, Σ, =, Ω vb. kullanılarak kurulabilir.
Saf lambda hesabı tek başına da yeterlidir. Çünkü lambda hesabı hesaplamayı kodlar.
PA’nın tutarlılığıyla ilgili olarak, PA içinde kanıtlanabilir: https://youtu.be/6pjLmmkZnIA
Gödel’in ikinci eksiklik teoremi, PA kendi tutarlılığını kanıtlayabiliyorsa PA’nın tutarsız olduğunu ve dolayısıyla yanlışlar dahil her şeyi kanıtlayabileceğini gösterir.
Bağlantıdaki çalışma PA’nın tutarsızlığını göstermiş değil; PA’nın “kendi tutarlılığını kanıtlar” sözünün daha zayıf yeni bir anlamını tanımlayıp PA’nın bu daha zayıf işi yapabildiğini göstermiştir.
İlginç bir çalışma, ama anlamlı olabilmesi için zaten epey mantık bilmek gerekiyor.
Bu yazı 123 puan almış; bağlantı verilen SO yazısının ise yalnızca 11 olumlu oyu var.
Orada yazı yayımlayınca kolayca silinebileceğine dair itibar sorununun üstüne bir de 15 puan sınırı eklenince, birçok kişi oy veremiyor gibi görünüyor.