Goodsteinin lause on matemaattisen logiikan lause luonnollisista luvuista , jonka on todistanut Reuben Goodstein [1] . Väittää, että kaikki Goodstein-sekvenssit päättyvät nollaan. Kuten L. Kirby ja Jeff Paris [2] [3] osoittavat , Goodsteinin lause ei ole todistettavissa Peanon aksiomatiikassa ( ) (mutta voidaan todistaa esimerkiksi toisen asteen aritmetiikassa ).
Tarkastellaan positiivisten kokonaislukujen esittämistä potenssitermien summana, joilla on sama kanta.
Esimerkiksi kirjoitetaan numero 581 käyttämällä kantaa 2:
Jaetaan eksponentit samalla periaatteella:
Samanlainen laajennus voidaan saada mille tahansa numerolle.
Käytämme rekursiivisesti seuraavaa toimintoa tuloksena olevaan lausekkeeseen:
Näin ollen, kun ensimmäinen operaatio on tehty (muuta 2 arvoon 3 ja vähennä yksi numerosta), lauseke saadaan
Toisen jälkeen (muuta 3 arvoon 4 ja vähennä yksi numerosta):
Kolmannen jälkeen (muuta 4 arvoon 5 ja vähennä yksi numerosta):
Goodsteinin lause sanoo, että lopputulos on aina 0.
Vahvempi väite on myös totta: Jos 1:n sijaan lisätään mielivaltainen luku kantaan ja vähennetään itse luvusta, saadaan aina 0, vaikka eksponentit eivät alun perin hajottaisi kantaa 2:een.
Viimeinen kanta alkuperäisen luvun diskreettifunktiona kasvaa hyvin nopeasti ja saavuttaa jo arvon . Sillä , se on aina Woodall-luku [4] .
Harkitse esimerkkiä Goodsteinin sekvenssistä numeroille 1, 2 ja 3.
Määrä | Pohja | Äänite | Merkitys |
---|---|---|---|
yksi | 2 | yksi | yksi |
3 | yksitoista | 0 | |
2 | 2 | 2 1 | 2 |
3 | 3 1-1 _ | 2 | |
neljä | 2-1 | yksi | |
5 | 1-1 | 0 | |
3 | 2 | 2 1 + 1 | 3 |
3 | (3 1 + 1) − 1 = 3 1 | 3 | |
neljä | 4 1 − 1 = 1 + 1 + 1 | 3 | |
5 | (1 + 1 + 1) − 1 = 1 + 1 | 2 | |
6 | (1 + 1) − 1 = 1 | yksi | |
7 | 1-1 = 0 | 0 |