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

Скачать файл
Заказать решение

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

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

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

Добавлен: 15.10.2024

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

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

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

232

 

 

 

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

ФУНКЦИИ

 

 

 

[ГЛ. 5

О п р е д е л е н и е

11.

1)

П-оператором

назовем

алгорифм,

пе­

реводящий

псевдочисла

в

псевдочисла

так,

что

равные

псевдочисла

переводятся

в

равные

псевдочисла.

 

 

 

 

 

 

2)

П-оператор

 

назовем

продолжением

функции

f,

если

при

любом

КДЧ

х

(из

ОД 1)

и любом псевдочисле

q таких, что х

= q,

выполняется

} (х) =

W (<?).

 

 

 

 

 

 

 

Почти

очевидна

 

 

 

 

 

 

 

 

 

Т е о р е м а

8.

Для

 

всякой равномерно

непрерывной

функции

можно построить П-оператор,

являющийся

ее

продолжением.

 

Для равномерно непрерывной функции / обозначим

через J

продолжающий ее Я-оператор.

 

 

 

 

 

 

Имеет

место следующая

теорема

(здесь и

ниже

мы

формули­

руем результаты для точных верхних границ; для точных нижних границ они, разумеется, остаются в силе).

Т е о р е м а

9. ( Л и ф ш и ц

[4]). Для

каждой

равномерно

непре­

рывной

функции

f можно

построить

псевдочисло

q

(из

0Д1) так,

что f(q)

равно

точной верхней

грани

f на

0 Д 1 .

 

 

 

 

В силу уже упоминавшихся результатов § 2

гл.

8

для

некото­

рых функций построенное

согласно теореме 9 псевдочисло

заведомо

не равно никакому КДЧ. Поэтому весьма интересна следующая

теорема, представляющая собой конструктивную

версию результатов

Г ж е г о р ч и к а

[2] и Л а к о м б а

[4]*).

 

 

 

 

Т е о р е м а

10.

Пусть

f — равномерно

непрерывная

функция,

КДЧ

х — ее точная

верхняя

грань

на 0 Д 1 . Если

псевдочисло

q та­

ково,

что

 

 

 

 

 

 

 

1)1(а)=х;

 

2)

можно

указать

рациональную

окрестность

точки

q такую,

что

для

всех

псевдочисел

q\

из этой

окрестности,

отличных

от q,

имеет место

f(qi) Ф

х,

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

КДЧ

у, равное

q.

 

 

 

Теорема

10 показывает, таким образом, что изолированный

экс­

тремум равномерно непрерывной функции вычислим.

 

 

 

 

 

Для

читателя,

придерживающегося

 

традиционной

ориентации,

заметим,

что

из первоначального варианта теоремы 10

 

(сформули­

рованного применительно к классическому континууму)

 

легко

сле­

дует вычислимость корней полиномов с вычислимыми

коэффициен­

тами**) .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Введенное в предыдущем пункте понятие /7-оператора

отли­

чается

от

понятия

всюду

определенной

конструктивной

функции

 

*) Гжегорчик и Лакомб используют

традиционное понятие дей­

ствительного

числа. В

работе

Л а к о м б а

[4]

приведена

также

про­

стая

и

исчерпывающая

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

тех

множеств

действитель­

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

зультаты также могут быть

интерпретированы

конструктивно,

но

мы не имеем возможности углубляться в этот вопрос.

 

 

**) Заметим попутно, что основная теорема

алгебры

имеет

ме­

сто в следующей, гораздо более сильной формулировке

(очевидное

определение конструктивных

комплексных чисел

(ККЧ)

предостав-

 

 

СВОЙСТВА

НЕПРЕРЫВНОСТИ

 

233

только

выбором

другой

числовой

системы (псевдочисел

вместо

К Д Ч ) . Аналогично примем

 

К-оператором

называется

алгорифм,

О п р е д е л е н и е

12.

1)

перерабатывающий

квазичисла

в квазичисла

так, что равные

квази­

числа

перерабатываются

в

равные

квазичисла.

 

 

2)

К-оператор

W

назовем

продолжением

функции

/, если при

любом

КДЧ х и

любом

квазичисле

р таких,

что х = р,

выполняется

f{x)=V(p).

 

 

 

 

 

 

 

 

П- и К-операторы могут наряду с конструктивными

функциями

рассматриваться

как уточнения

интуитивной

концепции

вычислимой

(точечной) функции действительной переменной*). Возникающее таким образом расщепление понятий соответствует возможности различных уточнений интуитивной концепции вычислимого действи­ тельного числа. (Мы не рассматриваем здесь операторов над /•'-чис­ лами, поскольку каждый такой оператор в силу своего определения

порождается

некоторой конструктивной функцией.)

 

В этом

пункте мы сформулируем некоторые результаты

автора

( К у ш н е р

[4]—[5]; [11]) о К- и Л-операторах.

 

Сравнительный объем понятий конструктивной функции

и К- и

/7-оператора выясняется следующими теоремами. (Термин «функ­

ция», как и выше, используется в качестве сокращения

термина

«всюду

определенная конструктивная

функция».)

 

 

 

 

Т е о р е м а

11.

1)

Для

каждой

функции

можно

построить

К-оператор, являющийся

 

ее

продолжением.

 

 

 

 

' 2)

Можно

построить

К-оператор,

не

являющийся

продолжением

никакой

 

функции.

 

 

Можно

построить

функцию,

для

которой

не­

Т е о р е м а

12.

1)

возможен

продолжающий

ее

П-оператор.

 

 

 

 

 

2)

Можно

построить

П-оператор,

не

являющийся

 

продолжением

никакой

 

функции.

 

 

 

 

 

 

 

 

 

 

 

Заметим, что

свойством,

указанным

в утверждении

1) теоре­

мы 12, обладает, например, эффективно

неравномерно

непрерывная

функция,

построенная

в

доказательстве

теоремы 3 § 2 гл. 8.

 

По

аналогии

с

определением 2

п. 1

можно ввести

понятие

не­

прерывности для К- и Л-операторов; однако теорема, аналогичная

ляется читателю): можно построить алгорифм, перерабатывающий

всякий

полином

Р„ (t) — a0tn +

...

+

ап

(где at

— ККЧ

и

а0 Ф

0)

в список ККЧ

zi,

2„

так,

что

Рп

(t)

— ай-(t

— Zi)

.. .• (t —

z„)

(см. О р е в

к о

в

[3],

в а н

д е р

К о р п у т

[1], Г у д с т е й н

[3]—[4],

Ш п е к е р

[3]).

 

 

 

 

 

 

 

 

 

 

 

 

*)

Для

читателя,

не заинтересованного в конструктивной

специ­

фике, отметим традиционную интерпретацию К- и Л-операторов. Именно, можно считать, что речь идет об алгорифмических опера­ торах двух типов: в первом случае (Д-операторы) аргументами и значениями оператора являются коды вычислимых, вычислимо схо­

дящихся

последовательностей рациональных

чисел,

во

втором

(Л-операторы)—коды вычислимых, сходящихся (в

традиционном

смысле

этого

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

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

чисел.

(В обоих случаях дополнительно требуется, чтобы оператор

сохра­

нял некоторое

естественное отношение равенства.\

 

 

234 КОНСТРУКТИВНЫЕ ФУНКЦИИ [ГЛ. 5

теореме 2, места не имеет: существуют не непрерывные К- и /"/-опе­ раторы. Несмотря на это, К- и Я-операторы обладают все же не­ которыми свойствами эффективной непрерывности: нужно лишь не­ сколько ослабить требования к регулятору непрерывности (ср. определение 2 п. 1), отказавшись от получения «б», соответствую­ щего данному 8 = 2"", в виде рационального числа.

Обозначим через Ж~ множество квазичисел

таких, что р е Ж~

тогда и только тогда, когда ПРЧ £ не возрастает

и

~] ~13«V//' (i, j> п => р (i) = р

(/))

(т. е. задающая р ПРЧ р «стабилизируется»).

Ясно, что

любое р е Ж'

не может не равняться некоторому

рациональному

числу.

 

Следующее

определение

мы сформулируем для краткости лишь

в случае Я-операторов; для /(-операторов понятие почти непрерыв­

ности

вводится

совершенно

аналогично.

 

 

 

 

 

О п р е д е л е н и е

13.

П-оператор

Ч

назовем

почти

непрерыв­

ным,

если

можно

построить алгорифм

91, перерабатывающий

вся­

кое слово

вида

 

q, п

(q — псевдочисло,

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

число)

в

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

квазичисло,

принадлежащее

Ж~

и такое,

что

при

любом

псевдочисле

qi,

удовлетворяющем

 

неравенству

 

 

I <7i - Я К % (<7> я).

выполняется

| V Ы - У (q) | < 2-".

(Таким образом, «б», соответствующее условию непрерывности в

данной точке

q

при данном

е =

2~п , эффективно

находится в

виде

положительного

квазичисла

из

Ж'.)

 

 

 

Т е о р е м а

 

13. 1) Всякий

К-оператор

почти

непрерывен.

 

2) Всякий

П-оператор почти

непрерывен.

 

 

Заметим, что доказательство теоремы 13 опирается на теорему

Клини о неподвижной точке

(см. К л и н и

[4; § 66], М а л ь ц е в

[1])

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

*Отметим также, что только что сформулированная теорема не­

прерывности не мешает /(-операторам обладать необычными как для конструктивных, так и для классических функций свойствами.

Например, в работе

К у ш н е р а [5]

указан пример /(-оператора

(почти

непрерывного

в силу теоремы

13), принимающего на еди­

ничном

сегменте в точности два значения (ср. § 4 гл. 5). Для Я-опе­

раторов такого рода примеры невозможны.

Из теоремы 11 и теоремы 3 § 2 гл. 8 следует, что существует эффективно неравномерно непрерывные /(-операторы. Использование новой по сравнению с гл. 8 конструкции позволяет также построить эффективно неравномерно непрерывную КФ, продолжимую до Я-оператора.

За дальнейшими сведениями о К- и Я-операторах мы отсылаем читателя к уже упоминавшимся работам автора [4]—[5], [11].

СТРУКТУРА КОНСТРУКТИВНЫХ ФУНКЦИЙ

235

§3. Структура конструктивных функций

Вданном параграфе будет изложена аппроксимационная теорема Цейтина для конструктивных функций.

Согласно

этой теореме (см. Ц е й т и н

[5])

всякая

непу­

стая (т.

е. определенная хотя бы в

одной

точке)

кон­

структивная функция допускает равномерное приближе­ ние на всей своей области определения посредством не­ которых стандартных функций, названных Цейтиным псевдополигональными. Для характеристики псевдополи­ гональных функций следует заметить, что эти функ­ ции получаются «склеиванием» согласованных после­ довательностей «угловых» функций. В свою очередь «угловая» функция — это конструктивная функция, опре­ деленная лишь в точках некоторого рационального ин­ тервала, кусочно линейная на этом интервале и имеющая

на нем не более одной угловой

 

 

точки (рис.

10).

 

 

^ \

 

Таким

образом,

область

у

\

определения

псевдополигональ­

 

 

ной функции

получается

объ­

 

 

единением

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

 

 

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

интервалов. В

 

х

п. 3 § 3 гл.

9

будет показано,

 

 

 

что область

определения

про­

 

 

извольной

 

конструктивной

Рис.

10.

функции может иметь

гораздо

 

 

более сложную структуру. Следует отметить, что не­ смотря на относительную простоту своего устройства псевдополигональные функции могут обладать необыч­

ными с точки зрения традиционного

анализа свойства­

ми— например, построенная

в § 2 гл. 8 всюду опреде­

ленная и неограниченная на

сегменте

0 Л 1 функция яв­

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

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