Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Goodstein's theorem
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{short description|Theorem about natural numbers}} In [[mathematical logic]], '''Goodstein's theorem''' is a statement about the [[natural number]]s, proved by [[Reuben Goodstein]] in 1944, which states that every '''Goodstein sequence''' (as defined below) eventually terminates at 0. Laurence Kirby and [[Jeff Paris (mathematician)|Jeff Paris]]{{sfn|Kirby|Paris|1982}} showed that it is [[independence (mathematical logic)|unprovable]] in [[Peano axioms#Peano arithmetic as first-order theory|Peano arithmetic]] (but it can be proven in stronger systems, such as [[second-order arithmetic]] or [[Zermelo-Fraenkel set theory]]). 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 [[Epsilon numbers (mathematics)|ε<sub>0</sub>]]-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.{{sfn|Kirby|Paris|1982}}
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)