Равномерность в теории вычислимых структур

Алгебра и логика, 42, N 5 (2003), 566—593

УДК 510.53

РАВНОМЕРНОСТЬ В ТЕОРИИ ВЫЧИСЛИМЫХ СТРУКТУР∗)

Р. ДОУНИ, Д. ХИРШВЕЛЬД, Б. ХУСАИНОВ

§ 1. Предварительные сведения Анализ эффективных версий теорем классической теории моделей играет существенную роль при исследовании вычислимых моделей. Представляет определенный интерес и изучение конкретных свойств структур, имеющих отношение к вычислимости. Одно из важных направлений в этих исследованиях связано с нахождением новых вычислимых структур с ”патологическими“ свойствами, которые отличают их от более естественных примеров, первоначально обосновывавших определения. В качестве примера рассмотрим число различных вычислимых версий данной структуры. Давно известно, что изоморфные вычислимые структуры могут существенно отличаться друг от друга с точки зрения теории вычислимости. Например, если L — линейное упорядочение по типу ω, S — отношение следования на L, то существует вычислимая копия L, в которой образ S вычислим, т. е. это — ω со стандартным порядком. При этом существуют вычислимые копии L, в которых образы S не вычислимы, см. [1]. Это приводит к следующим определениям. (Будем всегда предполагать, что расматриваются только вычислимые языки.) ОПРЕДЕЛЕНИЕ 1.1. Структура A называется вычислимой, если ее носитель |A| и атомная диаграмма структуры (A, a)a∈|A| вычислимы. Изо∗)

Работа выполнена при финансовой поддержке Фонда Марсдена Новой Зеландии.

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

Равномерность в теории вычислимых структур

567

морфизм из структуры A на вычислимую структуру называется вычислимым представлением для A. Эта терминология будет часто нарушаться, когда под вычислимым представлением будет подразумеваться его образ. Вычислимая размерность вычислимой структуры A — это число ее вычислимых представлений с точностью до вычислимого изоморфизма. Структуру вычислимой размерности 1 называют вычислимо категоричной. Легко построить примеры вычислимо категоричных структур (например, ω с функцией следования) и структур бесконечной вычислимой размерности (например, ω с линейным порядком). При этом построение структур конечной вычислимой размерности большей, чем 1 (оно впервые было осуществлено в [2]), достаточно сложно. Даже вычислимо категоричные структуры обладают порой неожиданными свойствами, связанными с вычислимой размерностью. Как показано в [3], существуют вычислимо категоричные структуры такие, что любое их расширение единственной константой уже не является вычислимо категоричным. Можно представлять себе, что в таких структурах закодированы структуры вычислимой размерности большей, чем 1. Один из подходов при столкновении с патологиями, подобными описанным выше, заключается в описании условий, при которых они не могут возникнуть. Предположим, например, что экзистенциальная диаграмма вычислимой структуры A вычислима. Тогда вычислимая размерность A равна либо 1, либо ω (см. [4]). Более того, если A вычислимо категорична, то каждое ее расширение конечным числом констант обладает тем же свойством (см. [5]). Другой подход состоит в попытке точного выявления источника патологий с последующим избавлением от них путем изменения соответствующих определений. Одним из примеров этого подхода является теория относительно вычислимых структур, предложенная независимо в [6, 7], основная идея которых заключается в изучении всех, а не только вычислимых, представлений структур. ОПРЕДЕЛЕНИЕ 1.2. Изоморфизм из структуры M на структуру A такую, что |A| ⊆ ω, называется представлением M. Как и в вычислимом

568

Р. Доуни, Д. Хиршвельд, Б. Хусаинов

случае, часто будем указывать на A как на представление для M. Степенью deg(A) данного представления называется объединение (тьюринговых) степеней носителя |A| и атомной диаграммы структуры (A, a)a∈|A| . Структура является относительно вычислимо категоричной, если любые два ее представления изоморфны посредством отображения, вычислимого относительно объединения степеней данных представлений. Строение относительно вычислимо категоричных структур достаточно прозрачно. В частности, любое расширение такой структуры конечным числом констант остается относительно вычислимо категоричным, что является следствием соответствия относительно вычислимой категоричности естественному синтаксическому понятию. ОПРЕДЕЛЕНИЕ 1.3. Пусть A — структура. Семейством Скотта для A называется вычислимо перечислимое (в.п.) множество S экзистенциальных формул в языке структуры A, расширенном конечным числом констант из A, такое, что каждый набор элементов из A удовлетворяет хотя бы одной формуле из S, а любые два набора элементов из A, удовлетворяющие одной и той же формуле из S, автоморфны. ТЕОРЕМА 1.4 [6, 7]. Вычислимая структура является относительно вычислимо категоричной тогда и только тогда, когда она обладает семейством Скотта. Маккой [8] показал, что при использовании понятия относительной вычислимой размерности, введенного Гончаровым и Венцовым, не существует вычислимой структуры, имеющей конечную относительную вычислимую размерность большую, чем 1. Следует отметить, что все известные естественные примеры вычислимо категоричных структур являются относительно вычислимо категоричными, где под естественными понимаются примеры, не требующие сложных конструкций, специально эксплуатирующих то, что в определении вычислимой категоричности упоминаются только вычислимые структуры. Такими естественными примерами являются линейные порядки с конечным числом пар соседних элементов, булевы алгебры с конечным числом атомов, алгебраически замкнутые поля конечной степени транс-

Равномерность в теории вычислимых структур

569

цендентности и многие другие. Возникновение при изучении вычислимых структур неожиданных примеров можно объяснить и недостаточностью требований равномерности в рассматриваемых определениях. Например, если вычислимая структура A вычислимо категорична, то для каждой вычислимой структуры B, изоморфной A, существует вычислимый изоморфизм из B на A, построение которого по заданному B может оказаться затруднительным, поскольку будет зависеть от тех свойств структуры B, которые не являются равномерно эффективными над всеми вычислимыми структурами, изоморфными A. С другой стороны, все упомянутые выше естественные примеры вычислимо категоричных структур, очевидно, являются равномерно вычислимо категоричными (в любом приемлемом смысле равномерности) при условии, что допускаются расширения конечным числом констант. (Например, ω с функцией следования не является равномерно вычислимо категоричной, но становится таковой, если мы добавим константу 0.) Цель настоящей статьи состоит в изучении эффектов, возникающих в результате добавления требований равномерности к некоторым определениям теории вычислимых структур. Мы увидим, что в зависимости от смысла, который вкладывается в понятие равномерности, эти эффекты могут быть такими же, как и в случае релятивизации. Предыдущие работы [9—13] в этом направлении обсуждаются ниже. В [14] рассматривалась общая ситуация, а также исследовались одновременно релятивизация и одно из понятий равномерности, которое также приводится ниже. Связи между этими работами обсуждаются в § 2. Основные сведения по теории вычислимости и теории моделей содержатся в [15, 16] соответственно. Если не оговорено специально, через Φ0 , Φ1 , . . . обозначается стандартная нумерация всех одноместных частично вычислимых функций. Как и в случае вычислимых функций, вычислимые структуры в заданном языке не могут быть эффективно занумерованы. Поэтому рассматриваются частично вычислимые структуры. Важно будет не то, как

570

Р. Доуни, Д. Хиршвельд, Б. Хусаинов

именно они определены, а то, что для любого вычислимого языка L существует вычислимая нумерация всех частично вычислимых структур в языке L (она включает в себя все вычислимые структуры). Предполагается, однако, что частично вычислимые структуры в языке L закодированы как подмножества ω эффективным образом так, что когда говорится о частично вычислимом операторе Ψ на частично вычислимых структурах b действующий на соязыка L, подразумевается тьюрингов функционал Ψ, ответствующих кодировках; т. е. если S есть код для частично вычислимой структуры M (как подмножество ω) в языке L, то через Ψ(M ) обозначаb ется Ψ(S). Аналогичная интерпретация подразумевается и для в.п. операторов на частично вычислимых структурах. Частичная структура в языке L — это структура, которая не обязательно содержит интерпретации всех константных символов из L, а функциональные символы из L интерпретируются как частичные функции. Если A — структура с носителем |A| ⊆ ω и n ∈ ω, то частичная структура A ↾ n получается ограничением носителя A на множество |A|∩{0, . . . , n−1} и соответствующим ограничением ее констант, функций и отношений (при этом интерпретации некоторых констант могут оказаться неопределенными, а функциональных символов — частичными).

§ 2. Равномерная вычислимая категоричность Существует не менее двух естественных способов определения равномерной вычислимой категоричности. В теории вычислимости она обычно определяется в терминах индексов. Однако, с теоретико-модельной точки зрения более естественно потребовать существование эффективной процедуры, строящей требуемые изоморфизмы не по индексам, а по самим структурам. Эти два подхода отражены в следующих определениях. ОПРЕДЕЛЕНИЕ 2.1. Пусть A — вычислимая структура, а M0 , M1 , . . . — вычислимая нумерация всех частично вычислимых структур в языке структуры A. Тогда A будет слабо равномерно вычислимо категоричной (слабо р.в.к.), если суще-

Равномерность в теории вычислимых структур

571

ствует всюду определенная вычислимая функция f такая, что Me ∼ =A⇒ ⇒ Φf (e) : Me ∼ = A; равномерно вычислимо категоричной (р.в.к.), если существует частично вычислимый оператор Ψ такой, что Me ∼ = A ⇒ Ψ(Me ) : Me ∼ =A (т. е. функция x 7→ Ψ(Me ; x) осуществляет изоморфизм из Me на A); (слабо) р.в.к. с параметрами, если существует конечное число элементов a0 , . . . , an ∈ |A| таких, что (A, a0 , . . . , an ) является (слабо) р.в.к. ЗАМЕЧАНИЕ. Для каждой частично вычислимой функции g существует всюду определенная вычислимая функция f такая, что g(e) ↓ ⇒ ⇒ Φf (e) = Φg(e) . Таким образом, для того, чтобы A была слабо р.в.к., достаточно существования частично вычислимой функции g, для которой Me ∼ = A. = A ⇒ g(e) ↓ ∧Φg(e) : Me ∼ Равномерно вычислимо категоричные (с параметрами) структуры изучал Венцов [12], слабо равномерно вычислимо категоричные (с параметрами) — Кудинов [9, 11], который также определил понятие особой, основанной на индексах, равномерности [10]. Различие между двумя понятиями, определенными выше, может быть понято с точки зрения программирования. Вычислимая структура A является слабо р.в.к., если существует вычислимая процедура, которая по заданной программе P (вычисляющей структуру B, изоморфную A) строит изоморфизм между B и A, возможно, используя информацию о P . С другой стороны, A является р.в.к., если существует вычислимая процедура, которая по заданной вычислимой структуре B, изоморфной A, строит изоморфизм между B и A без использования конкретной программы, которая выдает B. Таким образом, понятие равномерной вычислимой категоричности можно представить как интерактивную категоричность. Докажем несколько фактов, связывающих определенные выше понятия друг с другом, а также с понятиями вычислимой категоричности и относительной вычислимой категоричности. Рассмотрим несколько утверждений о вычислимой структуре A, а именно, C: A вычислимо категорична;

572

Р. Доуни, Д. Хиршвельд, Б. Хусаинов W: A слабо равномерно вычислимо категорична; WP: A слабо равномерно вычислимо категорична с параметрами; U: A равномерно вычислимо категорична; UP: A равномерно вычислимо категорична с параметрами; R: A относительно вычислимо категорична. Справедливы следующие импликации: U

⇒

⇓ W

UP

⇔

R

⇒

C,

⇓ ⇒

WP

и никакие другие, исключая получающиеся по транзитивности, в общем случае не имеют места. Все импликации в данной диаграмме очевидны за исключением эквивалентности утверждений UP и R, которая будет обсуждаться ниже. Если в качестве A взять ω с функцией следования, то UP верно (а значит, верно и WP), но W неверно (а значит, неверно U). Это подтверждает отсутствие стрелок из WP в W и из UP в U. Отсутствие других импликаций будет также обосновано ниже. Если A является жесткой (т. е. без нетривиальных автоморфизмов) или если имеет только конечное число автоморфизмов, то выполняются следующие соотношения: U

⇒

m W

UP

⇔

R

⇒

C.

m ⇒

WP

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

Равномерность в теории вычислимых структур

573

но ниже будет дано обоснование того, что и это тоже неверно. Рассмотрим также вопрос о сохранении этих понятий при расширении конечным числом констант. Покажем, что равномерная вычислимая категоричность является частным случаем понятия, введенного в [14]. В [17] рассматривался следующий вопрос. Если имеются структура A и бесконечное предложение ψ в языке структуры A, расширенном новым предикатным символом R, то верно ли, что для каждой структуры B, изоморфной A, существует deg(B)-вычислимое отношение RB на B такое, что (B, RB)  ψ? Было замечено, что проблема определения, будет ли структура относительно вычислимо категоричной, является частным случаем этого вопроса. Действительно, по данной структуре A можно определить кардиb структуры A с самой собой (а именно, двух дизъюнктнальную сумму A ных копий A в языке, расширенном двумя новыми символами одноместных предикатов, выделяющих эти копии). Существует такое вычислимое b расширенном новым бесконечное Π0 -предложение ψ в языке структуры A, 2

символом двухместного предиката R, при этом A относительно вычислимо категорична тогда и только тогда, когда для каждой структуры B, изоb существует deg(B)-вычислимое отношение RB на B такое, что морфной A, (B, RB)  ψ. (По существу, ψ утверждает то, что R осуществляет изоморфизм между двумя половинами несущей структуры, рассматриваемой как кардинальная сумма; ψ является бесконечной тогда и только тогда, когда язык структуры A бесконечен (см. [17])). Исследования в данном направлении были продолжены в [14], где вместо требования о существовании подходящего отношения RB для каждой структуры B, изоморфной A, внимание сосредоточено на вычислимых структурах B; для частного вида предложения ψ, описанного в предыдущем абзаце, это равносильно изучению вычислимой категоричности. Другой подход, рассмотренный в [14], состоит в том, чтобы потребовать от RB быть эффективно заданным (в операторном смысле) по структуре B, и это то понятие, которое, с той же ψ, как выше, равносильно равномерной

574

Р. Доуни, Д. Хиршвельд, Б. Хусаинов

вычислимой категоричности. Далее будет обсуждаться, какие выводы о равномерной вычислимой категоричности можно сделать из результатов работы [14]. Сначала покажем, что на равномерную вычислимую категоричность можно попрежнему смотреть как на равномерность в терминах индексов, но как на сильную, экстенсиональную форму равномерности, в которой нельзя обрабатывать разными способами две программы с одинаковыми выходами. Как замечено в [13], существует сходство между определенными аспектами предмета настоящей статьи и изучением вычислимости второго типа (вычислимости операторов типа (ω → ω) → ω). В частности, следующий результат можно расценивать как аналог фундаментальных теорем, доказанных в [18, 19], о связи между эффективными операциями и вычислимыми функционалами. (Формулировки этих теорем, а также обсуждение связанных с ними понятий и результатов есть в [20, § 15.3].) ТЕОРЕМА 2.2. Пусть A — вычислимая структура, а M0 , M1 , . . . — вычислимая нумерация всех частично вычислимых структур в языке структуры A. Если существует всюду определенная вычислимая функция f , для которой Me ∼ = A ⇒ Φf (e) : Me ∼ = A и Me = Mi ∼ =A⇒ ⇒ Φf (e) = Φf (i) , то A является р.в.к. ДОКАЗАТЕЛЬСТВО. Пусть f такая, как в формулировке теоремы. Используя теорему о рекурсии, определим двухместную вычислимую функцию g такую, что для каждого x ∈ ω частично вычислимые структуры Mgx (i) , где gx ≡ λy(g(x, y)) и i ∈ ω, задаются с помощью следующей процедуры.∗) ∗)

Для читателей, не имеющих опыта использования теоремы о рекурсии, будет по-

лезным более формальное определение функции g, помещенное ниже. Тем не менее, в первую очередь рекомендуется ознакомиться с ее описанием в основном тексте. Зададим всюду определенную вычислимую функцию d, частично вычислимые структуры MΦd(e) (x,2i) и значения Φd(e) (x, 2i + 1), e, x, i ∈ ω, по следующему правилу (Φd(e) (x, 2i + 1) используется в качестве индикатора; его вычисления сходятся, когда MΦd(e) (x,2i) доходит до этапа 4, описанного ниже). Вычисление каждой MΦd(e) (x,2i) начинается с э т а п а 1 путем эмулирования Mi . Если при этом когда-нибудь для некоторого se,x,i ∈ ω будет верно Φe (x, 2i)[se,x,i ] ↓ и

Равномерность в теории вычислимых структур

575

Вычисление каждой Mgx (i) начинается с э т а п а 1 путем эмулирования Mi . Если при этом когда-нибудь для некоторого si ∈ ω будет верно Φf (gx (i)) (x)[si ] ↓ = Φf (i) (x)[si ] ↓, то вычисление Mgx (i) переходит к этапу 2. В ходе э т а п а 2 ждем, пока не найдется какое-нибудь вложение Mgx (i) [si ] в A (если такое существует), а затем переходим к этапу 3. На э т а п е 3, как только найдем i 6= j такие, что Mgx (i) [si ] ⊆ Mgx (j) [sj ] и Φf (gx (i)) (x) 6= Φf (gx (j)) (x), то переходим к этапу 4. На э т а п е 4 для наименьшего вложения h (в некотором стандартном упорядочении конечных отображений) Mgx (j) [sj ] в A мы перенумеруем обе структуры так, чтобы их носители совпадали с ω и чтобы они были изоморфны структуре A посредством изоморфизма k ⊃ h, который отображает n-ый элемент из ω − dom(h) в n-ый элемент из |A| − rang(h). Определение g завершено. Вычислим Ψ(M ; x), где M — частичная структура в языке структуры A. Сначала определим, верно ли, что x ∈ |M |. Если нет, то по определеΦf (Φe (x,2i)) (x)[se,x,i ] ↓ = Φf (i) (x)[se,x,i ] ↓, то вычисление MΦd(e) (x,2i) переходит к этапу 2. В ходе э т а п а 2 ждем, пока не найдется какое-нибудь вложение MΦe (x,2i) [se,x,i ] в A (если такое существует), а затем переходим к этапу 3. На э т а п е 3, как только найдем i 6= j и шаг s такие, что 1) Φe (x, 2i)[s] ↓ и Φe (x, 2j)[s] ↓, 2) существуют вложения MΦe (x,2i) [s] и MΦe (x,2j) [s] в A, 3) Φe (x, 2i + 1)[s] ↑ и Φe (x, 2j + 1)[s] ↑, 4) MΦe (x,2i) [si ] ⊆ MΦe (x,2j) [sj ], 5) Φf (Φe (x,2i)) (x) 6= Φf (Φe (x,2j)) (x), вычисления MΦd(e) (x,2i) и MΦd(e) (x,2j) переходят к этапу 4. На э т а п е 4 сначала ищем наименьшее вложение h (в некотором стандартном упорядочении конечных отображений) MΦe (x,2j) [se,x,j ] в A, если такое существует. Затем перенумеруем обе структуры так, чтобы их носители совпадали с ω и чтобы они были изоморфными структуре A посредством изоморфизма k ⊃ h, который отображает n-ый элемент из ω − dom(h) в n-ый элемент из |A| − rang(h), если это возможно (в противном случае обе структуры перестают расти). Наконец, и Φd(e) (x, 2i + 1), и Φd(e) (x, 2j + 1) сходятся к шагу s. По теореме о рекурсии существует e ∈ ω такое, что Φe = Φd(e) . Для данного e определим g(x, i) = Φe (x, 2i). Несложно проверить, что g ведет себя так, как описано в доказательстве.

576

Р. Доуни, Д. Хиршвельд, Б. Хусаинов

нию Ψ(M ; x) расходится. В противном случае ищем i, s ∈ ω, при которых Φf (gx (i)) (x)[s] ↓ и Mgx (i) [s] = M ↾ Mgx (i) [s] . Если они найдены, то полагаем Ψ(M ; x) = Φf (gx (i)) (x). Очевидно, Ψ является частично вычислимым оператором. Пусть Me ∼ = A. Рассмотрим Mgx (e) . = A, покажем, что Ψ(Me ) : Me ∼ Если вычисление этой структуры никогда не то Mg (e) = Me , а значит, Mg (e) ∼ = A и x ∈ x

x

достигнет второго этапа, Mg (e) , но неверно, что x

Φf (gx (e)) (x) ↓ = Φf (e) (x) ↓, приходим к противоречию с определением f . Следовательно, вычисление Mgx (e) переходит ко второму этапу. Тогда оно достигнет и третьего, поскольку Me ∼ = A. Однако для всех i ∈ ω вычисление Mgx (i) не может перейти к четвертому этапу, поскольку это означало бы существование j ∈ ω, для которого ∼ A, но Φf (g (j)) 6= Φf (g (i)) , получилось бы противоречие Mg (i) = Mg (j) = x

x

x

x

с определением f . Таким образом, вычисление Mgx (e) переходит к третьему этапу, но никогда не покидает его, значит, Mgx (e) конечно. Следовательно, должны существовать i, s ∈ ω, для которых Φf (gx (i)) (x)[s] ↓ и Mgx (i) [s] = = Me ↾ Mgx (i) [s] . (Можно взять, например, i = e.) Поскольку по определению Ψ(M ; x) = Φf (gx (i)) (x) для первых найденных i и s, достаточно показать, что Φf (gx (i)) (x) = Φf (e) (x) для любого такого i. Если Φf (gx (i)) (x) 6= 6= Φf (e) (x), то из того, что вычисление Mgx (e) достигает второго этапа, следует Φf (gx (e)) (x) = Φf (e) (x), отсюда Φf (gx (i)) (x) 6= Φf (gx (e)) (x). Поэтому хотя бы одно из вычислений Mgx (e) или Mgx (i) переходит к четвертому этапу, что, как было уже доказано, невозможно. 2 Одно из следствий теоремы 2.2 состоит в том, что нет ни одного естественного понятия равномерности, расположенного строго между слабой равномерной вычислимой категоричностью и равномерной вычислимой категоричностью. Другое следствие заключается в том, что эти два понятия совпадают на жестких структурах; более сильной версией этого факта является СЛЕДСТВИЕ 2.3. Структура A, имеющая только конечное число автоморфизмов, является слабо р.в.к. (с параметрами) тогда и толь-

Равномерность в теории вычислимых структур

577

ко тогда, когда она является р.в.к. (с параметрами). ДОКАЗАТЕЛЬСТВО. Достаточно рассмотреть вариант без параметров. Пусть M0 , M1 , . . . — вычислимая нумерация всех частично вычислимых структур в языке структуры A, а f — как в определении слабой р.в.к. Построим всюду определенную вычислимую функцию fˆ, удовлетворяющую условиям теоремы 2.2. Пусть g0 , . . . , gn — автоморфизмы на A, S — множество всех j 6 n таких, что gj вычислим. Если Me = Mi и Φf (e) 6= Φf (i) , то Φf (e) ◦(Φf (i) )−1 = = gj для некоторого j 6 n, и в этом случае j ∈ S. Очевидно, существуют конечное D ⊂ |A| и попарно различные функции h0 , . . . , hn : D → |A| такие, что gi расширяет hi для каждого i 6 n. Пусть d0 < · · · < dm — все элементы из D. Определим fˆ так, чтобы Φfˆ(e) задавалось следующим образом. Сначала ждем, пока все hj (D), j ∈ S, появятся в области значений Φf (e) . Для всех j ∈ S и i 6 m выберем xji такое, что Φf (e) (xji ) = hj (di ). Выберем j ∈ S, для которого hxj0 , . . . , xjm i минимален в некотором фиксированном упорядочении наборов. Теперь начинаем вычисление gj ◦ Φf (e) . Очевидно, fˆ можно выбрать всюду определенной вычислимой функцией. Если Me ∼ = A, то Φfˆ(e) ≡ gj ◦ Φf (e) для некоторого j ∈ S, поэтому (D) и (D) = Φ−1 Φfˆ(e) : Me ∼ = A, то Φ−1 = A. Наконец, если Me = Mi ∼ fˆ(i) fˆ(e) Φf (e) ◦ (Φf (i) )−1 ↾ D является тождественным отображением, т. е. Φf (e) = = Φf (i) . По теореме 2.2, A является р.в.к. 2 Из результатов работы [14] о вычислимых бесконечных Π02 -предложениях, а также теоремы 2.5, сформулированной ниже, вытекает СЛЕДСТВИЕ 2.4. Вычислимая структура является р.в.к. с параметрами тогда и только тогда, когда она относительно вычислимо категорична. Таким образом, в силу теоремы 1.4 вычислимая структура является р.в.к. с параметрами тогда и только тогда, когда она обладает семейством Скотта. Теорема 2.5 также является следствием результатов [14]. Мы приводим доказательство только ради того, чтобы обосновать следствие 2.6.

578

Р. Доуни, Д. Хиршвельд, Б. Хусаинов ТЕОРЕМА 2.5 [12]. Вычислимая структура является р.в.к. тогда

и только тогда, когда она обладает семейством Скотта без параметров, и является р.в.к. с параметрами тогда и только тогда, когда обладает семейством Скотта. ДОКАЗАТЕЛЬСТВО. Вторая часть непосредственно следует из первой. Пусть A — вычислимая структура, а M0 , M1 , . . . — вычислимая нумерация всех частично вычислимых структур в языке структуры A. Н е о б х о д и м о с т ь. Если A является р.в.к., то возьмем Ψ, как в определении 2.1. Если ~x = (x0 , . . . , xk ) ∈ |A|k+1 , то пусть Me(~x) — ко нечная подструктура A такая, что xi ∈ Me(~x) и Ψ(Me(~x) ; xi ) ↓ для каждо го i 6 k. Пусть y0 , . . . , yn — элементы из Me(~x) , отличные от x0 , . . . , xk , δ(~x, y0 , . . . , yn ) — конъюнкция конечного числа элементов атомной диграммы подструктуры Me(~x) , и θ~x ≡ ∃y0 , . . . , yn δ(~x, y0 , . . . , yn ). Утверждается, что {θ~x | ~x ∈ |A|<ω } является семейством Скотта. Достаточно показать, что ~y лежит в орбите кортежа ~x, если A  θ~x (~y ). В этом случае существуют i и g такие, что g : A ∼ = Mi , g(~y ) = ~x и Me(~x) является подструктурой Mi . Нетрудно проверить, что (Ψ(A))−1 ◦ Ψ(Mi ) ◦ g является автоморфизмом структуры A, переводящим ~y в ~x. Д о с т а т о ч н о с т ь. Можно использовать стандартное доказательство того, что структура с семейством Скотта вычислимо категорична, поскольку там вычислимые изоморфизмы строятся равномерно. Предположим, что A обладает семейством Скотта без параметров {θn | n ∈ ω}. Оператор Ψ действует на структуре B следующим образом. Допустим, что x ∈ |B|, Ψ(B; y) уже определено для всех y ∈ |B| ↾ x, и Ψ(B; x) еще не определено. Тогда Ψ ищет θn такое, что B  θn (x0 , . . . , xk−1 , x), где x0 < . . . < xk−1 — все элементы из |B| ↾ x. Если такая формула найдена, то Ψ ищет z ∈ |A| такое, что A  θn (Ψ(B; x0 ), . . . , Ψ(B; xk−1 ), z). Если оно найдено, то Ψ(B; x) = z. Далее находим наименьшее w ∈ |A|, которое еще не попало в область значений Ψ(B), ищем θm такое, что A  θm (Ψ(B; x0 ), . . . , Ψ(B; xk−1 ), z, w), и затем v ∈ |B|, которое еще не лежит в области определения Ψ(B) и такое, что B  θm (x0 , . . . , xk−1 , x, v). Если это v найдено, то Ψ(B; v) = w.

Равномерность в теории вычислимых структур

579

Используя определение семейства Скотта, легко проверить, что если B∼ = A, то Ψ(B) является требуемым изоморфизмом. 2 Во второй половине доказательства теоремы 2.5 не требуется, чтобы B была вычислимой. Это значит, что релятивизация определения равномерной вычислимой категоричности не даст нам более сильное понятие. СЛЕДСТВИЕ 2.6. Если A является р.в.к., то существует частично вычислимый оператор Ψ такой, что для любого представления B структуры A выполняется Ψ(B) : B ∼ = A. Другое следствие теоремы 2.5 состоит в том, что равномерная вычислимая категоричность, в отличие от вычислимой категоричности, всегда сохраняется при расширении конечным числом констант (в самом деле, если структура обладает семейством Скотта, то любое ее расширение конечным числом констант тоже обладает семейством Скотта (см. [21])). СЛЕДСТВИЕ 2.7. Если A является р.в.к. (с параметрами) и a ∈ ∈ |A|, то (A, a) является р.в.к. (с параметрами). ТЕОРЕМА 2.8 [21]. Существует жесткая вычислимо категоричная структура без семейства Скотта. Соединив вместе теорему 2.5, следствие 2.3 и теорему 2.8, можно заключить, что слабая равномерная вычислимая категоричность является более сильным понятием, чем вычислимая категоричность. СЛЕДСТВИЕ 2.9 [9]. Существует вычислимо категоричная структура, не являющаяся слабо р.в.к. с параметрами. Необходимо показать, что слабая равномерная вычислимая категоричность и равномерная вычислимая категоричность являются различными понятиями. Это доказано в [11], используя результат из [22]. Ниже приводится прямая конструкция. ТЕОРЕМА 2.10 [11]. Существует слабо р.в.к. структура без семейства Скотта. ДОКАЗАТЕЛЬСТВО. Для каждого n ∈ ω через [n] обозначим ориентированный граф, состоящий из n + 3 узлов x0 , x1 , . . . , xn+2 с ребром из

580

Р. Доуни, Д. Хиршвельд, Б. Хусаинов

x0 в самого себя, из xn+2 в x1 и из xi в xi+1 для каждого i 6 n + 1. Узел x0 назовем вершиной графа [n]. Для каждого S ⊂ ω ориентированный граф [S] получается соединением копий графов [s] для всех s ∈ S путем отождествления всех их вершин. Пусть далее D0 , D1 , . . . — стандартная нумерация всех конечных непустых множеств, а B0n , B1n , . . . — n-ое равномерно в.п. (р.в.п.) семейство множеств в некотором стандартном упорядочении таких семейств. Построим р.в.п. семейство конечных множеств A0 , A1 , . . . со следующими свойствами: 1) не существует в.п. множества W такого, что каждое Ai содержит Dk для некоторого k ∈ W и (k ∈ W ∧ Dk ⊆ Ai , Aj ) ⇒ Ai = Aj ; 2) пусть N — множество всех i ∈ ω таких, что Ai непусто; существует частично вычислимая двухместная функция h такая, что если найдется биективное отображение g : ω → N , для которого при всех i ∈ ω выполняется Bin = Ag(i) , то и hn ≡ λi(h(n, i)) является таким отображением для каждого n ∈ ω. Предположим, что уже построены A0 , A1 , . . . с этими свойствами, и пусть A — вычислимый ориентированный граф, состоящий из дизъюнктного объединения графов [Ai ], i ∈ ω. Из первого свойства следует, что A не имеет семейства Скотта, а в силу второго он является слабо р.в.к. Перейдем к построению A0 , A1 , . . . . Можно предполагать, что Bin [s] =

= ∅, если s < hn, ii. Рассмотрим семейства множеств B0 , B1 , . . . , для которых существует биективное отображение g : ω → N такое, что Bi = Ag(i) для всех i ∈ ω. Не ограничивая общности можно считать, что для всех n, i, s ∈ ω существует j ∈ ω, для которого Bin [s] ⊆ Aj [s]. Для каждого e ∈ ω выберем k(e) такое, что Dk(e) = {2e}. Начинаем с Ai = ∅ для всех i ∈ ω. На шаге s действуем следующим образом. 1. Перечисляем 2s в Ahs,0i . 2. Ищем наименьшее e 6 s (если существует) такое, что k(e) ∈ We и Ahe,0i = {2e}. Если оно существует, то перечисляем 2he, 0i + 1 в Ahe,0i , а 2e и 2he, 1i + 1 в Ahe,1i . Будем говорить, что e активно на шаге s.

Равномерность в теории вычислимых структур

581

3. Для каждого e 6 s проверяем, существуют ли n, i ∈ ω такие, что hn, ii 6 s, e никогда не ускорялось из-за n ранее (определение ниже), 2e ∈ Bin [t], где t 6 s — шаг, на котором e активно, и Bin [s] 6= {2e}. Если это верно, то далее действуем следующим образом. Для каждого i 6 s такого, что 2e ∈ / Ahe,ii [s], перечисляем 2e в Ahe,ii . Для всех i, j 6 s таких, что 2he, ji + 1 ∈ / Ahe,ii [s], перечисляем 2he, ji + 1 в Ahe,ii . Перечисляем 2e и 2he, s + 1i + 1 в Ahe,s+1i . Будем говорить, что e ускоряется из-за n на шаге s. Построение закончено. Проверим, удовлетворяют ли A0 , A1 , . . . требуемым свойствам. Очевидно, A0 , A1 , . . . являются р.в.п. Каждое e ∈ ω может быть активным не более одного раза, поскольку e не может быть активным, пока Ahe,0i не станет одноэлементным, а если e однажды становится активным, то в дальнейшем это уже не повторится. Более того, если e активно на шаге s, то оно может ускориться не более одного раза для каждого n такого, что 2e ∈ Bin [s], i ∈ ω, поэтому каждое e ускоряется только конечное число раз. Ни одно число не перечисляется ни в какое Ahe,ii , i ∈ ω, на любом шаге, на котором e не является ни активным, ни ускоренным, поэтому каждое Ai конечно. Зафиксируем e ∈ ω. Если k(e) ∈ / We , то e никогда не будет активным, следовательно, Ahe,0i = {2e}, а значит, нет k ∈ We такого, что Dk ⊆ Ahe,0i . С другой стороны, если k(e) ∈ We , то либо e никогда не ускорится, и в этом случае Dk(e) ⊆ Ahe,0i , Ahe,1i и Ahe,0i 6= Ahe,1i , либо e ускорилось в последний раз на некотором шаге s, а в этом случае Dk(e) ⊆ Ahe,0i , Ahe,s+1i и Ahe,0i 6= Ahe,s+1i . Таким образом, нет в.п. множества W такого, что каждое Ai содержит Dk для некоторого k ∈ W и (k ∈ W ∧ Dk ⊆ Ai , Aj ) ⇒ ⇒ Ai = Aj . Определим отображение h. Пусть n, i ∈ ω заданы, h(n, j) уже определено для всех j < i. Дождемся шага s такого, что Bin [s] непусто и совпадает с Ak [s] для некоторого k ∈ / rang(h ↾ i), и определим h(n, i) = k. Очевидно, h частично вычислима. Зафиксируем n ∈ ω, для которого существует биективное отображение g : ω → N такое, что для всех i ∈ ω выполняется Bin = Ag(i) (поэтому

582

Р. Доуни, Д. Хиршвельд, Б. Хусаинов

каждое Bin непусто). Для завершения доказательства нам требуется показать, что hn ≡ λi(h(n, i)) является биективным отображением из ω на N , причем для всех i ∈ ω имеет место Bi = Ahn (i) . Очевидно, если hn определено для всех i ∈ ω, то оно является биективным (hn сюръективно, поскольку для каждого e ∈ ω найдется только конечное число k ∈ ω таких, что 2e ∈ Ak ). Предположим, что для всех j < i значение hn (j) определено и Bjn = Ahn (j) . Тогда hn (i) должно быть определено, в противном случае не существовало бы биективного отображения g : ω → N такого, что Bln = Ag(l) для всех l ∈ ω. Таким образом, осталось показать, что Bin = Ahn (i) для всех i ∈ ω. Зафиксируем i ∈ ω, и пусть k = hn (i). Сначала предположим, что для s из определения h(i) множество Bin [s] = Ak [s] не одноэлементно. Если Al и As содержат два одинаковых элемента, то в силу конструкции они равны, следовательно, Bin = Ag(i) = Ak . Теперь предположим, что для s из определения h(i) множество Bin [s] = Ak [s] одноэлементно. Тогда Bin [s] = {2e} и k = he, 0i для некоторого e ∈ ω. Если e никогда не становится активным, то Bin = {2e} = Ak . В противном случае каждое Al , содержащее 2e, имеет по крайней мере два элемента, и Bin обладает тем же свойством. Поэтому e ускоряется из-за n на некотором шаге t > s. Нетрудно проверить, что в этом случае Al ⊇ Bin [t] тогда и только тогда, когда l = he, ui, u 6 t. Кроме того, Ahe,ui = Ahe,vi для всех u, v 6 t. Значит, Al = Bin [t] тогда и только тогда, когда l = he, ui, u 6 t. В частности, Bin = Ak . 2 СЛЕДСТВИЕ 2.11. Существует слабо р.в.к. структура, не являющаяся р.в.к. с параметрами. Теорема 2.10 не исключает возможности того, что, в отличие от равномерной вычислимой категоричности, слабая равномерная вычислимая категоричность может не всегда сохраняться при расширении конечным числом констант. Следующий результат показывает, что в этом случае константы, которыми расширяется структура, не могут иметь простых орбит. В частности, невозможно закодировать структуру конечной вычислимой размерности, большей 1, внутри слабо р.в.к. структуры так, как это можно

Равномерность в теории вычислимых структур

583

было сделать в некоторых вычислимо категоричных структурах. ТЕОРЕМА 2.12. Если A является слабо р.в.к. (с параметрами) и орбита элемента a ∈ |A| вычислима, то (A, a) является слабо р.в.к. (с параметрами). ДОКАЗАТЕЛЬСТВО. Достаточно рассмотреть вариант без параметров. Пусть M0 , M1 , . . . — вычислимая нумерация всех частично вычислимых структур в языке (A, a). Поскольку A является слабо р.в.к., существует всюду определенная вычислимая f , для которой из Me ∼ = (A, a) вытекает, что Φf (e) : Me ∼ = (A, b) для некоторого b из орбиты элемента a. Определим частично вычислимую функцию fˆ, для которой из Me ∼ = (A, a) вытекает, что fˆ(e) ↓ и Φfˆ(e) : Me ∼ = (A, a). В силу замечания к определению 2.1 достаточно показать, что (A, a) является слабо р.в.к. Пусть e ∈ ω. Используя теорему о рекурсии, построим Mi следующим образом. Вначале копируем A. Как только найдется c ∈ |Mi | такое, что Φf (i) (c) = Φf (e) (aMe ), останавливаем построение Mi и спрашиваем, принадлежит ли c орбите элемента a. Если нет, то продолжаем копирование A. В противном случае ищем вложение g перечисленной на данный момент части Mi в A такое, что g(c) = a. Если такое вложение найдется, продолжаем строить Mi так, чтобы Mi оказалось изоморфным A посредством вычислимого изоморфизма h, расширяющего g, и определяем fˆ(e) так, чтобы Φfˆ(e) ≡ h ◦ (Φf (i) )−1 ◦ Φf (e) . Очевидно, fˆ частично вычислима. Если Me ∼ = A, то Φf (e) (aMe ) лежит в орбите элемента a и, следовательно, в силу свойств процедуры, описанной выше, заключаем, что c найдено и лежит в орбите элемента a, g найдено и fˆ(e) определено. Поэтому Φ ˆ является изоморфизмом из Me f (e)

в (A, a). 2 Модифицируя доказательство теоремы 2.12, можно показать, что термин ”вычислима“ допускает замену на термин ”Σ02 “, тем не менее остается открытым следующий ВОПРОС 2.13. Если A является слабо р.в.к. и a ∈ |A|, то будет ли (A, a) слабо р.в.к.?

584

Р. Доуни, Д. Хиршвельд, Б. Хусаинов § 3. Отношения на вычислимых структурах Изучение отношений на вычислимых структурах было начато в [23],

где рассматривались отношения, которые сохраняют некоторую степень эффективности в различных вычислимых представлениях структуры. ОПРЕДЕЛЕНИЕ 3.1. Пусть U — отношение на носителе вычислимой структуры A, а C — класс отношений. Говорят, что U является наследственно C на A, если образ этого отношения в любом вычислимом представлении A лежит в C. В этом параграфе будем рассматривать только инвариантные отношения, т. е. отношения, сохраняющиеся при всех автоморфизмах несущей структуры, поскольку понятия равномерности, связанные с неинвариантными отношениями, не имеют под собой разумных оснований. Начнем с равномерного аналога наследственной вычислимости. Оказывается, что в данном случае оба понятия равномерности совпадают. ОПРЕДЕЛЕНИЕ 3.2. Пусть A — вычислимая структура, M0 , M1 , . . . — вычислимая нумерация всех частично вычислимых структур в языке A, U — инвариантное k-местное отношение на A, и Φ0 , Φ1 , . . . — стандартная нумерация всех k-местных частично вычислимых функций. Отношение U является равномерно наследственно вычислимым, если существует всюду определенная вычислимая f такая, что Me ∼ = A ⇒ Φf (e) = U Me ; равномерно наследственно вычислимым с параметрами, если существует конечное число элементов a0 , . . . , an ∈ |A| таких, что U — равномерно наследственно вычислимое отношение на (A, a0 , . . . , an ). Определение выше похоже на определение из [13] (на самом деле, эквивалентно ему в силу результатов из [13] и следствия 3.9 ниже). ТЕОРЕМА 3.3. Пусть A — вычислимая структура, M0 , M1 , . . . — вычислимая нумерация всех частично вычислимых структур в языке A, и U — инвариантное k-местное отношение на A. Если U равномерно наследственно вычислимо, то существует частично вычислимый оператор Ψ такой, что Me ∼ = A ⇒ Ψ(Me ) = U Me .

Равномерность в теории вычислимых структур

585

ДОКАЗАТЕЛЬСТВО проводится как в теореме 2.2 с использованием

функции f , заданной в определении 3.2. Заметим, что Me = Mi ∼ = A ⇒ ⇒ Φf (e) = Φf (i) , поскольку U инвариантно. 2 Обратившись теперь к понятию наследственной вычислимой перечислимости, опять получаем два различных определения равномерности. ОПРЕДЕЛЕНИЕ 3.4. Пусть A — вычислимая структура, M0 , M1 , . . . — вычислимая нумерация всех частично вычислимых структур в языке A, U — инвариантное k-местное отношение на A, и W0 , W1 , . . . — стандартная нумерация всех в.п. множеств кортежей длины k. Отношение U является слабо равномерно наследственно в.п., если существует всюду определенная вычислимая f такая, что Me ∼ = A ⇒ Wf (e) = U Me ; равномерно наследственно в.п., если существует в.п. оператор W такой, что Me ∼ = A ⇒ W (Me ) = U Me ; (слабо) равномерно наследственно в.п. с параметрами, если существует конечное число элементов a0 , . . . , an ∈ |A| таких, что U является (слабо) равномерно наследственно в.п. отношением на (A, a0 , . . . , an ). Венцов [12] изучал равномерную наследственную вычислимую перечислимость (с параметрами), он же [13] исследовал понятие, подобное слабой равномерной наследственной вычислимой перечислимости (с параметрами). Конечное отношение не обязано быть слабо равномерно наследственно в.п. (хотя оно, конечно, всегда будет равномерно наследственно вычислимым с параметрами). Примером такого отношения служит одноместное отношение на ω с функцией следования, которое истинно только в 0. Из теоремы 3.3 вытекает СЛЕДСТВИЕ 3.5. Пусть U — отношение на вычислимой структуре A. Эквивалентны следующие условия: 1) U равномерно наследственно вычислимо (с параметрами); 2) U и его дополнение слабо равномерно наследственно в.п. (с параметрами);

586

Р. Доуни, Д. Хиршвельд, Б. Хусаинов 3) U и его дополнение равномерно наследственно в.п. (с параметра-

ми). Как и в случае вычислимой категоричности, операторное определение равномерности соответствует усиленной равномерности, основанной на индексах. ТЕОРЕМА 3.6. Пусть A — вычислимая структура, M0 , M1 , . . . — вычислимая нумерация всех частично вычислимых структур в языке A, U — инвариантное k-местное отношение на A, и Φ0 , Φ1 , . . . — стандартная нумерация всех (k + 1)-местных частично вычислимых функций. Если существует всюду определенная f такая, что Me ∼ = A ⇒ ⇒ (Φf (e) всюду определена ∧ {~x | ∃n(Φf (e) (~x, n) = 1)} = U Me ) и Me = = Mi ∼ = A ⇒ Φf (e) = Φf (i) , то U равномерно наследственно в.п. ДОКАЗАТЕЛЬСТВО проводится так, как и в теореме 2.2. Вместо двухместной функции g строится (k + 2)-местная функция g, заданная определяющими структурами Mg~x,n (i) , где g~x,n ≡ λy(g(~x, n, y)). Чтобы перечислить W (M ), ищем ~x, n, i и s такие, что Φf (g~x,n (i)) (~x, n)[s] ↓ = 1 и Mg~x,n (i) [s] = M ↾ Mg~x,n (i) [s] . Как только они будут найдены, перечисляем ~x в W (M ).

Как и раньше, можно показать, что если Me ∼ = A, то для любых ~x и n существуют i и s, для которых Φf (g~x,n (i)) (~x, n)[s] ↓ и Mg~x,n (i) [s] = M ↾ Mg~x,n (i) [s] , а для любого такого i выполняется Φf (g~x,n (i)) (~x, n) = Φe (~x, n). Поэтому W (Me ) = U Me . 2

В [12] доказано, что, как и в случае с равномерной вычислимой категоричностью, равномерная наследственная вычислимость и равномерная наследственная вычислимая перечислимость соответствуют естественным синтаксическим понятиям, которые впервые были сформулированы в [23]. Ниже приводится доказательство этого факта. ОПРЕДЕЛЕНИЕ 3.7. k-местное отношение U на вычислимой структуре A является формально в.п., если существует в.п. последовательность θ0 , θ1 , . . . экзистенциальных формул в языке A, расширенном конечным числом констант из A, такая, что для каждого ~x ∈ ω k выполняется

Равномерность в теории вычислимых структур U (~x) ⇔ A 

W

587

θn (~x). Отношение U на вычислимой структуре является

n∈ω

формально вычислимым, если оно само и его дополнение являются формально в.п. ТЕОРЕМА 3.8 [12]. Инвариантное отношение на вычислимой структуре является равномерно наследственно в.п. тогда и только тогда, когда оно является формально в.п. без параметров, и является равномерно наследственно в.п. с параметрами тогда и только тогда, когда оно является формально в.п. ДОКАЗАТЕЛЬСТВО. Достаточно рассмотреть первую часть. Н е о б х о д и м о с т ь. Пусть U — инвариантное отношение на вычислимой структуре A, k — его местность, M0 , M1 , . . . — вычислимая нумерация всех частично вычислимых структур в языке A. Если U равномерно наследственно в.п., то возьмем W , как в определении 3.4. Для каждого ~x ∈ |A|k ищем e(~x) такое, что Me(~x) являет k ся конечной подструктурой A, ~x ∈ Me(~x) ∩ W (Me(~x) ). Если оно найдено, что может произойти тогда и только тогда, когда ~x ∈ U , то пусть y0 , . . . , yn — элементы Me(~x) , отличные от элементов ~x, и δ(~x, y0 , . . . , yn ) — конъюнкция конечного числа элементов атомной диаграммы Me(~x) . Положим θ~x ≡ ∃y0 , . . . , yn δ(~x, y0 , . . . , yn ). Утверждается, что U (~y ) ⇔ A  

W

W

θ~x (~y ). Очевидно, U (~y ) ⇒ A 

~ x∈U

θ~x (~y ). С другой стороны, если A  θ~x (~y ), то существуют i и g, для

~ x∈U

которых g : A ∼ = Mi , g(~y ) = ~x и Me(~x) является подструктурой в Mi . Легко проверить, что ~x ∈ W (Me(~x) ) ⇒ ~x ∈ W (Mi ) ⇒ U Mi (~x) ⇒ U (~y ). Д о с т а т о ч н о с т ь. Как и в теореме 2.5, можно использовать стандартное доказательство. Предположим, что U формально в.п., это обеспечивается экзистенциальными формулами {θn | n ∈ ω}. Оператор W действует на структуре B следующим образом. По заданному ~x ∈ |B|k он ищет формулу θn такую, что B  θn (~x). Если она найдена, то W перечисляет ~x в W (B). Нетрудно видеть: если B ∼ = A, то W (B) = U B. 2 Из следствия 3.5 и теоремы 3.8 вытекает СЛЕДСТВИЕ 3.9. Инвариантное отношение на вычислимой структуре является равномерно наследственно вычислимым тогда и

588

Р. Доуни, Д. Хиршвельд, Б. Хусаинов

только тогда, когда оно формально вычислимо без параметров, и является равномерно наследственно вычислимым с параметрами тогда и только тогда, когда оно формально вычислимо. Можно определить естественные релятивизованные версии рассматриваемых понятий. ОПРЕДЕЛЕНИЕ 3.10. Пусть U — отношение на носителе структуры A. Оно является относительно наследственно вычислимым (соответственно в.п.) на A, если его образ в любом представлении A вычислим (соответственно в.п.) относительно степени представления. ТЕОРЕМА 3.11 [6, 7]. Отношение на структуре является относительно наследственно в.п. тогда и только тогда, когда оно является формально в.п. Собрав воедино теоремы 3.8, 3.11 и следствие 3.9, видно, что в данном контексте релятивизованный и операторный варианты равномерности (с параметрами) имеют один и тот же эффект. СЛЕДСТВИЕ 3.12. Инвариантное отношение на вычислимой структуре является равномерно наследственно в.п. с параметрами тогда и только тогда, когда оно является относительно наследственно в.п., и является равномерно наследственно вычислимым с параметрами тогда и только тогда, когда оно является относительно наследственно вычислимым. Как и в случае вычислимой категоричности, тот факт, что при доказательстве достаточности в теореме 3.8 не было необходимости требовать вычислимости структуры B, позволяет заключить, что релятивизация понятий равномерной наследственной вычислимости и равномерной наследственной вычислимой перечислимости не сделает их более сильными. СЛЕДСТВИЕ 3.13. Если инвариантное k-местное отношение U на носителе вычислимой структуры A является равномерно наследственно в.п., то существует в.п. оператор W , для которого при любом представлении B структуры A выполняется W (B) = U B. Если инвариантное k-местное отношение U на носителе вычисли-

Равномерность в теории вычислимых структур

589

мой структуры A является равномерно наследственно вычислимым, то существует частично вычислимый оператор Ψ такой, что для любого представления B структуры A выполняется Ψ(B) = U B. Следовало бы еще показать, что из наследственной вычислимости (слабой равномерной наследственной вычислимой перечислимости) не вытекает слабая равномерная наследственная вычислимая перечислимость с параметрами (равномерная наследственная вычислимая перечислимость с параметрами), но это уже сделано. В [24] построено отношение U на вычислимой структуре, которое наследственно вычислимо, но не является формально вычислимым. Вместе со следствиями 3.5 и 3.9, это приводит к тому, что U и его дополнение не могут быть слабо равномерно наследственно в.п. с параметрами. СЛЕДСТВИЕ 3.14. Существует отношение на вычислимой структуре, которое является наследственно вычислимым, но не является слабо равномерно наследственно в.п. с параметрами. В [25, теор. III] построено наследственно в.п. отношение на вычислимой структуре, не являющееся формально в.п. Нетрудно проверить, что это отношение, на самом деле, является слабо равномерно наследственно в.п. Вместе с теоремой 3.8 этот результат позволяет сделать вывод о том, что слабая равномерная наследственная вычислимая перечислимость и равномерная наследственная вычислимая перечислимость являются различными понятиями, это было также показано в [13] с использованием результата из [22]. СЛЕДСТВИЕ 3.15 [13]. Существует отношение на вычислимой структуре, которое слабо равномерно наследственно в.п., но не является равномерно наследственно в.п. с параметрами. Суммируя результаты данного параграфа, рассмотрим следующие утверждения об отношении U на вычислимой структуре. C: U наследственно вычислимо, CE: U наследственно в.п., UC: U равномерно наследственно вычислимо,

590

Р. Доуни, Д. Хиршвельд, Б. Хусаинов UCP: U равномерно наследственно вычислимо с параметрами, WUCE: U слабо равномерно наследственно в.п., WUCEP: U слабо равномерно наследственно в.п. с параметрами, UCE: U равномерно наследственно в.п., UCEP: U равномерно наследственно в.п. с параметрами, RC: U относительно наследственно вычислимо, RCE: U относительно наследственно в.п. Справедливы следующие импликации, причем никакие другие, ис-

ключая получающиеся по транзитивности, в общем случае не имеют места UC

⇒

⇓ UCE

⇔

RC

⇒

⇔

RCE

⇓

⇒

CE

C

⇓ ⇒

⇓ WUCE

UCP UCEP ⇓

⇒

WUCEP

§ 4. Заключительные замечания В добавление к вопросу 2.13 и открытым вопросам из [14], можно указать еще несколько направлений для проведения дальнейших исследований по равномерности в вычислимых структурах. Одно из них состоит в изучении других понятий, чьи равномерные аналоги могли бы быть интересными. Например, имеются ли естественные понятия равномерной вычислимой размерности? Даже в рамках того, что было здесь сделано, могут возникнуть дальнейшие интересные вопросы. Вместо рассмотрения равномерной вычислимой категоричности можно рассматривать равномерные аналоги C-категоричности для других классов степеней C (например, ∆02 -категоричность). Аналогично, можно рассмотреть равномерные аналоги наследственной принадлежности классу C отношений, отличных от вычислимых и в.п. отношений. В обоих случаях было бы хорошо иметь промежуточные понятия равномерности между основанными на индексах и операторными понятиями.

Равномерность в теории вычислимых структур

591

Две последние возможности состоят в исследовании дальнейших связей с вычислимостью второго типа, упомянутой перед теоремой 2.2, и в рассмотрении понятия равномерности, основанного на индексах, в общем контексте работы [14]. Авторы благодарят анонимного рецензента за предоставленные ценные библиографические ссылки.

ЛИТЕРАТУРА

1. R. G. Downey, Computability theory and linear orderings, in: Y. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel (eds.), Handbook of recursive mathematics (Stud. Logic Found. Math., 139), Amsterdam, Elsevier Science B.V., 1998, 823—976. 2. С. С. Гончаров, Проблема числа неавтоэквивалентных конструктивизаций, Алгебра и логика, 19, N 6 (1980), 621—639. 3. P. Cholak, S. Goncharov, B. Khoussainov, R. A. Shore, Computably categorical structures and expansions by constants, J. Symb. Log., 64, N 1 (1999), 13—37. 4. С. С. Гончаров, О числе неавтоэквивалентных конструктивизаций, Алгебра и логика, 16, N 3 (1977), 257—282. 5. T. Millar, Recursive categoricity and persistence, J. Symb. Log., 51, N 2 (1986), 430—434. 6. C. J. Ash, J. F. Knight, M. S. Manasse, T. A. Slaman, Generic copies of countable structures, Ann. Pure Appl. Logic, 42, N 3 (1989), 195—205. 7. J. Chisholm, Effective model theory vs. recursive model theory, J. Symb. Log., 55, N 3 (1990), 1168—1191. 8. C. F. D. McCoy, Finite computable dimension does not relativize, Arch. Math. Logic, 41, N 4 (2002), 309—320. 9. О. В. Кудинов, Автоустойчивая 1-разрешимая модель без вычислимого семейства Скотта ∃-формул, Алгебра и логика, 35, N 4 (1996), 458—467. 10. О. В. Кудинов, Некоторые свойства автоустойчивых моделей, Алгебра и логика, 35, N 6 (1996), 685—698.

592

Р. Доуни, Д. Хиршвельд, Б. Хусаинов

11. О. В. Кудинов, Проблема описания автоустойчивых моделей, Алгебра и логика, 36, N 1 (1997), 26—36. 12. Ю. Г. Венцов, Проблема эффективного выбора для отношений и сводимостей в классах конструктивных и позитивных моделей, Алгебра и логика, 31, N 2 (1992), 101—118. 13. Ю. Г. Венцов, Эффективные операции выбора на конструктивных и позитивных моделях, Алгебра и логика, 32, N 1 (1993), 45—53. 14. C. J. Ash, J. F. Knight, T. A. Slaman, Relatively recursive expansions. II, Fundam. Math., 142, N 2 (1993), 147—161. 15. R. I. Soare, Recursively enumerable sets and degrees (Perspect. Math. Logic), Heidelberg, Springer–Verlag, 1987. 16. W. Hodges, Model theory (Encycl. Math. Appl., 42), Cambridge, Cambridge University Press, 1993. 17. C. J. Ash, J. F. Knight, Relatively recursive expansions, Fundam. Math., 140, N 2 (1992), 137—155. 18. J. C. Shepherdson, J. Myhill, Effective operations on partial recursive functions, Z. Math. Logik Grundlag. Math., 1, N 4 (1955), 310—317. 19. G. Kreisel, D. Lacombe, J. R. Shoenfield, Partial recursive functionals and effective operations, in: A. Heyting (ed.), Constructivity in Mathematics: Proceedings of the Colloquium held at Amsterdam, 1957 (Stud. Logic Found. Math.), Amsterdam, North-Holland Publishing Co., 1959, 195—207. 20. H. Rogers, Jr., Theory of recursive functions and effective computability, 2nd ed., Cambridge, Mass., MIT Press, 1987. 21. B. Khoussainov, R. A. Shore, Computable isomorphisms, degree spectra of relations, and Scott families, Ann. Pure Appl. Logic, 93, N 1-3 (1998), 153—193. 22. В. В. Вьюгин, О дискретных классах рекурсивно перечислимых множеств, Алгебра и логика, 11, N 3 (1972), 243—256. 23. C. J. Ash, A. Nerode, Intrinsically recursive relations, in: J. N. Crossley (ed.), Aspects of effective algebra, Proc. conf., 1979, Monash Univ., Clayton, Aust., 1981, 26—41. 24. M. S. Manasse, Techniques and counterexamples in almost categorical recursive model theory, PhD Thesis, University of Wisconsin, Madison, 1982.

Равномерность в теории вычислимых структур

593

25. J. Chisholm, The complexity of intrinsically r.e. subsets of existentially decidable models, J. Symb. Log., 55, N 3 (1990), 1213—1232.

Адреса авторов:

Поступило 10 ноября 2000 г.

DOWNEY, Rod

HIRSCHFELDT, Denis,

School of Mathematical and

Department of Mathematics,

Computing Sciences,

University of Chicago,

Victoria University,

U.S.A.

Wellington,

e-mail: [email protected]

NEW ZEALAND. e-mail: [email protected] ХУСАИНОВ Бахадыр, Department of Computer Science, University of Auckland, Auckland, NEW ZEALAND. e-mail: [email protected]