close

Вход

Забыли?

вход по аккаунту

?

Линейные порядки. Теоремы кодирования

код для вставкиСкачать
Том 154, кн. 2
УЧЕНЫЕ ЗАПИСКИ КАЗАНСКОО УНИВЕСИТЕТА
Физико-математические науки
2012
УДК 510.53
ЛИНЕЙНЫЕ ПОЯДКИ. ТЕОЕМЫ КОДИОВАНИЯ
А.Н. Фролов
Аннотация
В работе рассмотрен ряд 0 - и 0 -кодирующих теорем. Получены две общие теоремы,
обобщающие все известные на данный момент 0? - и 0?? -кодирующие теоремы. Используя
одну 0? -кодирующую теорему, получено описание рангов ? -ункций ? -схожих линейных
порядков, не имеющих вычислимых представлений.
?
Ключевые слова:
вания.
??
линейные порядки, вычислимые представления, теоремы кодиро-
Введение
Основным объектом построения любого алгоритма является множество натуральных чисел N = {0, 1, 2, 3, . . . } . Этого вполне достаточно для построения любой
компьютерной модели. В частности, для кодирования целых чисел Z = {. . . , ?
?2, ?1, 0, 1, 2, . . . } можно использовать кодировку вида {. . . , 4, 2, 0, 1, 3, . . . } . Более
сложная кодировка позволяет также закодировать множество рациональных чисел
Q.
Каждое из вышеприведенных множеств имеет естественное отношение порядка,
которое является линейным, то есть таким, что любые два числа являются сравнимыми. При кодировании этих множеств нетрудно индуцировать естественное
отношение порядка. Построенные линейные порядки изоморны исходным порядкам, и поэтому имеют аналогичные свойства. Класс линейных порядков, изоморных исходному, называется типом порядка. Типы линейных порядков N , Z и Q
соответственно обозначаются ? , ? и ? .
ассмотренные порядки являются тривиальными. Они вычислимы и, более того, разрешимы, то есть любая ормула первого порядка вычислима. Нетривиальные линейные порядки, с точки зрения их алгоритмической сложности, впервые
были построены Л. Фейнером [6, 7?. Линейный порядок, упорядоченный по типу
? + a0 + ? + a1 + ? + a2 + · · · , называется сильным ? -представлением множества
A = {a0 < a1 < a2 < · · · } . Здесь натуральное число обозначает тип конечного
линейного порядка, мощность которого совпадает с этим числом.
Теорема 1 [6, 7?. Линейный порядок, являющийся сильным ? -представлением множества A , имеет вычислимое представление тогда и только тогда,
когда A является ?03 -множеством.
Здесь для оценки алгоритмической сложности используется так называемая ариметическая иерархия множеств ?n . Множество X называется ?n множеством, если x ? X ? ?(x) , где ? ?n -ормула над вычислимым отношением (то есть содержит n переменных кванторов, начиная с квантора ? ).
Множество X называется ?n -множеством, если X является ?n -множеством.
Если X является и ?n -, и ?n -множеством, то X называется ?0n -множеством.
ЛИНЕЙНЫЕ ПОЯДКИ. ТЕОЕМЫ КОДИОВАНИЯ
143
В дальнейшем ?0n+1 -множества называются ?(n) -вычислимыми. Все вышеприведенные определения переносятся на тьюринговые степени, содержащие соответствующие множества. Например, тьюринговая степень является 0(n) -степенью,
если она содержит ?(n) -множество. Для краткости 0(1) и 0(2) обозначаются как
0? и 0?? соответственно. Некоторые другие необходимые определения теории вычислимости будут излагаться далее в работе, а подробное изложение этой теории
можно найти в [16?.
Как мы видим, идея построения нетривиального линейного порядка заключается в кодировании в порядок некоторого множества. Ясно, что это кодирование
допускает релятивизацию (впрочем, как и все приведенные в настоящей работе).
Поэтому как следствие такого кодирования получаем, что существует 0? -вычислимый линейный порядок, не имеющий вычислимого представления. В качестве
искомого линейного порядка достаточно взять сильное ? -представление любого
?04 -множества, не являющегося ?03 -множеством.
Приведенное кодирование имеет предмет кодирования, которое является множеством A = {a0 < a1 < a2 < · · · } , и объект кодирования линейный порядок
?(A) = ? + a0 + ? + a1 + ? + a2 + · · · . Связь предмета и объекта кодирования
осуществляется с помощью оракула ?03 , поэтому такое кодирование называется
?03 -кодированием, а теорема Фейнера ?03 -кодирующей теоремой.
Следующее кодирование является примером кодирования одного линейного порядка в другой. Данный пример стал первым примером такого рода кодирования.
Теорема 2 [4?. Линейный порядок L имеет 0? -вычислимое представление
тогда и только тогда, когда линейный порядок (? + 2 + ?) · L имеет вычислимое
представление.
Как не трудно видеть, теорема связывает предмет кодирования (линейный порядок L ) с объектом кодирования (линейным порядком ?(L) ?
= (?+2+?)·L ). Связь
предмета и объекта кодирования осуществляется с помощью оракула 0? , поэтому
такие теоремы носят название 0? -кодирующих теорем, а ? 0? -кодированием.
Если в теореме вместо оракула 0? используется оракул 0(n) , то такие теоремы
называются 0(n) -кодирующими и выглядят следующим образом.
Теорема 3 0(n) -кодирующая теорема. Линейный порядок L имеет 0n -
вычислимое представление тогда и только тогда, когда линейный порядок ?n (L)
имеет вычислимое представление.
Здесь ?n (L) является 0(n) -кодированием. Требуем, чтобы такие кодирования
допускали релятивизацию. Другими словами, L имеет xn -вычислимое представление тогда и только тогда, когда линейный порядок ?n (L) имеет x -вычислимое
представление для любого степени x . азличные кодирования, как показывает
следующее предложение, связаны между собой и порождают новые кодирования.
Предложение 1. Если ?n является 0(n) -кодированием, а ?m 0(m) -коди-
рованием, то ?n ? ?m является 0(n+m) -кодированием.
Доказательство. Так как ?m является 0m -кодированием, линейный порядок
L имеет 0(n+m) -вычислимое представление тогда и только тогда, когда линейный
порядок ?m (L) имеет 0(n) -вычислимое представление. Тогда из того, что ?n является 0(n) -кодированием, следует, что ?m (L) имеет 0(n) -вычислимое представление
тогда и только тогда, когда ?n (?m (L)) имеет вычислимое представление.
Каждая 0(n) -кодирующая теорема имеет следующие следствия (эти следствия
были замечены в частном случае в ранней работе автора [18?). Напомним, множество X является n -низким, если X (n) ?T ?(n) , 1-низкое множество называется
просто низким.
144
А.Н. ФОЛОВ
Предложение 2. Если ?n является 0(n) -кодированием, то каждый n -
низкий линейный порядок, имеющий вид ?n (L) для некоторого L , является вычислимо представимым.
Доказательство. Пусть L0 = ?n (L) для некоторого L и L0 является
X -вычислимым, где X n -низкое множество. Так как ?n является 0(n) кодированием и X n -низкое множество, то L0 имеет X -вычислимое представление тогда и только тогда, когда L имеет X (n) -вычислимое представление, а это, в
свою очередь, тогда и только тогда, когда L имеет ?(n) -вычислимое представление,
что равносильно тому, что L0 имеет вычислимое представление.
Предложение 3. Если ?n является 0(n) -кодированием, то существует (n+
+ 1) -низкий линейный порядок, имеющий вид ?n (L) для некоторого L и не являющийся вычислимо представимым. Более того, порядок ?n (L) имеет представление в каждой ?02 -степени, не являющейся n -низкой.
Доказательство. . Миллер [12? построил линейный порядок A0 , имеющий
копию в каждой такой степени a , что 0(n) < T a < T 0(n+1) . Пусть L0 = ?n (A0 ) .
Заиксируем произвольную не n -низкую ?02 -степень c .
Так как ?n является 0(n) -кодированием, получаем, что L0 имеет копию в c
тогда и только тогда, когда A0 имеет копию в c(n) . Так как c не n -низкая ?02 степень, то 0(n) < T c(n) < T 0(n+1) . Тогда A0 имеет копию в c(n) , и следовательно,
L0 имеет копию в c .
Так как c произвольно выбранная не n -низкая ?02 -степень, то, в частности,
L0 имеет (n + 1) -низкое представление.
Как мы видим 0(n) -кодирующие теоремы имеют непосредственное приложение для построения вычислимых копий n -низких линейных порядков. В 1991 г.
К. Джокуш и . Соар [10? доказали, что не каждый низкий линейный порядок
имеет вычислимое представление (в отличие от булевых алгебр [3?). Однако, рассматривая дополнительные условия, накладываемые на порядковые типы, условие
ѕнизкостиї может обеспечить вычислимую представимость линейных порядков.
Так . Доуни и М. Мозес [5? установили, что для каждого низкого дискретного
порядка существует вычислимая копия (линейный порядок называется дискретным, если каждый элемент имеет последователя и предшественника). Естественно возникает вопрос об описании порядковых типов, для которых условие ѕнизкостиї достаточно для вычислимой представимости (. Доуни [2?). Этот вопрос
может быть естественным образом обобщен, заменив условие ѕнизкостиї на ѕ n низкостиї. В виду замеченной выше связи 0(n) -кодирующих теорем и n -низких
линейных порядков, рассматривая ниже 0? - и 0?? -кодирующие теоремы, мы затронем и вопрос, поставленный . Доуни, и вопрос, обобщающий вопрос . Доуни.
1.
0? -кодирующие теоремы
Как уже было сказано выше, первым 0? -кодированием является ?(L) = (? +
+ 2 + ?) . Согласно предложениям 2 и 3 из 0? -кодирующей теоремы 2 следуют
Следствие 1 [18?. Каждый низкий линейный порядок, имеющий вид (? + 2 +
+ ?) · L для некоторого L , является вычислимо представимым.
Следствие 2 [18?. Существует 2 -низкий линейный порядок, имеющий вид
(? + 2 + ?) · L для некоторого L и не являющийся вычислимо представимым.
Линейный порядок называется k -блочным, если все его блоки имеют мощность не более k . Блоком является множество [x]L = {y | F (x, y) ? F (y, x)} , где
ЛИНЕЙНЫЕ ПОЯДКИ. ТЕОЕМЫ КОДИОВАНИЯ
145
FL (x, y) ? (x < L y) & (|[x, y]L | < +?) и [x, y]L ? {z | x < L z < L y} . Отношение
FL (x, y) называется отношением блока линейного порядка L и порождает отношение эквивалентности x ? L y ? (x = y) ? FL (x, y) ? FL (y, x) . Не трудно видеть,
что блоки это классы эквивалентности относительно ? L .
Например, 1-блочными линейными порядками являются только лишь плотные
порядки. Линейные порядки, имеющие вид (?+2+?)·L для некоторого L , являются
2-блочными. Таким образом, последние два следствия утверждают, что существует
2-низкий 2-блочный линейный порядок, не имеющий вычислимого представления,
с другой стороны, каждый низкий 2-блочный линейный порядок имеет вычислимую копию. Чтобы обобщить эти следствия для произвольного k -блочного порядка
вместо 2-блочного, необходимо следующая 0? -кодирующая теорема, обобщающая
теорему 2.
Теорема 4 [18?. Линейный порядок (? + k + 1 + ?) · L имеет вычислимое представление тогда и только тогда, когда L имеет 0? -вычислимое представление.
Теперь согласно соответственно предложениям 2 и 3 мы имеем
Следствие 3 [18?. Каждый низкий линейный порядок вида (? + k + 1 + ?) · L
для некоторого L имеет вычислимое представление.
Следствие 4 [18?. Существует невычислимо представимый 2 -низкий
(k + 1) -блочный линейный порядок, не являющий k -блочным.
Линейный порядок L называется сильно ? -схожим, если он является k -блочным для некоторого k . Другими словами, линейный порядок является сильно
? -схожим, если существует натуральное число k такое, что все его блоки имеют мощность не более k . Чтобы доказать, что для всех k каждый низкий k блочный линейный порядок (то есть сильно ? -схожий) имеет вычислимое представление, необходима следующая теорема, которую можно назвать специической
0? -кодирующей теоремой.
Теорема 5 [18? (см. также [9?). Пусть L является сильно ? -схожим.
Тогда L имеет 0? -вычислимую копию, у которой отношение блока является 0? вычислимым, тогда и только тогда, когда L имеет вычислимую копию.
Следствие 5 [18?. Каждый низкий сильно ? -схожий линейный порядок изоморен некоторому вычислимому порядку.
В работе автора [18? предложена следующая теорема, позволяющая обобщить
0? -кодирующие теоремы . Доуни и Дж. Найт.
Теорема 6 [18?. Пусть ? является вычислимым линейным порядком без наименьшего и наибольшего элементов. Если L является 0? -вычислимым линейным
порядком, то ? · L имеет вычислимое представление.
Нетрудными рассуждениями можно показать, что теоремы 2 и 4 являются следствиями теоремы 6. Более того, из теоремы 6 выводится ряд следствий, которые
ранее были неизвестными и требовали собственного доказательства, например, следующее следствие и многие другие (включая следствие 7 из следующего раздела).
Следствие 6. Линейный порядок L имеет 0? -вычислимое представление то-
гда и только тогда, когда (? + 1 + ? + 2 + · · · + ? + k + 1 + ?) · L имеет вычислимое
представление.
Доказательство. (Теоремы 2 и 4 выводятся из теоремы 6 аналогичными рассуждениями.)
( ? ) Непосредственно следует из теоремы 6.
146
А.Н. ФОЛОВ
( ? ) Очевидно, что множество таких наборов (a1 , . . . , ak+1 ) , что (ai , ai+1 ) является парой соседних элементов для любого i ? k , является 0? -вычислимым. Ясно,
что это множество наборов с индуцированным порядком изоморно L .
2.
Одно применение 0? -кодирующей теоремы
Линейный
порядок называется ? -схожим ( ? -like), если его можно представить
P
в виде
/ rng(f ) . Функция
f (q) для некоторой ункции f : Q ? N такой, что 0 ?
q?Q
f называется ? -ункцией линейного порядка L . Не трудно видеть, что если область значений ? -ункции ? -схожего линейного порядка ограничена, то порядок
является сильно ? -схожим.
Дж. озенштейном [14? было установлено, что для вычислимого ? -схожего линейного порядка ? -ункция может быть выбрана из класса ?03 , и следовательно, ее ранг будет изPкласса ?03 . С. Феллнер [8? показал, что если f ? ?02 , то
линейный порядок
f (q) имеет вычислимое представление. Однако не каждая
q?Q
?03 -вычислимая ункция является ? -ункцией вычислимого линейного порядка.
Первый пример такой ункции (с бесконечным рангом) был построен в совместной работе М. Лермана и Дж. озенштейна [11?. Позже . Доуни [2, теорема 4.16?
?03 -вычислимую ункцию f такую, что rng(f ) = {1, 2, 3, 4} и линейный
построил P
f (q) не имеет вычислимого представления.
порядок
q?Q
Естественно возникает вопрос: какие еще ранги могут иметь аналогичные примеры ункций, то есть ункций, не являющихся ? -ункциями для вычислимых
линейных порядков. В частности, можно ли доказать утверждение . Доуни для
rng(f ) = {1, 2} вместо rng(f ) = {1, 2, 3, 4} ? Следующая теорема, опубликованная
ранее автором в кратком сообщении [20?, отвечает на эти вопросы.
Теорема 7. Пусть f произвольная X -вычислимая ? -ункция с неодноэлементным рангом. Тогда
существует X???? -вычислимая ? -ункция g такая, что
P
rng(g) = rng(f ) и
g(q) не имеет вычислимой копии. Причем если f имеет коq?Q
нечный ранг или хотя бы degT (f ) ? 0?? , то ункция g может быть выбрана
0?? -вычислимой.
Доказательство. Из теоремы 6 аналогично доказательству следствия 6 вытекает следующее 0? -кодирование.
Следствие 7. Пусть a0 < a1 < · · · < an , a0 6= 0 и n ? 1 . Тогда линейный
порядок L имеет 0? -вычислимое представление тогда и только тогда, когда линейный порядок L? = (a0 ? + a1 + a0 ? + · · · + a0 ? + an + a0 ?) · L имеет вычислимое
представление.
Понятно, что линейный порядок (a0 ? +a1 +a0 ? +· · ·+a0 ? +an +a0 ?)·L является
? -схожим, и следовательно, для него существует некоторая ? -ункция. Построим
ее вычислимо относительно оракула X такого, что X вычисляет L . Заиксируем
P
X -равномерно вычислимую последовательность {Qx }x?L такую, что Q =
Qx
x?L
является X -вычислимым линейным порядком, Qx плотным линейным порядком
без концевых точек для каждого x ? L . Тогда Q ?
= Q.
Выберем n произвольных элементов (например, с наименьшим натуральным
номером) q1x < Q · · · < Q qnx из каждого Qx . Определим вспомогательную ункцию fe: положим fe(qix ) = ai для всех x ? L и 1 ? i ? n и fe(q) = a0 для всех
P e ?
остальных q ? Q . Заметим, что
f (q) = a0 ? + a1 + a0 ? + · · · + a0 ? + an + a0 ? .
q?Qx
147
ЛИНЕЙНЫЕ ПОЯДКИ. ТЕОЕМЫ КОДИОВАНИЯ
Так как Q ?
= Q , существует X -вычислимый изоморизм ? : Q ? Q . Положим
теперь f (q) = fe(?(q)) для всех q ? Q . Понятно, что ункция f является X P
P e
P P e
P
f (q) ?
f (q) ?
f (q) ?
(a0 ? + a1 + a0 ? +
вычислимой. Причем
=
=
=
q?Q
q?Q
x?L q?Qx
x?L
+ · · · + a0 ? + an + a0 ?) ?
= (a0 ? + a1 + a0 ? + · · · + a0 ? + an + a0 ?) · L .
Таким образом, доказано, что для X -вычислимого
порядка L сущеP линейного
ствует X -вычислимая ? -ункция f такая, что
f (q) ?
= (a0 ? + a1 + a0 ? + · · · +
q?Q
+ a0 ? + an + a0 ?) · L , где a0 6= 0 и n ? 1 .
e 0?? Пусть D = {a0 < a1 < · · · < an } , где a0 6= 0 и n ? 1 . Предположим, что L
?
вычислимый линейный порядок, не имеющий 0 -вычислимой копии. Тогда
P по?доf (q) = L
казанному выше существует 0?? -вычислимая ? -ункция f такая, что
q?Q
e
e . Так как L
и rng(f ) = D , где L = (a0 ? + a1 + a0 ? + · · · + a0 ? + an + a0 ?) · L
не имеет 0? -вычислимого представления, из следствия 7 вытекает, что L не имеет
вычислимой копии.
Таким образом, доказано, что для конечного множества D такого, что 0P
?
/D и
|D| > 1 , существует 0?? -вычислимая ? -ункция f , что линейный порядок
f (q)
q?Q
не имеет вычислимого представления при rng(f ) = D .
Пусть теперь f произвольная ? -ункция с бесконечным
Pрангом. Построим
новую ункцию g , имеющую тот же самый ранг, что и f , но
g(q) не имеет выq?Q
числимой копии. Заиксируем конечное множество D ? rng(f ) : 0 ?
/ D и |D| > 1 .
??
Из доказанного вышеP
следует, что существует 0 -вычислимая ? -ункция fe, приe
чем rng(f ) = D и
fe(q) не имеет вычислимого представления. Пусть Q1 и
q?Q
Q2 два плотных линейных порядка без концевых точек. Имеем вычислимые изоморизмы ?1 : Q ? Q1 , ?2 : Q ? Q2 и ? : Q ? Q1 + 1 + Q2 . Заиксируем
произвольный элемент a0 из rng(f ) .
Построим новую ункцию g :
1) положим g(q) = fe(??1
1 (?(q))) для любого q ? Q такого, что ?(q) ? Q1 ;
2) положим g(q) = f (??1
2 (?(q))) для любого q ? Q такого, что ?(q) ? Q2 ;
3) положим, наконец, g(q) = a0 для единственного q ? Q , причем ?(q) ?
/ Q1
и ?(q) ?
/ Q2 .
Имеем
X
q?Q
g(q) ?
=
X
g(q) + a0 +
q?Q,?(q)?Q1
?
=
X
q?Q1
X
g(q) ?
=
q?Q,?(q)?Q2
fe(??1
1 (q)) + a0 +
X
q?Q2
?
f (??1
2 (q)) =
X
q?Q
fe(q) + a0 +
X
f (q).
q?Q
P e
f (q) не имеет вычислимого представления, лиТак как линейный порядок
q?Q
P
нейный порядок
g(q) также не имеет вычислимого представления. Наконец,
q?Q
очевидно, rng(g) = rng(f ) . Таким образом, теорема доказана.
3.
0?? -кодирующие теоремы
Классической 0?? -кодирующей теоремой является следующая
Теорема 8 [15?. Линейный порядок L имеет 0?? -вычислимое представление
тогда и только тогда, когда ? · L имеет вычислимое представление.
148
А.Н. ФОЛОВ
Модиицируя исходное доказательство, К. Эш и Дж. Найт [1? предлагают следующую 0?? -кодирующую теорему.
Теорема 9 [1?. Линейный порядок L имеет 0?? -вычислимое представление
тогда и только тогда, когда ? · L имеет вычислимое представление.
Оба доказательства используют так называемый приоритетный метод с бесконечными нарушениями, или метод 0?? -приоритета. Все известные 0? -кодирующие
теоремы доказаны с помощью приоритетного метода с конечными нарушениями, или метода 0? -приоритета. Метод 0?? -приоритета явно сложнее метода 0? приоритета. Имеющаяся картина кажется логичной. Однако в этом разделе получим некоторые обобщения известных 0?? -кодирующих теорем с использованием
только лишь метода 0? -приоритета, то есть более простым методом.
Для этого используется понятие отношения соседства на линейных порядках.
оворим, что элементы x и y линейного порядка L находятся в отношении соседства, если x < L y и для любого z не верно x < L z < L y . Отношение соседства на
линейном порядке L обозначается SuccL .
Теорема 10. Пусть ? является вычислимым линейным порядком с вычислимым отношением соседства и выполнено
(?x)(?n)(?x? , y ? )[(x < ? x? < ? y ? ) & |[x? , y ? ]? | = n]
(1)
(?x)(?n)(?x? , y ? )[(x > ? x? > ? y ? ) & |[x? , y ? ]? | = n].
(2)
или
Тогда если L является 0 -вычислимым линейным порядком, то ? · L имеет вычислимое представление, обладающее вычислимым отношением соседства.
?
Доказательство. Без ограничения общности можно предположить, что выполнены оба условия (1) и (2). Будем строить вычислимое
представление линейного
P
порядка L0 = ? · L из блоков Li , то есть L0 =
Li , где Li копия ? . В кажi?L
дом блоке необходимо объявлять некоторые пары элементов соседними и никогда
не добавлять между ними новых элементов. Так как L является 0? -вычислимым,
конечных линейных пото существует такая 0? -вычислимая последовательность
S
рядков {At }t?? , что A0 = ? , At ? At+1 и L = At . Следовательно, существует
t
равномерно вычислимая аппроксимация {At,s }t,s?? такая, что At = lim At,s .
s?+?
Строим L0 следующим образом. Если на некотором шаге s появляется новый
элемент i ? At,s и x < i < y соседние элементы в At,s , то добавляем в L новый
блок Li между блоками Lx и Ly . Если же некоторый j выходит из At,s? на некотором шаге s? , то элементы соответствующего блока Lj присоединяем к одному
из соседних блоков в L , так как эти элементы становятся уже ѕлишнимиї. Если
соседний только один, то присоединяем к нему. Если есть соседний и слева La ,
и справа Lb , то выбираем наименьшее из a и b (наименьшее как натуральное
число) и присоединяем ѕлишниеї элементы старого блока Lj к блоку с выбранным номером. Можно считать, что линейный порядок L не пустой, так как иначе
теорема очевидна. Поэтому предполагаем, что хотя бы один соседний блок имеется.
Присоединение ѕлишнихї элементов к некоторому блоку Lp справа или слева
осуществляется следующим образом. Для любых двух ѕлишнихї элементов x и y ,
которые расположены по соседству на данном шаге, но которые еще не объявлены соседними, положим новый ѕлишнийї элемент z между ними и объявим пары
(x, z) и (z, y) соседними. После этого все ѕлишниеї элементы будут попарно соседними. В силу условий (1) и (2) всегда можно расширить блок Lp слева или справа
так, чтобы сохранить построение копии ? с объявленными соседними элементами.
ЛИНЕЙНЫЕ ПОЯДКИ. ТЕОЕМЫ КОДИОВАНИЯ
149
Далее на каждом шаге в каждом блоке кладем новые элементы, строя копию ? .
Так как ? имеет вычислимое отношение соседства, то одновременно объявляем
соответствующие пары элементов соседними.
Пусть s = s(t) такой шаг, что для любого s? ? s At = At,s? , тогда после этого
шага никакой блок Li для i ? At не будет присоединен к другому, а только, может
быть, некоторые другие будут присоединены к нему слева или справа, но, как
уже говорилось выше, это не портит построение копии ? с вычислимыми парами
соседних элементов. Таким образом, L0 ?
= ? · L и L0 имеет вычислимое отношение
соседства.
Обозначим класс линейных порядков, которые либо имеют вычислимые представления, либо не имеют низкого представления, как L1 . Другими словами, если
L низкий линейный порядок и L ? L1 , то L имеет вычислимое представление. В этом обозначении вопрос . Доуни [2?, озвученный в первом разделе, теперь
означает описать класс L1 .
Теорема 11. Пусть ? является 0? -вычислимым с 0? -вычислимым отноше-
нием соседства, удовлетворяет условию (1) и условию (2) теоремы 10 и такой,
что ? · L ? L1 для любого линейного порядка L . Тогда если линейный порядок L
имеет 0?? -вычислимое представление, то ? ·L имеет вычислимое представление.
Доказательство. Пусть ? является 0? -вычислимым с 0? -вычислимым отно-
шением соседства и удовлетворяет условиям (1) и (2) теоремы 10. И пусть L является 0?? -вычислимым. По теореме 10, релятивизованной относительно 0? , линейный порядок ? · L имеет 0? -вычислимое представление с 0? -вычислимым отношением соседства.
В работе автора [19? и независимо в работе А. Монталбана [13? доказано, что линейный порядок имеет низкое представление тогда и только тогда, когда он имеет
0? -вычислимое представление, обладающее 0? -вычислимым отношением соседства.
(Этот результат может рассматриваться как специическая 0? -кодирующая теорема.)
Отсюда следует, что порядок ? · L имеет низкое представление. Так как
? · L ? L1 , то ? · L имеет вычислимую копию. Что и требовалось доказать.
Из теоремы 11 следует целый ряд следствий (теоремы 8 и 9 также являются
следствиями теоремы 11). Покажем только некоторые из них.
Следствие 8. Линейный порядок L имеет 0?? -вычислимое представление
тогда и только тогда, когда (? + 1 + ?) · L имеет вычислимое представление.
Следствие 9. Линейный порядок L имеет 0?? -вычислимое представление
тогда и только тогда, когда (? ? + ? + ?) · L имеет вычислимое представление.
Доказательство. Проведем одновременное доказательство теорем 8 и 9, следствий 8 и 9.
Для любого L линейные порядки ?·L , ?·L , (?+1+?)·L и (? ? +?+?)·L являются
0-квазидискретными. (Линейный порядок R называется 0-квазидискретным, если
либо [x]R ?
= ? , либо [x]R ?
= ? , либо [x]R ?
= ? ? для любого x .)
В работе [17? доказано, что каждый 0-квазидискретный линейный порядок
содержится в классе L1 . И следовательно, по теореме 11 если L является 0?? вычислимым, то ? · L , ? · L , (? + 1 + ?) · L и (? ? + ? + ?) · L имеют вычислимые
копии. Обратное утверждение устанавливается непосредственной проверкой.
Стоит отметить, что данное доказательство опирается на работу автора совместно с П. Алаевым и Дж. Тјрбером [17?, а также на теорему 10, доказательства
150
А.Н. ФОЛОВ
которых используют лишь метод приоритета с конечными нарушениями. А исходное доказательство теорем 8 и 9 использует метод приоритета с бесконечными
нарушениями.
Естественными модиикациями доказательств теорем 10 и 11 доказывается следующая теорема.
Теорема 12. Пусть ? является 0? -вычислимым k -блочным линейным поряд-
ком с 0? -вычислимым отношением соседства и выполнено
(?x)(?y)[(y > ? x) & |[y]? | = k]
(3)
(?x)(?y)[(y < ? x) & |[y]? | = k)].
(4)
или
Пусть ? ·L ? L1 для любого линейного порядка L . Тогда если линейный порядок L
имеет 0?? -вычислимое представление, то ? ·L имеет вычислимое представление.
Эта теорема позволяет получить некоторые новые 0?? -кодирования, например,
такие, как следующее следствие, и многие другие.
Следствие 10. Пусть k > n . Тогда линейный порядок L имеет 0?? -вычис-
лимое представление тогда и только тогда, когда (· · · + ? + k + 1 + ? + k + 1 + ? +
+ n + 1 + ? + k + 1 + ? + k + 1 + ? + · · · ) · L имеет вычислимое представление.
абота выполнена при инансовой поддержке ФФИ (проекты ќ 10-01-00399
и 12-01-97008), гранта для поддержки ведущих научных школ НШ-5383.2012.1,
а также гранта Президента Ф МК-611.2011.1.
Summary
A.N. Frolov.
Linear Orderings. Coding Theorems.
In this paper, we onsider 0? - and 0?? -oding theorems. We obtain two general theorems
whih generalize all 0? - and 0?? -oding theorems known at this moment. Using one 0? -oding theorem, we desribe ranges of ? -funtions of ? -like linear orderings with no omputable
representations.
Key words:
linear orderings, omputable representations, oding theorems.
Литература
1.
Computable strutures and the hyperarithmetial hierarhy. Amsterdam: North-Holland Pub. Co., 2000. XVI + 346 p.
Ash C.J., Knight J.
2.
Downey R.G. Computability theory and linear orders // Ershov Yu.L., Gonharov S.S.,
Nerode A., Remmel J.B. (eds.) Handbook of Reursive Mathematis. V. 1. Elsevier,
1988. P. 823976.
3.
Downey R.G., Jokush C.G. Every low Boolean algebra is isomorphi to a reursive
one // Pro. Amer. Math. So. 1994. V. 122, No 3. P. 871880.
4.
5.
Orderings with ? -th jump degree 0(?) // Pro. Amer. Math.
So. 1992. V. 114, No 2. P. 545552.
Downey R.G., Knight J.F.
Downey R.G., Moses M.F. On hoie sets and strongly nontrivial self-embeddings of
reursive linear orderings // Zeitshr. f. Math. Logik und Grundlagen d. Math. 1989. Bd. 35, H. 3. S. 237246.
ЛИНЕЙНЫЕ ПОЯДКИ. ТЕОЕМЫ КОДИОВАНИЯ
6.
7.
151
Orderings and Boolean Algebras not isomorphi to reursive ones: PhD
Thesis. Cambridge, MA: MIT, 1967. 89 p. URL: http://dspae.mit.edu/bitstream/
handle/1721.1/60738/29976019.pdf?sequene=1.
Feiner L.J.
Feiner L.J.
The strong homogeneity onjeture // J. Symb. Logi. 1970. V. 35, No 3. P. 373377.
Reursive and nite axiomatizability of linear orderings: PhD Thesis. New
Brundswik, N. J.: Rutgers Univ., 1976.
8.
Fellner S.
9.
Frolov A., Zubkov M.
10.
Inreasing ? -representable degrees // Math. Log. Quart. 2009. V. 55, No 6. P. 633636.
Jokush C.G. Jr., Soare R.I. Degrees of orderings not isomorphi to reursive linear
orderings // Ann. Pure Appl. Logi. 1991. V. 52, No 12. P. 3964.
11.
Lerman M., Rosenstein J.R.
12.
Miller R.
13.
14.
Reursive linear orderings // Patras Logi Symposion (Pro.
Logi Sympos. Patras, Greee, Aug. 1822, 1980) (Stud. Logi Found. Math. V. 109). 1982. P. 123136.
The ?02 spetrum of a linear ordering // J. Symboli Logi. 2001. V. 66,
No 2. P. 470486.
Montalban A. Notes on the jump of a struture // Mathematial Theory and
Computational Pratie. Berlin; Heidelberg: Springer-Verlag, 2009. P. 372378.
Linear orderings (Pure and Applied Mathematis. V. 98). N. Y.
London: Aad. Press In., Hartourt Brae Jovanovih Publ., 1982. 487 p.
Rosenstein J.R.
15.
Watnik R. A generalization of Tennenbaum's Theorem on eetively nite reursive linear
orderings // J. Symb. Logi. 1984. V. 49, No 2. P. 563569.
16.
Соар .И. Вычислимо перечислимые множества и степени. Казань: Казан. матем.
о-во, 2000. 576 с.
17.
Алаев П., Тјрбер Дж., Фролов А.
18.
Фролов А.Н.
19.
Фролов А.Н.
20.
Вычислимость на линейных порядках, обогащјнных предикатами // Алгебра и логика. 2009. Т. 48, ќ 5. С. 549563.
?02 копии линейных порядков // Алгебра и логика. 2006. Т. 45,
ќ 3. С. 354370.
Линейные порядки низкой степени // Сиб. матем. журн. 2010. Т. 51,
ќ 5. С. 11471162.
Фролов А.Н. анги ? -ункций ? -схожих линейных порядков // Изв. вузов. Матем. 2012. ќ 3. С. 9699.
Поступила в редакцию
14.02.12
Фролов Андрей Николаевич кандидат изико-математических наук, доцент каедры высшей математики и математического моделирования Казанского (Приволжского) едерального университета.
E-mail: Andrey.Frolovksu.ru
Документ
Категория
Без категории
Просмотров
6
Размер файла
242 Кб
Теги
теорема, кодирование, линейный, порядке
1/--страниц
Пожаловаться на содержимое документа