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

190

КОНСТРУКТИВНАЯ

с х о д и м о с т ь

[ГЛ. 3

Таким

образом, получаем

следующие теоремы.

Т е о р е м а 2. Каков

бы

ни был

интервал,

множе­

ство КДЧ,

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

этому интервалу,

неперечис-

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

не

является

областью

примени­

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

алфавита

Ч никакого

алгорифма.

Т е о р е м а

3.

То же, что и

теорема

2,

с заменой

ин­

тервала

на невырожденный

сегмент.

Т е о р е м а

4.

Множество

3)

(всех

КДЧ)

неперечис-

лимо

и,

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

не

является

областью

примени­

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

Ч никакого

алгорифма.

Таким

образом,

невозможен

алгорифм,

применимый

к слову

Р е

Ч тогда

и только

тогда,

когда

Р

является

КДЧ.

Из теорем 2—4 непосредственно получаем

С л е д с т в и е

3.

Каков

бы

ни

был

интервал

(невы­

рожденный

сегмент),

множество

КДЧ,

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

этому

интервалу

(сегменту),

не

является

разрешимым.

С л е д с т в и е

4.

Множество

3)

(всех

КДЧ)

не

яв­

ляется

разрешимым.

В гл. 4 будет показано, что теорема 3

(а

следова­

тельно, и следствие 3) сохраняется и

для

любого

вы­

рожденного сегмента.

В заключение заметим, что изложенные

результаты

можно несколько усилить в следующем

направлении.

Пусть

Ж — эффективно

несчетное

множество КДЧ.

§ I]

ПРОБЛЕМЫ, СВЯЗАННЫЕ С ОТНОШЕНИЯМИ

ПОРЯДКА

193

откуда вытекает,

что

$ я

(Я) = 0.

Пусть теперь

!Ф(Я) и S)(P)=f= 0.

Тогда

IV(Я)

и при

п 5з

V(/>)

©"(Я, n) =

2 - K ( i 5 b

l .

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

Ш Я (Р) =

2 - ^ Н > 0 ,

чем

установлено

свойство

2)

алгорифма

Ф,®. Свойство

кращенный оборот речи. Пусть si\,

sih — «-местные

отношения. Рассмотрим

дизъюнкцию

(1)

s4-x (х„ . . . , xn)V

si2

(*„ ....

хп) V

•••

. . . V stk{xu

хп).

Будем говорить, что алгорифм а указывает для лю­

бых

КДЧ

х\,

хп

верный

член дизъюнкции (1),

если

он

перерабатывает

всякое

слово

Х\,

. . . , хп

(где

все

Х{

— КДЧ)

в одно из натуральных

чисел от 1 до k,

при­

чем если <х{х\, . . ., хп)~с,

то выполняется sii(xu

. . . ,

хп).

Будем

говорить,

что

алгорифм

а указывает

верный

член

дизъюнкции

(1) для

любых

КДЧ

хи

хп,

удо­

влетворяющих

условию si,

если

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

лю­

бое слово

хх,

...,

хп

(где

все Xi — КДЧ) такое,

что

вы­

полняется

si(x\,

хп),

в одно

из натуральных чисел

от 1 до k, причем если а(хх,

..., хп)

=?= i, то выполняется

StiiXi

х п

) .

При конструктивном

понимании

дизъюнкции

для

того,

чтобы утверждать,

что Vx(six

(х ) V «5^2(•*))> нужно

ный член дизъюнкции six

(х) V s4-2(x). Следовательно, ут­

верждение "1 Vx (six (х)

V ^ 2 (#)) означает лишь невоз­

ком

разных логических

операторов.

Т е о р е м а 1. Невозможен

алгорифм,

применимый к

КДЧ

х тогда и только тогда, когда х = 0.

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

Предположим,

что построен

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

(2)

[<р(*) =

* = 0.

&в(/>) =

0 ^ - 1 ! ф ( Р ) ,

то из (2) вытекает, что при любом Р в

Ч0

!ф'(Р)^ - )!ф(Р) .

Это, однако,

невозможно.

С л е д с т в и е

1.

Каково

бы

ни было

КДЧ

у,

невоз­

можен алгорифм,

применимый

к

КДЧ

х

тогда

и

только

тогда, когда х

=

у.

ф по­

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

Пусть

такой

алгорифм

строен. Построим алгорифм ф' такой, что

Ф' (г) ~ ф ( 2 +

у).

Очевидно,

!q>'(z)B3z =

0.

Это, как только что доказано, невозможно.

С л е д с т в и е

2.

Каково

бы

ни было КДЧ у, множе­

ство КДЧ,

равных

у (т.

е. вырожденный

сегмент

у А у),

не является

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

* ) .

Т е о р е м а

2. Невозможен

алгорифм,

указывающий

для любого

КДЧ

х верный

член

дизъюнкции

1) ( * = 0 )

у{хф0);

2) (* =

0) V (х>

0) V

( * < 0 ) .