Accessible Independence Results for Peano Arithmetic 论文

摘要

Recently some interesting first-order statements independent of Peano Arithmetic (P) have been found. Here we present perhaps the first which is, in an informal sense, purely number-theoretic in character (as opposed to metamathematical or combinatorial). The methods used to prove it, however, are combinatorial. We also give another independence result (unashamedly combinatorial in character) proved by the same methods. The first result is an improvement of a theorem of Goodstein [2]. Let m and n be natural numbers, n> 1. We define the base n representation of m as follows: First write m as the sum of powers of n. (For example, if m = 266, n = 2, write 266 = 2 8 + 2 3 + 2 1.) Now write each exponent as the sum of powers of n. (For example, 266 = 2 23 + 2 2 + 1 +2 1.) Repeat with exponents of exponents and so on until the representation stabilizes. For example, 266 stabilizes at the representation 2 * +l + 2 2 + l +2 l. We now define the number Gn(m) as follows. If m = 0 set Gn(m) = 0. Otherwise set Gn(m) to be the number produced by replacing every n in the base n representation of m by n +1 and then subtracting 1. (For example, G2(266) = 3 33+1 + 3 3 + 1 +2). Now define the Goodstein sequence for m starting at 2 by So, for example, m0 = m, mx = G2{m0), m2 = G^mJ, m3 = G^m2),.... 266O = 266 = 2 22+1 + 2 2+1 + 2 X = 3 33+1 + 3 3+1 + 2 ~ 1O 38 2662 = 4 44+1 + 4 4+1 + l ~ 10 616 2663 = 5 s5+1 + 5 5+1 ~ 10 10- 000. Similarly we can define the Goodstein sequence for m starting at n for any n> 1. THEOREM 1. (i) (Goodstein [2]) Vm 3/c mk = 0. More generally for any m, n> 1 the Goodstein sequence for m starting at n eventually hits zero. (ii) Vm 3k mk = 0 (formalized in the language of first order arithmetic) is not provable