О позитивных нумерациях семейств множеств иерархии Ершова

Алгебра и логика, 42, N 6 (2003), 737—746

УДК 510.5

О ПОЗИТИВНЫХ НУМЕРАЦИЯХ СЕМЕЙСТВ МНОЖЕСТВ ИЕРАРХИИ ЕРШОВА∗) Ж. Т. ТАЛАСБАЕВА

Используемые в статье основные понятия из теории алгоритмов и теории нумераций содержатся в [1—3]. Понятие вычислимости в общей форме введено в [4], откуда следует, что для семейств множеств в иерархии Ершова [5] понятие вычислимости можно ввести следующим образом. ОПРЕДЕЛЕНИЕ 1. Нумерация ν : N → S семейства Σ−1 n -множеств −1 S называется Σ−1 n -вычислимой, если {hx, mi | x ∈ νm} ∈ Σn .

Особый интерес для теории нумераций представляют позитивные нумерации, введенные в [6]. ОПРЕДЕЛЕНИЕ 2. Нумерация ν называется позитивной (разрешимой), если ее нумерационная эквивалентность θν = {hn, mi | νn = νm} является вычислимо перечислимым (вычислимым) множеством. В [7] сформулирована гипотеза о существовании Σ−1 n -вычислимой позитивной неразрешимой нумерации семейства всех Σ−1 n -множеств для каждого n > 1. В [8] доказано существование Σ−1 n -вычислимой позитивной нумерации семейства всех Σ−1 n -множеств для n > 2. В [9] показано, что бесконечные вычислимые семейства вычислимо перечислимых множеств, содержащие наибольшее по включению множество, имеют счетное число позитивных неразрешимых вычислимых нумераций. ТЕОРЕМА. Для каждого четного n > 2 (нечетного n > 1), −1 бесконечное Σ−1 n -вычислимое cемейство S ⊆ Σn , допускающее хотя ∗)

Работа выполнена при финансовой поддержке INTAS-РФФИ, проект 00-499.

c Сибиpский фонд алгебpы и логики, 2003

738

Ж. Т. Таласбаева

бы одну Σ−1 n -вычислимую нумерацию и содержащее пустое множество (множество N ), обладает бесконечным числом неэквивалентных Σ−1 n вычислимых позитивных неразрешимых нумераций. ДОКАЗАТЕЛЬСТВО. Пусть α — произвольная Σ−1 n -вычислимая нумерация семейства S. Тогда существуют вычислимые последовательности вычислимо перечислимых множеств {R0,e }, {R1,e }, . . . , {Rn−1,e }, e ∈ N , такие, что Rn−1,e ⊆ Rn−2,e ⊆ . . . ⊆ R1,e ⊆ R0,e , а αe = (R0,e \ R1,e ) ∪ (R2,e \ \R3,e )∪. . .∪(Rn−2,e \Rn−1,e ) при четном n и αe = (R0,e \R1,e )∪(R2,e \R3,e )∪ ∪ . . . ∪ (Rn−3,e \ Rn−2,e ) ∪ Rn−1,e при нечетном n. t — конечная часть множества R , вычисленная к шагу t Пусть Ri,e i,e

в какой-нибудь равномерной по e процедуре перечисления множеств Ri,e , t \ Rt ) ∪ (Rt \ Rt ) ∪ . . . ∪ i 6 n − 1. Обозначим через αt e множество (R0,e 1,e 2,e 3,e t t t \Rt )∪(Rt \Rt )∪. . .∪ ∪(Rn−2,e \Rn−1,e ) при четном n и множество (R0,e 1,e 2,e 3,e t t t при нечетном n. ) ∪ Rn−1,e \ Rn−2,e ∪(Rn−3,e

Для каждого i ∈ N построим по шагам Σ−1 n -вычислимую нумерацию αi семейства S, удовлетворяющую следующим условиям: 1) все множества, кроме α0, имеют по одному αi -номеру, а совокупность номеров множества α0 в нумерации αi вычислимо перечислима; 2) множество N \ αi−1 (α0) не является вычислимо перечислимым. Будем строить вспомогательные частично вычислимые функции git (x)

для всех i, t и вычислимую функцию q(m, y, t). Области определения

функций git — конечные начальные сегменты натурального ряда, сильно вычислимые равномерно по i и t, причем dom(git ) ⊆ dom(git+1 ) для всех i, t. Кроме того, эти функции обладают следующим свойством: если значения git (x), git (y) определены и отличны от 0 для x, y, i, t ∈ N , то из x 6= y следует git (x) 6= git (y). Построение нумераций αi осуществляется с помощью функt = ∅ для всех i 6 n − 1 ций git (x). При четном n будем считать, что Ri,0 t = ∅ t = {0, 1, . . . , t}, Ri,0 и всех t. При нечетном n будем считать, что R0,0

для всех 1 6 i 6 n − 1 и всех t. Пусть F = {m | ∀m′ < m(αm 6= αm′ )}. Несложно доказать существование сильной последовательности конечных множеств {F t }t∈N такой, что limt F t = F , т. е.

О позитивных нумерациях семейств множеств иерархии Ершова

739

n ∈ F ⇔ ∃t0 ∀t > t0 (n ∈ F t ). Через ϕk обозначается одноместная частично вычислимая функция с геделевским номером k (см. [3]). Пусть Wn = dom(ϕn ) для всех n. Будем считать, что ϕ0 нигде не определена. Через c, l, r обозначаются канторовские нумерационные функции [1, 2]. Функции c3 и c3i , 1 6 i 6 3, кодируют и декодируют тройки натуральных чисел: c3 (x, y, z) = c(c(x, y), z), c31 (m) = l(l(m)), c32 (m) = r(l(m)), c33 (m) = r(m) для всех x, y, z и m. Будем также считать, что c31 (m), c32 (m), c33 (m) 6 m для любого m. Конструкция Ш а г 0. Полагаем gi0 (0) = 0, gi0 (e) неопределенным, αi0 0 = α0 0, αi0 e = = ∅ для всех e > 0 и i, q(m, y, 0) = y для всех m и y. Ш а г t+1. Выполняем последовательно процедуры 1—3. Если какуюлибо из них нельзя выполнить, то сразу переходим к следующей. Процедура 1. Ищем четверку hi, j, k, yi такую, что 1) i 6 t + 1, j 6 t + 1, k 6 t + 1; 2) y > c3 (i, j, k), y ∈ F t+1 ; 3) метка c3 (i, j, k) нигде не поставлена; 4) на y не поставлены метки e для всех e 6 c3 (i, j, k); 5′ ) если i = j, то для некоторого x имеем git (x) = y, x ∈ Wkt и ¬∃u(u ∈ ∈ Wkt ∧ git (u) ↓ = 0); 5′′ ) если i 6= j, то git (x) = gjt (z) = y для некоторых x, z. Заметим, что может выполниться лишь одно из условий 5′ или 5′′ . Если хотя бы одна такая нашлась, то выбираем четверки с наименьшим канторовским номером c3 (i, j, k) ⇋ m, среди них — все с наименьшим значением счетчика q(m, y, t), а среди последних — с наименьшей четвертой компонентой y. Ставим метку m на α-номер y, снимаем с y метки e для всех e > m. Если i = j, то полагаем git+1 (x) = 0. Если i 6= j, то полагаем q(m, y, t + 1) = = q(m, y, t) + 1. Процедура 2. Ищем четверки hi, j, k, yi такие, что i, j, k 6 t + 1; y ∈ ∈

F t+1 ;

на y стоит метка c3 (i, j, k) ; i 6= j; существуют x, z такие, что

740

Ж. Т. Таласбаева

git (x) = gjt (z) = y и ϕt+1 k (z) ↓ = x. Для каждой такой четверки полагаем git+1 (x) = 0. Процедура 3. Если существуют тройки hx, y, ri такие, что grt (x) = y, где r 6 t + 1 и y ∈ / F t+1 , то для каждой из них полагаем grt+1 (x) = 0 и снимаем с y все метки. Если существует хотя бы одна пара чисел hp, ai такая, что p 6 t + 1, a ∈ F t+1 и a не является значением функции gpt или существует x такое, что gpt (x) = a и gpt+1 (x) было определено как 0 по процедурам 1 и 2, то обозначим через hp0 , a00 i, . . . , hp0 , a0q0 i, hp1 , a10 i, . . . , hp1 , a1q1 i, . . . , hph , ah0 i, . . . , hph , ahqh i все пары чисел, удовлетворяющие приведенным условиям. Для (xi + j) = aij , где xi — наименьшее i = 0, . . . , h и j = 0, . . . , qi полагаем gpt+1 i натуральное число, не принадлежащее dom(gpt i ). Для всех m и y полагаем q(m, y, t + 1) = q(m, y, t), если значение q(m, y, t + 1) не определено в процедуре 1 в явном виде. Для всех e, s ∈ N полагаем gst+1 (e) = gst (e), если значение gst+1 (e) не определено ранее в явном виде. Для всех x и s полагаем αst+1 x = = αt+1 gst+1 (x), если значение gst+1 (x) определено и отлично от 0, и αst+1 x = = ∅, если значение gst+1 (x) не определено. Для всех x и s таких, что gst+1 (x) = 0, полагаем αst+1 x = ∅ при четном n, и αst+1 x = αst x ∪ αt+1 0 при нечетном n. Переходим к следующему шагу. Свойства конструкции 1. Ни одна из меток не ставится на 0. На каждом шаге конструкции на любом α-номере стоит не более одной метки. Каждая метка в начале любого шага может стоять не более чем на одном числе. 2. Для любых y, t из того, что y ∈ F t , y > 0 и метка e снимается с y на шаге t по процедуре 1, следует, что на этом же шаге на y ставится метка большего приоритета. 3. Для любых x, s, i если gis (x) = 0, то git (x) = 0 при всех t > s. Для любых x, t, i из того, что git+1 (x) 6= git (x) и git (x) определено, следует, что git+1 (x) = 0.

О позитивных нумерациях семейств множеств иерархии Ершова

741

4. Для любых i ∈ N и b ∈ F существует шаг t такой, что для всех s > t выполняется b ∈ Val(gis ). 5. Для любых i, x существует предел limt git (x). Определим Gi (x) ⇋ ⇋ limt git (x). Положим αi x = {y | ∃t∀s > t(y ∈ αis x)}. 6. Нумерации αi являются Σ−1 n -вычислимыми для всех i. 7. Для всех x, i справедливо равенство αi x = αGi (x). Свойства 1—5 очевидны. Свойства 6, 7 следуют из выбора последоt } вательности {R0,0 t∈N , свойства 3 и процедуры 3.

8. Для любой метки e существует шаг t0 такой, что метка e либо стоит на некотором α-номере y на всех шагах t > t0 , либо не стоит на шаге t0 и не ставится ни на одно число на всех больших шагах. Доказательство проводится индукцией по e. Б а з и с и н д у к ц и и: e = 0. Поскольку 0 — это канторовский номер тройки h0, 0, 0i, метка 0 может быть поставлена только при выполнении условий 1—4, 5′ процедуры 1. Так как W0 = ∅, условие 5′ в этом случае не выполнится. Следовательно, метка 0 нигде не ставится. И н д у к ц и о н н ы й ш а г. Пусть утверждение свойства 8 справедливо для меток 0 , 1 , . . . , n − 1 , т. е. существует шаг t1 > n такой, что каждая из этих меток на шаге t1 либо уже стоит и потом не снимается, либо не стоит ни на одном числе и не ставится в дальнейшем. Проверим свойство 8 для e = n. Пусть hi, j, ki — это тройка, канторовский номер которой равен n. В силу свойства 2 и выбора шага t1 метка n может быть снята на шагах t > t1 только по процедуре 3. Пусть Y — множество всех чисел, на которых на шаге t1 стоит хотя бы одна из меток 0 , 1 ,..., n − 1 . a) Пусть i 6= j. Выберем наименьшее число z и шаг t2 > t1 такие, что z ∈ F \ Y , z > n, z ∈ F t для всех t > t2 , а z является значением функций git2 и gjt2 . Выбор шага t2 возможен в силу свойства 4. Обозначим b ⇋ q(n, z, t2 ). Если существует шаг t′ > t2 такой, что q(n, z, t′ + 1) > q(n, z, t′ ), то метка n ставится на z на шаге t′ + 1 и не снимается на больших шагах.

742

Ж. Т. Таласбаева Рассмотрим теперь случай, когда q(n, z, t) = b для всех t > t2 . Заме-

тим, что четверки с четвертой компонентой y, большей b, не могут быть выбраны в процедуре 1 для постановки метки n на шагах t > t2 , поскольку q(n, y, 0) = y > b. Выбираем шаг t3 > t2 такой, что для всех y 6 b из ∃t(q(n, y, t) > b) вытекает q(n, y, t3 ) > b; из limt q(n, y, t) 6 b вытекает limt q(n, y, t) = q(n, y, t3 ). Выбор шага t3 возможен в силу монотонности по t функции q(n, y, t). Докажем, что на шаге t3 +1 метка n уже стоит на каком-нибудь числе и в дальнейшем не снимается. Достаточно установить, что для любого t′ > t3 метка n стоит на некотором числе после выполнения шага t′ . Предположим противное. Тогда метка n будет поставлена на какое-нибудь число a на шаге t′ + 1, это вытекает из того, что на всех шагах, больших t3 , для четверки hi, j, k, zi выполняются условия 1, 2, 4, 5′′ процедуры 1. Значит, q(n, a, t′ +1) = q(n, a, t′ )+1. С другой стороны, a 6 b и q(n, a, t′ ) 6 b. Следовательно, по выбору шага t3 справедливо q(n, a, t′ + 1) = q(n, a, t′ ), получаем противоречие. b) Пусть i = j. Заметим, что если метка n ставится на какое-нибудь ′

число a на некотором шаге t′ , то существует x′ такое, что x′ ∈ Wkt и git (x′ ) = 0 для всех t > t′ . Тогда на всех шагах t > t′ при любом y для четверки hi, i, k, yi не выполнится условие 5′ процедуры 1. Значит, на этих шагах нельзя поставить метку n . Отсюда следует утверждение свойства 8 для метки n . 9. Для любой тройки hi, j, ki, где i 6= j, существует шаг t0 , на котором на некоторое число y ставится метка c3 (i, j, k) и не снимается в дальнейшем. Это свойство следует из доказательства свойства 8. 10. Для любых s, a, где a ∈ F , существует x такое, что limt gst (x) = a. Для a = 0 имеем gst (0) = 0 при всех t, s. Пусть a ∈ F и a > 0. По конструкции на число a нельзя поставить метки e для e > a. По свойству 8 существует шаг t0 такой, что каждая из меток 0 , 1 , . . . , a − 1 либо стоит на некотором α-номере на всех шагах t > t0 , либо не стоит на шаге t0 и не ставится ни на одно число на всех больших шагах.

О позитивных нумерациях семейств множеств иерархии Ершова

743

Выберем шаг t1 > t0 такой, что a ∈ F t для всех t > t1 и существует x′ такое, что gst1 (x′ ) = a. Выбор шага t1 возможен в силу свойства 4. Докажем, что существуют шаг t2 > t1 и x такие, что gst (x) = a для всех t > t2 . Если gst (x′ ) = gst1 (x′ ) для всех t > t1 , то требуемое очевидно. ′

′

Рассмотрим наименьший шаг t′ > t1 , для которого gst +1 (x′ ) 6= gst (x′ ). По свойству 3 выполняется gst (x′ ) = 0 для всех t > t′ . На шаге t′ + 1 имеет место одна из следующих возможностей: ′

a) если бы gst +1 (x′ ) положили равным 0 по процедуре 3, то выполни′

лось бы условие a ∈ / F t +1 , а это невозможно ввиду выбора шага t1 ; ′

b) если бы gst +1 (x′ ) положили равным 0 по процедуре 1, то на шаге t′ + 1 на a поставили бы метку, это также невозможно в силу выбора шага t1 ; ′

c) пусть на шаге t′ + 1 значение gst +1 (x′ ) положили равным 0 по процедуре 2, тогда для некоторых j, k, z ∈ N на шаге t′ + 1 на a стоит ′

метка c3 (s, j, k) , gjt (z) = a и ϕtk +1 (z) = x′ ; метка c3 (s, j, k) останется на ′

a и на всех шагах, больших t′ + 1. ′

По процедуре 3 существует x такое, что gst +1 (x) = a и x 6= x′ . Для всех t > t′ справедливо равенство gjt (z) = a. Действительно, при t > t′ значение gjt (z) не может стать равным 0 при осуществлении процедур 1 и 3 в силу тех же причин, что и ранее. Не может оно стать равным 0 и по процедуре 2, поскольку в этом случае на a должна стоять метка m такая, что c31 (m) = j, однако s 6= j. Тогда и gst (x) = a для всех t > t′ . Действительно, пусть t > t′ + 1. По причинам, рассмотренным в случаях ”a“ и ”b“, gst (x) не может оказаться равным 0 в процедурах 1 и 3 шага t. То же верно для процедуры 2 шага t, поскольку ϕk (z) = x′ 6= x. 11. Нумерации αi являются нумерациями семейства S для всех i. Покажем, что {αi m | m ∈ N } = S. Включение {αi m | m ∈ N } ⊆ S следует из свойства 7. Проверим обратное включение. Возьмем A ∈ S. Пусть a — наименьший номер множества A в нумерации α. Тогда a ∈ F . По свойству 10, limt git (x) = a при некотором x. Тогда αi x = A по свойству 7. 12. Все множества семейства S, за исключением α0, имеют в αi в точности по одному номеру. По свойству 7, αi x = αGi (x) для всех x. Покажем сначала, что для

744

Ж. Т. Таласбаева

всех i значения функций λxGi (x) лежат в F . Пусть a — произвольный элемент из N \F . Тогда a 6= 0. Если для некоторого x выполняется Gi (x) = = a, то для некоторого t имеем git (x) = a. Существует t′ > t, i, при котором ′

′

a 6∈ F t . По процедуре 3, git (x) = 0. Тогда по свойству 3 верно git (x) = 0 для всех t > t′ и Gi (x) = 0. Пусть b ∈ F \ {0}. По свойству 10 существует x ∈ N , для которого Gi (x) = b. По построению для каждого t функция git имеет не более одного прообраза элемента b; это справедливо и при переходе к пределу. Остается заметить, что для каждого B ∈ S существует единственный b ∈ F , для которого B = αb. 13. Множество αs−1 (α0) является вычислимо перечислимым для всех s. Свойство 13 следует из следующего равенства: αs−1 (α0) = {x | ∃t gst (x) = 0}. Включение {x | ∃tgst (x) = 0} ⊆ αs−1 (α0) вытекает из свойств 3 и 7. Обратное включение справедливо в силу свойств 3 и 7, определения множества F и доказанного ранее утверждения о том, что Val(Gi ) = F . 14. Нумерации αi являются позитивными для всех i. Действительно, αi x = αi y ⇔ (x ∈ αi−1 (α0) ∧ y ∈ αi−1 (α0)) ∨ x = y. Поэтому и в силу свойства 13 нумерация αi позитивна. 15. Нумерации αi являются неразрешимыми для всех i. Достаточно установить, что N \ αi−1 (α0) 6= Wk для каждого k. Пусть p = c3 (i, i, k). Рассмотрим два случая. а) Одно из чисел отмечается меткой p на некотором шаге t0 + 1. Тогда на шаге t0 + 1 выполняются условия 1—4, 5′ процедуры 1. Следовательно, существует x такое, что x ∈ Wkt0 и git0 +1 (x) = 0. В силу свойства 3 получаем limt git (x) = 0, поэтому αi x = α0. Значит, x ∈ Wk ∩ αi−1 (α0), и Wk 6= N \ αi−1 (α0). b) Ни одно число не отмечается меткой p . Пусть t1 — наименьший шаг такой, что все метки большего приоритета после шага t1 не ставятся и не снимаются. Существование такого шага вытекает из свойства 8. Пусть

О позитивных нумерациях семейств множеств иерархии Ершова

745

a — наименьшее число из F такое, что a > p и на a не ставятся метки e для e 6 p. По свойству 10 существуют t2 и x такие, что t2 > i, k, a ∈ F t и git (x) = a для всех t > t2 . Пусть t3 = max{t1 , t2 }. В силу выбора t3 на всех шагах t > t3 таких, что i, k 6 t для четверки hi, i, k, ai выполняются условия 1—4 процедуры 1, но не выполняется условие 5′ . Значит, x ∈ / Wk или α0 ∈ αi (Wk ). В первом случае получаем x 6∈ αi−1 (α0)∪Wk , во втором — αi−1 (α0) ∩ Wk 6= ∅. 16. Все нумерации αs , s ∈ N , попарно несравнимы. Фиксируем произвольные i, j, k, причем i 6= j и k — геделевский номер вычислимой функции. Покажем, что αj не может сводится к αi посредством функции ϕk . По свойствам 4 и 9 можно выбрать четверку hi, j, k, ai такую, что метка c3 (i, j, k) постоянно стоит на числе a, начиная с некоторого шага. По свойству 1, a > 0. Из описания процедуры 3 следует, что a ∈ F . По свойству 10 существуют x и z такие, что Gi (x) = Gj (z) = a. Если ϕk не является всюду определенной функцией, то она не может сводить αj к αi . Пусть ϕk всюду определена. Пусть t0 настолько велико, что i, j, k 6 t0 + 1, метка c3 (i, j, k) стоит на a на шаге t0 + 1, a ∈ F t0 +1 , git0 (x) = gjt0 (z) = a и ϕtk0 +1 (z) определено. Если ϕk (z) = x, то на шаге t0 + 1 после выполнения процедуры 2 значение git0 +1 (x) станет равным 0 и Gi (x) = 0, что противоречит выбору x. Если же ϕk (z) 6= x, то αi ϕk (z) 6= αj z, так как x, по свойству 12, является единственным αi номером множества αa. Из свойств 6, 11, 14—16 следует утверждение теоремы. Из конструкции и доказательства теоремы вытекает СЛЕДСТВИЕ. Семейство всех Σ−1 n -множеств обладает бесконечным числом Σ−1 n -вычислимых позитивных неразрешимых нумераций для каждого n > 1. В заключение автор выражает глубокую благодарность научному руководителю С. А. Бадаеву за постоянное внимание к работе, а также С. Ю. Подзорову за полезные обсуждения.

746

Ж. Т. Таласбаева ЛИТЕРАТУРА 1. Ю. Л. Ершов, Теория нумераций, М., Наука, 1977. 2. А. И. Мальцев, Алгоритмы и рекурсивные функции, М., Наука, 1965. 3. Х. Роджерс, Теория рекурсивных функций и эффективная вычислимость, М., Мир, 1972. 4. C. C. Гончаров, А. Сорби, Обобщенно-вычислимые нумерации и нетривиальные полурешетки Роджерса, Алгебра и логика, 36, N 6 (1997), 621—641. 5. Ю. Л. Ершов, Об одной иерархии множеств I, Алгебра и логика, 7, N 1 (1968), 47—74. 6. А. И. Мальцев, Позитивные и негативные нумерации, Докл. АН СССР, 160, N 2 (1969), 243—256. 7. S. A. Badaev, S. S. Goncharov, Theory of Numberings. Open Problems, in: P. A. Cholak (ed.), Computability theory and its applications. Current trends and open problems. Proc. 1999 AMS-IMS-SIAM joint summer res. conf. (Contemp. Math., 257), Providence, RI, Am. Math. Soc., 2000, 23—38. 8. Ж. Т. Таласбаева, Позитивная вычислимость семейства Σ−1 n множеств, Материалы 54-й научн. конф. студ. молод. учен. КазГНУ, Алматы, 26–27 апреля, 2000, 145—148. 9. С. А. Бадаев, О позитивных нумерациях, Сиб. матем. ж., 18, N 3 (1977), 483—496.

Поступило 20 августа 2001 г. Адрес автора:

Окончательный вариант 15 июля 2003 г.

ТАЛАСБАЕВА Жулдыз Таласбаевна, КАЗАХСТАН, 480012, г. Алматы, ул. Масанчи, 39/47, КазНУ, механико-математический факультет, кафедра геометрии, алгебры и математической логики.