Goodsteins teoremi - Goodsteins theorem - Wikipedia

İçinde matematiksel mantık, Goodstein teoremi hakkında bir ifadedir doğal sayılar tarafından kanıtlandı Reuben Goodstein 1944'te Goodstein dizisi sonunda 0'da sona erer. Kirby ve Paris[1] olduğunu gösterdi kanıtlanamaz içinde Peano aritmetiği (ancak daha güçlü sistemlerde kanıtlanabilir, örneğin ikinci dereceden aritmetik ). Bu, Peano aritmetiğinde kanıtlanamayan gerçek bir ifadenin üçüncü örneğiydi. Gödel'in eksiklik teoremi ve Gerhard Gentzen 1943'nin kanıtlanamazlığının doğrudan kanıtı0-Peano aritmetiğinde indüksiyon. Paris – Harrington teoremi daha sonraki bir örnekti.

Laurence Kirby ve Jeff Paris bir grafik teorik tanıttı hydra oyunu Goodstein dizilerindekine benzer davranışa sahip: "Hydra" (mitolojik çok başlı Hydra of Lerna ) köklü bir ağaçtır ve bir hareket, hidra'nın belirli kurallara göre sınırlı sayıda yeni baş oluşturarak yanıt verdiği "kafalarından" (ağacın bir dalı) birini kesmekten oluşur. Kirby ve Paris, Herkül'ün kafasını kesmek için kullandığı stratejiden bağımsız olarak Hydra'nın sonunda öldürüleceklerini kanıtladılar, ancak bu çok uzun zaman alabilir. Tıpkı Goodstein dizilerinde olduğu gibi, Kirby ve Paris bunun sadece Peano aritmetiğinde kanıtlanamayacağını gösterdi.[1]

Kalıtsal temeln gösterim

Goodstein dizileri, "kalıtsal temel" adı verilen bir kavramla tanımlanır.n ". Bu gösterim, olağan tabana çok benzer.n konumsal gösterim, ancak olağan gösterim, Goodstein teoreminin amaçları için yeterli değildir.

Sıradan bazda-n gösterim, nerede n 1'den büyük doğal bir sayıdır, keyfi bir doğal sayıdır m güçlerin katlarının toplamı olarak yazılır n:

her katsayı nerede aben tatmin eder 0 ≤ aben < n, ve ak ≠ 0. Örneğin, 2 tabanında,

Böylece, 35'in taban-2 gösterimi 100011'dir, yani 25 + 2 + 1. Benzer şekilde, taban-3'te temsil edilen 100, 10201'dir:

Üslerin kendilerinin tabanda yazılmadığını unutmayın.n gösterim. Örneğin, yukarıdaki ifadeler 2'yi içerir5 ve 34ve 5> 2, 4> 3.

Bir tabanı dönüştürmek için-n kalıtsal tabana temsiln gösterim, önce tüm üsleri tabanda yeniden yazın-n gösterim. Sonra üsler içindeki üsleri yeniden yazın ve ifadede görünen her sayı (tabanların kendileri hariç) tabana dönüştürülene kadar bu şekilde devam edin.n gösterim.

Örneğin, sıradan 2 tabanlı gösterimde 35 25 + 2 + 1kalıtsal temel-2 gösteriminde şu şekilde yazılmıştır:

gerçeğini kullanarak 5 = 22 + 1. Benzer şekilde, kalıtsal taban-3 gösteriminde 100

Goodstein dizileri

Goodstein dizisi G(m) bir sayı m doğal sayılar dizisidir. Dizideki ilk öğe G(m) dır-dir m kendisi. İkinciyi almak için, G(m) (2), yaz m kalıtsal temel-2 gösteriminde, tüm 2'leri 3s olarak değiştirin ve sonra sonuçtan 1 çıkarın. Genel olarak (n + 1) -st dönem G(m)(n + 1) Goodstein dizisinin m Şöyleki:

  • Kalıtsal temeli ele alalım.n + 1 temsili G(m)(n).
  • Bazın her bir oluşumunu değiştirin.n + 1 ile n + 2.
  • Bir çıkar. (Bir sonraki terimin hem önceki terime hem de dizine bağlı olduğunu unutmayın. n.)
  • Sonuç sıfır olana kadar devam edin, bu noktada sıra sona erer.

Erken Goodstein dizileri hızla sona erer. Örneğin, G(3) 6. adımda sona erer:

BazKalıtsal gösterimDeğerNotlar
23Taban 2 gösteriminde 3 yazın
332'yi 3'e değiştirin, sonra 1'i çıkarın
433'ü 4'e çevirin, sonra 1'i çıkarın. Artık 4 saniye kalmadı
525 saniyeye geçmek için 4 saniye kalmadı. Sadece 1 çıkar
616s'ye geçmek için 5s kalmadı. Sadece 1 çıkar
707 saniyeye geçmek için 6 saniye kalmadı. Sadece 1 çıkar

Daha sonra Goodstein dizileri çok sayıda adım için artar. Örneğin, G(4) OEISA056193 şu şekilde başlar:

BazKalıtsal gösterimDeğer
24
326
441
560
683
7109
11253
12299
241151

Unsurları G(4) bir süre artmaya devam ediyor, ancak temelde maksimuma ulaşırlar , bir sonraki için orada kal Adımlar ve sonra ilk inişlerine başlayın.

0 değerine temelde ulaşılır . (Merakla, bu bir Woodall numarası: . Bu aynı zamanda 4'ten büyük başlangıç ​​değerleri için diğer tüm son temellerde de geçerlidir.[kaynak belirtilmeli ])

Ancak, hatta G(4) sadece Nasıl Goodstein dizisinin öğeleri hızla artabilir.G(19) çok daha hızlı artar ve şu şekilde başlar:

Kalıtsal gösterimDeğer
19
7625597484990

Bu hızlı büyümeye rağmen, Goodstein'ın teoremi şunu belirtir: her Goodstein dizisi sonunda 0'da sona erer, başlangıç ​​değeri ne olursa olsun.

Goodstein teoreminin kanıtı

Goodstein'ın teoremi aşağıdaki gibi kanıtlanabilir (Peano aritmetiği dışındaki teknikler kullanılarak, aşağıya bakınız): Bir Goodstein dizisi verildiğinde G(m), paralel bir dizi oluşturuyoruz P(m) nın-nin sıra sayıları ki bu kesinlikle azalıyor ve sona eriyor. Sonra G(m) da sona ermelidir ve yalnızca 0'a gittiğinde sona erebilir. Bu kanıtın yaygın bir yanlış anlaşılması, buna inanmaktır. G(m) 0'a gider Çünkü hakimdir P(m). Aslında gerçek şu ki P(m) hakim G(m) hiçbir rol oynamaz. Önemli olan nokta şudur: G(m)(k) ancak ve ancak P(m)(k) var (paralellik). O zaman eğer P(m) sona erer, yani G(m). Ve G(m) sadece 0 geldiğinde sona erebilir.

Bir fonksiyon tanımlıyoruz kalıtsal tabanı hesaplayan k temsili sen ve ardından tabanın her oluşumunu değiştirir k ilk sonsuzla sıra numarası ω. Örneğin, .

Her dönem P(m)(n) dizinin P(m) daha sonra olarak tanımlanır f(G(m)(n),n + 1). Örneğin, G(3)(1) = 3 = 21 + 20 ve P(3)(1) = f(21 + 20, 2) = ω1 + ω0 = ω + 1. Sıralı sayıların toplanması, çarpılması ve üslenmesi iyi tanımlanmıştır.

Biz iddia ediyoruz :

İzin Vermek olmak G(m)(n) ilkini uyguladıktan sonra, taban değiştirme Goodstein dizisinin sonraki elemanını oluşturma işlemi, ancak ikinciden önce eksi 1 bu nesilde operasyon. Bunu gözlemleyin .

Sonra açıkça . Şimdi uyguluyoruz eksi 1 operasyon ve , gibi .Örneğin, ve , yani ve , kesinlikle daha küçüktür. Hesaplamak için unutmayın f (G (m) (n), n + 1)önce yazmalıyız G(m)(n) kalıtsal temelde n+1 gösterim, örneğin ifade ya hiç mantıklı değil ya da eşit .

Böylece dizi P(m) kesinlikle azalmaktadır. Standart sıra sağlam temelli sonsuz, kesin olarak azalan bir dizi var olamaz veya eşdeğer olarak, her kesin olarak azalan sıra sırası sona erer (ve sonsuz olamaz). Fakat P(m)(n) doğrudan hesaplanır G(m)(n). Dolayısıyla dizi G(m) da sona ermelidir, yani 0'a ulaşması gerekir.

Goodstein teoreminin bu kanıtı oldukça kolay olsa da, Kirby-Paris teoremi,[1] Bu, Goodstein'ın teoreminin Peano aritmetiğinin bir teoremi olmadığını, teknik ve oldukça zor olduğunu gösterir. Kullanır sayılabilir standart olmayan modeller Peano aritmetiği.

Genişletilmiş Goodstein teoremi

Goodstein dizisinin tanımının, tabanın her oluşumunu değiştirmek yerine değiştirildiğini varsayalım. b ile b+1ile değiştirir b+2. Sıra yine de biter mi? b1, b2, b3,… Herhangi bir tam sayı dizisi olabilir. n+ 1.dönem G(m)(n+1) Genişletilmiş Goodstein dizisinin m aşağıdaki gibi olun: kalıtsal temeli alın bn temsiliG(m)(n) ve tabanın her geçtiği yeri değiştirin bnile bn+1 ve sonra bir çıkar. İddia, bu dizinin hala sona ermesidir. Genişletilmiş ispat, P(m)(n) = f(G(m)(n), n) asfollows: kalıtsal temeli alın bn temsiliG(m)(n) ve tabanın her geçtiği yeri değiştirinbn ilk sonsuzla sıra numarası ω. taban değiştirme Goodstein dizisinin buradan giderken çalışması G(m)(n) için G(m)(n+1) hala değerini değiştirmez fÖrneğin, eğer bn = 4 ve eğer bn+1 = 9,sonradolayısıyla sıra sıralı olandan kesinlikle daha büyüktür

Başlangıç ​​değerinin bir fonksiyonu olarak sıra uzunluğu

Goodstein işlevi, , öyle tanımlanmıştır ki ile başlayan Goodstein dizisinin uzunluğu n. (Bu bir toplam işlev çünkü her Goodstein dizisi sona erer.) fonksiyonlar gibi çeşitli standart sıralı indeksli fonksiyon hiyerarşileriyle ilişkilendirilerek kalibre edilebilir içinde Hardy hiyerarşisi ve fonksiyonlar içinde hızlı büyüyen hiyerarşi Löb ve Wainer:

  • Kirby ve Paris (1982) bunu kanıtladı
yaklaşık olarak aynı büyüme oranına sahiptir (ki ile aynıdır ); daha kesin, hakim her biri için , ve hakim
(Herhangi iki işlev için , söylendi hakim olmak Eğer yeterince büyük herkes için .)
  • Cichon (1983) gösterdi ki
nerede koymanın sonucudur n kalıtsal baz-2 gösteriminde ve sonra tüm 2'leri ω ile değiştirerek (Goodstein teoreminin ispatında yapıldığı gibi).
  • Caicedo (2007) gösterdi ki ile sonra
.

Bazı örnekler:

n
12
24
36
43·2402653211 − 2 ≈ 6.895080803×10121210694
5> Bir (4,4)>
6> Bir(6,6)
7> Bir(8,8)
8> Bir3(3,3) = Bir(Bir(61, 61), Bir(61, 61))
12> fω + 1(64) > Graham'ın numarası
19

(İçin Ackermann işlevi ve Graham'ın numarası sınırlar bkz hızlı büyüyen hiyerarşi # Hızla büyüyen hiyerarşilerde işlevler.)

Hesaplanabilir işlevlere uygulama

Goodstein'in teoremi bir toplam oluşturmak için kullanılabilir hesaplanabilir işlev Peano aritmetiğinin tam olduğunu kanıtlayamayacağı. Bir sayının Goodstein dizisi etkin bir şekilde bir Turing makinesi; böylece eşleyen işlev n Goodstein dizisi için gereken adım sayısına n sonlandırmak için belirli bir Turing makinesi hesaplanabilir. Bu makine yalnızca Goodstein dizisini numaralandırır. n ve sıra ulaştığında 0, dizinin uzunluğunu döndürür. Her Goodstein dizisi sonunda sona erdiğinden, bu işlev toplamdır. Ancak Peano aritmetiği, her Goodstein dizisinin sona erdiğini kanıtlamadığından, Peano aritmetiği, bu Turing makinesinin bir toplam işlevi hesapladığını kanıtlamaz.

Ayrıca bakınız

Referanslar

  1. ^ a b c Kirby, L .; Paris, J. (1982). "Peano Aritmetiği için Erişilebilir Bağımsızlık Sonuçları" (PDF). Londra Matematik Derneği Bülteni. 14 (4): 285. CiteSeerX  10.1.1.107.3303. doi:10.1112 / blms / 14.4.285.

Kaynakça

Dış bağlantılar