Goodstein Dizisi: Sıfıra İner Ama Peano'nun Görmeye Gücü Yetmez

Tek bir sayıyla başlayan bir oyun

Reuben Goodstein'ın 1944'te tanımladığı oyun:

1. Bir başlangıç sayısı seç, örneğin $n = 4$.
2. Onu iteratif taban-$2$ gösteriminde yaz: $4 = 2^{2}$.
3. Tüm $2$'leri $3$'e değiştir, sonra $1$ çıkar.
4. Yeni sayıyı iteratif taban-$3$'te yaz, $3$'leri $4$'e değiştir, $1$ çıkar.
5. Bu şekilde devam et.

İteratif taban-$b$ gösterimi ne? Standart taban-$b$'de $266 = 2 \cdot 11^2 + 4 \cdot 11 + 2$ yazılır ama üsler de $11$'den büyük olabilir. İteratif versiyonda üsleri de tabana açarsınız, ve onların üslerini de... ta ki tabandan küçük sayılarla bitene kadar.

Örnek: $266 = 2^{2^{2+1} + 1} + 2^{2+1} + 2$ (taban-2 iteratif).

Tipik bir Goodstein dizisi

$n = 4$ ile başlarsak:

• $a_2 = 4 = 2^2$
• Tabanı 3'e çevir: $3^3 = 27$, sonra −1: $a_3 = 26 = 2 \cdot 3^2 + 2 \cdot 3 + 2$
• Tabanı 4: $2 \cdot 4^2 + 2 \cdot 4 + 2 = 42$, −1: $a_4 = 41$
• Tabanı 5: $... = 60$, −1: $a_5 = 59$
• ...

İlk birkaç adımda büyür, sonra yavaşlar. Sonunda — milyonlarca/milyarlarca adım sonra — sıfıra iner. $n=4$ için kesin değer: dizi $3 \cdot 2^{402653211} - 2$ adımda sıfıra ulaşır.

Goodstein teoremi (1944)

Her başlangıç sayısı için Goodstein dizisi sonlu adımda sıfıra iner.

Başlangıç sayısı $n=2$ kadar küçük olsun, $n=10^{100}$ kadar büyük olsun — dizi daima sonludur ve sıfırla biter. İstisna yok.

Astronomik büyüme

Ama "sonlu" bizim hayal edemeyeceğimiz büyüklüktedir. Örneğin $n=12$ için dizi yaklaşık $10^{10^{10^{19}}}$ adım sürer. Standart sayma teknikleriyle ifade edilemez; Knuth'un yukarı ok notasyonu ya da Conway zincir notasyonu gerekir.

Yine de... sonlu.

Şaşırtıcı kanıt

Kanıt nasıl çalışır? Sıralı sayılar (ordinaller) kullanılır. Her Goodstein dizisi terimini, sayısal değerini değil iteratif tabanını "$\omega$ ile değiştirilmiş" sıralı eşdeğeri olarak ele alın:

• $4 = 2^2$ → $\omega^\omega$
• $26 = 2 \cdot 3^2 + 2 \cdot 3 + 2$ → $2 \cdot \omega^2 + 2\omega + 2$
• ...

Her adımda sıralı azalır (çünkü "−1" terimi bir basamağı azaltır). Sıralı sayıların iyi-sıralı özelliği gereği, azalan sıralı diziler sonludur. Dolayısıyla Goodstein dizisi de sonludur.

Kullanılan sıralı uzayı $\varepsilon_0$ (epsilon-sıfır) — taban-$\omega$ kulesinin limit sayısı:

$\varepsilon_0 = \omega^{\omega^{\omega^{\cdots}}}$

Paris-Kirby teoremi (1982): Peano'da kanıtlanamaz

Britanyalı mantıkçılar Laurie Kirby ve Jeff Paris 1982'de şu olağanüstü sonucu kanıtladılar:

Goodstein teoremi, Peano aritmetiğinde (PA) kanıtlanamaz.

Peano aritmetiği = doğal sayıların standart aksiyom sistemi (tümevarım dahil). PA içinde Goodstein teoremini ifade edebilirsiniz ama kanıtlayamazsınız.

Neden? Çünkü kanıt $\varepsilon_0$'a kadar olan sıralılarla iyi-sıralılığı gerektirir; PA bunu içeremez. Daha güçlü bir sistem (ZFC, ya da PA + $\varepsilon_0$-iyi-sıralı aksiyomu) gerekir.

Bu, Gödel'in eksiklik teoreminin somut bir örneği. Gödel 1931'de "kanıtlanamaz ama doğru bir önerme vardır" demişti; Paris-Kirby 51 yıl sonra doğal, klasik bir önermenin böyle olduğunu gösterdiler.

Bu, eksiklik teoreminin uygulamalı yüzü.

Karşılaştırma: Friedman, hidra

Benzer mantıkta başka örnekler:

• Kirby-Paris hidra oyunu: Lerna hidrasını "kafa keserek" öldürmeye çalışırsınız; her kesik daha çok kafa doğurur. Yine kazanırsınız (her stratejiyle), ama PA bunu kanıtlayamaz.
• Friedman'ın sonsuz Kruskal teoremi: Bir parça kombinatoryal teorem; ZFC'nin alt sistemlerinde kanıtlanamaz.
• Robertson-Seymour graf minör teoremi: PA'da çok aşılarak kanıtlanabilir.

Bu örneklere "doğal bağımsız önermeler" denir; matematik mantığının ilginç kısımlarından.

Bilgisayar bilimine bağ: terminate eden programlar

Bir program "sonlandığını" kanıtlamak için, her döngü adımında bir ordinal'in azaldığını gösterirsiniz. Bu, iyi-sıralılık prensibiyle programın er ya da geç duracağını garanti eder.

Goodstein dizisi, doğal sayılarla ifade edilen ama ordinallerle anlaşılan terminasyonun en zarif örneği. Modern tip teorisi (Coq, Lean) bu prensipler üzerine kuruludur.

Sezgisel mesaj

Goodstein dizisinin "büyür ama döner" davranışı, matematiksel bir karşı-sezgidir: bir nicelik muazzam büyüyebilir, sınır yokmuş gibi görünür, ama yine de er ya da geç inerek sıfıra ulaşır — yeter ki süreç iyi-sıralı bir altyapı tarafından yönetilsin.

Uygun bir benzetme: bir ülkenin çiçekleyen ama mütemadiyen düşen iktisadı, bir hayvanın yaşamı, bir uygarlığın yükseliş-çöküşü. Üst sınır yok, ama bir gizli zayıf invaryant azalır.

Goodstein bu yapıyı sayılarda gösterdi.

Sonuç

Goodstein dizisi matematiksel düşüncenin tuhaflığını gösteren en güzel örneklerden biri:

• Çok basit kurallı bir oyun;
• Astronomik büyüyen ara değerler;
• Daima sonlu çıkış;
• Standart Peano aritmetiğinde kanıtlanamayan bir gerçek.

Matematik bazen kendini aşar. Gerçeği görmek için, gerçeği yaratan sistemden daha yükseğe çıkmak gerekir.