Кіріспе
Натурал сандар туралы теорема. Математикалық логикада Гудштейн теоремасы – Рубен Гудштейннің 1944 жылы дәлелдеген, Гудштейн тізбегінің кез келгенінің (төменде берілген анықтама бойынша) ақырында 0-ге дейін аяқталуын көрсететін, натурал сандар туралы мәлімдеме. Лоренс Кирби мен Джефф Пэрис оның Пеано арифметикасында дәлелденбейтінін көрсетті (бірақ оны жоғары дәрежелі арифметика сияқты күшті жүйелерде дәлелдеуге болады). Бұл, Гёдельдің толық еместік теоремасы және Герхард Гентценнің 1943 жылғы Пеано арифметикасында ε0 индукциясының дәлелденбейтінін тікелей дәлелдеуінен кейін, Пеано арифметикасында дәлелденбейтін натурал сандар туралы үшінші нақты мәлімдеме болды. Париж-Харрингтон теоремасы тағы бір мысал келтірді. Кирби мен Пэрис Гудштейн тізбектеріне ұқсас мінез-құлыққа ие граф теориялық гидра ойынын енгізді: «Гидра» (мифологиялық көп басты Лерна гидрасының атымен аталған) – тамырланған ағаш, ал әрекет оның «бастарының» біреуін (ағаш бұтағын) кесуден тұрады, ал гидра белгілі бір ережелерге сәйкес жаңа бастардың шекті санын өсіру арқылы жауап береді. Кирби мен Пэрис Гидраның Гераклдың басын кесу стратегиясына қарамастан, ақырында өлтірілетінін дәлелдеді, бірақ бұл өте ұзаққа созылуы мүмкін. Гудштейн тізбектері сияқты, Кирби мен Пэрис оны тек Пеано арифметикасымен дәлелдеуге болмайтынын көрсетті. Егер P(m) аяқталса, G(m) да аяқталатын болады. Шегі жоқ регрессия арқылы G(m) 0-ге жетеді, бұл аяқталуын қамтамасыз етеді. Біз u-дың мұрагерлік k негізіндегі жазылуын есептейтін және содан кейін k негізінің әрбір кездесуін бірінші шексіз реттік сан ω-мен ауыстыратын функцияны анықтаймыз. Мысалы, P(m)(n) тізбегінің әрбір мүшесі f(G(m)(n), n+1) ретінде анықталады. Мысалы, 1 = G(3)(1) = 3 = 21 + 20 және 1 = P(3)(1) = f(21 + 20, 2) = ω1 + ω0 = ω + 1. Реттік сандарды қосу, көбейту және дәрежелеу жақсы анықталған. Біз былай деп мәлімдейміз: G(m)(n) Гудштейн тізбегінің келесі мүшесін құру кезінде бірінші, негізді өзгерту операциясын қолданғаннан кейін, бірақ осы ұрпақтағы екінші минус 1 операциясынан бұрын. Енді біз минус 1 операциясын қолданамыз, және, мысалы, және, және, және, бұл қатаң түрде кіші. f(G(m)(n), n+1) есептеу үшін алдымен G(m)(n) н+1 мұрагерлік негізінде жазылуын алу керек, мысалы, өрнегі реттік сан емес. Осылайша P(m) тізбегі қатаң түрде төмендейді. Реттік сандардағы стандартты < рет жақсы негізделгендіктен, шексіз қатаң түрде төмендейтін тізбек болуы мүмкін емес, немесе, балама ретінде, реттік сандардың кез келген қатаң түрде төмендейтін тізбегі аяқталады (және шексіз бола алмайды). Бірақ P(m)(n) тікелей G(m)(n) арқылы есептеледі. Сондықтан G(m) тізбегі де аяқталуы керек, яғни ол 0-ге жетуі керек. Гудштейн теоремасының бұл дәлелі оңай болғанымен, Гудштейн теоремасы Пеано арифметикасының теоремасы емес екенін көрсететін Кирби-Пэрис теоремасы техникалық және әлдеқайда қиын. Ол Пеано арифметикасының санаулы емес стандартты емес модельдерін пайдаланады.
In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence (as defined below) eventually terminates at 0. Laurence Kirby and Jeff Paris showed that it is unprovable in Peano arithmetic (but it can be proven in stronger systems, such as second order arithmetic). This was the third example of a true statement about natural numbers that is unprovable in Peano arithmetic, after the examples provided by Gödel's incompleteness theorem and Gerhard Gentzen's 1943 direct proof of the unprovability of ε0 induction in Peano arithmetic. The Paris–Harrington theorem gave another example. Kirby and Paris introduced a graph theoretic hydra game with behavior similar to that of Goodstein sequences: the "Hydra" (named for the mythological multi headed Hydra of Lerna) is a rooted tree, and a move consists of cutting off one of its "heads" (a branch of the tree), to which the hydra responds by growing a finite number of new heads according to certain rules. Kirby and Paris proved that the Hydra will eventually be killed, regardless of the strategy that Hercules uses to chop off its heads, though this may take a very long time. Just like for Goodstein sequences, Kirby and Paris showed that it cannot be proven in Peano arithmetic alone. Then if P(m) terminates, so does G(m). By infinite regress, G(m) must reach 0, which guarantees termination. We define a function which computes the hereditary base k representation of u and then replaces each occurrence of the base k with the first infinite ordinal number ω. For example,
Each term P(m)(n) of the sequence P(m) is then defined as f(G(m)(n),n+1). For example, 1=G(3)(1) = 3 = 21 + 20 and 1=P(3)(1) = f(21 + 20,2) = ω1 + ω0 = ω + 1. Addition, multiplication and exponentiation of ordinal numbers are well defined. We claim that :
Let be G(m)(n) after applying the first,
base changing operation in generating the next element of the Goodstein sequence,
but before the second minus 1 operation in this generation. Observe that
Then Now we apply the minus 1 operation, and , as For example, and , so and , which is strictly smaller. Note that in order to calculate f(G(m)(n),n+1), we first need to write G(m)(n) in hereditary base n+1 notation, as for instance the expression is not an ordinal. Thus the sequence P(m) is strictly decreasing. As the standard order < on ordinals is well founded, an infinite strictly decreasing sequence cannot exist, or equivalently, every strictly decreasing sequence of ordinals terminates (and cannot be infinite). But P(m)(n) is calculated directly from G(m)(n). Hence the sequence G(m) must terminate as well, meaning that it must reach 0. While this proof of Goodstein's theorem is fairly easy, the Kirby–Paris theorem, which shows that Goodstein's theorem is not a theorem of Peano arithmetic, is technical and considerably more difficult. It makes use of countable nonstandard models of Peano arithmetic.
Есептелетін функцияларға қолдану
Гудштейн теоремасы Пьяно арифметикасының толық екенін дәлелдей алмайтын толық есептелетін функцияны құру үшін қолданылуы мүмкін. Санның Гудштейн тізбесін Тьюринг машинасы тиімді түрде санап шығара алады; демек, n-ді n-нің Гудштейн тізбесінің аяқталуына қажетті қадамдар санына бейімдейтін функция нақты бір Тьюринг машинасымен есептелуге болады. Бұл машина тек n-нің Гудштейн тізбесін санап шығарады және тізбек 0-ге жеткенде, тізбектің ұзындығын қайтарады. Барлық Гудштейн тізбектері әрқашан аяқталады, сондықтан бұл функция толық болып табылады. Бірақ Пьяно арифметикасы Гудштейннің әрбір тізбегінің аяқталуын дәлелдей алмайды, сондықтан Пьяно арифметикасы бұл Тьюринг машинасы толық функцияны есептейді деп дәлелдей алмайды.