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

Скачать файл (14,18Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 161

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

РАЗРЕШИМЫЕ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

103

чески полон. Далее, если Q е Л, то при некотором i

Пусть алгорифм 91 делает над i точно k шагов. Тогда

1 2

По определению h, /г найдется / (в качестве / нужно взять K(i, k)) такое, что

При этом /		/ 2 2 ( /) = * .
При этом /		21' (У)=г=« (/) = Q.
Таким образом,		21' (У)=г=« (/) = Q.
Таким образом,		лГ £ = . #' .
		лГ £ = . #' .
Включение	г	U {Р} совершенно очевидно. Лемма
доказана.

Читатель, по-видимому, заметил, что в приведенном доказательстве используется, по существу, диагональный метод Коши, т. е. метод, посредством которого в теории множеств доказывается счетность счетного объединения

счетных	множеств (см., например, А л е к с а н д р о в [1]).
В самом	деле, алгорифм [91] «выписывает» бесконечную
матрицу;	(£, /)-элемент этой матрицы есть пустое или
непустое	слово в зависимости от того, кончает	алгорифм
91 к /-му	шагу свою работу над i или нет. С	помощью

алгорифмов h, h мы «пробегаем» все элементы ма трицы, сопоставляя непустым словам Р, а пустым — зна

чения	алгорифма		91 на	номере	соответствующей	строки.
Т е о р е м а		1.	Если	перечислимое множество Л		имеет
хотя	бы один	элемент,		то оно	может быть перечислено

арифметически полным алгорифмом.

Действительно, пусть слово Р принадлежит Л. При меняя к ! и Р только что доказанную лемму, получаем искомый арифметически полный алгорифм, перечисляю

щий Л (множество	Л'	из леммы	1, очевидно, совпадает
в данном случае с	Л).
Следующим нашим		шагом	будет усовершенство
вание перечисляющих алгорифмов			в смысле исключения

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

повторений их значений и сведения их областей приме

нимости к начальным отрезкам натурального ряда								(воз
можно, пустым или совпадающим со					всем	натуральным
рядом).
	Пусть алгорифм 51 перечисляет множество Ж.							Ска
жем, что		51 перечисляет		Ж без повторений,		если		равен
ство 51 (г) =			51(/) возможно лишь при i =			/.
	Алгорифм		51 назовем	стройным,	если	при	любом		п
из	применимости 51 к п + 1 вытекает применимость								31
к	п.
	Таким	образом, если		стройный алгорифм			применим
к некоторому числу, то он применим					и ко всем		меньшим
числам.			2. Всякое	перечислимое	множество			пере
	Т е о р е м а
числимо		без	повторений	стройным	алгорифмом.
	Д о к а з а т е л ь с т в о .			Пусть алгорифм 51 перечисляет

множество Ж. Нетрудно описать искомый алгорифм на интуитивном уровне. Возьмем какую-нибудь букву а, не принадлежащую алфавиту А (Ж является множеством слов в алфавите А), и построим, исходя из 51, по лемме 1 арифметически полный алгорифм 51ь перечисляющий множество Ж' такое, что

(1) Ж<= J T S J T U M .

Искомый алгорифм 33 состоит в следующем. Сначала ищем, последовательно вычисляя 51 [(0), 9Ii(l) и т. д. (здесь используется арифметическая полнота 5li), наи меньшее /, при котором 5lj(/) Ф а. Если такое i найдено, то 5l! (i) есть результат работы 33 над нулем. Вычислив 33(0), переходим к вычислению 33(1), отыскивая наи меньшее i > i (где i— число, найденное при вычислении 23(0)) такое, что %Ц)фа и 51, (/) ф 33 (0). Если такое / найдено, то 311(/) есть значение 33 на единице. Вычислиз 33(1), аналогично переходим к вычислению 23(2) и т. д.

Наметим оформление изложенного алгорифма как нормального. Пусть 5Ii — как и раньше, арифметически полный алгорифм, перечисляющий множество Ж', обла дающее свойством (1). Введем для сокращения обозна

чений	следующее		свойство	натуральных		чисел:	^(i)
выполняется		тогда	и только	тогда,	когда	2 1 \| ( г ) ^ а	и
г),31 Ф	91 , (/)	при	всех /, меньших		I. Нашей ближайшей

	РАЗРЕШИМЫЕ		И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА		105
целью	является построение такого алгорифма £ ,				что
		6 ( 0 ) ^ / ( ? ( / ) ) ,
		® (л +	1) са \|it (г >	S (л) & <g> (г)).
Ясно,	что	искомый	алгорифм	23 легко строится,	исходя
из 6 и 91ь		по теореме композиции

23(n)~9t1 (e (л)).

Пусть б — буква, не принадлежащая алфавиту А\ и отличная от ее. Построим алгорифм 912 так, чтобы при любых словах Р и Q в алфавите Л U {а} выполнялось

(2)	m2(P6Q)
(3)	9 I 2 ( P 6 Q ) = A ^ P # Q .

Алгорифм 912 легко построить, используя, например, ал горифм, распознающий графическое равенство слов (§ J, п. 7).

Построим алгорифм 913 так, чтобы

(4)9t3 (P6rt6Q)~Q9t2 (P69I1 (n)).

По схеме примитивной рекурсии определим алго

рифм

214

(теорема

12 § 1, п. 7)

9t4 (P60)~2i2 (P 6а),

9t4 (Р 6л +

1) ~ % (Р 6л 6214

(Р 6л)).

На

основании

(4)

последнее

равенство

можно перепи

сать

так:

2I4 (Р 6п + 1) ~ 2t4 (Р 6л) % (Р 691! (л)).

Ввиду

(2) — (3)

легко видеть, что

(5)

914

применим

любому

слову

Рбл

(Р — слово

Л U {а})

аннулирует

это

слово

тогда и

только

тогда,

когда

отлично от а

и от

всех

слов

9li(/)

{

0 <

п).

Построим алгорифм 915 так, что

915 (л)~914 (91!(л)6л).

Ввиду (5) этот алгорифм применим к любому п и

(6)

Я , ( я ) т Л э ? ( п ) .

106	АЛГОРИФМЫ И			ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА				[ГЛ. 1
	Строим алгорифм 5i6 так, что
(7)			Яб (л,	0 ~ 215	Ч- 1 + 0-
По	теореме	11	(§ 1, п. 7) строим алгорифм			917 так,		что
			Я 7 ( л ) ~ ц / ( Я в ( п , /) = Л) .
Ввиду (6) — (7)			это равенство можно переписать				в	виде
(8)			2 1 7 ( я ) ~ ( н ( г > п & ^ ( / ) ) .
	Искомый алгорифм легко строится теперь с помощью
примитивной рекурсии				(теорема	12 § 1, п. 7)
			Й ( 0 ) ~ \| х / ( 2 1 5 ( 0 = Л ) ,
			(Ц/г +	1 ) ~ 9 1 7 ( В Д ) .
Используя		(6)	и (8),	нетрудно	убедиться,	что g	обла
дает требуемыми свойствами. Теорема доказана.
	Применение		теоремы 2 и принципа Маркова				позво

ляет усилить теорему 1. Докажем сначала, что имеет место

Т е о р е м а 3.	Для всякого	непустого	перечислимого
множества можно	указать его	элемент.

Чтобы пояснить эту не совсем обычную с традицион ной точки зрения формулировку, заметим, что непустое множество — это множество, для которого опровергнуто утверждение, что оно пусто. Ясно, что из такого опро вержения не извлекается, вообще говоря, элемент рас

сматриваемого	множества.
Итак, пусть	Ж — непустое	перечислимое множество
и алгорифм 91	перечисляет Ж.	Исходя из 91, построим

по теореме 2 стройный алгорифм 91', перечисляющий Ж. Предположим, что

"1 !9Х' (0).

Тогда, ввиду стройности 91', при любом i ~]!51'(0.

Отсюда следует пустота Ж, что неверно. Следователь но, выполняется

" П 1 Г ( 0 ) , откуда по принципу Маркова получаем

191'(0).

$ 3]

РАЗРЕШИМЫЕ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

107

Поскольку 91' перечисляет Ж, то				9 1 ' ( 0 ) е ^ ,		чем и за
канчивается доказательство.
Т е о р е м а	4.	Всякое	непустое	перечислимое		множе
ство перечислимо		арифметически		полным	алгорифмом.
Эта теорема		следует	из теорем 1 и 3.		Поясним ко
ротко различие	между теоремами			1 и 4. И в том и в дру

гом случае речь идет о построении алгорифма, опреде ленным образом связанного с исходным множеством. Однако в первом случае в качестве исходных данных этого построения используется перечисляющий алгорифм и элемент исходного множества, тогда как во втором используется лишь перечисляющий алгорифм.

Множество Ж назовем бесконечным, если осуществим арифметически полный алгорифм, перечисляющий без


повторений некоторое подмножество						Ж.
Из теоремы 2 вытекает
Т е о р е м а		5. Всякое		бесконечное		перечислимое		мно
жество перечислимо			без	повторений		арифметически		пол
ным	алгорифмом.
Множество		Ж	назовем		финитным, если		можно	ука
зать	такой список		Р0, . . . ,		Рп его элементов,		что всякий

элемент Ж совпадает с одним из членов этого списка * ) . Множество Ж назовем нефинитным, если неверно,

что оно финитно.

Ясно, что бесконечное множество нефинитно. Обрат ное утверждение, неверное, вообще говоря, для произ вольных множеств (таковы иммунные множества; см.,

например, М а л ь ц е в

[1]), для перечислимых

множеств

легко следует

из теоремы

2 (и принципа Маркова).

Т е о р е м а

Всякое

нефинитное

перечислимое

мно

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

без повторений

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

пол

ным алгорифмом

(и,

следовательно,

бесконечно).

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

ссылок

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

варианты

теорем

1 и 4.

Скажем, что

алгорифм 91 является

двухместным

пе

речисляющим

алгорифмом

(относительно

алфавита

А),

если он перерабатывает всякое слово

вида

Pan (Р —

слово

в А,

п — натуральное число),

к которому он

при

меним,

слово

А.

Таким образом,

при

каждом Р

*) Очевидно, всякое финитное множество разрешимо и перечис лимо.

Смотрите также файлы

Лебедев, Н. Н. Курс инженерной геодезии. Геодезические работы при проектировании и строительстве городов и тоннелей учебник.pdf

Лурье, Г. Б. Основы технологии абразивной доводочно-притирочной обработки учебник.pdf

Маринов, И. А. Устройство и эксплуатация преобразовательных подстанций городского электротранспорта учеб. пособие.pdf

Межотраслевые связи и народнохозяйственные пропорции Восточной Сибири и Дальнего Востока..pdf

Мирзоян, Э. Н. Развитие учения о рекапитуляции.pdf

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

Смотрите также файлы

Информация

Списки файлов

Дополнительно