Вычислимо отделимые модели

Аннотация

Приведены основополагающие результаты структурной теории вычислимо отделимых моделей и продемонстрированы приложения этой теории к решению некоторых актуальных вопросов теории эффективных линейных порядков и теоретической информатики.

Полный текст

ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ Базовые понятия, используемые в работе, содержатся в [1-4, 20-25]. Под словом модель понимается множество вместе с фиксированным семейством операций и отношений, заданных на этом множестве. Введенное академиком А. И. Мальцевым в [21] понятие нумерованной модели - одно из наиболее общих центральных понятий, возникших на стыке теории моделей и теории нумераций. В силу чрезвычайной общности класса всех нумерованных моделей изучение последних обычно проводится в предположениях наличия ограничений на алгоритмические сложности нумерационных эквивалентностей. В этом аспекте, в первую очередь, нужно отметить вычислимые и, в более общем случае, позитивные и негативные модели, теория которых представляет бурно развивающийся раздел современной математической логики. Проблемы существования и числа вычислимых нумераций (представлений) моделей стали уже классическими (Ю. Л. Ершов [3, 4], Ю. Л. Ершов, С. С. Гончаров [2]), а ослабление требований к алгоритмической сложности нумерационных эквивалентностей является одним из общепринятых способов расширения исследуемого класса нумерованных моделей. Другой путь ограничения исследуемого класса нумерованных моделей, который, в отличие от предыдущего, игнорирует сложность нумерационной эквивалентности, заключается в наложении эффективных условий типа отделимости. Идеи использования понятия отделимости в теории нумераций восходят к В. А. Успенскому [26, 27] и А. Нероуду [37] и развиваются в работах А. И. Мальцева [21] и Ю. Л. Ершова [3]. Классическим условием отделимости в теории алгоритмов является условие вычислимой отделимости. Синтез понятий модели и вычислимо отделимой нумерации образует понятие вычислимо отделимой модели. В работах [5-12] Н. Х. Касымова изучены наиболее общие эффективные, структурные и топологические свойства вычислимо отделимых алгебр и описаны важнейшие типы таких алгебр. Многие естественные и важные типы нумерованных алгебр оказались вычислимо отделимыми, в том числе - среди неочевидных - негативные алгебры, позитивные алгебры со счетными решетками конгруэнций, стандартно нумерованные конечнопорожденные и финитно-аппроксимируемые алгебры и ряд других. В предлагаемой работе демонстрируется возможность естественного обобщения основополагающих структурных результатов теории вычислимо отделимых алгебр на нумерованные модели. В различных по методам доказательства и звучанию результатах о нумерованных моделях из упомянутых выше классов имеется немало принципиальных общих моментов, причем справедливость весьма сильных свойств оказалась не зависящей от сложности нумерационной эквивалентности. Эти факты становятся прозрачными именно при обобщенном взгляде на ситуацию - с точки зрения теории вычислимо отделимых нумерованных моделей. На базе и в рамках этой теории решается ряд естественных вопросов, возникших в связи с работами А. И. Мальцева [21], В. Баура [28, 29], Д. Бергстры и Д. Такера [30], М. Броя и др. [31], С. Камина [34] в теории вычислимо представимых моделей и в теории абстрактных типов данных. Целесообразность изучения вычислимо отделимых нумерованных моделей обуславливается еще одним обстоятельством. Несмотря на обширность, класс этих моделей допускает вполне удовлетворительные, в тех или иных смыслах, описания. Для естественного класса отделимых нумерованных моделей справедливы только релятивизированные варианты основных утверждений. В связи с этим уместно отметить, что в теории нумерованных моделей роль и место вычислимо отделимых нумерованных моделей - с точки зрения сложности отделяющих множеств, подобны роли и месту вычислимых моделей - с точки зрения сложности нумерационной эквивалентности. Понятие нумерованной модели является естественным обобщением понятия нумерованной алгебры. При изучении нумерованных моделей, так же, как в случае алгебр, налагаются ограничения на алгоритмические сложности нумерационных эквивалентностей, хотя здесь имеются принципиальные отличия. В данном обзоре изучается понятие вычислимо отделимой нумерованной модели, являющейся обобщением понятия вычислимо отделимой универсальной нумерованной алгебры, и приводятся основные факты о ее структурных свойствах. Неформально говоря, нумерованная модель вычислимо отделима, если каждая точка ложности любого основного отношения (включая равенство) имеет вычислимую окрестность, не пересекающуюся с областью истинности данного отношения. В работе также продемонстрирована возможность приложения результатов этой теории к решению некоторых принципиальных вопросов, возникших в смежных областях математической логики и теоретической информатики. Следуя академикам Ю. Л. Ершову и С. С. Гончарову [2-4], приведем ряд основных определений. Напомним, что всюду определенная функция из множества натуральных чисел ω в ω называется вычислимой, если существует вычисляющий ее алгоритм. Подмножество α ⊆ ω называется вычислимым (перечислимым, соответственно коперечислимым), если вычислима его характеристическая функция (α, соответственно ω '-. α - область значений некоторой вычислимой функции). Эти определения естественным образом переносятся на многоместные функции и отношения. Если ÷M; Σ) - счетная модель эффективной сигнатуры Σ, то ее нумерацией будем называть всякое такое отображение ν множества натуральных чисел ω на основное множество модели M, для которого существует эффективное семейство F вычислимых функций, представляющих Σоперации модели M в нумерации ν, т. е. всякая операция σ ∈ Σ представляется соответствующей ей такой вычислимой функцией f ∈ F, что ∀x σν(x)= νf (x). Заметим, что любая не более чем счетная модель эффективной сигнатуры имеет нумерацию (например, индуцированную геделевской нумерацией абсолютно свободной Σ-модели от счетного множества свободных порождающих, т. к. любая Σ-модель есть гомоморфный образ абсолютно свободной от подходящего числа свободных порождающих). Ядром нумерации ν модели M будем называть нумерационную эквивалентность {÷x, y)|νx = νy}. Если ν - нумерация, то через ker(ν) будем обозначать ее ядро. Будем говорить, что модель M представима над эквивалентностью η на множестве натуральных чисел ω, если существует нумерация ν модели M с ядром, равным η (т. е. ker(ν)= η). Характеристической трансверсалью эквивалентности η на ω (обозначаемой через tr(η)) называется множество всех натуральных чисел, являющихся наименьшими в содержащих их смежных η-классах, т. е. {x|x = y (mod η) → x � y}. Характеристической трансверсалью нумерации ν называется характеристическая трансверсаль ее ядра, т. е. tr(ker(ν)). Пусть (M ; ν) - нумерованная модель. Подмножество B основного множества модели M называется ν-вычислимым (ν-перечислимым, ν-коперечислимым), если вычислимо (перечислимо, соответственно коперечислимо) множество ν-1(B). Если из контекста будет ясно, какая нумерация имеется в виду, то подмножества основного множества модели будем называть просто вычислимыми (перечислимыми, коперечислимыми) без приставки ν. Если даны две нумерованные модели (M, μ) и (N, ν), то гомоморфизм ϕ из M в N называется морфизмом, если он эффективен на номерах, т. е. существует такая вычислимая функция g, что ϕμ = νg. Другими словами, мы рассматриваем только гомоморфизмы, эффективные на номерах, т. е. по любому μ-номеру любого элемента модели (M, μ) можно эффективно, с помощью функции g, вычислить некоторый ν-номер ϕ-образа этого элемента. Далее под гомоморфизмами нумерованных моделей мы понимаем их морфизмы, т. е. мы работаем в категории нумерованных моделей с морфизмами в качестве эффективных на номерах гомоморфизмов. Нумерованная модель, в которой все основные отношения (включая равенства) перечислимы (коперечислимы) на номерах, называется позитивной (негативной). Пусть (M, ν) - нумерованное множество. Подмножество A ⊆ ω называется ν-замкнутым, если оно является объединением подходящих смежных ker(ν)-классов, т. е. (x ∈ A ∧ νx = νy) → y ∈ A. Определение 1.1. Нумерованная модель (M, ν) называется вычислимо отделимой, если для всякого n-местного отношения P (включая равенство) модели M и любого такого кортежа натуральных чисел x ∈ ωn, что M |= P (νx), существует такое ν-замкнутое вычислимое множество A ⊆ ωn, что x ∈ A&∀a ∈ A(M |= P (νa)). Это определение является естественным обобщением определения вычислимо отделимой алгебры. Неформально говоря, вычислимая отделимость нумерованной модели означает, что каждая точка ложности любого предиката имеет вычислимую окрестность, не пересекающуюся с областью истинности данного предиката. С технической точки зрения удобнее следующее определение. Определение 1.2. Нумерованная модель (M, ν) называется вычислимо отделимой, если для всякого n-местного отношения P (включая равенство) модели M и любого такого кортежа натуральных чисел x ∈ ωn, что M |= P (νx), существуют такие ν-замкнутые вычислимые множества A1 ⊆ ω,..., An ⊆ ω, что x ∈ A1 × ... × An&∀a ∈ A1 × ... × An(M |= P (νa)). Предложение 1.1. Определения 1.1 и 1.2 эквивалентны. Доказательство. Достаточно показать, что из вычислимой отделимости модели по первому определению следует вычислимая отделимость модели по второму определению. Пусть A - вычислимое множество, отделяющее фиксированную точку ложности x = ÷x1,..., xn)∈ ωn n-местного отношения P от области истинности данного отношения. Рассмотрим следующую процедуру. Шаг 0: Положим Ai0 = {xi} для всех i = 1,n и B0 = ∅. Шаг e + 1: Берем первый кортеж z = ÷z1,..., zn) , не принадлежащий множеству A1e × ... × Ane ∪ Be при перечислении A. Если для всех i = 1,n выполняется условие A1e × ... × {zi}× ... × Ane ⊆ A, то полагаем В противном случае Конец шага e + 1. Положим Aie+1 = Aie ∪ {zi}, Be+1 = Be. Aie+1 = Aie, Be+1 = Be ∪ {z}. Ai = I Aie, B = I Be. e∈ω e∈ω Тогда A = A1 × ... × An ∪ B, и множества A1 × ... × An и B перечислимы. Поскольку A - вычислимое множество, то построенное множество вычислимо. По построению и из ν-замкнутости A следует ν-замкнутость A1 × ... × An. Отсюда вытекает, что Ai (для всех i = 1, n) является ν-вычислимыми множествами и x ∈ A1 × ... × An&∀a ∈ A1 × ... × An(M |= P (νa)). 2. КРИТЕРИЙ ВЫЧИСЛИМОЙ ОТДЕЛИМОСТИ Из результатов обзорной работы [14] вытекает исключительная важность негативных нумераций и негативных алгебр с точки зрения теории вычислимо отделимых нумерованных алгебр. Негативные модели играют аналогичную роль в характеризации вычислимо отделимых нумерованных моделей. Кроме того, понятие негативной модели является алгоритмически «двойственным» одному из важнейших понятий теории вычислимых моделей и теории абстрактных типов данных - понятию позитивной модели. Наконец, негативные нумерации и негативные модели сами по себе являются весьма естественным объектами. В данном разделе дается характеризация вычислимо отделимых нумерованных моделей в терминах их гомоморфизмов на негативные модели. Следующая теорема показывает, что негативные модели являются важными (и неочевидными) примерами вычислимо отделимых моделей. Теорема 2.1. Всякая негативная модель является вычислимо отделимой. Доказательство. Пусть (M, ν) - негативная модель. Обозначим через [ ]ν оператор ν-замыкания, т. е. [α]ν есть наименьшее ν-замкнутое множество, содержащее α. Будем говорить, что натуральное число z отвергается множеством α, если z ∈/ [α]ν. Пусть δ0,... δn,... - сильно перечислимая последовательность конечных множеств (т. е. по номеру n множества δn можно эффективно восстановить все элементы этого множества). Заметим, что в силу негативности ν отношение «z отвергается множеством δn» является перечислимым, равномерно зависящим от z и n. Допустим, что M |= P (νx). Построим множество A ⊆ ωn, определяемое следующей процедурой. Шаг 0: Полагаем α0 = {x}, β0 = ∅. Шаг e + 1: Выбираем первый кортеж z ∈ ωn (в некотором фиксированном перечислении всех кортежей длины n, например, заданном канторовской нумерационной функцией), не принадлежащий αe ∪ βe и начинаем проверять z на предмет отвержения каждым из этих множеств. Если z отвергается αe, то полагаем αe+1 = αe, βe+1 = βe ∪ {z}. Если z отвергается βe, то начинаем проверять, что условие P (νz) ложно. Если ответ «да», то полагаем αe+1 = αe ∪ {z}. Если это не так, то гарантированно через конечное число шагов z отвергнется αe, и в этом случае полагаем Конец шага e + 1. αe+1 = αe, βe+1 = βe ∪ {z}. Покажем, что каждый шаг e завершается с занесением текущего набора z в одно из множеств αe, βe. На шаге 0 имеем Пусть [α0]ν ∩ [β0]ν = ∅. [αe]ν ∩ [βe]ν = ∅, тогда любое z отвергается хотя бы одним из множеств αe, βe. Если z отвергается βe, то либо M |= P (νz), либо z отвергается αe. Следовательно, множества αe и βe определены для всех e. Положим α = I αe, β = I βe. e;;;0 e;;;0 Поскольку z относится к одному из этих множеств, то α ∪ β = ωn. Из [αe]ν ∩ [βe]ν = ∅ для всех e, следует что α ∩ β = ∅. Остается проверить, что α (а значит, и β) является ν-замкнутым. Пусть u ∈ α и νu = νv. Если cu< cv (c - канторовская функция свертки), то для некоторого e имеем u ∈ αe и v ∈/ αe ∩ βe, тогда v не отвергается множеством α ни на каком шаге, а значит, v отвергается на некотором шаге e1 > e множеством βe1 и имеет место M |= P (νv), следовательно, v ∈ α. Если cu > cv, то v ∈ α, так как в противном случае u не отвергается βe ни на каком шаге, а значит, u отвергается αe, но тогда u ∈/ αe. Противоречие. Следовательно, α - ν-замкнутое вычислимое множество. Положим A = α. Тогда, по построению, x ∈ A и ∀a ∈ A(M |= P (νa)). Формулировке следующей теоремы предпошлем замечание алгебраического характера. Пусть A0, A1 - разбиение основного множества модели M на две непересекающиеся части. Рассмотрим множество Θ(A0, A1) всех конгруэнций функционального обеднения модели M, не «склеивающих» никакой элемент из A0 ни с каким элементом из A1. Тогда в Θ(A0, A1) имеется наибольший элемент. Обозначим эту конгруэнцию через Q∗(A0, A1). Теперь, если (M, ν) - нумерованная модель и ν-1A0 (а значит, и ν-1A1) вычислимо, то функциональное обеднение нумерованной фактор-модели (M/Q∗(A0, A1), ν∗), где через ν∗ обозначена естественная проекция ν по конгруэнции Q∗(A0, A1) (т. е. ν∗ = ν/Q∗(A0, A1)), является негативным (Н. Х. Касымов [13]). Теорема 2.2. Нумерованная модель (M, ν) является вычислимо отделимой тогда и только тогда, когда она аппроксимируется негативными моделями. Доказательство. Пусть (M, ν) - вычислимо отделимая модель и для некоторого x ∈ ωn и nместного отношения модели (M |= P (νx)). Тогда, по условию, существуют вычислимые множества A1 ⊆ ωn,..., A1 ⊆ ωn такие, что x ∈ A1 × ... × An ∧ ∀a ∈ A1 × ... × An(M |= P (νa)). i Рассмотрим негативные конгруэнции Q∗(Ai, Ai) (i = 1, n) функционального обеднения модели. Лемма 2.1. Пересечение вычислимого семейства S негативных конгруэнций является негативной конгруэнцией. Согласно этой лемме конгруэнция n i Q∗ = Q∗(Ai, Ai) i=1 является негативной конгруэнцией функционального обеднения модели (M, ν), не «склеивающей» никакой элемент из A1 × ... × An ни с каким элементом из его дополнения. Рассмотрим гомоморфизм ϕ : (M, ν) → (M/Q∗, ν∗) такой, что M/Q∗ |= P (ϕνa) ⇔ a ∈ A1 × ... × An, а остальные отношения (исключая равенство) полагаем тождественно истинными в (M/Q∗, ν∗). В силу вычислимости A1 × ... × An, P является негативным отношением, сохраняющим ложность в точке ϕνx. Обратно, пусть нумерованная модель (M, ν) аппроксимируется негативными моделями. Если для некоторого x ∈ ωn и n-местного отношения P имеет место (M |= P (νx)), то согласно условию, существует такая негативная модель (N, μ), гомоморфизм ϕ : (M, ν) → (N, μ) и вычислимая функция f, что N |= P (ϕνx) и ϕν = μf. По теореме 2.1 негативная модель (N, μ) вычислимо отделима. Следовательно, существует μзамкнутое вычислимое множество α, отделяющее fx от области истинности P, но тогда f -1α является ν-замкнутым вычислимым множеством, отделяющим x от области истинности отношения P. Эти теоремы подчеркивают исключительную роль негативных моделей с точки зрения структурной теории вычислимо отделимых нумерованных моделей. В некотором, уточняемом ниже, смысле, негативные модели приоритетнее позитивных. Например, всякое позитивное поле вычислимо, тогда как любое бесконечное вычислимо представимое поле имеет негативную невычислимую нумерацию (см. [35]). В этой же статье показано существование негативных невычислимых представлений следующих классических объектов: (а) стандартной модели арифметики ÷ω; S, +, ×); (б) вычислимо представимой абелевой группы без кручения; (в) бесконечного вычислимо представимого векторного пространства над конечным полем; (г) алгебры термов от эффективного множества порождающих. Заметим, что все позитивные представления указанных выше систем являются вычислимыми. Покажем, что негативность может иметь место при весьма общих ограничениях на свойства нумераций моделей. Определение 2.1. Нумерация называется T1-отделимой (T2-отделимой; T3-отделимой; T4отделимой), если для всякой пары натуральных чисел, различных по модулю ее нумерационной эквивалентности, найдется перечислимая окрестность первого числа, не содержащая второе, и перечислимая окрестность второго, не содержащая первое (найдутся непересекающиеся перечислимые окрестности этих чисел; для всякого элемента и замкнутого в эффективно порожденной топологии множества, не содержащего этот элемент, найдутся их непересекающиеся окрестности; для всякой пары непересекающихся замкнутых множеств найдутся их непересекающиеся окрестности). Обозначим через Km (0 � m � 4) класс пространств, гомеоморфных эффективно порожденным пространствам, для которых выполняется аксиома Tm-отделимости. Предложение 2.1. Km '-. Km+1 /= ∅ для m ∈ {0, 1}, K3 = K4. Для m =0 тривиальный пример дается связным двоеточием, т. к. если α - перечислимое невычислимое множество, то двухэлементное множество {α, ω '-. α} с естественной нумерацией, сопоставляющей каждому числу содержащее его множество, есть эффективно порожденное отделимое и не T1-отделимое пространство. Для m = 1 в [14] построен пример эффективно порожденного пространства, гомеоморфного счетно-бесконечному пространству Зарисского, т. к. непустыми вполне перечислимыми подмножествами в этом примере являются все коконечные множества и только они. Для m = 3 вопрос так же, как и для m = 0, тривиален, т. к. для счетных топологических пространств регулярность и нормальность равносильны (предполагается T1-отделимость). Для m =2 вопрос открыт. В случае вычислимо порожденных пространств ситуацию полностью описывает Предложение 2.2. Нумерация модели вычислимо отделима тогда и только тогда, когда вычислимо порожденное топологическое пространство совершенно нормально и вполне несвязно. Доказательство см. в [14]. В заключение раздела продемонстрируем возможность наличия тесных связей между отделимостью и негативностью на двух естественных примерах алгебр, всякие T2-отделимые (T1отделимые) нумерации которых негативны. Простейшей подпрямо неразложимой бесконечной алгеброй с артиновой решеткой конгруэнций является алгебра предшествования (ω; p), где ω - множество натуральных чисел, p(x + 1) = x, p(0) = 0. Предложение 2.3. Всякая T2-отделимая нумерация алгебры предшествования является негативной. Доказательство. Пусть ν - T2-отделимая нумерация алгебры предшествования P = (ω; p), η - нумерационная эквивалентность нумерации ν. На самом деле, доказательство можно провести в гораздо более слабых предположениях T2-отделимости элементов 0 и 1 алгебры P (т. е. p(0) = 0, p(1) = 0). Пусть α, β - такие η-замкнутые непересекающиеся перечислимые множества, что 0 ∈ να и 1 ∈ νβ. Тогда x /= y (ker η) ↔ ∃n ∈ ω[(pn(x) ∈ α ∧ pn(y) ∈ β) ∨ (pn(y) ∈ α ∧ pn(x) ∈ β)], где p0(z)= z. Заметим, что в доказательстве этого предложения не используются ни T2-отделимость нумерации ν (достаточно предположить T2-отделимость неподвижной точки и ее непосредственного последователя), ни теорема об аппроксимируемости эффективно отделимыми алгебрами из [16], ни теорема о вычислимости отделимой нумерации алгебры с артиновой решеткой конгруэнций (также из [16]), что дает повод для предположения возможности наблюдения аналогичных эффектов негативности в достаточно широких классах T2-отделимых нумерованных алгебр. Алгеброй Мальцева назовем алгебру, удовлетворяющую тождествам ϕ(x, x, z)= z, ϕ(x, z, z)= x, где ϕ - термальный многочлен в сигнатуре исходной алгебры (алгебра из конгруэнц-перестановочного многообразия). Рассмотрим алгебру M = (ω; f ), где z, x = y; f (x, y, z)= Очевидно, что M - алгебра Мальцева. x, x /= y. Предложение 2.4. Всякая T1-отделимая нумерация алгебры M является вычислимой. Доказательство. Пусть ν - T1-отделимая нумерация алгебры M, η - нумерационная эквивалентность нумерации ν. Так же, как и в случае предложения 2.3, доказательство можно провести при более слабых предположениях. Допустим, что имеется пара таких различных элементов a, b, что для подходящих η-замкнутых перечислимых множеств α, β имеем a ∈ να ∧ b ∈/ να и b ∈ νβ ∧ a ∈/ νβ. Докажем, что элемент α вполне вычислим. В самом деле, пусть νm = a и νn = b, тогда x = m (ker η) ↔ f (m, x, n) ∈ β. Заметим, что область значений одноместной вычислимой функции λx.f (m, x, n) с параметрами m, n есть m/η ∪ n/η и потому не пересекается с множеством α ∩ β. Если x /= m (ker η), то f (m, x, n) ∈ α, следовательно, приведенная процедура определения принадлежности классу m/η успешно и корректно завершается для каждого x ∈ ω, т. е. ν-1(a) вычислимо. Положим γ = ν-1(a). Покажем, что алгебра M простая. В самом деле, пусть a /= b, θ - ненулевая конгруэнция алгебры M, «склеивающая» пару элементов a, b, а z - произвольный элемент этой алгебры. Тогда f (a, b, z)= f (a, a, z) (ker θ) → a = z (ker θ). Поскольку M простая, то ν вычислима. Легко понять, что вычислимая отделяющая последовательность множеств, определяемых как эффективные прообразы вычислимого множества γ относительно множества всех трансляций, представляющих операции алгебры M в нумерации ν, является сильно вычислимой и потому η негативна. Очевидно, что x = y (ker η) ↔ ∃z[x /= z (ker η) ∧ f (x, y, z) /= x (ker η)], так как x /= y (ker η) → ∀z(f (x, y, z)= x (ker η)), x = y (ker η) → ∀z[z /= x (ker η) → (f (x, y, z) /= x (ker η)], и алгебра M, согласно сделанному выше замечанию, неодноэлементная. В силу негативности η правая часть вышеуказанной равносильности перечислима, т. е. η позитивна, а значит, и вычислима. Таким образом, в некоторых важных частных случаях, для известных типов алгебр, существование T1-отделимых (T2-отделимых) нумераций может являться достаточным условием их негативности. 3. РАВНОМЕРНОСТЬ С фундаментальным в теории алгоритмов принципом равномерности можно ознакомиться в монографиях [3, 24]. Если в определении вычислимой отделимости нумерованной модели потребовать наличие эффективного процесса, который для каждой точки ложности любого предиката «выдает» соответствующий алгоритм разрешения множества, содержащего данную точку и не пересекающегося с областью истинности данного предиката, то получим понятие равномерно вычислимо отделимой модели. Формально, дадим следующее Определение 3.1. Нумерованная модель (M, ν) называется равномерно вычислимо отделимой, если существует частичная вычислимая функция g(c(x), γ(P ), z), где c - канторовская функция свертки и γ(P ) - клиниевский индекс характеристической функции ν-прообраза предиката P, со следующим свойством: для всякого n-местного отношения P и любого такого набора натуральных чисел x ∈ ωn, что M |= P (νx), одноместная функция λz[g(c(x), γ(P ), z)] (λ - стандартное λ-обозначение) есть вычислимая характеристическая функция множества, являющегося сверткой ν-замкнутого вычислимого множества, отделяющего x от области истинности отношения ν-1P. Под перечислимым индексом негативной модели мы понимаем алгоритм, определяющий процедуру перечисления дополнения всех основных отношений. Пусть K - некоторый фиксированный класс негативно нумерованных моделей. Определение 3.2. Нумерованная модель (M, ν) называется равномерно аппроксимируемой Kмоделями, если существует алгоритм, значение которого на каждой паре ÷P, x) при M |= P (νx) определено и равно перечислимому индексу негативной K-модели, сохраняющей ложность P в естественном гомоморфном образе набора νx. Определение 3.3. Бескванторная формула вида A1 ∨ ... ∨ An → Φ, где Ai - атомарные, Φ - позитивная формулы, называется дизъюнктивно-импликативно-позитивной (ДИП-формулой). ДИП-формулами являются, в частности, позитивные формулы (при n = 0), конъюнкции отрицаний атомарных формул (при Φ= ∅), а также бескванторные части однопосылочных квазитождеств вида S → Φ (при n = 1). Универсальное замыкание ДИП-формулы называется универсальным ДИП-предложением. Негативные модели, опять-таки, образуют важный класс равномерно вычислимо отделимых моделей (см. [15]). Теорема 3.1. Для нумерованной модели (M, ν) равносильны следующие условия (см. [15]): 1. (M, ν) - равномерно вычислимо отделимая модель; 2. если Φ - перечислимое множество универсальных ДИП-предложений, реализующееся в M, то (M, ν) равномерно аппроксимируется негативными Φ-моделями. В формулировке этой теоремы нельзя заменить универсальные ДИП-предложения произвольными универсальными и экзистенциальными ДИП-предложениями, так же, как нельзя опустить условие равномерности. Следствие 3.1. Нумерованная модель равномерно вычислимо отделима тогда и только тогда, когда она равномерно аппроксимируется негативными моделями. Подмножество A ⊂ M называется слабо перечислимым, если существует такое перечислимое множество α ⊂ ω, что να = A. Используя предыдущие соображения, легко доказать следующий критерий негативности нумерованной модели. Теорема 3.2. Нумерованная модель негативна тогда и только тогда, когда она является равномерно вычислимо отделимой моделью со слабо перечислимыми дополнениями всех основных отношений. Следствие 3.2. Всякая негативная модель равномерно вычислимо отделима. Следующий результат из [13] имеет важные применения в теоретической информатике и теории нумерованных систем с условиями конечности, что будет показано ниже в разделе 5. Предложение 3.1. Существует конечно порожденная равномерно вычислимо отделимая позитивная модель с иммунной характеристической трансверсалью. Общий метод построения таких моделей приведен в [14]. 4. ВЫЧИСЛИМО ОТДЕЛИМЫЕ ЛИНЕЙНЫЕ ПОРЯДКИ 1. Представимость линейных порядков над эквивалентностями. Понятие линейно упорядоченного множества (далее - линейного порядка), являющееся фундаментальным математическим понятием, играет также важную роль в теории абстрактной вычислимости. Линейные порядки вместе с их вычислимыми представлениями являются классическими объектами исследования в теории вычислимых моделей. Имеется, по крайней мере, четыре причины, мотивационно обуславливающих целесообразность изучения негативных моделей вообще и негативных линейных порядков в частности. Во-первых, естественные расширения класса вычислимых линейных порядков - позитивные и алгоритмически двойственные к ним, т. е. негативные, также образуют важные классы линейных порядков, хотя бы потому, что вычислимость порядка равносильна его одновременной позитивности и негативности. Однако, больший приоритет в исследовании нумерованных структур отдается позитивным моделям, т. к. позитивные модели естественным образом возникают в различных областях математики и теоретической информатики (классический пример - перечислимо определенные свободные системы эффективно аксиоматизируемых квазимногообразий [20]). Априори могло казаться, что ситуация при сравнении понятий позитивных и негативных линейных порядков будет вполне симметричной. Тем не менее, с алгоритмической точки зрения, свойства позитивных и негативных порядков оказались не просто различными, но и, в определенном смысле, противоположными, что подтверждается результатами данной статьи. Так, например, еще в 1970 году L. Feiner в [32] указал позитивно представимый линейный порядок, не имеющий вычислимого представления, тогда как почти очевидно, что всякий негативно представимый линейный порядок имеет вычислимое представление. Во-вторых, особенно наглядно и выпукло различия между алгоритмическими свойствами позитивных и негативных линейных порядков проявляются в рамках понятия их представимости над заданными эквивалентностями. Так, существуют позитивные эквивалентности, над которыми позитивно не представимы никакие линейные порядки. Если же эквивалентность негативна и обладает бесконечным числом смежных классов, то над ней, как минимум, негативно представимы все типы изоморфизмов счетных плотных линейных порядков (и не только они!). Более того, существует позитивное представление естественного порядка рациональных чисел, в котором множество вычислимых сечений пусто [36]. Множество же вычислимых сечений любого негативного представления плотного линейного порядка оказалось не просто труднообозримым, но и эффективно неисчерпаемым (т. е. продуктивным в обычном алгоритмическом смысле). В этом же русле, связанном с представимостью порядка над эквивалентностью, лежит и ряд исследований по структурам степеней представимости моделей над эквивалентностями. В работе [33] были получены некоторые принципиальные результаты о строении структуры степеней позитивной представимости линейных порядков. Ответы на некоторые аналогичные вопросы для степеней негативной представимости оказались существенно иными и приводятся в настоящей статье. При этом, в настоящее время, вопросов, в т. ч. принципиальных, касающихся структуры степеней негативной представимости линейных порядков, больше, чем ответов. Например, существуют ли две несравнимые бесконечные степени негативной представимости линейных порядков? С точки зрения теоретической информатики именно понятие степени представимости может быть одним из возможных уточнений понятия реализуемости моделей данных над заданными эффективными универсумами. Отметим, что с точки зрения представимости алгебр над эквивалентностями класс негативных систем также оказался существенно богаче класса позитивных. К примеру, над любой негативной эквивалентностью представима конгруэнц-простая конечно-порожденная алгебра [13], в то время как существуют позитивные эквивалентности, над которыми представимы лишь тривиальнейшие алгебры [14] (т. е. все сигнатурные операции которых действуют на основном множестве как проектирующие или константы). Третий аспект мотивации изучения данного понятия связан с эффективной отделимостью как основой распознавания при функционировании сложных систем (заданных своими представлениями/нумерациями с теми или иными ограничениями алгебраическо-алгоритмического характера). Вычислимая отделимость любой пары смежных классов негативной эквивалентности впервые была отмечена академиком А. И. Мальцевым в [22]. В обзорной работе [14], в которой описаны основы теории вычислимо отделимых универсальных алгебр и их приложения в теоретической информатике, центральным результатом является теорема о равносильности свойств вычислимой отделимости нумерованной алгебры и ее аппроксимируемости негативными алгебрами, позволяющая развить структурную теорию таких алгебр и устанавливающая фундаментальную роль негативных алгебр в этой теории. Эффекты негативности часто возникают даже при довольно общих предположениях на свойства отделимости [16], что дает дополнительное обоснование целесообразности систематического изучения негативных систем наряду с позитивными. И, наконец, в-четвертых. Классический конструктивный анализ при рассмотрении вычислимых вещественных чисел аппелирует к множеству рациональных чисел как к базисному конструктивному универсуму, вместе с его естественным порядком (см., например, [25]). Вопрос о возможности существования более общих алгоритмических представлений этого базиса, в рамках которых можно получить основные факты конструктивного анализа, также приводит к негативным линейным порядкам, т. к. для позитивных плотных порядков (как было отмечено выше) возможны ситуации пустых семейств вычислимых сечений. Более того, бо´льшая часть классических методов построения вычислимых последовательностей в области рациональных чисел естественным образом переносится на любые негативные плотные линейные порядки, что позволяет развить для них основы элементарного конструктивного анализа (на языке вычислимых последовательностей или вычислимых дедекиндовых сечений). Терминологическое замечание. В прежней русскоязычной терминологии вычислимые модели назывались конструктивными, а вычислимо представимые - конструктивизируемыми. В современной западной литературе по теории абстрактной вычислимости под вычислимыми моделями обычно понимаются системы с вычислимыми носителями (алгоритмически разрешимыми подмножествами ω), на которых заданы вычислимые операции и отношения, а под вычислимо представимыми - те, для которых существуют вычислимые копии, т. е. изоморфные системам с вычислимыми носителями, на которых заданы вычислимые операции и отношения. Мы будем придерживаться рамок ныне принятой терминологии, хотя, как отмечалось выше, понятие вычислимости имеет и другие, не менее важные, интерпретации (см. Ю. Л. Ершов [3]), что может создавать ощутимые неудобства в восприятии излагаемых фактов. Следуя сказанному, дадим следующее неформальное Определение 4.1. Нумерованное семейство объектов (⊆, ν) называется вычислимым, если существует равномерно эффективная процедура, транслирующая ν-номер любого ⊆-объекта в его (заранее оговоренные) алгоритмические свойства. Далее, исходя из необходимости, данное определение будет уточняться так, чтобы из контекста всегда было ясно, что мы вкладываем в понятие вычислимости. Так, к примеру, вычислимость (относительно нумерации μ) семейства � представляющих вычислимых функций нумерованной унарной алгебры (A, μ) означает существование такой нумерации γ семейства �, что для подходящей вычислимой функции f имеет место γ = χf (где χ - клиниевская нумерация унарных частично вычислимых функций). Определение 4.2. Если система имеет нумерацию, в которой все основные отношения (вклю- 0 0 чая равенство) являются ),(тт)-вычислимыми (а функции, представляющие операции, согласно n n 0 0 данному выше определению, автоматически вычислимы), то говорят, что данная модель ),(тт)n n представима. Как отмечалось выше, с понятием позитивной (негативной) представимости системы уместно (и, как оказалось, полезно) связать двойственное понятие представимости системы над эквивалентностью η над ω, подразумевая следующее 0 0 Определение 4.3. Система M называется ),(тт)-представимой над эквивалентностью η на n n 0 0 ω, если существует ),(тт)-нумерация системы M с нумерационной эквивалентностью, равной η. n n При этом, вообще говоря, в самом общем случае можно не предполагать, что ядро нумерации, 0 0 т. е. η, является ),(тт)-множеством. n n Замечание 4.1. С точки зрения представимости систем над эквивалентностью, «первичным» фиксированным понятием является эквивалентность (что порождает проблему описания общих свойств всех систем, представимых над заданной эквивалентностью), в то время как в рамках теории нумерованных систем основной объект есть сама система, по отношению к которой все ее нумерации «вторичны» (соответственно, в этом случае основная проблематика - описание свойств нумераций с теми или иными свойствами и соотношений между ними). Однако эти понятия двойственны, что мы и будем использовать в дальнейшем без каких-либо ограничений и оговорок, если из контекста будет явно вытекать то, что имеется в виду. Как обычно, сечением линейного порядка ÷L; -j_L) (к символу порядка, заданного на множестве, мы часто будем приписывать имя этого множества в качестве нижнего индекса, что позволит избежать возможных недоразумений) назовем такое разбиение основного множества этого порядка на два непустых непересекающихся множества A и B, что всякий элемент из A строго меньше (в смысле -j_L) всякого элемента из B. При этом множество A называется нижним классом сечения, а B - верхним классом. Существует три типа сечений: 1. в A есть наибольший элемент и в B есть наименьший (скачок); 2. в A есть наибольший элемент, а в B нет наименьшего, либо в A нет наибольшего, а в B есть наименьший (дедекиндово сечение); 3. в A нет наибольшего элемента и в B нет наименьшего (щель). В случае плотных порядков случай скачков не имеет места, что будет использоваться далее без напоминаний. Сечение A|B нумерованного линейного порядка ÷L, ν) называется вычислимым, если вычислимо множество всех ν-номеров нижнего класса сечения. Заметим, что в силу симметричности понятия вычислимости и непустоты обоих классов сечения, не имеет значения, брать ли нижний класс или верхний. Элемент a линейного порядка ÷L; -j_L) называется предельным снизу, если ∀x[x ≺L a → ∃y(x ≺L y ≺L a)], где ≺L обозначает «строго меньше». Аналогично определяется предельность сверху. Предельным называется элемент, предельный либо снизу, либо сверху. Если элемент пределен как сверху, так и снизу, то мы будем называть его двухсторонне предельным. Пусть η - произвольная (не обязательно негативная или позитивная) бесконечная эквивалентность на ω. Предельный снизу элемент n/η представимого над η линейного порядка ÷ω/η; -j_η ) называется эффективно предельным снизу, если существует такая вычислимая последовательность x0, x1,... натуральных чисел, что x0/η ≺η x1/η ≺η ··· ≺ n/η, ∀z[z/η ≺η n/η → ∃i ∈ ω(z/η ≺η xi/η)], где ≺η =-j_η '-.id ω/η. Аналогично определяется эффективно предельный сверху элемент. Данное в предыдущем подразделе определение позитивного (негативного) линейного порядка можно обобщить, имея в виду произвольные нумерационные эквивалентности. Определение 4.4. Линейный порядок ÷L; -j_L) называется негативно (позитивно) представимым над эквивалентностью η на ω, если существует такая его нумерация ν, что η = {÷x, y)| νx = νy} и множество {÷x, y)| νx -j_L νy} является коперечислимым (соответственно перечислимым). Далее, во избежание перегрузки текста термином «представимый», будем без оговорок использовать как его синонимы прилагательные «определимый» и «реализуемый». Предложение 4.1. Негативный (позитивный) линейный порядок с позитивной (соответственно, негативной) нумерационной эквивалентностью является вычислимым. Доказательство см. в [17]. Таким образом, для рассмотрения собственных расширений класса линейных порядков, обладающих вычислимыми представлениями, имеет смысл изучение линейных порядков, негативно (позитивно) представимых над негативными же (соответственно позитивными) эквивалентностями, т. к. другие комбинации дают вычислимые порядки. Далее через ÷Q; -j_Q) будем обозначать множество рациональных чисел вместе с их естественным упорядочением типа τ. Отметим, что сами рациональные числа (точнее, их изображения) удобно считать их же номерами, сопоставляя каждому числу все его представления в виде пары целых чисел (числитель/знаменатель). Эквивалентно, можно выбрать любую геделевскую нумерацию всех пар целых чисел, отождествляя их с рациональными и считать основным множеством ω, на котором задается вычислимый линейный порядок. Детали мы опускаем. Очевидно, что для любого такого представления полученная модель будет вычислимой. Предложение 4.2. Существует позитивная эквивалентность, над которой не определим никакой линейный порядок. Доказательство также см. в [17]. Заметим, что любая позитивная (негативная) эквивалентность с конечным числом смежных классов является вычислимой, и порядковый тип всякого линейного порядка, эффективно реализуемого над ней, с точностью до изоморфизма, есть начальный отрезок порядкового числа ω. Поэтому с точки зрения дескриптивной теории алгоритмов (т. е. принципиального наличия или отсутствия алгоритмов) интерес представляют лишь бесконечные эквивалентности. Известно, что всякий предельный элемент негативного линейного порядка является эффективно предельным, в то время как предельный элемент позитивного линейного порядка может не быть эффективно предельным и, более того, существует позитивная совершенная нумерация порядка рациональных чисел ÷Q; -j_Q), в которой никакой элемент не является эффективно предельным (см. [17]), т. е. в данном позитивном представлении порядкового типа τ множество вычислимых сечений пусто. Для любой же негативной нумерации порядка типа τ семейство вычислимых сечений, как будет показано далее, трудно обозримо. Можно показать, что всякий не двухсторонне предельный элемент негативного линейного порядка является рубежом подходящего вычислимого дедекиндова сечения, в то время как для двухсторонне предельных это не так. Следующая теорема из [17] вместе с предыдущим предложением обосновывает целесообразность рассмотрения именно негативных линейных порядков как наиболее широкого и естественного класса моделей, в котором можно развить теорию эффективных предельных переходов. Эти же факты в определенном смысле обуславливают приоритетность негативных порядков перед позитивными, хотя, традиционно считалось, что позитивные модели гораздо важнее негативных. Теорема 4.1. Над всякой бесконечной негативной эквивалентностью негативно представимы все типы изоморфизмов счетных плотных линейных порядков. Автоморфизм нумерованной системы называется вычислимым, если он поддерживается вычислимой на номерах функцией, т. е. если M - модель, α - ее автоморфизм, а ν - нумерация модели M, то α называется вычислимым (точнее, ν-вычислимым), если существует такая вычислимая функция f, что αν = νf. Очевидно, что вычислимые автоморфизмы любой нумерованной модели образуют полугруппу. Легко также понять, что множество вычислимых автоморфизмов любой позитивной модели есть группа. В [19] доказана следующая теорема. Теорема 4.2. Существует негативный линейный порядок, полугруппа вычислимых автоморфизмов которой не является группой. Более того, можно указать негативный линейный порядок с бесконечной полугруппой вычислимых автоморфизмов, среди которых единственным вычислимо обратимым является тождественный. Обозначим η(β)= β2 ∪ id ω для любого β ⊆ ω. Оказалось, что в рамках эквивалентностей типа η(β) можно характеризовать линейные порядки, определимые над ними (см. [19]). Теорема 4.3. Пусть β - коперечислимое, но невычислимое множество, а ÷L; -j_) - произвольный линейный порядок. Тогда эквивалентны следующие условия: (a) ÷L; -j_) негативно представим над η(β); (б) ÷L; -j_) имеет вычислимое представление и обладает хотя бы одним предельным элементом. 2. Степени негативной представимости. Для негативной эквивалентности η обозначим через L(η) класс всех линейных порядков, негативно представимых над η. На множестве негативных эквивалентностей на ω введем следующее бинарное отношение "JNLO : η1 "JNLO η2 ⇔ L(η1) ⊆ L(η2). Очевидно, что "JNLO является предпорядком (т. е. рефлексивным и транзитивным отношением) на множестве всех негативных эквивалентностей на ω. Тогда его симметричное замыкание ≡NLO есть эквивалентность, факторизация по которой разбивает множество всех негативных эквивалентностей на ≡NLO -классы эквивалентности. Содержательно, ≡NLO -эквивалентность двух эквивалентностей означает совпадение представимых над ними классов порядковых типов. Если Π - семейство всех негативных эквивалентностей, то на Π/ ≡NLO действует частичный порядок, индуцированный предпорядком "JNLO, который мы будем обозначать так же (корректность этого очевидна). Частично упорядоченное множество ÷Π/ ≡NLO ; "JNLO ) будем называть структурой негативной представимости линейных порядков, а его элементы - степенями негативной представимости. Далее, если будет ясно, о чем идет речь, структуру негативной представимости линейных порядков будем называть просто структурой негативной представимости, а ее элементы - степенями. Для сокращения обозначений через d(η) будем обозначать степень эквивалентности η. Будем также говорить, что линейный порядок представим над заданной степенью, если он представим над некоторой (а значит, и над любой) эквивалентностью из этой степени. Строение структуры негативной представимости линейных порядков отражает алгоритмическую природу эквивалентностей с точки зрения предоставляемых возможностей для реализации над ними важных объектов, каковыми являются линейные порядки. Ясно, что чем "JNLO -выше расположена степень, тем больше реализационных возможностей она предоставляет. Такой подход может оказаться также полезным в рамках теоретической информатики. Отметим, что конечные негативные эквивалентности (которые в данном случае, очевидно, будут вычислимыми) порождают изолированные степени в структуре негативной представимости, т. к. если число классов эквивалентности есть n, то над ней представим только порядковый тип, изоморфный конечному ординалу n. Отбросив все ≡NLO -классы, порожденные конечными эквивалентностями, получим ограничения отношений "JNLO, ≡NLO на бесконечные негативные эквивалентности. Всюду далее, структура негативной представимости рассматривается в контексте отсутствия степеней, содержащих конечные эквивалентности. Пусть Σ - множество бесконечных позитивных эквивалентностей, и отношение η1 "JP LO η2 на Σ означает, что всякий линейный порядок, позитивно представимый над η1, позитивно представим и над η2. Совершенно аналогично негативному случаю, путем симметричного замыкания предпорядка "JP LO и факторизации относительно полученного отношения эквивалентности на множестве всех бесконечных позитивных эквивалентностей, получим структуру позитивной представимости линейных порядков ÷Σ/ ≡P LO ; "JP LO ), которая оказалась совершенно отличной от структуры негативной представимости линейных порядков ÷Π/ ≡NLO ; "JNLO ). Так, в структуре позитивной представимости имеется бесконечная позитивная степень, над которой не определим никакой линейный порядок, в то время как над любой бесконечной негативной степенью представим плотный порядок. Из вышесказанного также следует, что существует наименьшая позитивная степень. Изучению основных свойств структуры ÷Σ/ ≡P LO ; "JP LO ) посвящена работа [33], в которой, в частности, показано, что эта структура не имеет наибольшего элемента, но имеет максимальный (им будет степень d(id ω)), существует бесконечно убывающая цепь позитивных степеней и имеются несравнимые степени (аналог теоремы Фридберга-Мучника). Некоторые принципиальные вопросы, рассмотренные в работе [33], являются в настоящий момент открытыми для структуры ÷Π/ ≡NLO ; "JNLO ). Вместо линейных порядков можно также рассматривать другие объекты, в т. ч. универсальные алгебры (не фиксируя сигнатуру), которые широко используются в абстрактных типах данных и объектно-ориентированном программировании. Так например, как уже отмечалось, над любой негативной эквивалентностью представима конечно-порожденная конгруэнц-простая алгебра (см. [13]), тогда как существуют позитивные эквивалентности, над которыми представимы только тривиальные структуры (см. [14]), заданные проектирующими функциями и функциямиконстантами, которые, очевидно, представимы над любой эквивалентностью. С другой стороны, разумные расширения класса рассматриваемых эквивалентностей также позволяют получать структуры с содержательными свойствами. Так, для эффективно отделимых эквивалентностей (которые содержат и негативные, и позитивные) показано, что они являются основой теории отделимых алгебр - отделимость нумерованной алгебры равносильна ее аппроксимируемости эффективно отделимыми, см. [16]. В этой же работе показаны примеры использования классических условий конечности с точки зрения представимости алгебр над эквивалентностями - для нумерованных алгебр с артиновыми решетками конгруэнций их отделимость равносильна эффективной отделимости. Цель настоящего подраздела - изучение простейших свойств структуры негативной представимости, а также роли и места плотных линейных порядков в этой структуре. Из сказанного выше вытекает важный факт: Предложение 4.3. Структура негативной представимости имеет наибольший элемент. Доказательство вытекает из того, почти очевидного, факта, что всякий негативно представимый линейный порядок имеет вычислимую нумерацию. Таким образом, всякий негативно представимый бесконечный линейный порядок представим над степенью d(id ω), которая и является наибольшей в структуре негативной представимости. Важно подчеркнуть (см. [32]), что наличие позитивного представления линейного порядка вовсе не влечет существование его вычислимого представления. По теореме 4.1 над всякой бесконечной негативной эквивалентностью представим плотный линейный порядок, по теореме 4.3 - существует негативная эквивалентность, над которой не представим порядок, имеющий непредельный элемент, что порождает естественный вопрос: «является ли структура негативной представимости бесконечной?». В [17] доказана следующая теорема. Теорема 4.4. Существует бесконечно убывающая цепь степеней негативной представимости линейных порядков. Через ω∗ обозначим тип линейного упорядочения, двойственный типу ω, т. е. изоморфный естественному порядку целых отрицательных чисел. Следствие 4.1. Структура бесконечных степеней негативной представимости линейных порядков содержит множество степеней, упорядоченное по типу 1+ ω∗. 3. Продуктивность негативных плотных порядков. Факт эффективной реализуемости плотных линейных порядков над любой бесконечной негативной эквивалентностью особо значим как на фоне предложения 4.2 о существовании бесконечных позитивных эквивалентностей, над которыми вовсе не представимы никакие линейные порядки, так и в свете следующего утверждения о существовании богатых семейств вычислимых сечений негативных плотных порядков. Теорема 4.5. Для любого негативного плотного линейного порядка существует эффективная процедура, сопоставляющая всякой паре различных элементов этого порядка вычислимую щель, отделяющую эти элементы. Доказательство в [17]. Таким образом, в негативных плотных линейных порядках для любой пары различных элементов отделяющая их вычислимая щель не просто существует, но, более того, разрешающий алгоритм соответствующей щели дается равномерно эффективной процедурой по данной паре элементов. Дадим точное определение вычислимого семейства вычислимых сечений негативного линейного порядка. Пусть χ - фиксированная вычислимая нумерация семейства всех одноместных частично вычислимых функций. Например, если k - бинарная клиниевская функция, универсальная для класса унарных частично вычислимых функций (т. е. семейство одноместных частично вычислимых функций есть множество объектов {λx.k(x, n)|n ∈ ω}), то можно положить χ(n)= λx.k(x, n). Следующие определения содержат неизбежные коллизии, возникающие при различных толкованиях вездесущего прилагательного «вычислимый», о чем было упомянуто выше. Определение 4.5. Нумерация γ семейства вычислимых сечений ⊆ негативного линейного порядка называется вычислимой, если существует такая вычислимая функция f, что γ = χf (т. е. по любому γ-номеру сечения эффективно определяется некоторый его χ-номер, являющийся индексом характеристической функции нижнего класса данного сечения). Семейство вычислимых сечений негативного линейного порядка называется вычислимым, если существует его вычислимая нумерация. Неформально, вычислимость семейства вычислимых сечений означает перечислимость алгоритмов разрешения для сечений данного семейства. Назовем семейство вычислимых щелей негативного линейного порядка относительно полным, если любая пара различных элементов этого порядка отделяется подходящей щелью из данного семейства. Следствие 4.2. Для всякого негативного плотного линейного порядка существует вычислимая (даже негативная) нумерация относительно полного семейства вычислимых щелей. Множество всех пар различных по модулю негативной эквивалентности натуральных чисел перечислимо. Сопоставляя каждой такой паре индекс характеристической функции нижнего класса, отделяющей их щели, получим искомую вычислимую нумерацию. В действительности, всякая такая вычислимая нумерация будет негативной, т. к. для двух различных сечений гарантированно найдется элемент, принадлежащий верхнему классу для одного из этих сечений и нижнему классу - для другого. Детали мы опускаем. Определение 4.6. Вычислимым пополнением негативного плотного линейного порядка называется множество всех вычислимых щелей (индексов вычислимых характеристических функций их нижних классов) данного порядка. Ниже будет показано, что вышеупомянутая относительно полная система отделяющих вычислимых щелей негативного плотного линейного порядка далеко не исчерпывает всего разнообразия вычислимых сечений, что обосновывает введение данного определения. Обратим внимание на два обстоятельства, связанные с этим определением. Во-первых, сечения, рубежами которых являются элементы самого порядка (т. е. дедекиндовы сечения), определены неоднозначно (элемент может быть как наибольшим в нижнем классе, так и наименьшим в верхнем). Во-вторых (и это - главное!), ни одно из двух дедекиндовых сечений, рубежами которых являются элементы порядка, вообще говоря, не обязано быть вычислимым. Иными словами, в множестве всех вычислимых сечений негативного порядка могут не оказаться сами элементы порядка в качестве пределов подходящих вычислимых последовательностей. Поэтому мы определяем вычислимые пополнения именно как щели. Впрочем, для задачи эффективного сравнения рубежей дедекиндовых сечений и щелей эти факты не являются препятствием, поскольку для различных рубежей вычислимых сечений (неважно, дедекиндовых или щелей) всегда эффективно найдется пара различных элементов линейного порядка, отделяющих эти рубежи. Если элемент негативного порядка не является двухсторонне предельным, то он есть рубеж вычислимого сечения. В самом деле, пусть ÷ω/η; -j_η ) - негативный линейный порядок и его элемент m/η (смежный η-класс, содержащий число m) не пределен, скажем, справа. Тогда существует элемент n/η, расположенный непосредственно над m/η (т. е. строго между m/η и n/η нет других элементов). Следовательно, множества A = {x|x -j_η m} (= {x|x ≺η n}) и B = {x|n -j_η x} (= {x|m ≺η x}) - перечислимые (а значит, и вычислимые, т. к. A и B - непересекающиеся, объединение которых есть ω), первое из которых определяет нижний класс дедекндова сечения A|B, а второе - верхний. При этом, элемент m/η является наибольшим в нижнем классе. Аналогично доказывается случай, когда m/η не пределен слева (тогда m/η оказывается наименьшим в верхнем классе). Приведем простейший пример негативной нумерации порядкового типа ω +1+ ω∗, в которой для единственного предельного (как снизу, так и сверху) элемента нет вычислимого сечения, рубежом которого он является. Пусть α, β - вычислимо перечислимые невычислимые множества, объединение которых невычислимо (существование таких множеств вытекает, например, из теоремы Фридберга о разложении) и a0, a1,... ; b0, b1,... - эффективные пересчеты без повторений множеств α и β соответственно. Положим γ = ω '-. (α ∪ β) и рассмотрим эквивалентность η(γ)= γ2 ∪ id ω, которая, очевидно, негативна. Единственным неодноэлементным смежным классом по этой эквивалентности является множество γ, которое и будет определять предельный элемент. Определим следующий линейный порядок -j_ над η(γ) (т. е. на ω/η(γ)): a0/η ≺ a1/η ≺ ··· ≺ γ ≺ ··· ≺ b1/η ≺ b0/η, где через ≺ обозначен строгий порядок, т. е. ≺=-j_ '-.id ω/η(γ). Нетрудно заметить, что дополнение линейного порядка -j_ есть объединение двух множеств {÷x, ai)|i ∈ ω, x ∈ ω '-. {a0,..., ai}} ∪ {÷ai, aj )|i ∈ ω, j < i}, {÷bi, x)|i ∈ ω, x ∈ ω '-. {b0,..., bi}} ∪ {÷bj, bi)|i ∈ ω, j < i}, которые, очевидно, перечислимы, т. е. -j_ - действительно негативный линейный порядок на фактор-множестве ω/η(γ). Элемент γ негативного линейного порядка ÷ω/η(γ); -j_) является рубежом двух сечений. Покажем, что ни одно из них не может быть вычислимым. Если γ является наибольшим в нижнем классе, то верхний класс сечения есть множество β, которое невычислимо, поэтому невычислим и нижний класс. Аналогично рассматривается случай, когда γ - наименьший в верхнем классе. В связи с существованием относительно полной системы отделяющих вычислимых щелей, задаваемой равномерно эффективной процедурой, возникает естественный и принципиальный вопрос об алгоритмической природе совокупности всех вычислимых сечений негативного плотного линейного порядка. Определение 4.7. Семейство ⊆ вычислимых сечений нумерованного линейного порядка называется продуктивным, если существует эффективная процедура, позволяющая по каждому вычислимому подсемейству ⊆0 ⊆⊆ строить вычислимое сечение из ⊆ '-. ⊆0. Теорема 4.6. Семейство всех вычислимых сечений негативного плотного линейного порядка является продуктивным. Доказательство в [17]. Следствие 4.3. Множество всех вычислимых сечений произвольного негативного плотного линейного порядка не является вычислимым. 5. СПЕЦИФИКАЦИИ 1. Алгебраические спецификации. В теории спецификаций программ и эффективной реализуемости можно считать достаточно утвердившимся тезис о позитивной представимости любой модели данных. Семантика таких моделей должна адекватно определяться их синтаксическими описаниями, которые, очевидно, обязаны иметь однозначно определенную интерпретацию и механизмы генерирования фактов о свойствах моделей. Другими словами, языки описания по определению являются логическими. На сегодняшний день наиболее изученным и обладающим достаточно большой областью применимости является язык исчисления предикатов первого порядка и различные его фрагменты. Особенно часто применяемую на практике часть этого языка образуют универсальные хорновские предложения, на которых основаны языки логического программирования. Этот факт связан с двумя обстоятельствами: 1. всякое непротиворечивое эффективное множество универсальных хорновских предложений имеет позитивно представимую модель; 2. семантика этой модели заключена в устройстве инициальной модели данного множества предложений, которая всегда существует и, более того, существует алгоритм извлечения ее эффективной реализации из синтаксического описания. Эти факты являются классическими в математической логике, поэтому определение границ применимости данного языка, вопросы определимости моделей в классах их гомоморфных образов (инициальная семантика - строение свободной системы соответствующего ранга), а также о числе реализаций (эффективных, поскольку ничто другое нельзя считать реализацией в рамках идеологии Computer Science) являются основополагающими в этой парадигме программирования. Согласно этой парадигме алгоритм должен иметь не императивный, а декларативный характер, и решение задачи должно заключаться не в описании конкретных процедур достижения цели, а в формулировке желаемой цели, при предоставлении поиска реализующей процедуры самой машине (универсальному алгоритму), предпринимающему эти попытки, исходя из синтаксического материала описания модели данных. Вопросы о числе эффективных реализаций (с точностью до вычислимой эквивалентности) входят в число принципиальных вопросов теории вычислимо представимых моделей и теории спецификаций программ. Например, как заметил С. С. Гончаров, для классических аксиом Пеано, описывающих стандартную модель арифметики, эта стандартная модель является единственной (с точностью до изоморфизма) среди тех, которые имеют позитивные представления. Более того, для аксиоматики арифметики С. С. Гончарова [1], в которой определен естественный линейный порядок, единственной эффективно реализуемой моделью как в классе позитивно, так и негативно представимых является стандартная модель арифметики [15]. Вообще, любое непротиворечивое множество формул логики первого порядка, имеющее счетнобесконечную модель, как правило, имеет и массу других, в том числе элементарно эквивалентных, а также элементарно расширяемых счетных моделей. В рамках инициальной семантики, которую мы принимаем, разумно исключить различные расширения и сосредоточиться на гомоморфных образах. Можно принять в определении модели данных пункт, требующий порожденности сигнатурными константами, который автоматически выводит из класса реализаций те, которые нестандартны в данном смысле. В любом случае следует помнить, что говоря о единственности реализации, мы подразумеваем эту единственность для стандартной модели. Если (M, ν) - нумерованная модель, то через Mν, будем обозначать следующее обогащение модели M счетным множеством констант, каждая из которых не принадлежит сигнатуре модели M : νn = cn. Модель Mν будем называть стандартным ν-обогащением модели M. Далее нумерованная модель (M, ν) и обогащение Mν модели M будут отождествляться, поскольку в рассматриваемых нами случаях эти представления вычислимо эквивалентны. Определение 5.1. Спецификацией называется любое непротиворечивое перечислимое множество предложений логики первого порядка. Спецификация называется хорновской (универсальной, экзистенциальной, индуктивной и т. д.), если каждое предложение из предложение хорновское (соответственно универсальное, экзистенциальное, индуктивное и т. д.). В работах [30, 31, 34] был поставлен принципиальный вопрос: всякая ли модель данных имеет обогащение, обладающее конечной алгебраической спецификацией? Равносильно, всякая ли конечно-порожденная позитивно представимая модель имеет обогащение, являющееся свободной системой некоторого конечно-базируемого многообразия (квазимногообразия, позитивного класса и т. д.)? Из теоремы 3.1 и предложения 3.1 вытекает следующая теорема. Теорема 5.1. Существует конечно-порожденная позитивно представимая модель, никакое обогащение которой не является инициальной системой ни в каком конечно-базируемом многообразии (квазимногообразии, заданном однопосылочными квазитождествами, позитивном классе). Доказательство. В самом деле, упомянутый пример модели M обладает позитивной нумерацией μ с иммунной характеристической трансверсалью tr(ker(μ)). По условию (M, μ) равномерно аппроксимируется негативными моделями. Пусть ϕ : (M, μ) → (N, ν) - один из этих гомоморфизмов. Очевидно, tr(ker(ν)) ⊆ tr(ker(μ)), однако в силу негативности ν характеристическая трансверсаль tr(ker(ν)) перечислима, а значит, она конечна (т. к. tr(ker(μ)) иммунна). Следовательно, M финитно аппроксимируема моделями, в которых реализуется любое перечислимое множество ДИП-предложений, выполняющихся в M. Отсюда следует вычислимость M. Противоречие. Таким образом, выразительная мощность естественных фрагментов языка логики предикатов первого порядка с хорошими интерпретациями оказывается недостаточной для адекватного алгебраического описания класса всех моделей данных. 2. Универсальная спецификация с единственной эффективной реализацией. Пусть (M, ν) - позитивная модель, Φ - универсальная хорновская спецификация в сигнатуре модели M, реализующаяся в M. Тогда, очевидно, Φ реализуется и в Mν. Н. Х. Касымов показал в [14], что если Φ не реализуется ни в каком эффективном гомоморфном образе модели Mν, то ν - вычислимая нумерация. Другими словами, если (M, ν) - позитивная невычислимая модель и Φ - универсальная хорновская спецификация, реализующаяся в M, то в классе Φ-моделей содержатся собственные позитивно представимые гомоморфные образы M. Следовательно, никакую позитивную невычислимую модель нельзя выделить в классе ее собственных позитивных гомоморфных образов никакой универсальной хорновской спецификацией. Известно также, что никакую позитивную невычислимую модель нельзя выделить в классе ее собственных гомоморфных образов никакой универсальной спецификацией (см. [14]). Сказанное выше поставило проблему определения тонкой грани (если она существует) между выразительными возможностями универсальных хорновских и универсальных спецификаций в рамках проблемы определимости модели в классе ее гомоморфных образов (см. [14, проблема № 13]). Иначе говоря, можно ли в принципе выделить позитивную невычислимую модель в классе ее собственных эффективных гомоморфных образов подходящей универсальной спецификацией? Теорема 5.2. Существует позитивно представимая модель M, не обладающая вычислимыми представлениями, которая выделяется в классе своих собственных позитивно представимых гомоморфных образов подходящей универсальной спецификацией. Доказательство. Пусть A - простое не гиперпростое множество, d0, d1,... - сильная таблица для дополнения A, т. е. процедура построения каждого di по каноническим индексам вычислима (di не пересекается с dj для различных i, j, и для каждого i множество di содержит элемент из дополнения A). Можно считать, что семейство di покрывает весь натуральный ряд ω, каждое di имеет вид y + 1,y + 2,...,y + f (i), где вычислимая функция f определяет мощность множеств di, т. е. f (i)= card(di) для каждого i, и все числа из предыдущего (по номерам) множества меньше всех чисел из последующего. Кроме того, можно считать, что каждый член сильной таблицы содержит как минимум два элемента из дополнения A. Определим неформальную процедуру построения вычислимого дерева T на ω следующим образом. Обозначим d0 через {x1, x2,..., xf (0)}. Эти числа - единственные минимальные в T. Пусть 0 0 0 z0,..., zm - все максимальные в T элементы, построенные на предыдущем шаге, расположенные в порядке возрастания как натуральные числа, k - номер множества из сильной таблицы, содержащего число zm + 1. Определим T (z0, x) для всех x из dk, T (z1, x) для всех x из dk+1, ..., T (zm, x) для всех x из dk+m. Рефлексивное и транзитивное замыкание данного множества завершает процедуру. По построению, если T (x, y)&T (x, z)&T (y, u)&T (z, u), то T (y, z) ∨ T (z, y), т. е. T - дерево. Очевидно, оно вычислимо. Теперь определим множество B как совокупность {x|x ∈ A ∨ ∃y ∈ A(T (y, x))}. Лемма 5.1. B - простое не гиперпростое множество. Доказательство. В d0 есть элемент из дополнения A. Над ним (в смысле частичного порядка, определяющего дерево T ) есть минимум два элемента из дополнения A. Рассуждая таким же образом далее, получим континуум ветвей, целиком лежащих в дополнении B. Следовательно, B - перечислимое расширение простого множества A с бесконечным дополнением, т. е. оно простое. Не гиперпростота следует из построения, для которого на каждом шаге явно строится множество, заведомо содержащее числа из дополнения B. Зафиксируем разбиение B на две непересекающиеся бесконечные части P и Q. Построим модель M = (ω; P, Q, C), где P, Q определены выше, а интерпретация I множества C = {c0, c1,.. .} определяется стандартным образом: I(cn) = n. Пусть w1, w2,... - сильная таблица для дополнения B из построения, т. е. в терминах нашего построения на шаге n конечное множество wn есть объединение dk , dk+1, . . . , dk+m. Определим следующее множество Φ универсальных предложений: 1. ∀x∀y((P (x) ∨ Q(x))&T (x, y)) → (P (y) ∨ Q(y)); 2. ci /= cj для всех различных i, j; 3. ∀x((P (x) → Q(x))&(Q(x) → P (x))). Очевидно, Φ реализуется в M. Лемма 5.2. Модель M имеет континуум гомоморфных образов, реализующих Φ, и всякий собственный Φ-образ модели M содержит бесконечное расширение либо отношения P, либо отношения Q. Доказательство. Любая ветвь (максимальное линейно упорядоченное подмножество) дерева T, не пересекающаяся с B, может быть континуумом способов разбита на две части, одна из которых расширяет P, а другая Q. Для доказательства второй части леммы заметим, что всякое собственное расширение отношения P (или Q) содержит элемент из дополнения B (назовем его g), над которым, опять-таки, есть элемент из дополнения B и т. д. Универсальное предложение 1 гарантирует вовлеченность всех элементов над g в процесс расширения хотя бы одного из отношений - P либо Q. Таким образом, любая собственная Φ-реализация модели M содержит бесконечное расширение хотя бы одного из двух основных отношений. Для завершения доказательства теоремы покажем, что можно выбрать P и Q так, чтобы они реализовали поставленную перед нами цель. Лемма 5.3. Существует такое разложение множества В на две перечислимые части P и Q, что всякое перечислимое расширение множества P (соответственно Q), не пересекающееся с Q (соответственно с P ) отличается от P (от Q) на конечное число элементов. Доказательство. Применим к множеству В классическую процедуру разложения Фридберга [24] любого перечислимого невычислимого множества на две перечислимые невычислимые части. Пусть это будут P и Q. Согласно построению Фридберга, любое перечислимое расширение множества P (соответственно Q), не пересекающееся с Q (соответственно с P ), отличается от P (от Q) на конечное число элементов. Предположим противное. Пусть, например, P I - бесконечное расширение P, не пересекающееся с Q. Тогда из построения Фридберга следует, что разность между P I и P перечислима. Но B, по лемме 5.1, простое, а значит, его дополнение иммунно. Противоречие. Аналогично рассматриваются и расширения Q. Таким образом, собственное расширение любого из отношений P или Q в модели M, реализующее Φ, согласно лемме 5.2 является бесконечным. По лемме 5.3 никакое из этих расширений не является перечислимым, т. е. все эти гомоморфные образы не имеют эффективных представлений. Уникальность модели из теоремы 5.2 демонстрирует следующий факт. Следствие 5.1. Существуют позитивно представимая модель M и ее универсальная спецификация Φ со следующими свойствами: 1. M не имеет вычислимого представления; 2. всякая позитивно представимая Φ-модель, построенная из констант, изоморфна M ; 3. M изоморфно вложима во всякую позитивно представимую Φ-модель. Заметим, что теорему 5.2 можно усилить. Следствие 5.2. Существует позитивно представимая модель, не обладающая вычислимыми представлениями, которая выделяется в классе своих собственных позитивно представимых гомоморфных образов подходящей бескванторной спецификацией. Очевидно, что такая спецификация не может быть хорновской. Таким образом, язык универсальных спецификаций оказывается существенно богаче языка универсальных хорновских предложений с точки зрения адекватного описания эффективно представимых моделей.