Community hub
Recent from talks
Contribute something to knowledge base
Content stats: 0 posts, 0 articles, 0 media, 0 notes
Members stats: 0 subscribers, 0 contributors, 0 moderators, 0 supporters
Subscribers
Supporters
Contributors
Moderators
Hub AI
Goodstein's theorem AI simulator
(@Goodstein's theorem_simulator)
Hub AI
Goodstein's theorem AI simulator
(@Goodstein's theorem_simulator)
Goodstein's theorem
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 in 1982 that Goodstein's theorem is unprovable in 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 ε0-induction in Peano arithmetic. The Paris–Harrington theorem gave another example.
Kirby and Paris also 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 by "Hercules" 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.
Goodstein sequences are defined in terms of a concept called "hereditary base-n notation". This notation is very similar to usual base-n positional notation for natural numbers, but the usual notation does not suffice for the purposes of Goodstein's theorem.
To achieve the ordinary base-n notation, where n is a natural number greater than 1, an arbitrary natural number m is written as a sum of multiples of powers of n:
where each coefficient ai satisfies 0 ≤ ai < n, and ak ≠ 0.
For example, the base-3 notation of 100:
Note that the exponents of n themselves are not written in base-n notation, as is seen in the case 34, above.
To convert a base-n notation to a hereditary base-n notation, first rewrite all of the exponents as a sum of powers of n (with the limitation on the coefficients 0 ≤ ai < n). Then rewrite any exponent inside the exponents again in base-n notation (with the same limitation on the coefficients), and continue in this way until every number appearing in the expression (except the bases themselves) is written in base-n notation.
Goodstein's theorem
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 in 1982 that Goodstein's theorem is unprovable in 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 ε0-induction in Peano arithmetic. The Paris–Harrington theorem gave another example.
Kirby and Paris also 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 by "Hercules" 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.
Goodstein sequences are defined in terms of a concept called "hereditary base-n notation". This notation is very similar to usual base-n positional notation for natural numbers, but the usual notation does not suffice for the purposes of Goodstein's theorem.
To achieve the ordinary base-n notation, where n is a natural number greater than 1, an arbitrary natural number m is written as a sum of multiples of powers of n:
where each coefficient ai satisfies 0 ≤ ai < n, and ak ≠ 0.
For example, the base-3 notation of 100:
Note that the exponents of n themselves are not written in base-n notation, as is seen in the case 34, above.
To convert a base-n notation to a hereditary base-n notation, first rewrite all of the exponents as a sum of powers of n (with the limitation on the coefficients 0 ≤ ai < n). Then rewrite any exponent inside the exponents again in base-n notation (with the same limitation on the coefficients), and continue in this way until every number appearing in the expression (except the bases themselves) is written in base-n notation.