Теория алгоритмов. Зюзысов В.М. - 53 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

2. m < n ⇔ B
b
(m) < B
b
(n);
3. B
b
(n) = B
b+1
(F
b
(n)) (поскольку в правой части основание b в наследственном
представление n сначала заменяется на b+1, а потом b+1 заменяется на ω).
Зафиксируем n>0 и пусть g
0
, g
1
, g
2
, … – последовательность Гудстейна для данного
числа n, т.е. g
k
= G
k
(n) при k=0,1,2,… Определим теперь соответствующую
последовательность ординалов a
0
, a
1
, a
2
, … по правилу a
k
= B
k+2
(g
k
) при k=0,1,2,… Пусть
для всех k=0,1,2,… выполнено g
k
> 0. Придем к противоречию, и тем самым теорема будет
доказана.
Сравним a
k
и a
k+1
. Имеем g
k+1
=
F
k+2
(g
k
)-1 (здесь как раз используется
предположение, что последовательность Гудстейна не содержит 0), поэтому
a
k+1
= B
k+3
(g
k+1
) = B
k+3
(F
k+2
(g
k
)-1) < B
k+3
(F
k+2
(g
k
)) = (по свойству (3)) B
k+2
(g
k
) = a
k
.
Проиллюстрируем предыдущее неравенство на примере:
Пусть n=266. Тогда g
0
= 266 =
21
2
2
+
+ 2
2
+ 2, и a
0
= B
2
(g
0
) =
1
ω
ω
ω
+
+ ω
ω
+ ω.Также имеем g
1
=
+ 3
31
3
3
+
3
+ 2, и a
1
= B
3
(g
1
) =
1
ω
ω
ω
+
+ ω
ω
+ 2. Очевидно, a
1
< a
0
.
Таким образом, получили бесконечную убывающую последовательность
ординалов a
0
> a
1
> > a
2
> a
3
> … , что невозможно.
Гудстейн доказал теорему в 1944 году, используя трансфинитную индукцию [3]. В
1982 году Л. Кирби и Дж. Парис получили результат о том, что теорема Гудстейна
формально недоказуема в рамках аксиоматической системы элементарной арифметики
[4].

Страницы