Файл: Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf

112

АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ

МНОЖЕСТВА

1ГЛ. I

Будем

говорить, что

алгорифм

91 над

алфавитом А\

является

последовательностью

перечислимых

множеств

в алфавите А, если при каждом п алгорифм

91 п а

пере­

числяет некоторое множество слов в алфавите А.

(Здесь

а — произвольная буква, не принадлежащая

А.)

Пусть

91 — последовательность

перечислимых

мно­

жеств

в алфавите А, Ж — множество слов в этом

алфа­

вите.

Будем

говорить,

что

Ж является

пересечением

(объединением)

последовательности

91, если для

любого

слова Р в А выполняется

Р*=Л^Чп(Р<Е={%па})

(соответственно

P e I s H « ( P e

{€„„})).

В

связи

с теоремой

13

возникает

вопрос

о

том,

Т е о р е м а

14. Объединение

последовательности

пе­

речислимых

множеств перечислимо.

Д о к а з а т е л ь с т в о .

Пусть 91 — последовательность

перечислимых

множеств,

Ж — объединение этой

после­

довательности. Построим

алгорифм 93 так, что

93(n)~2t(/2 (tt) а/2 (п)),

и покажем, что 93 перечисляет

Ж.

Пусть Р е

Ж. Тогда при некоторых m и i

Р =

91 (таг).

Найдем

/

так, что

слов в алфавите

Ч\.)

Алфавит Ч будет являться «универсальным» в том

смысле, что изучаемые в данных

главах конструктивные

объекты — либо

слова

в этом алфавите, либо кодируют­

ся посредством

таких

слов.

Обозначим

через

Ча двухбуквенное

расширение

Ч U {ab}

алфавита Ч.

Поскольку

рассматриваемые в гла­

вах 2—8

алгорифмы

интересуют

нас лишь

с точки зре­

(или Ч{), то все эти алгорифмы

могут

быть

построены

с помощью теоремы о переводе

(п. 5 §

1 гл.

1) как

ал­

горифмы в алфавите Ча. Поэтому мы, как правило,

опу­

скаем упоминания об алфавитах,

в которых строятся те

или иные алгорифмы, имея в виду алфавит

Ча.

114

АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

{ГЛ. I

В тех случаях, когда это не приводит к недоразуме­

ниям, мы

будем

опускать

в обозначениях

%Р и %р по­

следнюю

разделительную букву, т. е. если Р имеет вид

или

Р^Ри

р

==;>,*.

то вместо

91р,

и 9tp,» мы

будем писать 91р,. Используе­

мая разделительная буква

должна в этом случае

усмат­

риваться

из контекста.

Для алгорифмов в алфавите Ча определяется их за­

пись (см. п. 8 §

1 гл. 1). Запись

алгорифма

21 есть

слово

в алфавите {0|}. Это слово мы

обозначаем

посредством

£213-

сел, изоморфные излагаемой, могли бы быть

построены

и другими методами, в частности, с помощью

надлежа­

ния (см.,

например, З а с л а в с к и й [3]—[4], У с п е н-

с к и й [ 3 ; §

12]).

структивная специфика сравнительно

слабо проявляется

в этих

вопросах — приводимые нами

элементарные тео­

ремы

в большинстве случаев могли

бы быть доказаны

традиционных

изложений

(например, от той

же книги

Л а н д а у

[1]),

мы

систематически

проводим

знаковый

подход — натуральные, целые и рациональные

числа оп­

ределяются

как знаковые

комплексы

(слова) определен­

ных типов.

1. Натуральные числа. Сформулируем несколько бо­

лее точно, чем это делалось раньше

(см. п. 4

введения),

определение натурального

числа.

О п р е д е л е н и е

1.

Натуральными

числами

являют­

ся

слова

в

алфавите

Ч,

которые могут быть

получены

с

помощью

следующих

порождающих

правил:

116

КОНСТРУКТИВНЫЕ

ДЕЙСТВИТЕЛЬНЫЕ

ЧИСЛА

[ГЛ. 2

1)

слово

О есть натуральное

число;

2)

если

слово Р в алфавите

Ч — натуральное

число,

то слово

Р\,

получаемое

приписыванием

к Р

буквы

«|»,

также есть натуральное

число.

Для

обозначения конкретных

натуральных

чисел мы

лику, так что слова 0|,

0||,

0 | | |

. . .

будут обозначаться

посредством

1, 2, 3 . ..

Ч,

Множество

слов

в

алфавите

являющихся

нату­

ральными

числами,

мы

обозначим

через Ж. Нетрудно

видеть, что это множество разрешимо. Буквы

i, /,

k,

I,

m, n с индексами или без них

будут

использоваться

нами

в

качестве переменных

по

натуральным

числам.

О п р е д е л е н и е

2

(отношения равенства

и

порядка

на множестве натуральных чисел).

Пусть

пит

— произвольные

натуральные

числа.

1)

Будем

говорить,

что пит

равны

(запись

п =

т),

если

п~т.

эс

2)

Будем

говорить,

что п меньше

(больше)

т,

и писать

п<

m

(соответственно

п >

/и),

если

осуществимо

не­

пустое

слово

Р е

Ч такое,

что т =

пР

(соответственно

п — тР).

3)

Будем

говорить,

что п

не

меньше

(не

больше)

т,

и

писать

п~^т

(соответственно

п^.т),

если

неверно,

что п <

т (соответственно неверно,

что п >

т).

Очевидно, отношения

= , > , < ,

<Пр

разрешимы,

«7/1

«7/1

«7/1

£7/1

т. е. для

каждого из

crV

с/х-

е/t/

c/v

c/v

алго­

этих отношений

осуществим

вающий Р

в пустое

слово

тогда и только тогда,

когда

P = n * m ,

где

п

и т — натуральные числа, связанные

соответствующим

отношением.

Ниже индекс «Ж» будет, как правило, опускаться.

Вместо ~~\(п =

т) мы будем писать п ф т.

Т е о р е м а

1. Каковы бы ни

были натуральные

числа

п, m,

I, П\, т\, имеет место

1)

(n =

m)V

(п>

m)V

(п<

т);

2)

(пфт)=>

((п > т) V (я <

т));

3)

(п >

т) V (п <

т);