Goodstein teoremi
In matematik ve daha doğrusu içinde matematiksel mantık , Goodstein'e teoremi bir olan aritmetik deyim ilişkin dizileri denilen Goodstein'e dizileri . Goodstein dizileri, başlangıçta son derece hızlı büyüyen tam sayı dizileridir ve teorem, (görünüşe rağmen) her Goodstein dizisinin 0 ile bittiğini belirtir. Adını, yazarına, matematikçi ve mantıkçı Reuben Goodstein'a borçludur .
Goodstein'e teoremi kanıtlanabilir değildir Birinci dereceden Peano aritmetik gibi, ama daha güçlü teoriler ortaya konabilir ZF küme kuramı (basit bir kanıtı kullandığı sıra sayıları kadar ) ya da ikinci dereceden aritmetik . Bu nedenle teorem, birinci dereceden aritmetiğin özel durumunda, Gödel'in eksiklik teoremleri ile elde edilenlerden daha doğal bir karar verilemez ifade örneği verir .
ε0{\ displaystyle \ varepsilon _ {0}}
Goodstein dizisinin tanımı
Bir Goodstein dizisini tanımlamadan önce, ilk olarak temel n kalıtım gösterimini tanımlayalım . Böyle bir gösterimle doğal bir tamsayı yazmak için, önce onu temel n ayrışımının klasik biçiminde yazıyoruz :
-dekdeğilk+-dek-1değilk-1+⋯+-de0{\ displaystyle a_ {k} n ^ {k} + a_ {k-1} n ^ {k-1} + \ cdots + a_ {0}}burada her biri 0 ile n-1 arasında bir tamsayıdır . Daha sonra, sadece 0 ve n-1 arasındaki tam sayılardan oluşan bir ifade elde edene kadar aynı işlemi k , k-1 ,… üslerine yinelemeli olarak uygularız .
-deben{\ displaystyle a_ {i}}
Örneğin, 35 taban 2'de yazılır ve kalıtsal gösterim ( yinelemeli puanlama olarak da bilinir ) taban 2'de yazılır .
25+2+1{\ displaystyle 2 ^ {5} + 2 + 1}222+1+21+1{\ displaystyle 2 ^ {2 ^ {2} +1} + 2 ^ {1} +1}
Arasında Goodstein'e sekansı bir tam sayı m ile gösterilir, G ( m, dizinin ilk elemanı aşağıdaki gibidir:) tanımlanır m . Aşağıdaki elemanı elde etmek için, 2 tabanında kalıtsal gösterimde m yazıyoruz , sonra her 2'yi 3'e değiştiriyoruz ve son olarak sonuçtan 1 çıkarıyoruz. Ardından dizinin ikinci elemanına sahibiz. Üçüncüyü elde etmek için, kalıtsal gösterimde önceden hesaplanan elemanı 3 tabanına yazıyoruz, 3'leri 4'e değiştiriyoruz ve 1 çıkarıyoruz. 0 elde edene kadar bu şekilde devam ediyoruz (aşağıda gösterildiği gibi).
Daha resmi olarak, sıra aşağıdaki iki işlemin yinelenmesiyle tanımlanır: adım n'de (poz vererek ):
G(m){\ displaystyle G (m)}G1(m)=m{\ displaystyle G_ {1} (m) = m}
- Tamsayıyı kalıtsal gösterimde n + 1 tabanına yazın ve n + 1'i n + 2 ile değiştirin;Gdeğil(m){\ displaystyle G_ {n} (m)}
- 1 Çıkarın; biz böyle elde ederiz .Gdeğil+1(m){\ displaystyle G_ {n + 1} (m)}
Teoremin ifadesi
Goodstein teoremi - m'nin başlangıç değeri ne olursa olsun, Goodstein dizisi G ( m ) 0 ile biter.
Goodstein süit örnekleri
Goodstein'ın ilk devam filmleri hızla sona eriyor.
- Böylece, G (1) için:
-
G1{\ displaystyle G_ {1}}(1) = 1,
-
G2{\ displaystyle G_ {2}}(1) = 1-1 = 0
- Ve G (2) için:
-
G1{\ displaystyle G_ {1}}(2) = 2 = 2 1
-
G2{\ displaystyle G_ {2}}(2) = 3 1 - 1 = 2
-
G3{\ displaystyle G_ {3}}(2) = 2-1 = 1
-
G4{\ displaystyle G_ {4}}(2) = 1-1 = 0
Ancak, son bölümde daha kesin olarak göreceğimiz gibi, Goodstein dizileri genellikle çok sayıda aşamada büyür . Örneğin, G (4) ve G (5) dizileri şu şekilde başlar:
Değer
|
Kalıtsal gösterim
|
---|
4
|
2 2 |
26
|
2 3 2 + 2 3 + 2
|
41
|
2 4 2 + 2 4 + 1
|
60
|
2 5 2 + 2 5
|
83
|
2 6 2 + 6 + 5
|
109
|
2 7 2 + 7 + 4
|
|
...
|
253
|
2 11 2 + 11
|
299
|
2 12 2 + 11
|
|
...
|
1058
|
2 23 2 |
1151
|
24 2 + 23 24 + 23
|
|
...
|
|
|
Değer
|
Kalıtsal gösterim
|
---|
5
|
2 2 +1
|
27
|
3 3 |
255
|
3 4 3 + 3 4 2 + 3 4 + 3
|
467
|
3 5 3 + 3 5 2 + 3 5 + 2
|
775
|
3 6 3 + 3 6 2 + 3 6 + 1
|
1197
|
3 7 3 + 3 7 2 + 3 7
|
1751
|
3 8 3 + 3 8 2 + 2 8 + 7
|
|
...
|
10830
|
3 15 3 + 3 15 2 + 2 15
|
13087
|
3 16 3 + 3 16 2 + 16 + 15
|
|
...
|
92287
|
3 31 3 + 3 31 2 + 31
|
101407
|
3 32 3 + 3 32 2 + 31
|
|
...
|
762048
|
3 63 3 + 3 63 2 |
798719
|
3 64 3 + 2 64 2 + 63 64 + 63
|
|
...
|
|
- G (4) dizisi ile ilgili olarak, 6, 12 ve 24 bazları için gözlemlenen fenomen, p = 3 × 2 n formunun tüm bazları için yeniden üretilir : önceki değer bir birim terim içermez (terim (p- 1) 0 ) ve bu nedenle, p tabanında, güç terimi 1 veya 2'nin bir birimi kadar eşzamanlı olarak azaltılmasıyla (p-1) 'e eşit güç terimi 0 görünür.
Böylece ulaşmak baz b = 3 × 2 27 - 1 = 402 653 183, dizinin terimdir eşit için b 2 = 162 129 585 780 031 489 aşağıdaki terim (olduğunu b + 1) 2 - 1 yani ( b + 1) tabanında : b ( b + 1) + b ve bu nedenle sonraki terim b ( b + 2) + b - 1 vb. olacaktır, böylece artık herhangi bir terim kalmaz. kalıtımsal gösterimde güç 2 veya daha büyük.
B = ( b + 1) 2 b - 1 = 3 × 2 402 653210 - 1 tabanına ulaştığımızda, dizinin terimi B'ye eşittir (dizi de tabandan sabitti ( B + 1) / 2). Bu nedenle bir sonraki değer B-1'dir, yani sekans sonunda azalmaya başlar ve 2 B + 1 = 3 × 2 402 653211 - 1 tabanı için sıfır değerine ulaşır , bu da başka bir Woodall sayı (çünkü 3 × 2 402 653211 = 402653184 × 2 402653184 ). .
Temeli üzerinde, daha sonra G sekansı açısından sayısıdır aracı 120 milyondan fazla numaraları ile (4) uçları, G (4) mertebesindedir , 10 120 000 000 .
- G (5) dizisi çok daha hızlı büyümese de, çok daha uzun sürüyor ve olağan üstel gösterimler artık ulaşılan en büyük tabanı ifade etmemize izin vermiyor. Poz verme:
g(değil)=değil2değil{\ displaystyle g (n) = n2 ^ {n}}
gk=g∘g∘⋯∘g{\ displaystyle g ^ {k} = g \ circ g \ circ \ cdots \ circ g} k kere
M=g3(64)=270+270+2702270{\ displaystyle M = g ^ {3} (64) = 2 ^ {70 + 2 ^ {70} + 2 ^ {70} 2 ^ {2 ^ {70}}}}
DEĞİL=gM(M), P=gDEĞİL(DEĞİL), Q=gP(P),{\ displaystyle N = g ^ {M} (M), \ P = g ^ {N} (N), \ Q = g ^ {P} (P),}
G (5) dizisinin terim sayısı Q - 2'dir (bu hesaplamanın gerekçeleri için son bölüme bakın). Bu sayı tam olarak Knuth'un ok gösterimi kullanılarak ifade edilemez , ancak (bu gösterimde) 2 ↑↑↑ 6 mertebesinde veya yine Ackermann'ın fonksiyonu kullanılarak A (5, 4) mertebesinde ifade edilir .
- Bununla birlikte, bu iki örnek, Goodstein dizisinin ne kadar hızlı büyüyebileceği konusunda henüz yeterli bir fikir vermemektedir. Böylece G (19) çok daha hızlı büyür ve şu şekilde başlar:
(Bu hızlı büyümeye rağmen için bir n , n 7 adımda daha büyük bir sayı için, ve bu Graham sayıdan ), dizi, sonunda sıfıra azalır.
Kanıt
Goodstein'e teoremi kullanılarak (dış Peano aritmetik olan bir yöntem ile) gösterilebilir sıra sayıları : bir tamsayıdır verilen m ve Goodstein'e sekansı G ( m ), bir paralel dizi oluşturmak P ( m, sıra sayıları arasında) bu şekilde P ( m ) kesinlikle azalır ve biter. O zaman, yalnızca iptal edildiğinde sona erebilecek olan Goodstein G ( m ) ' nin devamı için aynı olacaktır .
Daha açık olarak, her bir tam sayı için n terimi dizisi P ( m ), bir dönüşümü uygulanarak elde edilir ucuna ait Goodstein'e dizisinin m aşağıdaki gibi: Biz baz kalıtsal temsil almak n teriminin + 1 , ve n + 1'in her bir oluşumunu ilk sonsuz ordinal ω ile değiştiririz; yani, örneğin ve . Sıralı sayıların toplanması, çarpılması ve üslenmesi iyi tanımlanmıştır ve sonuç, Cantor'un normal biçiminde temsil edilen bir sıradır . Ayrıca, gitmek Goodstein'e sekansında bir baz değişikliği gerçekleştirmek zaman için , elimizdeki : bu yapı merkez noktası (örneğin, ).
Pdeğil(m){\ displaystyle P_ {n} (m)}fdeğil+1{\ displaystyle f_ {n + 1}}Gdeğil(m){\ displaystyle G_ {n} (m)}Gdeğil(m){\ displaystyle G_ {n} (m)}G1(3)=3=21+20{\ displaystyle G_ {1} (3) = 3 = 2 ^ {1} + 2 ^ {0}}P1(3)=f2(G1(3))=ω1+ω0=ω+1{\ displaystyle P_ {1} (3) = f_ {2} (G_ {1} (3)) = \ omega ^ {1} + \ omega ^ {0} = \ omega +1}Gdeğil(m){\ displaystyle G_ {n} (m)}Gdeğil+1(m){\ displaystyle G_ {n + 1} (m)}Pdeğil(m)=fdeğil+1(Gdeğil(m))=fdeğil+2(Gdeğil(m)){\ displaystyle P_ {n} (m) = f_ {n + 1} (G_ {n} (m)) = f_ {n + 2} (G_ {n} (m))}f4(3⋅444+3.40)=3ωωω+3=f5(3⋅555+3){\ displaystyle f_ {4} (3 \ cdot 4 ^ {4 ^ {4}} + 3.4 ^ {0}) = 3 \ omega ^ {\ omega ^ {\ omega}} + 3 = f_ {5} (3 \ cdot 5 ^ {5 ^ {5}} + 3)}
1 çıkarıldıktan sonra, kesinlikle şunlardan daha az olacaktır :
Pdeğil+1(m)=fdeğil+2(Gdeğil(m))-1=fdeğil+2(Gdeğil+1(m)){\ displaystyle P_ {n + 1} (m) = f_ {n + 2} (G_ {n} (m)) - 1 = f_ {n + 2} (G_ {n + 1} (m))}Pdeğil(m){\ displaystyle P_ {n} (m)}
- ve Cantor, normal bir şekilde zaman formdadır ile , = . Yani kesinlikle şundan büyüktür ;Pdeğil(m){\ displaystyle P_ {n} (m)}X+α.ω0{\ displaystyle X + \ alpha. \ omega ^ {0}}α≠0{\ displaystyle \ alpha \ neq 0}Pdeğil+1(m){\ displaystyle P_ {n + 1} (m)}Pdeğil(m){\ displaystyle P_ {n} (m)}f4(3⋅444+3)=3ωωω+3{\ displaystyle f_ {4} (3 \ cdot 4 ^ {4 ^ {4}} + 3) = 3 \ omega ^ {\ omega ^ {\ omega}} + 3}f5(3⋅555+3)-1)=3ωωω+2{\ displaystyle f_ {5} (3 \ cdot 5 ^ {5 ^ {5}} + 3) -1) = 3 \ omega ^ {\ omega ^ {\ omega}} + 2}
- aynı şekilde, bir limit sıralı olduğunda , kesinlikle daha düşüktür, bu nedenle kesinlikle daha yüksektir ;Pdeğil(m){\ displaystyle P_ {n} (m)}Pdeğil+1(m){\ displaystyle P_ {n + 1} (m)}f4(3⋅44)=3ωω{\ displaystyle f_ {4} (3 \ cdot 4 ^ {4}) = 3 \ omega ^ {\ omega}}f5(3⋅55-1)=f5(2⋅54+4⋅53+4⋅52+4⋅51+4⋅50)=2⋅ω4+4⋅ω3+4⋅ω2+4⋅ω+4{\ displaystyle f_ {5} (3 \ cdot 5 ^ {5} -1) = f_ {5} (2 \ cdot 5 ^ {4} +4 \ cdot 5 ^ {3} +4 \ cdot 5 ^ {2 } +4 \ cdot 5 ^ {1} +4 \ cdot 5 ^ {0}) = 2 \ cdot \ omega ^ {4} +4 \ cdot \ omega ^ {3} +4 \ cdot \ omega ^ {2} +4 \ cdot \ omega +4}
- her iki durumda da, paralel dizinin P ( m ) kesinlikle azaldığı sonucuna varıyoruz .
P ( m ) dizisinin kesin düşüşü bir kez belirlendikten sonra, argüman şu şekilde devam eder: eğer G ( m ) dizisi 0'a ulaşmazsa, sonsuz olacaktır (çünkü her zaman tanımlanacaktır). Dolayısıyla P ( m ) de sonsuz olacaktır (çünkü her zaman tanımlanacaktır). Ancak P ( m ) kesinlikle azalmaktadır; artık standart düzen < az sıra sayıları setinde a, iyi bir düzen , orada bu nedenle sıkı bir sıra sayıları arasında sonsuz bir dizi azalmakta ya da başka bir deyişle, herhangi bir katı azalan sıra sayıları uçlarının sekansı, ve bu nedenle de sonsuz olamaz. Bu çelişki, G ( m ) dizisinin sona erdiğini ve dolayısıyla 0'a ulaştığını gösterir (bu arada, = 0 gibi bir doğal k sayısı olduğu için ve P ( m ) tanımına göre , bizde de = 0 var).
Gk+1(m){\ displaystyle G_ {k + 1} (m)}Pk+1(m){\ displaystyle P_ {k + 1} (m)}ε0{\ displaystyle \ varepsilon _ {0}}Gk(m){\ displaystyle G_ {k} (m)}Pk(m){\ displaystyle P_ {k} (m)}
Goodstein'in teoreminin ispatı görece kolay olsa da, Laurence Kirby ve Jeff Paris'in Goodstein'in teoreminin Peano'nun aritmetiğinde ispatlanamayacağını belirten teoremi, tekniktir ve oldukça zordur. Kirby ve Paris kanıtı kullanan sayılabilir standart dışı modeller Peano için Goodstein'e teoremi azaltmak için aritmetik arasında Gentzen en teoremi sıra £ değerinin indüksiyon kadar aritmetik kıvamına verir, 0 (Goodstein'e ispatı için kullanılan sıra sayıları daha yüksek bağlanmış teoremi).
Başlangıç değerinin bir fonksiyonu olarak dizinin uzunluğu
İşlev Goodstein'e , tarafından tanımlanan " Goodstein'e dizisi uzunluğu G ( n (bir)" uygulanarak bütün takımları Goodstein'e son olarak). Son derece hızlı büyüme fonksiyonları gibi ordinals tarafından dizine fonksiyonların çeşitli hiyerarşileri, bağlanarak ölçülebilir bir hiyerarşi Hardy (in) , veya fonksiyonlar arasında hızlı büyüyen hiyerarşi lob ve Wainer ait:
G:DEĞİL→DEĞİL{\ displaystyle {\ mathcal {G}}: \ mathbb {N} \ - \ mathbb {N} \, \!}G(değil){\ displaystyle {\ mathcal {G}} (n)}G{\ displaystyle {\ mathcal {G}} \, \!}Hα{\ displaystyle H _ {\ alpha} \, \!} fα{\ displaystyle f _ {\ alpha} \, \!}
- Kirby ve Paris (1982) bunu gösterdi
G{\ displaystyle {\ mathcal {G}} \, \!}yaklaşık olarak (ve dolayısıyla ) kadar hızlı büyür ; daha doğrusu, hakim her şey için ve baskındır
Hε0{\ displaystyle H _ {\ varepsilon _ {0}} \, \!}fε0{\ displaystyle f _ {\ varepsilon _ {0}} \, \!}G{\ displaystyle {\ mathcal {G}} \, \!}Hα{\ displaystyle H _ {\ alpha} \, \!}α<ε0{\ displaystyle \ alpha <\ varepsilon _ {0} \, \!}Hε0{\ displaystyle H _ {\ varepsilon _ {0}} \, \!}G.{\ displaystyle {\ mathcal {G}} \, \!.}
(iki fonksiyonlar için , biz demek ağırlıkta olmak eğer herkes için yeterince büyük). Daha doğrusu, Cichon (1983) şunu gösterdi:
f,g:DEĞİL→DEĞİL{\ displaystyle f, g: \ mathbb {N} \ - \ mathbb {N} \, \!}f{\ displaystyle f \, \!} g{\ displaystyle g \, \!}f(değil)>g(değil){\ displaystyle f (n)> g (n) \, \!}değil{\ displaystyle n \, \!}
G(değil)=HR2ω(değil+1)(1)-1,{\ displaystyle {\ mathcal {G}} (n) = H_ {R_ {2} ^ {\ omega} (n + 1)} (1) -1,}
burada yazılı sonucudur n (Goodstein'e teoreminin kanıtı gibi), co Tüm 2 yerine, taban 2 kalıtsal gösterimde.
R2ω(değil){\ displaystyle R_ {2} ^ {\ omega} (n)}
- (2007) Caicedo gösterdi ki eğer ile daha sonradeğil=2m1+2m2+⋯+2mk{\ displaystyle n = 2 ^ {m_ {1}} + 2 ^ {m_ {2}} + \ cdots + 2 ^ {m_ {k}}}m1>m2>⋯>mk,{\ displaystyle m_ {1}> m_ {2}> \ cdots> m_ {k},}
G(değil)=fR2ω(m1)(fR2ω(m2)(⋯(fR2ω(mk)(3))⋯))-2{\ displaystyle {\ mathcal {G}} (n) = f_ {R_ {2} ^ {\ omega} (m_ {1})} (f_ {R_ {2} ^ {\ omega} (m_ {2}) } (\ cdots (f_ {R_ {2} ^ {\ omega} (m_ {k})} (3)) \ cdots)) - 2}.
İşte bazı örnekler:
değil
|
G(değil){\ displaystyle {\ mathcal {G}} (n)}
|
---|
1
|
20{\ displaystyle 2 ^ {0}}
|
2-1{\ displaystyle 2-1}
|
Hω(1)-1{\ displaystyle H _ {\ omega} (1) -1}
|
f0(3)-2{\ displaystyle f_ {0} (3) -2}
|
2
|
2
|
21{\ displaystyle 2 ^ {1}}
|
21+1-1{\ displaystyle 2 ^ {1} + 1-1}
|
Hω+1(1)-1{\ displaystyle H _ {\ omega +1} (1) -1}
|
f1(3)-2{\ displaystyle f_ {1} (3) -2}
|
4
|
3
|
21+20{\ displaystyle 2 ^ {1} + 2 ^ {0}}
|
22-1{\ displaystyle 2 ^ {2} -1}
|
Hωω(1)-1{\ displaystyle H _ {\ omega ^ {\ omega}} (1) -1}
|
f1(f0(3))-2{\ displaystyle f_ {1} (f_ {0} (3)) - 2}
|
6
|
4
|
22{\ displaystyle 2 ^ {2}}
|
22+1-1{\ displaystyle 2 ^ {2} + 1-1}
|
Hωω+1(1)-1{\ displaystyle H _ {\ omega ^ {\ omega} +1} (1) -1}
|
fω(3)-2{\ displaystyle f _ {\ omega} (3) -2}
|
3 2 402 653211 - 2
|
5
|
22+20{\ displaystyle 2 ^ {2} + 2 ^ {0}}
|
22+2-1{\ displaystyle 2 ^ {2} + 2-1}
|
Hωω+ω(1)-1{\ displaystyle H _ {\ omega ^ {\ omega} + \ omega} (1) -1}
|
fω(f0(3))-2{\ displaystyle f _ {\ omega} (f_ {0} (3)) - 2}
|
> A (5,4) (burada A , Ackermann işlevidir )
|
6
|
22+21{\ displaystyle 2 ^ {2} + 2 ^ {1}}
|
22+2+1-1{\ displaystyle 2 ^ {2} + 2 + 1-1}
|
Hωω+ω+1(1)-1{\ displaystyle H _ {\ omega ^ {\ omega} + \ omega +1} (1) -1}
|
fω(f1(3))-2{\ displaystyle f _ {\ omega} (f_ {1} (3)) - 2}
|
> Bir (7.6)
|
7
|
22+21+20{\ displaystyle 2 ^ {2} + 2 ^ {1} + 2 ^ {0}}
|
22+1-1{\ displaystyle 2 ^ {2 + 1} -1}
|
Hωω+1(1)-1{\ displaystyle H _ {\ omega ^ {\ omega +1}} (1) -1}
|
fω(f1(f0(3)))-2{\ displaystyle f _ {\ omega} (f_ {1} (f_ {0} (3))) - 2}
|
> A (9,8)
|
8
|
22+1{\ displaystyle 2 ^ {2 + 1}}
|
22+1+1-1{\ displaystyle 2 ^ {2 + 1} + 1-1}
|
Hωω+1+1(1)-1{\ displaystyle H _ {\ omega ^ {\ omega +1} +1} (1) -1}
|
fω+1(3)-2{\ displaystyle f _ {\ omega +1} (3) -2}
|
> A 3 (3,3) = A ( A (61, 61), A (61, 61))
|
⋮{\ displaystyle \ vdots}
|
12
|
22+1+22{\ displaystyle 2 ^ {2 + 1} + 2 ^ {2}}
|
22+1+22+1-1{\ displaystyle 2 ^ {2 + 1} + 2 ^ {2} + 1-1}
|
Hωω+1+ωω+1(1)-1{\ displaystyle H _ {\ omega ^ {\ omega +1} + \ omega ^ {\ omega} +1} (1) -1}
|
fω+1(fω(3))-2{\ displaystyle f _ {\ omega +1} (f _ {\ omega} (3)) - 2}
|
> f ω + 1 (64)> G, Graham sayısı
|
⋮{\ displaystyle \ vdots}
|
16
|
222{\ displaystyle 2 ^ {2 ^ {2}}}
|
222+1-1{\ displaystyle 2 ^ {2 ^ {2}} + 1-1}
|
Hωωω(1)-1{\ displaystyle H _ {\ omega ^ {\ omega ^ {\ omega}}} (1) -1}
|
fωω(3)-2{\ displaystyle f _ {\ omega ^ {\ omega}} (3) -2}
|
> , yalnızca Conway gösteriminde Graham'ın sayısından daha büyük bir sayıda okla ifade edilebilen bir sayı .
fω2(G){\ displaystyle f _ {\ omega ^ {2}} (G)} |
⋮{\ displaystyle \ vdots}
|
19
|
222+21+20{\ displaystyle 2 ^ {2 ^ {2}} + 2 ^ {1} + 2 ^ {0}}
|
222+22-1{\ displaystyle 2 ^ {2 ^ {2}} + 2 ^ {2} -1}
|
Hωωω+ωω(1)-1{\ displaystyle H _ {\ omega ^ {\ omega ^ {\ omega}} + \ omega ^ {\ omega}} (1) -1}
|
fωω(f1(f0(3)))-2{\ displaystyle f _ {\ omega ^ {\ omega}} (f_ {1} (f_ {0} (3))) - 2}
|
|
( Ackermann işlevi A ve Graham sayısı G'yi içeren eşitsizlikler, hızlı büyüme hiyerarşisi makalesinde ayrıntılı olarak açıklanmıştır ).
Genellemeler ve benzer teoremler
Izin vermek bir tamsayılar dizisi (kesinlikle arttığını varsayabiliriz ); bir genel Goodstein'e dizisini tanımlayabilir ayarlayarak ve her aşamada, yazma kalıtsal baz gösterimde , tüm değiştirilmesi ile , ve elde edilmesi için sonuç 1 çıkarılması ; bu dizi, normal Goodstein dizisinden çok daha hızlı büyüyebilse de (buna karşılık gelir ), dizinin büyüme hızı ne olursa olsun , önceki ispat geçerlidir ve dizi her zaman 0'a ulaşır.
(bdeğil){\ displaystyle (b_ {n})}b0=2{\ displaystyle b_ {0} = 2}G(m)(değil){\ displaystyle G (m) (n)}G(m)(0)=m{\ displaystyle G (m) (0) = m}G(m)(değil){\ displaystyle G (m) (n)}bdeğil{\ displaystyle b_ {n}}bdeğil{\ displaystyle b_ {n}}bdeğil+1{\ displaystyle b_ {n + 1}}G(m)(değil+1){\ displaystyle G (m) (n + 1)}bdeğil=değil+2{\ displaystyle b_ {n} = n + 2}(bdeğil){\ displaystyle (b_ {n})}
Paris ve Kirby, Herkül'ün Lerna Hydra'yla savaş efsanesinden esinlenen bir hidra modelini kullanarak benzer süitler inşa ettiler . Bunlar, Herkül'ün her darbede bir tepe noktasını (bir kafa) kesebildiği ağaçlardır, bu da rastgele sayıda alt ağacın yeniden büyümesine neden olur, ancak daha düşük bir seviyede; Her bir ağacı sıralı (ε 0'dan küçük ) değiştirerek, elde edilen sıra sayılarının azalan bir sıra oluşturduğunu gösteriyoruz, bu nedenle sonuç: Herkül'ün stratejisi ne kadar kötü olursa olsun, ve ne kadar çok sayıda baş olursa olsun, hidra her zaman biter. yenilmek üzere; daha karmaşık baş büyütme kuralları ile, benzer akıl yürütme ayrıca ε 0'dan çok daha büyük sıra sayılarının kullanılmasını gerektirebilir .
Notlar
-
(inç) James M. Henle, Küme Teorisinin Anahatları ( çevrimiçi okuyun ) , s. 137-138.
-
Ortak bir hata olduğunu düşünmek için G ( m ) 0 ulaşır çünkü hakim olduğu P ( m ); aslında, bu P ( m ) hakim G ( m ) herhangi bir rol oynamaz: merkezi bir nokta olduğunu , ancak ve ancak mevcut (dizilerinin paralellik) bulunmaktadır. O zaman P ( m ) biterse, zorunlu olarak G ( m ) de biter . Ve G ( m ) yalnızca 0'a ulaşarak bitebilir.Gk(m){\ displaystyle G_ {k} (m)}Pk(m){\ displaystyle P_ {k} (m)}
-
(en) L. Kirby ve J. Paris , " Peano aritmetiği için erişilebilir bağımsızlık sonuçları " , Bull. Londra. Matematik. Soc. , cilt. 14,1982, s. 285-293 ( çevrimiçi okuyun ).
-
David Madore, " ψ (εΩ + 1) 'e kadar saymayı ve hidraları evcilleştirmeyi öğreniyorum " , http://www.madore.org ,16 Mart 2008(erişim tarihi 29 Nisan 2019 ) .
Ayrıca görün
Kaynakça
- (tr) R. Goodstein , " Kısıtlı sıra teoremi hakkında " , J. Symb. Mantık , cilt. 9,1944, s. 33-41 ( DOI 10.2307 / 2268019 )
-
(tr) EA Cichon , " Yinelemeli Teorik Yöntemler Kullanılarak Yakın Zamanda Keşfedilen İki Bağımsızlık Sonucunun Kısa Kanıtı " , Proc. Acı. Matematik. Soc. , cilt. 87,1983, s. 704-706 ( çevrimiçi okundu , 23 Haziran 2013'te erişildi ).
-
(en) A. Caicedo , " Goodstein'ın işlevi " , Revista Colombiana de Matemáticas , cilt. 41, n o 22007, s. 381-391 ( çevrimiçi okundu , 23 Haziran 2013'te erişildi ).
- Patrick Dehornoy , “ Sonsuzluk Gerekli mi? " La bilim dökün , n o " infinites 278" ,2000, s. 102-106 ( çevrimiçi okuyun )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">