Книги по разным темам Pages:     | 1 | 2 | Сибирский математический журнал Январь февраль, 2002. Том 43, № 1 УДК 517.11:518.5 АРИФМЕТИКА ВТОРОГО ПОРЯДКА И ПУЛЬСИРУЮЩИЕ ИЕРАРХИИ Е. В. Гайлит Аннотация: Осуществляется машинно-оракульное моделирование арифметики IIго порядка средствами итерированной клиниевской вычислимости. Искомый оракул строится посредством пульсирующего трансфинитного процесса, представляющего собой модификацию аналогичного процесса, использованного Н. В. Белякиным для решения частного случая этой задачи. Библиогр. 5.

1. Данная статья посвящена машинно-оракульному моделированию классического анализа (арифметики второго порядка). В теории вычислений с оракулами [1] приводятся дополнительные требования к оракулам, которые обеспечивают комфортную вычислимость. Эти условия должны обеспечивать замкнутость множества вычислимых функций относительно разнообразных квазиалгоритмических процедур, так или иначе связанных с бесконечным перебором. Основное условие регулярность или наличие селекторного свойства, т. е. такой вычислимой процедуры, которая по коду непустого F -перечислимого множества (области определения F -вычислимой функции) находит его элемент.

Другое полезное условие, накладываемое на оракул F : если у F -вычислимого дерева обрываются все F -вычислимые цепи, то у него обрываются все цепи.

Последнее условие равносильно F -вычислимости функционала E1 (гиперджампа):

0, если ()(t)(((t)) = 0), E1() = 1 в противном случае, где (t) = (0),..., (t - 1). Это значит, что E1(t{y}F (t)) F -вычислимо рав номерно по y B(F ), где B(F ) множество, состоящее из всевозможных F -кодов тотальных F -вычислимых функций. Пусть MF множество всех таких функций. Задача заключается в построении такого оракула F, чтобы MF давало модель арифметики второго порядка.

Нас будут далее интересовать оракулы, построенные средствами итерированной клиниевской вычислимости [2]. Напомним их определение. Пусть ординальная нумерация (вообще говоря, многозначная), т. е. отображение некоторого числового множества K [] на ординал ||; начальный отрезок нумерации длины ; N номерное множество ординала.

Каждому || ставится в соответствие оракул H, определяемый как частичная числовая функция (удовлетворяющая некоторому условию минимальности), для которой (равномерно по, ) выполнены условия:

а) функционал E1 H -вычислим;

б) графики H и номерные множества N ( < ) H -разрешимы равномерно по -номерам.

й 2002 Гайлит Е. В.

34 Е. В. Гайлит В дополнение к сказанному отметим, что все оракулы H по построению 1 регулярны и 1 < 2 || влечет H H. Кроме того, упомянутая равномерность по, означает, что при построении H используются только -номера ординалов <. Множество MH будем в дальнейшем обозначать через M.

Ординал || называется точкой насыщения нумерации, если B(H ) = B(H).

< Множество всех точек насыщения обозначим через N []. Пусть N [] 0 +множество элементов N [], являющихся предельными точками N []. Для предельных пусть N [] = N []. Если N [] - N [], то будем +< говорить, что точка насыщения ранга. Множество всех точек насыщения ранга обозначим через N[].

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

|| || M x ((x) = 0 M (x)), (1) || где произвольная формула арифметики второго порядка, M резуль|| тат ограничения функциональных кванторов множеством M. Формула может включать помимо x другие свободные переменные (числовые и функциональные), и подразумевается, что функциональные переменные замещены произвольными H||-вычислимыми тотальными функциями.

В статье [3] построена такая, для которой требование (1) выполнялось лишь применительно к таким, которые, будучи приведены к предваренной форме, содержат в приставке не более двух функциональных кванторов. Здесь этот результат обобщается на произвольные.

Построение нужной нумерации осуществлялось в [3] посредством некоего пульсирующего процесса. В предлагаемой статье этот процесс надлежащим образом обобщается и модифицируется.

2. Осуществим некоторые вспомогательные построения. Как явствует из [4, гл. 16], для того чтобы удовлетворить схеме (1), достаточно построить такой оракул F, что для любого r B(F ) множество {a : Q11 MF... Qnn MF Qn+1t({r}F (a, 1(t),..., n(t)) = 0)}, где Q1,..., Qn+1 цепочка чередующихся кванторов и, F -разрешимо равномерно по r. Принимая это во внимание, построим для произвольной много i, значной нумерации числовые множества S,r для r B H||, i < и для i, подходящих ||. Построение множеств S,r будет осуществляться индукцией по i.

Чтобы уловить замысел этого индукционного построения, рассмотрим случаи i = 1, 2, 3. Дальнейший индукционный процесс после этого станет очевидным.

1, Итак, займемся определением множеств S,r. Для каждого r B H|| 1, существует минимальное 1(r) || такое, что r B H (r) ; множества S,r определяются для 1(r):

1(r) 1, S,r = a : M t({r}H (a, (t), (t)) = 0). (2) Арифметика второго порядка Легко видеть, что поскольку рассматриваемые оракулы вычисляют гиперджамп, то в формуле (2) можно неограниченный квантор заменить огра ниченным квантором M. Такая формула будет определять то же самое 1, множество. Легко видеть, что при возрастании множества S,r могут лишь расширяться.

1, Пусть нумерация такова, что всякая последовательность S,r (1(r) ||) стабилизируется в некоторый момент 1(r) для каждого r B H||.

Подразумевается, что 1(r) < ||, коль скоро 1(r) < ||, если же 1(r) = ||, то полагаем 1(r) = ||. Для любого || положим 1() = {1(r) : 1(r) }.

Легко видеть, что 1(||) = || (в принципе это возможно и для < ||). Опре 2, делим теперь множества S,r (для r B H|| и 1(r) ||), полагая 1(r) 2, S,r = a : M M () t({r}H (a, (t), (t), (t)) = 0).

2,1 2,Убедимся, что 1 < 2 влечет S,r S,r.

2,1 Действительно, пусть a S,r и M такова, что 1(r) M () t ({r}H (a, (t), (t), (t)) = 0).

1, Это означает, что a S,r (1) для подходящего r B H, а поскольку / 1, 2,1(1) 1(2), то (согласно определению 1) a S,r (2), т. е. a S,r.

/ 2, Если всякая последовательность S,r стабилизируется в момент 2(r) ||, то можно определить функцию 2() = {2(r) : 1(r) }.

Ясно, что 2(||) = || начиная с некоторого ||. Определим множество 1(r) 2 3, S,r = a : M M () M 2 () t ({r}H (a, (t), (t), (t), = 0) (t)) для r B H||, 1(r) ||. Аналогично предыдущему случаю убеж3,1 3,даемся, что если 1 < 2, то S,r S,r и мы можем построить подходящую функцию 3(), и т. д.

После того как закономерность уже найдена в этом индукционном проi, цессе, мы можем построить функции i () и множества S,r для всех i <, i, а также проверить монотонность всех множеств S,r при возрастании. При этом должно выполняться условие, чтобы на каждом предыдущем шаге имела место нужная стабилизация. Более формальное описание аналогичного процесса можно найти в [5]. Здесь цель состоит в построении нумерации таким i, образом, чтобы || N [], множества S,r стабилизировались до момента ||, а также все они были H||-разрешимыми равномерно по r.

3. Переходим к описанию пульсирующего процесса. Индукцией по On построим последовательность многозначных нумераций и вспомогательных множеств M. Пусть построены и M ( < ) и приняты некоторые индукционные предположения. Вводить их будем постепенно по мере надобности.

36 Е. В. Гайлит Отметим сразу, что в этих нумерациях точки насыщения только конечных рангов и процесс будет устроен таким образом, что он оборвется при достижении первой точки насыщения ранга. Полученная при этом нумерация будет результирующей.

Через будем обозначать множество тех, для которых существует < такое, что для любого такого, что <, верно | | >. Наименьшее такое обозначим через ().

Будем говорить, что для выполняется случай (A), если начиная с неко торого < справедливо | |.

(i) Индукционное предположение. Если () < и <, то имеет место N = N (ii) Индукционное предположение. Если имеет место случай (A), то из 1 < 2 < следует, что = N N, где для любого 1 N, если < | |, N = M, если = | |.

Построим вспомогательную нумерацию, || =, полагая по опреде лению N = N для любого <. Из индукционного предположения (i) () следует |()| = () ( < ), H = H для любого |()| и, () значит, нумерации () и |()| имеют одни и те же точки насыщения тех же рангов.

Займемся теперь описанием структуры множеств N.

(iii) Индукционное предположение. Если | | не точка насыщения, то множество N состоит из всевозможных четверок вида (0; r; a; s), где r B H - B H ; < и t ({r}H (a, (t), (t)) = 0) для некоторой функции, графиком которой является множество таких s, что (0; r; a; s) N. Говоря неформально, функция удостоверяет принадлеж 1,+ ность a множеству S,r (когда < | |). Напомним, что согласно определе нию итерированной клиниевской вычислимости множество N, вообще говоря, не является H -разрешимым и поэтому H -вычислимость не гарантиру ется.

Замечание. Сказанное в (iii) распространяется и на множества N для, не являющихся точками насыщения нумерации, так как |()| = ().

Далее ищем наименьший ординал = () < || (если он существует) такой, что для некоторых r B H() - B H : < () найдутся 1,|| a S,r такие, что никакая четверка вида (0; r; a; s) не принадлежит N().

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

Займемся построением M применительно к данному случаю.

Для каждой нарушающей пары r, a находим H| |-вычислимую функ цию r,a (с минимальным г еделевским номером), удостоверяющую принад1,|| лежность a множеству S,r, т. е. такую, что () t ({r}H (a, r,a(t), (t)) = 0).

Арифметика второго порядка Для данной нарушающей пары r, a строим множество четверок вида (0; r; a; s) для всех s, принадлежащих графику r,a. Каждое такое множество добавляем к номерному множеству N(), и эту сумму берем в качестве M.

Допустим, что пульсации (первого рода) нет и не точка насыщения ну мерации. Если для имеет место случай (A), то возьмем в качестве нумерацию длины + 1 такую, что = и N = N : <.

Построим множество M для этого случая. Оно состоит из четверок вида (0; r; a; s) таких же, как в индукционном предположении (iii), но применительно к r B H| | - B H : < ||.

Очевидно, что M непусто, поскольку || непредельный ординал (см. [2]).

Допустим, что для не имеет места случай (A). Полагаем =. Мно жество M построим, как в предыдущем случае. Непустота M данном случае в обеспечивается тем, что не точка насыщения и в B H| | наверняка най дутся новые г еделевские номера тождественно истинного предиката.

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

Займемся сначала случаем, когда ранг равен нулю, т. е. изолированная 2, точка насыщения. При этом ниже нам понадобятся множества вида S,r и потому надо предварительно выяснить, как обстоит дело с функцией 1, и одновременно что-то предположить по индукции касательно функций ( < ).

(iv) Индукционное предположение. Пусть какая-нибудь точка насыщения нумерации. Берем < и любое r B H. Рассмотрим 1, последовательность S,r, где | |. Предположение заключается в том, что для любого такого r эта последовательность стабилизируется на некотором шаге 1(r) <. (Тогда в соответствии с определением из п. 2 имеем для < в силу регулярности оракула H 1 () < и 1 () =.) Очевидно, если для < имеет место N [()], то для 1, 2, где () 1 < 2 <, справедливо 1 = 1. Отсюда, в частности, вы1 текает, что 1 () = 1 (), если < |()|. Так как точка насыщения, () то 1 () < для < и 1 () =.

(v) Индукционное предположение. Если | | точка насыще ния нумерации ранга 0, то N состоит из всевозможных четверок вида {1; r; a; s), где r B H - B H : < и N0[ ].

При этом для каждого такого r и для каждого a, упомянутого в четверке, содержащей r, имеет место 1 (+) M t ({r}H (a, (t), (t), (t)) = 0) для некоторой функции, графиком которой является множество таких s, что (1; r; a; s) N (где + = + 1, если < | |, и + = | |, если = | |).

38 Е. В. Гайлит 2,+Функция на этот раз удостоверяет принадлежность a множеству S,r (для < | |).

Замечание. Сказанное распространяется на нумерацию, как это бы ло для индукционного предположения (iii) по аналогичной причине. Введем понятие пульсации второго рода.

Ищем наименьший ординал = 2() < || (если он существует) такой, что для некоторых 2 r B H () - B H : < 2() и N0[] 2,|| найдутся a, принадлежащие S,r, такие, что никакая четверка вида (1; r; a; s) не принадлежит N (). Каждую такую пару r, a будем называть нарушаю щей парой (второго рода). Если для существует хотя бы одна такая на рушающая пара, то будем говорить, что имеет место пульсация второго рода, и тогда положим = 2(). Множество M строится так. Для каждой нарушающей пары r, a находим H| |-вычислимую функцию r,a (с минималь ным г еделевским номером), удостоверяющую принадлежность a множеству 2,|| S,r. Для каждой нарушающей пары r, a строим множество четверок вида (1; r; a; s) для всех s, принадлежавших графику r,a. Каждое такое множество добавляем к номерному множеству N (), и эту сумму берем в качестве M.

Если нет пульсации (второго рода), а изолированная точка насыщения и при этом имеет место случай (A), то в качестве берем нумерацию длины || + 1, полагая =, а N = N : <.

Если не имеет места случай (A) (и N0[]), то полагаем =.

Строим M так же, как в случае, когда не была точкой насыщения, но на этот раз применительно к r B H| | - B H, < ||, N0[] 2,|| (и для a S,r ).

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

Опишем вкратце случай, когда N1[]. Тогда на основании уже рас смотренного ранее мы можем определить функцию 2, предварительно приняв надлежащее индукционное предположение, которое в данном случае имеет следующий вид.

(vi) Индукционное предположение. Пусть какая-нибудь точка насыщения нумерации ранга 1. Берем < и любое r B H.

2, Рассмотрим последовательность S,r для. Предположение заключается в том, что для любого r эта последовательность стабилизируется на некотором шаге 2(r) <. Тогда в соответствии с определением из п. 2 имеем 2 () = для 2 () <, <.

Pages:     | 1 | 2 |    Книги по разным темам