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

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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

СУЩЕСТВОВАНИЕ СИНГУЛЯРНЫХ ПОКРЫТИИ

31!

ограниченная непрерывная, но неравномерно непрерыв ная функция и т. д.).

Другим источником подобного рода примеров яв ляется разработанная З а с л а в с к и м и Ц е й т и н ы м [1]—И теория сингулярных покрытий*). Аппарат сингу лярных покрытий оказывается также удобным при по строении примеров неинтегрируемых функций и доказа

тельстве

неразрешимости

алгорифмических

проблем,

связанных с интегрированием.

§ 1. Основные определения. Существование

сингулярных покрытий

1. Условимся

некоторых

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

Два

сег

мента

Х\ А

у\

и х2 Л у2 назовем

пересекающимися,

если

max

(Л:,,

x 2 ) < m i n ( t / , ,

У2)-

Если

два

сегмента

х\Ау\

и х2Ау2

пересекаются,

то

сегмент

max(xi,x2 ) Л min(y b у2)

называется

их

пересе

чением

обозначается

посредством

Х\ А у\ Г) х2

у2.

В случае,

когда

х\

у\,

х2

у2

не

пересекаются,

мы

считаем

\х\

А у\

П х2

у2\

(Посредством

|хХ#1

обозначается

длина

промежутка

х\у,

т. е. у — х.)

Для

любых

двух

промежутков

хх

X У и

х2 X У2

величина

I х \ X У\ П х 2

X У21 понимается как

| Х\

у у Пх2

у21.

то

Если

Т — система

промежутков

(см. § 3

гл. 5),

запись

х е 7

означает,

что

принадлежит

какому-ни

будь из промежутков этой системы.

2. Пусть

Ж — некоторое

множество

КДЧ.

О п р е д е л е н и е

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

интервалов

Ф * * ) называется

интервальным

покрытием

множества

Ж, если

можно построить

алгорифм

(называемый

ха

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

алгорифмом

покрытия

Ф)

типа

( Ж *

)

такой,

что для

всякого

е !

х<=

Ф(а(х)).

*) Существование сингулярных интервальных покрытий было независимо установлено также К р а й з е л о м и Л а к о м б о м [1].

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

***) То есть а перерабатывает всякий э л е м е н т о в натуральное число,

312

СИНГУЛЯРНЫЕ

ПОКРЫТИЯ

[ГЛ. 8

О п р е д е л е н и е

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

сегментов

4х называется

сегментным

покрытием

множества

Ж,

если можно

построить

алгорифмы

ось

а 2

типа

(Ж-+Ж)

(характеристические

алгорифмы

покрытия

такие,

что при

любом

х £= Ж

Уа, (х)

= =

Utx%

(х)

Ua,

(х)

X ^

Уа2

(х)

(здесь

через

Uh, Vh обозначены

левый

правый

концы

сегмента

^(k)).

Сегментное

покрытие

назовем

О п р е д е л е н и е

дизъюнктным,

если

при

i=j=\

сегменты

4х

(t),

^ (\)

не

имеют

общих

внутренних

точек.

В качестве множества Ж у нас будут фигурировать промежутки положительной длины и множество всех КДЧ ZD, называемое ниже «конструктивной прямой».

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

стых примера. Пусть 4х !,	— такие		алгорифмы,		что
OA-			при	п =	О,
4х , (п) =			при	п=\,
		-/1+1	при	п ^ 2 ;
ОД -	при	четном		п,
А 1	при	нечетном		п.

Можно показать, что 4 х i не является сегментным по крытием OA 1, хотя и невозможен х из О А 1, не при надлежащий никакому сегменту Wi (i). Алгорифм W2 дает пример сегментного покрытия 0 А 1 , для которого тре бование существования пары характеристических алго рифмов нельзя заменить требованием существования одного алгорифма, указывающего для каждого х чис ло i так, что х е ^2(1) •

§ 1]	СУЩЕСТВОВАНИЕ				СИНГУЛЯРНЫХ ПОКРЫТИЙ					313
О п р е д е л е н и е				4.	Покрытие		(сегментное или			ин
тервальное)		Ч1-	множества			Ж назовем		рациональным,
если	все промежутки			W(n)		рациональные		(т. е.	концы
этих промежутков — рациональные							числа),	точным,		если
при	любом	п	Л¥(п)^Ж,			невырожденным,		если	всегда
\Ч{п)\Ф0.
Все рассматриваемые					в данной		главе покрытия		пред

полагаются рациональными и невырожденными. Поэто му соответствующие прилагательные, как правило, опу

скаются.

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

промежут

О п р е д е л е н и е

ков

Ф называется

г-ограниченной,

если

при

любом

ю .

1 =0

О п р е д е л е н и е

Покрытие

W (интервальное

или

сегментное)

промежутка

х \ у

называется

сингуляр

ным,

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

\Р

г-ограничена

при

неко

тором е,

меньшем

у — х.

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

промежут

О п р е д е л е н и е

ков

Ф назовем

регулярной,

если

при любом

\Ф(1)\<2-1.

О п р е д е л е н и е

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

рациональ

ных

интервалов

назовем

универсальной,

если

для

лю

бой

регулярной

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

рациональных

интер

валов

Ф можно

найти 1Ф и /Ф такие, что

П Ф )

Ф ( / Ф ) -

3. Т е о р е м а

1 ( З а с л а в с к и й ,

Ц е й т и н

[2]).

Для

любого

осуществима

2~п-ограниченная

универ

сальная

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

интервалов.

Доказательство этой теоремы использует диагональ ную конструкцию. Фиксируем произвольное п. Поль

зуясь универсальным	алгорифмом,	построим алгорифм
21 так, что для любого	алгорифма а	(в Ча)

(1)21 (£«3, £ ) ~ а ( £ + / г + 1).

При каждом k обозначим через Жн множество ра циональных интервалов длины, меньшей чем 2~n~k~l. Очевидно, все множества Жи перечислимы. Построим

314

СИНГУЛЯРНЫЕ ПОКРЫТИЯ

[ГЛ. 8

алгорифм v, перерабатывающий слова в Ч0 в натураль ные числа так, что разные слова переводятся в разные натуральные числа, и обозначим через Ж множество слов вида Р, v(P) (где - Р е Ч0) таких, что


	Р, v (Р) е		21 (Р,	v (Р)) & 21 (Р,	v (Р)) <= J?v ( Р ) .
Нетрудно		убедиться		(ср. теоремы	9—10 § 3 гл. 1),
что множество Ж перечислимо. Ясно					также	((1)), что
для	любой	регулярной		последовательности		рациональ
ных	интервалов Ф
(2)		£ФЗ, v(E03)'e^r.
Следовательно,			Ж бесконечно и		можно	построить

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

(3)	Q ( 0 ^ « ( Y ( 0 ) -
Очевидно, Q — последовательность рациональных ин
тервалов.
Пусть	Y I . Y2 — такие алгорифмы, что

Y (0 =*= Yi (О. Y2 (0- Тогда Y2 — ПНЧ, причем при i-ф j

				Y2 (0 ^ Y2 (/)•
Используя			это обстоятельство,			получаем		оценку
k			k		оо
21 Q(/) к 22-n-yiH)-1 < 22 - " - ' - 1								=	2 " \
i=0			( = 0		1 = 0
Остается			показать,		что последовательность					Й уни
версальна.		Пусть		Ф — регулярная			последовательность.
Ввиду	(2) при некотором /
(4)			Y ( 0 - £ 0 > 3 > v ( W ) -
Тогда	((1),	( 3 ) - ( 4 ) )
			й ( / ) ~ Ф ( у ( £ Ф З ) +			п + 1),
что и требовалось.
Т е о р е м а			2	( З а с л а в с к и й ,			Ц е й т и н			[1]—[2],
К р а й з е л ,		Л а к о м б			[1]). Для	любого п			осуществи
мо 2~п-ограниченное				интервальное			покрытие			конструк
тивной	прямой.

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

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

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

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

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

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

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

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

Информация

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

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