Goodstein's theorem

Goodstein sequences are special sequences of natural numbers. They play a role in a mathematical theorem, the set of Goodstein. The special thing about this set is that while he formulate itself with the means of Peano arithmetic, but does not exclusively prove with them. This is because that the Peano arithmetic of natural numbers not clearly modeled, ie, it allows other models as the natural numbers, in which the set of Goodstein does not apply. This sentence is an example that not every unprovable statement needs to be as complex and " unimaginable " as the unprovable statements in Gödel 's incompleteness between.

Definition of Goodstein sequences

Every natural number n can be developed to a given base b as follows:

Wherein the coefficients are comprised between 0 and b -1 (see priority system ).

For example, " 35" the representation of a natural number in the decimal system:

To the base 2 is the representation

This the base b representation is now applied to the exponent, and then the exponent of the exponent, until no number occurs more above the base. This representation is called the iterated the base b representation (English hereditary base b representation ). For the number 35 gives this illustration:

Using this representation iterated ( engl. "bump the base" ) is the Goodsteinsche operation " bloat " is defined. This replaces wherever in the iterated representation of a number to base b is, by this. This illustration that the number n to base b is iterated and then inflates, here is as

Written (there are in the literature many different spellings for it).

Now if n is a natural number, then the Goodstein sequence with start value n is

Using this mapping defined as follows:

The second follow-up member is so calculated by iterated n represents the base, then swells and subtracted from the number 1 inflated.

Examples

The Goodstein sequences for n = 1 to 3 are still quite short:

N = 1:

N = 2:

N = 3:

Note that, here B = 4, the increase of the base has no effect because the count is then smaller than the base, it is bgzl. this basis, so to speak, " digit ".

N = 4

This sequence increases quite a long time, until the base 3 ·, remains again twice as long as constant, and then decreases until, at the base 3 x - 1, the value 0 is reached. The number of steps required here is thus itself a number with more than 121 million decimal places.

An impression of Goodstein sequences can grow as quickly, provide larger values ​​of n

N = 19:

The set of Goodstein

The set of Goodstein is:

This theorem was proved in 1944 by the English logician Reuben Louis Goodstein ( 1912-1985 ). This set is especially so interesting within mathematics, because it may be implied by the axioms of Peano arithmetic. Instead, the evidence means of set theory, especially the theory of ordinal numbers.

Proof of the theorem of Goodstein

The set of Kirby and Paris states that the set of Goodstein is not provable with funds from the Peano arithmetic. So you need a more powerful tool: the ordinal numbers.

The theory of the ordinal numbers by extending the natural sizes that are larger than any natural numbers. The smallest infinite ordinal ω (small Greek letter omega) called. Ordinals can you add, multiply and multiply, but some computation rules of natural numbers do not apply to ordinal numbers (eg, is ω 1 ω = ω ≠ 1 ). Ordinals in order of size (they have a total order ), the arithmetic mentioned three are monotonic in all arguments, and the ordinals are well-ordered, ie, there are no strictly decreasing infinite sequence of ordinals.

We now assign to each natural number n to an ordinal, by taking n to base b are iterated and then replace each b by ω. The resulting ordinal numbers can be obtained by a finite sequence of additions, multiplications and exponentiations of ω and the natural numbers; the amount of such displayable ordinal means ( this amount is the minimum ordinal number in this way can not be displayed ). So we have a picture

(again, there are in the literature different spellings ).

It is, for example,

N is less than B, then a finite ordinal number, for example, is

The inflation has no effect on the ordinal, because it does not matter whether one equal to each b replaced in the iterated presentation by ω, or until each b by and then each of ω, it is therefore

However, the subtraction of one affects the ordinal number: This is reduced.

For example, applies

The Goodstein sequence we associate now a sequence of ordinals as to:

This sequence is often called the "parallel sequence" (English " parallel sequence" ).

This sequence of ordinals is strictly decreasing, so it must after finitely many steps at 0 end ( ordinals have a well-ordering ). Since for all n and b applies, including the Goodstein sequence terminates after finitely many steps.

The set of Goodstein says nothing about how many steps ends a Goodstein sequence; So he is a pure existence theorem:

Independence of Peano arithmetic

During the proof of the theorem of Goodstein is relatively easy (if you are familiar with the theory of ordinal numbers ) is the claim that this sentence is provable solely on the Peano arithmetic, much more difficult to prove. This was Laurie Kirby and Jeff Paris 1982. Named after them set of Kirby and Paris used a so-called non- standard model of Peano arithmetic.