Относительно гиперимунные отношения на структурах

Алгебра и логика, 43, N 2 (2004), 170—183

УДК 510.53

ОТНОСИТЕЛЬНО ГИПЕРИМУННЫЕ ОТНОШЕНИЯ НА СТРУКТУРАХ∗) С. C. ГОНЧАРОВ, Ч. Ф. Д. МАК-КОЙ, Дж. Ф. НАЙТ, В. С. ХАРИЗАНОВА § 1. Предварительные сведения В работе рассматриваются счетные структуры вычислимых предикатных языков, исследуются относительно гипериммунные и относительно гиперпростые отношения на этих структурах. Отношение R на носителе A счетной структуры A называется дополнительным, если символ для данного отношения не входит в язык L структуры A. Можно отождествить носитель структуры A с подмножеством ω, и представлять его как множество констант. Через LA обозначается расширение языка L константными символами a для всех a ∈ A, а через AA — соответствующая обогащенная структура. Атомной диаграммой D(A) структуры A называется множество всех атомных и отрицаний атомных предложений в языке LA , истинных в AA . Говорят, что структура вычислима, если вычислима ее атомная диаграмма. Нас интересуют синтаксические условия существования изоморфной копии структуры A, в которой образ R является относительно гиперпростым, а также синтаксические условия существования копии A, в которой ∗)

Работа выполнена при финансовой поддержке Национального научного фонда,

двухнациональный проект N DMS-0075899, первый автор был также поддержан Российским фондом фундаментальных исследований, проект N 02-01-00593, и Советом по грантам Президента РФ и государственной поддержке ведущих научных школ, проект НШ-2112.2003.1.

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

Относительно гипериммунные отношения на структурах

171

образ ¬R является относительно гипериммунным. Бесконечное множество натуральных чисел является гипериммунным тогда и только тогда, когда никакая вычислимая функция не мажорирует его главную функцию (см. [1]). Множество называется гиперпростым, если оно вычислимо перечислимо (в.п.), и его дополнение гипериммунно. Совокупность всех гиперпростых множеств является собственным подмножеством множества всех простых множеств, т. е. в.п. множеств, дополнение которых бесконечно и не содержит бесконечных в.п. подмножеств. В [2] показано, что дефицитное множество вычислимого 1-1-перечисления для невычислимого в.п. множества является гиперпростым. Следовательно, любая ненулевая в.п. тьюрингова степень содержит гиперпростое множество. Любой иммунный начальный сегмент вычислимого линейного порядка является гипериммунным [3]. В [4] изучались ко-в.п. интервалы в вычислимом линейном порядке с гипериммунными (эквивалентно, иммунными) образами в некоторой изоморфной копии данного линейного порядка. В [5] для вычислимой булевой алгебры A, атомы которой образуют бесконечное вычислимое множество, установлено, что для любой ненулевой в.п. тьюринговой степени существует изоморфная копия B алгебры A такая, что множество всех атомов этой копии является гипериммунным множеством, содержащимся в данной степени. В [6] изучались иммунность и простота отношений на вычислимых структурах, а также относительные иммунность и простота отношений на счетных структурах; были получены различные синтаксические условия, эквивалентные соответствующим семантическим условиям. В [7] были введены понятия формальной гипериммунности и формальной гиперпростоты для отношений на вычислимых структурах. Эти понятия являются синтаксическими аналогами гипериммунности и гиперпростоты. Там же были получены первые результаты о существовании для таких отношений. В [8] были предложены общие достаточные условия для существования гиперпростого отношения на вычислимой структуре, содержащегося в произвольной ненулевой в.п. тьюринговой степени. В настоящей работе рассматриваются относительные версии гипер-

172

С. C. Гончаров, Ч. Ф. Д. Мак-Кой, Дж. Ф. Найт, В. С. Харизанова

иммунности и гиперпростоты отношений на счетных структурах. Результаты, устанавливающие эквивалентность синтаксического и соответствующего семантического условий в вычислимых структурах, обычно требуют дополнительных предположений о разрешимости, аналогичные результаты для относительных версий алгоритмических свойств не содержат подобных предположений. Примеры таких относительных результатов представлены в [6, 9—12]. Всюду далее через A обозначается бесконечная вычислимая структура языка L, через R — дополнительное бесконечное и кобесконечное отношение на A. Без ограничения общности будем считать, что R является одноместным. Как обычно, и R, и ¬R будут обозначать дополнение множества R. Пусть ϕ0 , ϕ1 , ϕ2 , . . . — фиксированное эффективное перечисление всех одноместных частичных вычислимых функций, X ⊆ ω. Тогда X X ϕX 0 , ϕ1 , ϕ2 , . . . — фиксированное эффективное перечисление всех одно-

местных X-частичных вычислимых функций. Для структуры B под ϕB e D(B)

будем подразумевать функцию ϕe

. Следующая (каноническая) нумераdef

ция конечных множеств является стандартной. Пусть D0 = ∅. Для m > 0 полагаем Dm = {d0 , . . . , dk−1 }, где d0 < . . . < dk−1 и m = 2d0 + . . . + 2dk−1 . Следующее определение тоже стандартное (см. [1]). Последовательность (Ui )i∈ω конечных множеств называется сильной таблицей, если существует одноместная вычислимая функция f такая, что для любого i ∈ ω выполняется Ui = Df (i) . Сильная таблица называется таблицей без пересечений, если ее элементы попарно не пересекаются. ОПРЕДЕЛЕНИЕ 1. Пусть S ⊆ ω. (i) Отношение ¬S называется гипериммунным (на ω), если оно бесконечно, и не существует такой сильной таблицы без пересечений (Ui )i∈ω , что для любого i ∈ ω выполняется Ui ∩ S 6= ∅. (ii) Отношение S называется гиперпростым (на ω), если S в.п., а ¬S является гипериммунным. Аналогичным образом можно определить гипериммунность и гиперпростоту отношений на произвольном вычислимом множестве. Введем относительные версии гипериммунности и гиперпростоты.

Относительно гипериммунные отношения на структурах

173

ОПРЕДЕЛЕНИЕ 2. Пусть S — дополнительное (одноместное) отношение на носителе B счетной структуры B. (i) Последовательность (Ui )i∈ω конечных множеств назовем сильной таблицей относительно B, если существует одноместная B-вычислимая функция f такая, что для любого i ∈ ω выполняется Ui = Df (i) . (ii) Отношение ¬S назовем гипериммунным относительно B, если оно бесконечно и нет сильной относительно B таблицы без пересечений (Ui )i∈ω такой, что для любого i ∈ ω выполняется Ui ∩ S 6= ∅. (iii) Отношение S называется гиперпростым относительно B, если S в.п. относительно B, а ¬S является гипериммунным относительно B. В работе рассматриваются следующие проблемы. ПРОБЛЕМА 1. При каких синтаксических условиях существует изоморфизм F из A на копию B такой, что ¬F (R) является гипериммунным относительно B? ПРОБЛЕМА 2. При каких синтаксических условиях существует изоморфизм F из A на копию B такой, что F (R) является гиперпростым относительно B? Через ~a обозначается конечная последовательность (кортеж) элементов; часто будем писать a ∈ ~a вместо a ∈ ran(~a) и ~a ∩ G = ∅ вместо ran(~a) ∩ G = ∅. § 2. Относительно гипериммунные отношения В [7] введено синтаксическое свойство, соответствующее семантическому свойству гипериммунности, будем называть его формальной гипериммунностью. ОПРЕДЕЛЕНИЕ 3 [7]. (i) Формальной сильной таблицей на A называется такая вычислимая последовательность (ψi (~c, ~xi ))i∈ω экзистенцальных формул в языке L с конечным числом параметров ~c, что для любого конечного множества G ⊆ A существуют i ∈ ω и последовательность → −

~ai ∈ Alh(xi ) , для которых выполняется [AA |= ψi (~c, ~ai )] ∧ [~ai ∩ G = ∅].

174

С. C. Гончаров, Ч. Ф. Д. Мак-Кой, Дж. Ф. Найт, В. С. Харизанова (ii) Отношение ¬R называется формально гипериммунным на A, ес-

ли нет формальной сильной таблицы (ψi (~c, ~xi ))i∈ω на A такой, что для любого i ∈ ω выполняется 

 ∀~ai ∈ Alh(~xi ) [(AA |= ψi (~c, ~ai )) ⇒ (~ai ∩ R 6= ∅)].

Оказывается, что формальная гипериммунность на A является необходимым условием существования вычислимой копии A такой, что соответствующий образ является гипериммунным (см. [7]). Допустим, что B — вычислимая копия A, и F — изоморфизм из A на B. Нетрудно показать: если (ψi (~c, ~xi ))i∈ω — формальная сильная таблица на A, то (ψi (F (~c), ~xi ))i∈ω — формальная сильная таблица на B (см. [8]). ТЕОРЕМА 2.1 [7]. (i) Если F (¬R) является гипериммунным на B, то ¬R будет формально гипериммунным на A. (ii) Предположим, что существует алгоритм, который по заданной последовательности ~c ∈ A<ω и экзистенциальной формуле ψ(~u, ~x) в языке L, lh(~u) = lh(~c), определяет, выполняется ли 

 → − ∀~a ∈ Alh( x ) [(AA |= ψ(~c, ~a)) ⇒ (~a ∩ R 6= ∅)].

Если ¬R формально гипериммунно на A, то существуют вычислимая структура B и изоморфизм F из A на B такие, что отношение F (¬R) является гипериммунным на B. Бесконечной Σ1 -формулой называется Lωω1 -формула вида _

∃~ui ψi (~x, ~ui ),

i∈I

где для каждого i ∈ I формула ψi (~x, ~ui ) является конечной бескванторной. Будем считать, что конечные бескванторные формулы закодированы с помощью некоторой эффективной геделевской нумерации, а ψi является i-й формулой в данной нумерации. Если индексное множество I в.п., то получим вычислимую Σ1 -формулу. Можно рекурсивно продолжить определение вычислимых бесконечных формул, определив Σα - и Πα -формулы для каждого вычислимого ординала α (см. [9]).

Относительно гипериммунные отношения на структурах

175

ОПРЕДЕЛЕНИЕ 4. (i) Инфинитарной формальной сильной таблицей на A называется вычислимая последовательность вычислимых Σ1 формул (ψi (~c, ~xi ))i∈ω такая, что для любого конечного множества G ⊆ A → −

существуют i ∈ ω и ~ai ∈ Alh(xi ) , для которых выполняется [AA |= ψi (~c, ~ai )] ∧ [~ai ∩ G = ∅]. (ii) Отношение ¬R называется инфинитарно формально гипериммунным на A, если нет такой инфинитарной формальной сильной таблицы (ψi (~c, ~xi ))i∈ω на A, что для любого i ∈ ω выполняется 

 ∀~ai ∈ Alh(~xi ) [(AA |= ψi (~c, ~ai )) ⇒ (~ai ∩ R 6= ∅)].

Непосредственно из определения вытекает ПРЕДЛОЖЕНИЕ 2.1. Отношение ¬R инфинитарно формально гипериммунно на A тогда и только тогда, когда оно формально гипериммунно на A. Если существует изоморфная копия A, на которой образ ¬R является относительно гипериммунным, то ¬R должно быть формально гипериммунным на A. Оказывается, что данное необходимое синтаксическое условие является достаточным. ТЕОРЕМА 2.2. Пусть A — вычислимая L-структура, R — одноместное бесконечное и кобесконечное отношение на A. Тогда эквивалентны следующие условия: (i) Для всех копий B структуры A и всех изоморфизмов F из A на B отношение ¬F (R) не является гипериммунным относительно B. (ii) Отношение ¬R не является формально гипериммунным на A. ДОКАЗАТЕЛЬСТВО. (ii)⇒(i). Допустим, что ¬R не является формально гипериммунным на A. Пусть (ψi (~c, ~xi ))i∈ω — соответствующая формальная сильная таблица на A. Пусть B — копия A, а F — изоморфизм из A на B. Следовательно, (ψi (F (~c), ~xi ))i∈ω — формальная сильная таблица на B. Поскольку для любого ~ai ∈ A<ω выполняется (~ai ∩ R 6= ∅) ⇒ (F (~ai ) ∩ F (R) 6= ∅),

176

С. C. Гончаров, Ч. Ф. Д. Мак-Кой, Дж. Ф. Найт, В. С. Харизанова

имеем 

 ∀~bi ∈ B lh(~xi ) [(BB |= ψi (F (~c), ~bi )) ⇒ (~bi ∩ F (R) 6= ∅)].

Покажем, что F (R) не является гипериммунным относительно B, перечислив соответствующую сильную относительно B таблицу. Будем одновременно перечислять конечные последовательности элементов B, удовлетворяющих формулам из (ψi (F (~c), ~xi ))i∈ω , так, чтобы любая из этих последовательностей не пересекалась ни с одной ранее перечисленной. Это возможно в силу основного свойства формальной сильной таблицы. Для любой такой последовательности ~bi со свойством BB |= ψi (F (~c), ~bi )) имеем ~bi ∩ F (R) 6= ∅, что и требовалось. Образы этих последовательностей образуют сильную таблицу относительно B. (i)⇒(ii). Построим генерическую копию (B, S) структуры (A, R). Предположив, что ¬S не является гипериммунным относительно B, определим инфинитарную формальную сильную таблицу (ψi )i∈ω на A, поэтому ¬R не будет инфинитарно формально гипериммунным на A. Пусть B = {b0 , b1 , b2 , . . .} — бесконечное вычислимое множество, носитель B. Без ограничения общности можно считать, что (∀i)[bi = i]. Множество F условий форсинга состоит из всех конечных 1-1 частичных функций из B в A. Буквами p, q, r, . . . будут обозначаться элементы множества F. Пусть R — символ одноместного отношения, не лежащий в L. В качестве языка форсинга выберем пропозициональный язык P ∗ , в котором пропозициональными переменными являются атомные предложения в расширенном языке (L ∪ {R})B . Пусть P — подъязык языка P ∗ , состоящий из атомных предложений в языке LB . Пусть S∗ — множество вычислимых бесконечных предложений в языке P ∗ , S — множество вычислимых бесконечных предложений в языке P . Вычислимые бесконечные формулы рассматриваются только в нормальной форме. Следовательно, отрицания могут возникнуть только в конечных открытых подформулах. Для предложения ψ через neg(ψ) будем обозначать вычислимое бесконечное предложение (в нормальной форме), которое является двойственным к ψ, т. е. эквивалентно отрицанию ψ. Предложение ψ в языке форсинга P ∗ является

Относительно гипериммунные отношения на структурах

177

пропозициональным, но его можно также представлять как предикатное предложение в языке (L ∪ {R})B . Константами в ψ будем называть константы, которые входят в пропозициональные переменные формулы ψ. Особенно интересны предложения, для некоторого фиксированного e ∈ ω выражающие в (B, S) следующие факты: (i) ϕB e всюду определена (в языке S); ′ (ii) DϕB и D ϕB ′ не пересекаются для n 6= n (в языке S); e (n ) e (n)

(iii) DϕB (n) ∩ S6= ∅ для всех n (в языке S∗ ). e Запишем предложение из (i) следующим образом: ^ _

_

θσ .

n∈ω m∈ω {σ:ϕσ e (n)=m}

Здесь ϕσe (n) = m — это сходящееся вычисление на оракульной машине Тьюринга с геделевым индексом e, с n — на входе, m — на выходе, за не более, чем lh(σ) шагов, использующее конечный оракул σ ∈ 2lh(σ) , где θσ = θσn,m (~bσn,m ) — открытое предложение в языке LB , которое выражает информацию о D(B), содержащуюся в σ. Запишем предложение из (ii) в следующем виде: _

^

n6=n′ Dm ∩Dm′ =∅

_

′

{θσ ∧ θσ′ : ϕσe (n) = m ∧ ϕσe (n′ ) = m′ },

где θσ и θσ′ — открытые предложения в языке LB , выражающие подходящую информацию оракула о D(B), необходимую для вычислений ′

ϕσe (n) = m и ϕσe (n′ ) = m′ соответственно. Запишем предложение из (iii) следующим образом:   ^ _ _  {θσ : ϕσe (n) = m} ⇒ ¬R(bj ) . n,m

{j:j∈Dm }

Пусть p ∈ F и предложение ψ принадлежит S∗ , определим отношение вынуждения, p ψ, так: 1) p ψ для конечного предложения ψ тогда и только тогда, когда все константы из ψ принадлежат dom(p) и при отображении p предложение ψ становится истинным в (AA , R);

178

С. C. Гончаров, Ч. Ф. Д. Мак-Кой, Дж. Ф. Найт, В. С. Харизанова 2) p

ψi тогда и только тогда, когда (∃i ∈ I)[p ψi ];

i∈I V

3) p ⊇ q)[r ψi ].

W

i∈I

ψi тогда и только тогда, когда (∀q ⊇ p)(∀i ∈ I)(∃r ⊇

Имеют место обычные для форсинга леммы для любых p, q ∈ F и предложения ψ из S∗ . ЛЕММА 2.3. Выполняется [p ψ ∧ q ⊇ p] ⇒ q ψ. ЛЕММА 2.4. Выполняется ¬[(p ψ) ∧ (p neg(ψ))]. ЛЕММА 2.5. Выполняется (∃r ⊇ p)[(r ψ) ∨ (r neg(ψ))]. Говорим, что r разрешает ψ, если [(r ψ) ∨ (r neg(ψ))]. Полной последовательностью форсинга назовем цепь (pn )n∈ω таких условий форсинга, что для любого предложения ψ из S∗ существует n, при котором pn разрешает ψ; для любого a ∈ A существует n, при котором a ∈ ran(pn ); и для любого b ∈ B существует n, при котором b ∈ dom(pn ). Существование полной последовательности форсинга (pn )n∈ω вытекает из S леммы 2.5. Легко видеть, что pn является 1-1-функцией из B на A. n∈ω −1  S def . Тогда F индуцирует на B копию (B, S) струкpn Положим F = n∈ω

туры (A, R), где S = F (R).

Имеет место следующая ЛЕММА 2.6 (об истинности и форсинге). Для любого ψ ∈ S∗ условие (BB , F (R)) |= ψ выполняется тогда и только тогда, когда pn ψ для некоторого n ∈ ω. Для завершения доказательства теоремы 2.2 нам потребуется ЛЕММА 2.7. Отношение F (¬R) является гипериммунным относительно B. ДОКАЗАТЕЛЬСТВО. Предположим противное. Тогда существует e ∈ ω такое, что (DϕB )n∈ω является сильной таблицей на B, а для люe (n) бого n ∈ ω выполняется DϕB ∩ S = ∅. В силу леммы об истинности и e (n) форсинге существует p ∈ F (p = pn для некоторого n) такое, что p вынуждает утверждения, выражающие этот факт. Пусть p отображает d~ на ~c.

Относительно гипериммунные отношения на структурах

179

Определим вычислимую последовательность вычислимых Σ1 -формул в языке L с параметрами ~c. Пусть ~x0 , ~x1 , ~x2 , . . . — эффективное перечисление всех конечных последовательностей переменных языка L. Для i ∈ ω обозначим через ψi (~c, ~xi ) формулу _ _

~ ~ {q |= ”ϕB xi }. e (n) = m“ : n, m ∈ ω ∧ Dm = bi ∧ q(bi ) = ~

q⊇p

Заметим, что формула ϕB e (n) = m записывается с помощью вычислимой последовательности вычислимых Σ1 -формул. Это следует из эквивалентности ϕB e (n) = m ↔

_

(Du ⊆ B ∧ Dv ⊆ B ∧ hu, vi ∈ Wρ(e,n,m) ).

n,m∈ω

Докажем, что (ψi (~c, ~xi ))i∈ω является инфинитарной формальной сильной таблицей на A. Пусть G — конечное подмножество A. Положим def

M = {n ∈ ω : DϕB ∩ F (G) 6= ∅}. e (n) Очевидно, M является конечным множеством. Если найдется такое p′ ⊇ p, что для любого a ∈ G существует n ∈ ω со свойством p′ ”F (a) ∈ DϕB “, e (n) то выберем такое p′ . Иначе, возьмем p′ ⊇ p, при котором нет p′′ ⊇ p такого, что p′′ вынуждает какие-либо новые элементы из F (G) (т. е. такие, что p′ S их не вынуждает) в D ϕB . Выберем n ∈ / M такое, что для некоторых e (n) n∈ω

q ⊇ p′ и m выполняется q ”ϕB e (n) = m“, где Dm ⊆ dom(q). Определим def

~ai = q(Dm ), тогда AA  ψi (~c, ~ai ). Допустим теперь, что для некоторого ~ai ∈ Alh(~xi ) выполняется AA   ψi (~c, ~ai ). Тогда существуют q ⊇ p и ~bi , n, m такие, что q(~bi ) = ~ai , Dm = = ~bi и q ”ϕB(n) = m“. Следовательно, найдется q ′ ⊇ q такое, что для e

некоторого j ∈ Dm имеет место q ′ ¬R(bj ) откуда aj ∈ R. 2

§ 3. Относительно гиперпростые отношения При изучении в.п. отношений важную роль играют вычислимые Σ1 формулы с позитивными вхождениями R в расширенном языке L ∪ {R}.

180

С. C. Гончаров, Ч. Ф. Д. Мак-Кой, Дж. Ф. Найт, В. С. Харизанова ОПРЕДЕЛЕНИЕ 5. (i) Инфинитарной R+ -формальной сильной

таблицей на (A, R) называется такая вычислимая последовательность вычислимых Σ1 -формул (ψi (~c, ~xi ))i∈ω в языке L ∪ {R}, имеющих только позитивные вхождения R и конечное число параметров ~c, что для любого конечного множества G ⊆ A существуют i ∈ ω и последовательность ~ai ∈ Alh(~xi ) такие, что [(AA , R) |= ψi (~c, ~ai )] ∧ [~ai ∩ G = ∅]. Если описанные Σ1 -формулы являются конечными экзистенциальными, то говорят о R+ -формальной сильной таблице. (ii) Отношение R называется формально гиперпростым на A, если R является в.п. и нет R+ -формальной сильной таблицы (ψi (~c, ~xi ))i∈ω на (A, R) такой, что для любого i ∈ ω выполняется (∀~ai ∈ Alh(~xi ) )[((AA , R) |= ψi (~c, ~ai )) ⇒ (~ai ∩ R 6= ∅)]. В [7] установлено, что при подходящих условиях разрешимости R является формально гиперпростым на A тогда и только тогда, когда существует вычислимая копия B структуры A, в которой соответствующий образ R является гиперпростым на B. В следующей теореме предлагается релятивизованный аналог этого результата. ТЕОРЕМА 3.1. Пусть A — бесконечная вычислимая структура в предикатном языке L, R — вычислимое одноместное бесконечное и кобесконечное отношение на A. Тогда эквивалентны следующие условия: (i) для всех копий B структуры A и любого изоморфизма F из A на B отношение F (R) не является гиперпростым относительно B; (ii) отношение R не является формально гиперпростым на A. ДОКАЗАТЕЛЬСТВО. (ii)⇒(i). Доказывается так же, как в теореме 2.2. (i)⇒(ii). Докажем от противного. Предположим, что R является формально гиперпростым на A. Если R определимо на A с помощью вычислимой Σ1 -формулы с конечным числом параметров, то в любой копии B структуры A образ R будет в.п. относительно B. Следовательно, если B —

Относительно гипериммунные отношения на структурах

181

копия, в которой образ ¬R является относительно гиперимунным, то образ R будет относительно гиперпростым. Допустим, что R не определимо вычислимой Σ1 -формулой с конечным числом параметров. Тогда в генерической копии B структуры A образ R не является в.п. относительно B (см. [10, 11]). Введем, как в [6], расширенный язык L∗ = L ∪ {R′ } ∪ {Q}, где R′ — новый символ одноместного отношения, Q — новый символ двухместного отношения. Обогатим L-структуру A до L∗ -структуры A∗ . Структура A∗ получается с помощью расширения носителя A до бесконечного вычислимого множества R′ и добавления в A одноместного отношения R′ и двухместного отношения Q, последнее является 1-1-отображением из R′ на R. В структуре A∗ открытая L∗ -формула ¬R′ (x) определяет A, а экзистенциальная L∗ -формула ∃ yQ(y, x) определяет R. Следующая лемма является следствием доказательства результата из [6]. ЛЕММА 3.2. Пусть D ⊆ A. Если множество D определимо в A∗ с помощью вычислимой Σ1 -формулы ψ ∗ (~c ∗ , x) языка L∗ , то оно определимо в (A, R) с помощью некоторой Σ1 -формулы ψ(~c, x) языка L ∪ {R}, имеющей конечное число параметров ~c и только позитивные вхождения R. Более того, можно получить ψ(~c, x) эффективно из ψ ∗ (~c ∗ , x), равномерно по геделеву номеру ψ ∗ . В силу леммы 3.2 отношение ¬(R ∪ R′ ) является формально гиперпростым на A∗ . Применяя теорему 2.2 к отношению R ∪ R′ на структуре A∗ , найдем копию B∗ структуры A∗ и изоморфизм F из A∗ на B∗ такой, что структура B является образом A при отображении F и выполняются следующие свойства: (a) структура B вычислима относительно структуры B∗ ; (b) отношение F (R) является в.п. относительно B∗ ; (c) отношение (B ∗ \ F (R ∪ R′ )) гипериммунно относительно B∗ . Таким образом, в силу (a), любая вычислимая относительно B функция является вычислимой относительно B∗ . Очевидно, B \ F (R) = B ∗ \ F (R ∪ ∪R′ ). Поэтому B \ F (R) гипериммунно относительно B. Однако пока нель-

182

С. C. Гончаров, Ч. Ф. Д. Мак-Кой, Дж. Ф. Найт, В. С. Харизанова

зя заключить, что F (R) будет гиперпростым относительно B, поскольку F (R) не обязательно является в.п. относительно B. Теперь, используя конструкцию из [13], можно аналогично [6] доказать, что существует либо автоморфизм H структуры A, для которого H(R) является гиперпростым, либо изоморфизм H из B на структуру C такой, что H(F (R)) является гиперпростым относительно C. Следовательно, структура C является изоморфной копией A, на которой соответствующий образ R будет относительно гиперпростым. 2

ЛИТЕРАТУРА 1. R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Berlin, Springer-Verlag, 1987. 2. J. C. E. Dekker, A theorem on hypersimple sets, Proc. Am. Math. Soc., 5, N 5 (1954), 791—796. 3. C. G. Jockusch, Jr., Semirecursive sets and positive reducibility, Trans. Am. Math. Soc., 131, N 2 (1968), 420—436. 4. G. Hird, Recursive properties of intervals of recursive linear orders, in: J. N. Crossley, J. B. Remmel, R. A. Shore, M. E. Sweedler (eds.), Logical Methods, Boston, Birkhauser, 1993, 422—437. 5. J. B. Remmel, Recursive isomorphism types of recursive Boolean algebras, J. Symb. Log., 46, N 3 (1981), 572—594. 6. S. S. Goncharov, V. S. Harizanov, J. F. Knight, C. McCoy, Simple and immune relations on countable structures, Arch. Math. Logic, 42, N 3 (2003), 279—291. 7. G. R. Hird, Recursive properties of relations on models, Ann. Pure Appl. Logic, 63, N 3 (1993), 241—269. 8. V. S. Harizanov, Turing degrees of hypersimple relations on computable structures, Ann. Pure Appl. Logic, 121, N 2 (2003), 209—226. 9. C. J. Ash, J. F. Knight, Computable structures and the hyperarithmetical hierarchy, Amsterdam, Elsevier, 2000. 10. C. Ash, J. Knight, M. Manasse, T. Slaman, Generic copies of countable structures, Ann. Pure Appl. Logic, 42, N 3 (1989), 195—205. 11. J. Chisholm, Effective model theory vs. recursive model theory, J. Symb. Log., 55, N 3 (1990), 1168—1191.

Относительно гипериммунные отношения на структурах

183

12. A. Nerode and J. B. Remmel, A survey of lattices of r.e. substructures, in: A. Nerode, R. Shore (eds.), Recursion Theory (Proc. Symp. Pure Math., 42), Providence, RI, Am. Math. Soc., 1985, 323—375. 13. J. F. Knight, Degrees coded in jumps of orderings, J. Symb. Log., 51, N 4 (1986), 1034—1042.

Поступило 23 апреля 2002 г. Адреса авторов: ГОНЧАРОВ Сергей Савостьянович, Институт математики СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, РОССИЯ. e-mail: [email protected] McCOY, Charles F. D., Department of Mathematics, University of Wisconsin, Madison, Madison, WI 53706, USA. e-mail: [email protected] KNIGHT, Julia F., Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556, USA. e-mail: [email protected] HARIZANOV, Valentina S., Department of Mathematics, The George Washington University, Washington, D.C. 20052, USA. e-mail: [email protected]