Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

книги из ГПНТБ / Кушнер, Б. А. Лекции по конструктивному математическому анализу

.pdf

Скачиваний:

Добавлен:

22.10.2023

Размер:

14.87 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 1011 / 4511 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

102

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

ГГЛ. 1

нием алгорифмов в этом алфавите и можно ограничиться при изучении перечислимых множеств в алфавите А. 'Аналогичное замечание можно было бы сделать и о раз решимых множествах.

Доказательство разрешимости		(перечислимости) мно
жества связано, очевидно,	с	решением	конструктив
ной задачи — построением	разрешающего		(перечисляю

щего) алгорифма. Естественно, что этот алгорифм является весьма существенной характеристикой соответ

ствующего	множества;	в тех	случаях, когда	речь идет
о каких-то	построениях	над	разрешимыми	(перечисли

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

Как следует из определения, перечислимое множе ство может перечисляться своим перечисляющим алго рифмом довольно беспорядочно. Этот алгорифм может, например, пропускать некоторые натуральные числа, бу дучи на них не определен, может принимать некоторые свои значения много раз и т. д. В следующем пункте бу дут приведены теоремы, показывающие возможность уст ранения таких неприятных эффектов. Эти теоремы, в частности, позволяют рассматривать бесконечные пе речислимые множества как естественные эффективные аналоги счетных (в традиционном смысле) множеств.

3. Некоторые стандартные способы перечисления пе речислимых множеств. Алгорифм 21 назовем арифмечески полным, если он применим к любому натураль ному числу.

Л е м м а	1.	Пусть	Ж—	перечислимое		множество,
Р — некоторое		слово. Можно		построить		арифметически
полный алгорифм, перечисляющий					такое множество			Ж',
что Ж <= Ж'	<= Ж U {Р}.
Д о к а з а т е л ь с т в о .			Пусть		алгорифм	21	перечис
ляет множество		Ж. Рассмотрим			алгорифм	[21]	(см. п.	10

§ 1) и построим, пользуясь теоремами сочетания, алго

рифм	21' так,	что
,	\|	Р,	если	[21](/J(п),	/ 1 ( п ) ) #	Л .
Д	{ П ) ~ (	21 (II («)),	если	[21] 01 (п),	It (п)) =	Л .

Алгорифм 21' искомый. Действительно, из определе ния алгорифмов [21] и l\, l\ следует, что 2Г арифметц-

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

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 (Р —

слово

в А,

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

к которому он

при

меним,

слово

А.

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

при

каждом Р

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

108		АЛГОРИФМЫ И			ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА						[ГЛ. 1
алгорифм %ра перечисляет некоторое							множество				{21ра}
слов	в Л.			По всякому		двухместному			перечисляю
Т е о р е м а			7.
щему	алгорифму			21 можно		построить	алгорифм			21' так,
что при		любом		слове	Р в	А алгорифм		%ра		является
стройным		алгорифмом,			перечисляющим			без	повторений
множество			{%Ра}.
Т е о р е м а			8. При		тех же условиях,			что в	теореме 7,
и дополнительном				условии		непустоты		всех		множеств
{ЩР а } можно			построить алгорифм 2F так, что при								каж
дом	Р алгорифм			21ра	арифметически		полн		и	перечис
ляет множество				{21ра}.

Использованные здесь обозначения введены в п. 2

данного	параграфа и в п. 11 § 1; через	21ра обозначается
перевод	% Р а в алфавит Л?.	области определе
4. Перечислимые множества как		области определе

ния алгорифмов. Перечислимость разрешимых множеств.


Пусть Ж — множество			слов в алфавите А,			% — алго
рифм над Л. Назовем Ж областью					применимости			(об
ластью определения)		21 относительно А, если для					любого
слова Р в этом	алфавите
		РеЖ^Ш(Р).
Т е о р е м а	9. Всякое		перечислимое		множество			слов
в алфавите А	является		областью	применимости			относи
тельно А некоторого		алгорифма.		а — буква,
Д о к а з а т е л ь с т в о .			Пусть			не	принад
лежащая алфавиту Л. По лемме				1 построим		арифмети
чески полный	алгорифм		21', перечисляющий			некоторое
множество Ж'	такое, что

ЛГ s= J " S ЛГ U {а}.

Нетрудно построить алгорифм (ср. п. 7 § I) S3 так, что 33 применим к любому слову вида Р8п ( Р е Л , п — натуральное число, б — буква, отличная от а и от всех букв алфавита А\), причем

Ъ(РЬп)= А ==Р = 21'(я).

Построим теперь алгорифм (5 (по теореме И § 1) так,

что

e ( p ) ^ i i / ( » ( p 6 0 * ! - A ) .

РАЗРЕШИМЫЕ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА		109
Ясно, что
&{P)~\ii(P==	%'(?)>).
Следовательно, для любого слова Р в алфавите		А
! б ( Р) =	Ре= Ж.

Таким образом, Ж является областью применимости й относительно А, чем и заканчивается доказательство.

При доказательстве обратного утверждения нам по требуется следующая очевидная

Л е м м а 2. Множество всех слов в алфавите А пере числимо.

Чтобы доказать эту лемму, нужно оформить в виде нормального алгорифма какой-нибудь из способов пе ресчета слов в данном алфавите. Например, можно упо рядочить буквы в этом алфавите и затем нумеровать слова в порядке возрастания их длин, располагая слова одинаковой длины в лексикографическом порядке. За


подробностями	мы	отсылаем читателя к		работе	Д е т -
л о в с а [1].		Область применимости		любого	алго
Т е о р е м а	10.
рифма относительно алфавита А является				перечислимым
множеством слов в этом			алфавите.	Ж является
Д о к а з а т е л ь с т в о .			Пусть множество

областью применимости алгорифма (5 относительно ал фавита А. Обозначим через 351 арифметически полный алгорифм, перечисляющий множество всех слов в алфа

вите А. Пусть далее А 2 — а л ф а в и т		алгорифма f£ и алго
рифм 352 аннулирует всякое слово		в этом	алфавите	(см.
пример 3 п. 4 § 1). По теоремам		композиции и объеди
нения построим алгорифм	91 так, что
2t (ft) ~ 35, (ft) D2 (S(35,(tt))).
Ясно, что
!2t (ft) =3 16(35, (ft)),
причем, если ! & (35,(/г)),	то
91 (п)	= 35, (/г).
Легко видеть, что 21 перечисляет Ж.			В самом	деле,
если 121 (п), то КЦ35,(«))	и, следовательно,

35, (/г) е= Ж.

по	АЛГОРИФМЫ		И ПЕРЕЧИСЛИМЫЕ				МНОЖЕСТВА				[ГЛ. I
Поэтому			% (л) <=		Л.
			% (л) <=		Л.
Обратно,	если Р^Ж,		то	при	некотором			п
и, следовательно,			P=f=®l (я)
и, следовательно,			IG (©,(»))•
Тогда			IG (©,(»))•
Тогда			21 («) = £>, (п) — Р .
			21 («) = £>, (п) — Р .
Таким	образом,		множество		слов		в данном			алфавите
перечислимо		тогда	и только тогда,				когда	оно		является
областью	применимости			некоторого			алгорифма			относи
тельно этого		алфавита.
Т е о р е м а		11. Всякое		разрешимое			множество				пере
числимо.
Действительно, пусть алгорифм 21 разрешает множе
ство Ж. Построим алгорифм 2li в алфавите А,										примени
мый лишь к пустому слову (пример 4								п. 4	§	1).	По
строим, наконец, алгорифм 212					так, что
			2l2 (P)~2I,(2l(P)).
Ясно, что для любого				слова	Р	в алфавите			А
			Р<=М = Ш2			(Р).

Отсюда на основании теоремы 10 получаем, что Ж пе речислимо.

Пусть теперь ф — алгорифм, построенный согласно теореме 4 § 2. Обозначим через Ж множество тех слов в алфавите {0|}, к которым неприменим этот алгорифм. Из теоремы 4 вытекает, что Ж не является областью при менимости относительно {0|} никакого алгорифма. Сле довательно, Ж неперечислимо. Обозначим через Ж мно жество тех слов в {0|}, к которым ф применим. Очевид но, Ж перечислимо. Вместе с тем по теореме 5 § 2 это множество не является разрешимым. Таким образом, имеет место


§ 3]	РАЗРЕШИМЫЕ И			ПЕРЕЧИСЛИМЫЕ			МНОЖЕСТВА		111
Т е о р е м а 12.			1)	Существует		перечислимое		множе
ство слов в		алфавите		{0\|}, дополнение			которого до		мно
жества	всех	слое в	этом алфавите неперечислимо					* ) .
2) Существует			перечислимое			множество слов		в	ал
фавите	{0\|},	не являющееся			разрешимым.

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

5. Пересечение и объединение перечислимых мно


жеств.		Пересечение	конечного	числа		перечис
Т е о р е м а 13.
лимых	множеств	перечислимо.	Ж\,	Жп—
Д о к а з а т е л ь с т в о . Пусть						перечис
лимые множества. По теореме 9 построим					алгорифмы
%\	21„ так, что каждое множество			Ж\	является об

ластью определения алгорифма 2Ij относительно алфа вита А (если исходные множества были в разных алфа витах, то можно рассмотреть их все в объединении этих

алфавитов). По теореме объединения		строим алгорифм
91 так, что
%(Р)~%(Р)%2(Р)	. . .	%п(Р).
Ясно, что		& Шп (Р),
131 (Р) Е 121! (Р) & \|Я2 (Р) & . . .		& Шп (Р),
т. е.
!?I(P)=Pe= f]	Ли

Отсюда, ввиду теоремы 10, следует перечислимость

множества f") Ли

Нетрудно также показать, что пересечение конечного числа разрешимых множеств является разрешимым мно жеством.

*) Дополнением множества Ж слов в алфавите Л_до множества всех слов в этом алфавите мы называем множество Ж слов в А, оп ределяемое условием

P e i s " ] ( P £ Л),

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 1011 / 4511 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ

#
29.10.20235.79 Mб13Куцый П.Ф. Повелители молний.pdf
#
25.10.202312.79 Mб19Кучко А.С. Аэрофотография. Основы и метрология.pdf
#
25.10.202318.43 Mб47Кушманов И.В. Электронные приборы учеб. пособие.pdf
#
27.10.202319.55 Mб11Кушнарев Д.М. Использование энергии взрыва в строительстве.pdf
#
19.10.20232.48 Mб24Кушнарев, Ю. М. Авторулевой Печора учебное пособие для студентов судоводительского факультета.pdf
#
22.10.202314.87 Mб19Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf
#
24.10.202311.94 Mб20Кушнерев Н.Т. Программирование для ЭВМ Минск-32.pdf
#
25.10.202312.78 Mб21Кушнирская М.Ц. Крашение древесины в производстве мебели.pdf
#
27.10.202320 Mб7Кэтермоул К.В. Принципы импульсно-кодовой модуляции.pdf
#
23.10.20234.75 Mб13Лабинский Ю.В. Корабельные ядерные реакторы учеб. пособие.pdf
#
23.10.20238.6 Mб4Лабозин П.Г. Качество крупнопанельного домостроения.pdf