Отделимые алгоритмические представления классических систем и их приложения

Полный текст

ОГЛАВЛЕНИЕ 1. Предварительные сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707 2. Отделимые алгоритмические представления универсальных алгебр . . . . . . . . . . . . 711 3. Топологические нумерованные алгебры . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725 4. Отделимые представления групп, колец и тел . . . . . . . . . . . . . . . . . . . . . . . . 730 5. Логические спецификации и алгоритмические представления моделей данных . . . . . 735 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748 1. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ Базовые понятия, используемые в работе, содержатся в [1, 3-5, 49, 52, 54-58]. Под словосочетанием алгебраическая система будем понимать непустое множество вместе с фиксированным семейством конечноместных операций и отношений, заданных на нем. Иногда, для краткости, алгебраические системы будем называть моделями. Под словом алгебра будем понимать модель чисто функциональной сигнатуры. При этом язык алгебраической системы (т. е. список имен операций и отношений) называется сигнатурой. Стандартным приемом в математике является выделение класса алгебраических систем фиксированной сигнатуры путем определения некоторых простых законов, которым должны удовлетворять системы данного класса. Например, группы, кольца, поля, решетки и т. п. (см. [54]). Заметим, что в этих классах, как правило, есть некоторые «стандартные» представители, имеющие очень ясную алгоритмическую природу, т. е., фактически, упомянутые законы и задают алгоритмические реализации этих систем. К примеру, в любом конечно аксиоматизируемом квазимногообразии существуют свободные системы любого конечного ранга, которые обладают «хорошими» (в уточняемом далее смысле) алгоритмическими представлениями, строящимися в соответствии с некоторой единообразной эффективной процедурой, исходя из синтаксического материала, заключенного в самих аксиомах (см. [3, 5, 52, 54, 55]). Задание алгебраических систем порождающими и определяющими соотношениями также дает один из примеров такого подхода. Работа выполнена при финансовой поддержке фонда «Наследие академика Т. Н. Кары-Ниязова». © РОССИЙСКИЙ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ, 2021 Эта работа доступна по лицензии Creative Commons 4.0 International https://creativecommons.org/licenses/by-nc-nd/4.0/deed.ru 707 Аналогичный подход широко используется в теоретической информатике, когда по заданной спецификации (тексту программы в некотором необходимо логическом языке) нужно автоматически (без элементов креативности) построить некую стандартную модель, реализующую данную спецификацию, причем строительным материалом для этой модели служит сама спецификация, т. е. сигнатура и формальные математические законы (см., например, [2, 63, 64, 67]). Введенное академиком А.И. Мальцевым в [52] понятие нумерованной алгебры- одно из наиболее общих центральных понятий, возникших на стыке теории универсальных алгебр и теории нумераций. В силу чрезвычайной общности класса всех нумерованных алгебр изучение последних обычно проводится в предположениях наличия ограничений на алгоритмические сложности нумерационных эквивалентностей. В этом аспекте, в первую очередь, нужно отметить вычислимые и, в более общем случае, позитивные и негативные алгебры, теория которых представляет бурно развивающийся раздел современной математической логики. Проблемы существования и числа вычислимых нумераций (представлений) алгебраических систем стали уже классическими (С.С. Гончаров, Ю.Л. Ершов [3], Ю.Л. Ершов [4, 5]), а ослабление требований к алгоритмической сложности нумерационных эквивалентностей является одним из общепринятых способов расширения исследуемого класса нумерованных систем. Другой путь ограничения исследуемого класса нумерованных алгебр, который, в отличие от предыдущего, игнорирует сложность нумерационной эквивалентности, заключается в наложении эффективных условий типа отделимости. Идеи использования понятия отделимости в теории нумераций восходят к В.А. Успенскому [59, 60] и А. Нероуду [72] и развиваются в работах А.И. Мальцева [53] и Ю.Л. Ершова [4]. Классическим условием отделимости в теории алгоритмов является принцип вычислимой отделимости. Синтез понятий универсальной алгебры и вычислимо отделимой нумерации образует понятие вычислимо отделимой алгебры. В работах [6-25, 35-37, 47, 48] изучены наиболее общие эффективные, структурные и топологические свойства вычислимо отделимых алгебр и описаны их важнейшие типы. Многие естественные и важные типы нумерованных алгебр оказались вычислимо отделимыми, в том числе - среди неочевидных- негативные алгебры, позитивные алгебры со счетными решетками конгруэнций, стандартно нумерованные конечно порожденные и финитно аппроксимируемые алгебры и ряд других. В различных по методам доказательства и звучанию результатах о нумерованных алгебрах из упомянутых выше классов имеется немало принципиальных общих моментов, причем справедливость весьма сильных свойств оказалась не зависящей от сложности нумерационной эквивалентности. Эти факты становятся прозрачными именно при обобщенном взгляде на ситуацию - с точки зрения теории вычислимо отделимых нумерованных алгебр. На базе и в рамках этой теории решается ряд естественных вопросов, возникших в связи с работами А.И. Мальцева [52], В. Баура [61, 62], Д. Бергстры и Д. Такера [63], М. Броя и др. [64], С. Камина [67] в теории вычислимо представимых алгебр и в теоретической информатике. Целесообразность изучения вычислимо отделимых нумерованных алгебр обуславливается еще одним обстоятельством. Несмотря на обширность, класс этих алгебр допускает вполне удовлетворительные, в тех или иных смыслах, описания. Для естественного класса отделимых нумерованных алгебр справедливы только релятивизированные варианты основных утверждений. В связи с этим уместно отметить, что в теории нумерованных алгебр роль и место вычислимо отделимых нумерованных алгебр - с точки зрения сложности отделяющих множеств - подобны роли и месту вычислимых алгебр - с точки зрения сложности нумерационной эквивалентности. Более того, оказалось, что основные структурные теоремы, справедливые для универсальных алгебр, оказались верными и для их естественных обобщений- вычислимо отделимых алгебраических систем и моделей (см. [34, 38]). Однако более фундаментальным условием отделимости для универсальных алгебр является условие перечислимой отделимости (т. е. для всякой пары различных элементов нумерованной алгебры имеется перечислимое множество, содержащее в точности один из элементов данной пары), т. к., в определенном смысле, можно сказать, что теория алгоритмов как наука начинается с доказательства существования невычислимых перечислимых множеств. Понятие отделимой нумерованной универсальной алгебры является естественным обобщением понятия вычислимо отделимо нумерованной алгебры. В настоящем обзоре изучается понятие перечислимо отделимой нумерованной алгебры, являющейся обобщением понятия вычислимо отделимой универсальной нумерованной алгебры, и излагаются основные факты о структурных, алгоритмических и топологических свойствах отделимо нумерованных алгебр. Рассматриваются вопросы строения классических отделимых систем (групп, колец, полей), а также демонстрируются возможности приложения результатов теории отделимо нумерованных алгебр к решению некоторых принципиальных вопросов, возникших в смежных областях математической логики и теоретической информатики. Мы предполагаем, что читатель хорошо знаком с основными определениями, касающимися вычислимых функций, а также вычислимых и перечислимых множеств (см., например, [55, 57, 58]). Следуя Ю.Л. Ершову и С.С. Гончарову [3-5], приведем ряд основных определений. Всюду далее под словом алгебра, если не оговорено противное, будем понимать произвольную универсальную алгебру эффективной сигнатуры, т. е. мы предполагаем зафиксированной некоторую естественную нумерацию сигнатуры, для которой число аргументов произвольного символа эффективно находится по его номеру в этой нумерации. Если- счетная алгебра эффективной сигнатуры Σ, то ее нумерацией называется всякое отображение ν множества натуральных чисел ω на основное множество алгебры A такое, что по любому номеру сигнатурной операции σ эффективно находится алгоритм для вычисления такой функции f, что ∀x (σν(x) = νf (x)). Заметим, что любая не более чем счетная алгебра эффективной сигнатуры имеет нумерацию (например, индуцированную геделевской нумерацией абсолютно свободной алгебры Σ-термов от счетного множества свободных порождающих, т. к. любая Σ-алгебра есть гомоморфный образ абсолютно свободной от подходящего вычислимого множества свободных порождающих). Стоит отметить, что в теории вычислимых моделей сегодня используется общее понятие нумерации, в котором отсутствует требование вычислимости сигнатурных операций на ν-номерах. В данной работе мы следуем первоначальному определению А.И. Мальцева из [52] и, таким образом, использованное нами определение является более узким. Ядром нумерации ν алгебры A будем называть нумерационную эквивалентность νy}. Если ν - нумерация, то ее ядро будем обозначать через ker(ν). Если η - фиксированная эквивалентность на ω, то всякую алгебру, обладающую нумерацией с ядром, равным η, будем называть η-алгеброй (или определимой над η). Иными словами, алгебра A определима над эквивалентностью η, если существует такая вычислимая алгебра , где F - вычислимое семейство вычислимых функций, что η является конгруэнцией алгебры и A изоморфна фактор-алгебре . Характеристической трансверсалью эквивалентности η на ω (обозначаемой через tr(η)) называется множество всех натуральных чисел, являющихся наименьшими в содержащих их смежных η-классах, т. е.. Характеристической трансверсалью нумерации ν называется характеристическая трансверсаль ее ядра, т. е. tr(ker(ν)). Эквивалентность с бесконечным (конечным) числом смежных классов будем называть бесконечной (соответственно, конечной). Пусть (A;ν) - нумерованная алгебра. Подмножество B основного множества алгебры A называется ν-вычислимым (ν-перечислимым, ν-коперечислимым), если вычислимо (перечислимо, соответственно, коперечислимо) множество ν-1(B). Если из контекста будет ясно, какая нумерация имеется в виду, то подмножества основного множества алгебры часто будем называть вычислимыми (перечислимыми, коперечислимыми), без приставки ν. Если даны две нумерованные алгебры (A,μ) и (B,ν), то гомоморфизм ϕ из A в B называется морфизмом, если он эффективен на номерах, т. е. существует такая вычислимая функция g, что ϕμ = νg. Другими словами, мы рассматриваем только гомоморфизмы, эффективно заданные на номерах, т. е. по любому μ-номеру любого элемента алгебры (A,μ) можно эффективно, с помощью функции g, вычислить некоторый ν-номер ϕ-образа этого элемента. Далее под гомоморфизмами нумерованных алгебр мы понимаем их морфизмы, т. е. мы работаем в категории нумерованных алгебр с морфизмами в качестве эффективных на номерах гомоморфизмов, что совершенно естественно с точки зрения дескриптивной теории вычислимости. Определение 1.1. Нумерованная алгебра с вычислимым (перечислимым, коперечислимым) ядром называется вычислимой (позитивной, негативной). Алгебра называется вычислимо (позитивно, негативно) представимой, если существует ее вычислимая (позитивная, негативная) нумерация. Согласно определению 1.1 вычислимая представимость алгебры равносильна либо ее конечности, либо ее изоморфности алгебре вида, где ω - множество натуральных чисел, а F - подходящее эффективно задаваемое семейство вычислимых функций. Для позитивных (негативных) нумерованных алгебр возникают их фактор-алгебры по соответствующим ядру нумерации конгруэнциям, и в этих случаях исходную алгебру, вообще говоря, уже нельзя свести к представлению, изоморфному алгебре вида. Замечание 1.1. Далее в тексте, когда это не вызывает недоразумений, мы часто будем пользоваться существительными «представление» и «реализация» как синонимами понятия «нумерация». В особенности это касается последнего раздела, т. к. более употребимое в теоретической информатике понятие алгоритмической реализации с математической точки зрения равносильно понятию представления (или нумерации). Это связано с тем, что в рамках информатики функция обычно трактуется интенсионально (т. е. как процесс, заданный алгоритмом или программой в некотором формальном языке), а с точки зрения математики- функция задается экстенсионально (если f - функция, то она полностью определена своим графиком, т. е. множеством упорядоченных пар ). Однако именно теория вычислимости объединяет в себе два подхода к фундаментальному понятию отображения, поскольку нумерации (алгоритмические представления) задаются соответствующими алгоритмами (интенсиональность), являясь одновременно актуально бесконечными объектами, воспринимаемыми наблюдателем как нечто целостное и априори заданное (экстенсиональность). Эта двойственность будет присутствовать во всех наших построениях. При этом мы не рассматриваем реализации с точки зрения их «практической эффективности» (хотя это крайне важная задача, она не входит в круг вопросов, изучаемых в предлагаемой статье), т. к. находимся в рамках дескриптивной теории алгоритмов, интересующейся принципиальными вопросами существования алгоритмов или их отсутствием, игнорируя при этом количественные характеристики «времени» и «памяти», необходимые для решения задачи. Пусть (M,ν) - нумерованное множество. Подмножество α ⊆ ω называется ν-замкнутым, если оно является объединением подходящих смежных ker(ν)-классов, т. е. (x ∈ α∧νx = νy) → y ∈ α). Если (A,μ),(B,ν) - две нумерованные алгебры, то будем говорить, что (A,μ) сводится к (B,ν) (в обозначениях ), если существует такой изоморфизм ϕ : A → B, который поддерживается подходящей вычислимой функцией f на номерах, т. е. ϕμ = νf. Заметим, что из сводимости вовсе не следует , т. к. обратный изоморфизм может и не поддерживаться на номерах вычислимой функцией (см., например, [42]). Множество всех нумераций фиксированной алгебры разбивается на классы эквивалентности ≈ (получающемуся эквивалентным замыканием предпорядка, индуцированного ). Алгебра A называется вычислимо (позитивно, негативно) устойчивой, если для любой пары ее вычислимых (позитивных, негативных) нумераций μ,ν имеет место (A,μ) ≈ (A,ν). Это определение является эффективным аналогом понятия единственности (с точностью до вычислимого изоморфизма) алгоритмического представления алгебры. Например, нетрудно заметить, что всякая конечно порожденная алгебра позитивно устойчива. Все приведенные выше определения естественным образом обобщаются для алгебраических систем (далее, для краткости, - моделей). Так, нумерованная модель (M,μ) эффективной сигнатуры Σ называется вычислимой (позитивной, негативной), если ее функциональное обеднение (т. е. сужение сигнатуры Σ = ΣF ∪ΣP до функциональной части ΣF) является таковым же и для всякого отношения p ∈ ΣP множество μ-номеров этого отношения (т. е. {x|μx ∈ p}), причем соответствующий алгоритм строится равномерно эффективно по имени (номеру) предикатного символа p. Напомним (см. [4, 55, 57, 58]), что Σ01 - класс перечислимых множеств в арифметической иерархии (проекции множеств, получающиеся путем навешивания кванторов существования на некоторые аргументы вычислимых отношений), а Π01 - класс коперечислимых множеств, являющихся дополнениями Σ01-множеств. Их пересечение есть в точности класс вычислимых множеств Δ01. Далее, исходя из непустоты разностей как , так и , строится иерархия, относительно определимости в которой полезно следующее весьма общее определение. Определение 1.2. Пусть η - эквивалентность на ω. Алгебраическая система M называется Δ0nопределимой над эквивалентностью η на ω (Σ0n-определимой над η, Π0n-определимой над η), если существует такая ее нумерация, в которой все основные отношения являются Δ0n-множествами (Σ0n-множествами, Π0n-множествами, соответственно). Заметим, что в данном определении алгоритмическая сложность эквивалентности η может быть какой угодно. Каждому нумерованному множеству (M,μ) естественным образом сопоставляется два топологических пространства, первое из которых определяется базой, состоящей из μ-замкнутых вычислимых подмножеств ω, а второе порождается μ-замкнутыми перечислимыми подмножествами. Заметим, что всякий гомоморфизм нумерованных алгебр непрерывен относительно обеих этих топологий, т. к. прообразы вполне вычислимых (вполне перечислимых) подмножеств являются таковыми же. Более того, все операции любой нумерованной алгебры, представляемые подходящими вычислимыми функциями в данной нумерации, также непрерывны относительно обеих топологий, причем этот факт не зависит от алгоритмической сложности сигнатуры алгебры (см. [46]). Для фиксированной нумерации ν будем называть первое их этих пространств ν-вычислимым и обозначать его через τcomp(ν), а второе- ν-перечислимым (в обозначениях τ(ν)). Очевидно, что вообще говоря, τ(ν)-топология сильнее τcomp(ν)-топологии (т. к. всякое вычислимое множество перечислимо) и, как было отмечено выше, перечислимая топология более фундаментальна с точки зрения абстрактной вычислимости. Определение 1.3. Нумерованная алгебра (A,ν) называется вычислимо отделимой, если всякая пара различных ее элементов отделяется подходящим ν-вычислимым множеством. Очевидно, что данный вид отделимости определяется базой открыто-замкнутых множеств, т. к. дополнения вычислимых множеств также вычислимы. Определение 1.4. Нумерованная алгебра (A,ν) называется отделимой, если всякая пара различных ее элементов отделяется подходящим ν-перечислимым множеством. Таким образом, отделимость для алгебры, заданной алгоритмическим представлением, мы отождествляем с наличием семейства перечисляющих алгоритмов (или, двойственно (см. замечание 1.1), множеств, перечисляемых этими алгоритмами), отделяющих все пары различных элементов данной алгебры. Этот, более общий, вид отделимости соответственно и задается более сложной топологией. Например, рассмотрим двухэлементное множество M = {a,b} и его нумерацию ν, которая отображает перечислимое невычислимое множество Имеем T0-отделимое пространство, гомеоморфное связному двоеточию. При вычислимом α все четыре подмножества двухэлементного множества M = {a,b} будут открыты. Максимальная разница в силах топологий, определенных вычислимо отделимыми и отделимыми нумерациями, наблюдается в следующем случае. Пусть η - совершенная эквивалентность, т. е. позитивная эквивалентность с бесконечным числом смежных классов, единственными η-замкнутыми вычислимыми множествами для которой являются ∅ и ω (массу примеров таких эквивалентностей можно найти в Ю.Л. Ершов [4]). Тогда вычислимая топология на фактор-множестве ω/η есть пространство слипшихся точек, а перечислимая топология- дискретна. 2. ОТДЕЛИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРЕДСТАВЛЕНИЯ УНИВЕРСАЛЬНЫХ АЛГЕБР В этом разделе будут рассмотрены наиболее общие алгоритмические, структурные и, частично, топологические свойства универсальных алгебр. 2.1. Вычислимо отделимые представления. Из результатов обзорной работы [25] вытекает важность негативных нумераций и негативных алгебр с точки зрения теории вычислимо отделимых нумерованных алгебр. Негативные модели играют аналогичную роль в характеризации вычислимо отделимых нумерованных моделей. Кроме того, понятие негативной модели является алгоритмически «двойственным» одному из важнейших понятий теории вычислимых моделей и теории абстрактных типов данных - понятию позитивной модели. Наконец, негативные нумерации и негативные модели сами по себе являются весьма естественными объектами. В данном подразделе дается характеризация вычислимо отделимых нумерованных моделей в терминах их гомоморфизмов на негативные модели. Следующая теорема показывает, что негативные модели являются важными (и неочевидными) примерами вычислимо отделимых моделей. Теорема 2.1. Нумерованная алгебра вычислимо отделима тогда и только тогда, когда она аппроксимируется негативными алгебрами. Доказательство см. в [17]. Оказалось, что эту теорему можно обобщить и для моделей. Если (A,ν) - нумерованная система, то n-местное отношение P на множестве A (т. е. P ⊆ An) называется ν-вычислимым (ν-перечислимым), если вычислим (перечислим) полный ν-прообраз этого отношения, т. е. множество. Определение 2.1. Нумерованная алгебраическая система (A,ν) называется вычислимо отделимой (отделимой), если всякая точка ложности любого основного отношения этой модели имеет ν-вычислимую (ν-перечислимую) окрестность, не пересекающуюся с областью истинности данного отношения. Напомним, что алгебраические системы, для краткости, мы называем моделями. Предложение 2.1. Нумерованная модель является вычислимо отделимой тогда и только тогда, когда она аппроксимируется негативными моделями. Доказательство см. в [34]. Теорема 2.1 и предложение 2.1 подчеркивают исключительную роль негативных моделей с точки зрения структурной теории вычислимо отделимых нумерованных моделей. Приведем некоторые следствия теоремы 2.1. Назовем эквивалентность на ω эффективно бесконечной, если существует инъективная вычислимая функция, значения которой на различных аргументах попарно различны по модулю этой эквивалентности. Соответственно, нумерация эффективно бесконечна, если таково ее ядро. Эквивалентность (нумерацию) с бесконечным числом смежных классов, не являющуюся эффективно бесконечной, будем называть неэффективно бесконечной. Фундаментальным понятием теории алгоритмов является понятие иммунного множества, которое можно назвать конечным с точки зрения возможности алгоритмического отслеживания его эффективных подмножеств: множество называется иммунным, если всякое его собственное перечислимое подмножество конечно (см. [55, 57, 58]). Усилением свойства иммунности является гипериммунность - такое свойство множества α, которое не позволяет отслеживать элементы α даже при наличии столь мощного инструмента, как перечислимая по каноническим индексам (т. е. имея алгоритм мы имеем в явном виде все конечное множество) последовательность попарно непересекающихся конечных множеств, в каждом из которых содержится элемент из α (см. также [55, 57, 58]). Очевидно, что из гипериммунности следует иммунность (иначе для бесконечного неиммунного множества можно было бы выделить его бесконечное перечислимое подмножество и для него определить упомянутую выше прослеживающую последовательность конечных множеств). Обратное неверно (см. [55, 57]). Пусть (A,ν) - неэффективно бесконечная алгебра. Легко заметить, что гипериммунность характеристической трансверсали ее ядра tr(ker(ν)) влечет неэффективную бесконечность ν, которой, в свою очередь, достаточно для иммунности tr(ker(ν)). Можно показать, что обратные включения не имеют места (см. [25]). Стандартной нумерацией назовем такую нумерацию алгебры, которая сводится к любой другой. Такие нумерации существуют, например, для конечно-порожденных алгебр конечных сигнатур (см. также [25]). Поэтому, говоря об алгоритмическом свойстве алгебры безотносительно нумерации, имеется в виду именно стандартная нумерация, являющаяся наименьшей в классе эквивалентных относительно упомянутой выше алгоритмической сводимости нумераций. Следствие 2.1. Стандартная нумерация конечно порожденной финитно аппроксимируемой алгебры является вычислимо отделимой. Следствие 2.2. Неэффективно бесконечная конечно порожденная алгебра вычислимо отделима тогда и только тогда, когда она финитно аппроксимируема. Предложение 2.2. Характеристическая трансверсаль негативной (позитивной) эквивалентности перечислима (соответственно, коперечислима). Доказательство. Пусть η - негативная эквивалентность на ω. Тогда z (mod η))). В силу перечислимости правой части указанной равносильности tr(η) перечислима. Если же η позитивна, то x /∈ tr(η) ⇔ ∃z(z < x ∧ z = x (mod η)). Из очевидной перечислимости правой части равносильности следует перечислимость, т. е. коперечислимость tr(η). Следствие 2.3. Всякая бесконечная вычислимо отделимая алгебра, конечно определенная в конечно базируемом многообразии, является эффективно бесконечной. Доказательство. В самом деле, если бы стандартная нумерация (существование которой в данном случае очевидно) такой алгебры была бы неэффективно бесконечной, то, в силу ее аппроксимируемости негативными алгебрами по теореме 2.1, а также наличия семейства конечных аппроксимирующих алгебр (в силу следствия 2.2), проблема равенства слов в ней была бы коперечислимой, т. е. она была бы негативной (даже вычислимой), что невозможно, т. к. характеристическая трансверсаль любой негативной нумерации согласно предложению 2.2 перечислима. Предложение 2.3. Существует конечно порожденная алгебра, стандартная нумерация которой вычислимо отделима, неэффективно бесконечна и позитивна. Доказательство см. в [8]. Следствие 2.4. Существует конечно порожденная позитивная алгебра, всякое позитивно представимое обогащение которой является финитно аппроксимируемым. Это следствие дает пример приложения теории вычислимо отделимых алгебр к теоретической информатике, т. к. оно решает проблему, сформулированную в [63, 64, 67] о существовании неявных эквациональных спецификаций для моделей данных (подробнее см. в последнем разделе). Ряд других неожиданных результатов теории вычислимо отделимых алгебр можно найти в упомянутом обзоре [25]. 2.2. Негативные аппроксимации. Нумерация ν семейства перечислимых множеств S называется вычислимой, если перечислимым является множество . Если (M,ν) - нумерованное множество, то подмножество M0 ⊆ M называется ν-перечислимым (ν-вычислимым), если перечислимым (вычислимым) является множество {x | νx ∈ M0} всех ν-номеров элементов множества M0. Как отмечалось выше, будем использовать термины перечислимый (вычислимый), имея в виду фиксированную нумерацию ν, если из контекста будет ясно, о чем идет речь. Последовательность A0,A1,... перечислимых множеств называется вычислимой, если перечислимым является множество. Эквивалентность η называется эффективно отделимой, если для нее существует вычислимая последовательность η-замкнутых перечислимых отделяющих множеств. Аналогично, нумерация называется эффективно отделимой, если таковой является ее нумерационная эквивалентность. Замечание 2.1. Поскольку одним из центральных понятий работы является понятие вычислимой (в смысле Ю.Л. Ершова) нумерации (т. е. вычислимой нумерации семейства вычислимо перечислимых множеств), то мы будем, по мере возможности, избегать чересчур частого применения прилагательного «вычислимый», предпочитая использовать эквивалентные ему прилагательные, понятные из контекста. Ранее в русскоязычной (и не только) литературе использовался вполне устоявшийся термин «рекурсивный» как синоним нынешнего «вычислимый». Мы принимаем компромиссное терминологическое решение. Например, словосочетание «вычислимая нумерация вычислимого семейства вычислимых множеств» в нашей интерпретации будет звучать приблизительно как «вычислимая нумерация эффективного семейства разрешимых множеств». Точно так же, вместо ныне общепринятого термина «вычислимо перечислимый» часто будем употреблять его сокращение «перечислимый», что позволит избежать терминологических недоразумений и режущих слух выражений. Определение 2.2. Нумерация ν семейства вычислимых множеств называется вполне вычислимой, если вычислимым является множество. Эквивалентность η назовем вполне отделимой, если для нее существует перечислимая по индексам характеристических функций последовательность R0,R1,... вычислимых отделяющих множеств. Неформально, вычислимость нумерации семейства перечислимых множеств равносильна наличию эффективной процедуры, которая по номеру вычислимо перечислимого множества перечисляет элементы данного множества. Вполне вычислимость же означает существование алгоритма, который по номеру вычислимого множества «выдает» алгоритм разрешения этого множества. Таким образом, если вычислимость подразумевает возможность перечисления семейства по вычислимо перечислимым индексам, то вполне вычислимость означает перечислимость данного семейства по индексам характеристических функций его элементов. В частности, если семейство перечислимых множеств содержит хотя бы одно невычислимое множество, то для него заведомо бессмысленна постановка вопроса о существовании вполне вычислимой нумерации. Одним из центральных результатов для эффективно отделимых нумераций является следующий (Ю.Л. Ершов, [4, гл. 1, §3, предложение 8, с. 60]): Теорема 2.2. Эквивалентность эффективно отделима тогда и только тогда, когда она является нумерационной эквивалентностью вычислимой нумерации подходящего семейства вычислимо перечислимых множеств. При этом нумерационные эквивалентности вычислимых нумераций не имеют четкой характеризации в арифметической иерархии Клини-Мостовского. Так, пусть E0 - класс эффективно отделимых эквивалентностей на ω. Тогда E0 содержит позитивные (из класса Σ01) и негативные (из класса Π01) эквивалентности и E0 ⊂ Π20. Однако для имеет место как , так и . Следующая теорема показывает, что для вполне вычислимых нумераций их нумерационные эквивалентности в точности совпадают с классом негативных эквивалентностей. Предложение 2.4. Для произвольной эквивалентности η на ω следующие условия равносильны: 1. η -нумерационная эквивалентность подходящей вполне вычислимой нумерации; 2. η негативна; 3. η вполне отделима. Доказательство. 1 ⇒ 2. Пусть ν - вполне вычислимая нумерация подходящего семейства вычислимых множеств и η - нумерационная эквивалентность нумерации ν. Тогда , где правая часть соотношения перечислима в силу равномерной вычислимости отношения p ∈ νq по p,q. 2 ⇒ 3. Пусть η - негативная эквивалентность. Еще А.И. Мальцевым в [52] отмечалась вычислимая отделимость любых двух различных η-классов негативной эквивалентности. В действительности, как показано в [17], отделяющие множества можно выбирать среди η-замкнутых, причем процедура предоставления характеристического индекса соответствующего множества равномерно зависит от пар чисел, различных по модулю η. Поэтому вычислимо перечислимое множество пар чисел, различных по модулю η, определяет вполне вычислимую последовательность η-замкнутых вычислимых отделяющих множеств. 3 ⇒ 2. Пусть R0,R1,... - вполне отделяющая последовательность для η. Построим нумерацию ν некоторого семейства вычислимых множеств, определенную следующим образом: νx = {n | x ∈ Rn}. Очевидно, что ν - вполне вычислимая нумерация. Покажем, что нумерационная эквивалентность этой нумерации есть η. В самом деле, если x = y (mod η), то, в силу η-замкнутости всех множеств из отделяющей последовательности, каждое множество, содержащее x(y), одновременно содержит и y (соответственно x), т. е. νx = νy. Если же , то для них найдется отделяющий член последовательности, скажем, x ∈ Rn и y /∈ Rn, поэтому объекты, нумеруемые числами x и y, являются различными, т. к. n ∈ νx и n /∈ νy. Напомним, что алгебра называется определимой над эквивалентностью η на ω, если существует нумерация этой алгебры с нумерационной эквивалентностью в качестве η. Отметим, что в современной теории вычислимых структур вычислимость семейства F представляющих функций, согласованных с эквивалентностью η, вообще говоря, не требуется, однако, для большинства приводимых ниже результатов это условие необходимо. Как обычно, в рамках понятий универсальной алгебры, из согласованности всех F-операций с эквивалентностью η (или, что равносильно, из того, что эквивалентность η есть конгруэнция вычислимой алгебры ) следует корректная определенность фактор-алгебры , т. к. действия F-операций на фактор-множестве ω/η определены однозначно. Это позволяет обосновать запись . Уместно отметить, что вычислимые алгебры вида , где F - произвольное (не обязательно вычислимое) семейство вычислимых функций, играют в теории вычислимых структур роль «абсолютно свободных» объектов, т. к. образуют тот исходный материал, из которого строится любая нумерованная алгебра путем подходящей факторизации. Поскольку всякая не более чем счетная алгебра эффективной сигнатуры имеет нумерацию, то всякая такая алгебра определима над некоторой эквивалентностью на ω. Всюду далее в тексте, говоря о нумерованных алгебрах, будем подразумевать, что эти алгебры содержат более одного элемента, т. к. иначе возникает вырожденная ситуация, которую всегда нужно будет оговаривать. Известно, что существуют нетривиальные позитивные эквивалентности, над которыми определимы только тривиальные алгебры в следующем смысле. Очевидно, что функции-константы и проектирующие функции (и только они) согласованы с любой эквивалентностью. Существует позитивная эквивалентность с бесконечным числом смежных классов, по модулю которой всякая согласованная с этой эквивалентностью вычислимая функция действует либо как константа, либо как проектирующая. Пример такой эквивалентности можно найти в (Ю.Л. Ершов, [4, гл. 3, §6, с. 296-299]). Для негативных эквивалентностей ситуация диаметрально противоположная, как показывает Следствие 2.5. Над всякой негативной эквивалентностью определима конгруэнц-простая алгебра. Доказательство. Если η - эквивалентность на ω и α ⊆ ω, то η-замыканием α называется наименьшее η-замкнутое расширение множества α (в обозначениях [α]η). Будем говорить, что число z η-отвергается множеством α, если z /∈ [α]η. Нетрудно заметить, что отношение «z отвергается γx» - перечислимое отношение для любой негативной эквивалентности η, равномерно зависящее от z,x (здесь γ - каноническая нумерация семейства всех конечных подмножеств ω). Если ясно, о какой эквивалентности идет речь, то будем говорить, что z отвергается α, без явного указания η. Пусть η - негативная эквивалентность. Выше было отмечено, что tr(η) перечислима. Если характеристическая трансверсаль tr(η) конечна, то доказывать нечего. В противном случае зафиксируем некоторое разнозначное вычислимое перечисление бесконечной характеристической трансверсали tr(η) = {t0,t1,...}. Покажем, что для любой пары существует η-замкнутое разрешимое множество, отделяющее x,y, и, более того, это множество равномерно строится по данным x,y (более подробно об алгоритмах отвержения см. в [24, 25]). Шаг 0. A0x = {x},A0y = {y}. Шаг s + 1. Пусть z - наименьшее натуральное число, не принадлежащее Asx ∪ Asy. Проверяем z на предмет его отвержения хотя бы одним из множеств Asx,Asy. Если z отвергается Asx, то полагаем Asx+1 = Asx,Asy+1 = Asy∪{z}; если x отвергается . Если z отвергается обоими множествами, то относим его к. Конец шага s + 1. Определим . Индукцией по шагам построения легко показать, что каждый шаг заканчивается с отнесением текущего тестируемого натурального числа к одному из двух множеств, а также тот факт, что для любого шага s. Поэтому перечислимые Ax,Ay не пересекаются, являются η-замкнутыми и их объединение покрывает все ω. Равномерная зависимость индексов характеристических функций Ax,Ay от x,y очевидна. Теперь для каждой пары различных по модулю η чисел построим вычислимое семейство операций Fx,y = {fx,y,m,n|m,n ∈ ω} следующим образом: z ∈ Ax ⇒ fx,y,m,n(z) = tm;z ∈ Ay ⇒ fx,y,m,n(z) = tn, где Наконец, определим вычислимое семейство операций . Очевидно, что любая операция f ∈ F согласована с η, т. е. x = y (mod η) ⇒ f(x) = f(y) (mod η) и потому корректно определена фактор-алгебра вычислимой алгебры по конгруэнции η. Так как для любой пары различных по модулю η чисел x,y и любых различных tm,tn ∈ tr(η) найдется операция из F, переводящая x в tm и y в tn, то алгебра проста. Определение 2.3. Эквивалентность η называется равномерно вычислимо отделимой, если существует частичная вычислимая функция, значение которой определено на каждой паре чисел, различных по модулю этой эквивалентности, и равно характеристическому индексу η-замкнутого вычислимого множества, отделяющего одно из этих чисел от другого. Предложение 2.4 позволяет давать более прямые и краткие описания важных свойств негативных эквивалентностей. Например, имеет место Следствие 2.6. Эквивалентность негативна тогда и только тогда, тогда она является равномерно вычислимо отделимой эквивалентностью с перечислимой характеристической трансверсалью. Доказательство. Конструкцию опишем с умеренной степенью детализации. Если эквивалентность η негативна, то, по предложению 2.4, она вполне отделима, т. е. для нее существует перечислимая по характеристическим индексам последовательность R0,R1,... η-замкнутых вычислимых отделяющих множеств. Тогда частичная вычислимая функция f, определенная следующим образом: f(x,y) = μn((x ∈ Rn ∧ y /∈ Rn) ∨ (y ∈ Rn ∧ x /∈ Rn)), где μ - оператор минимизации, определена на каждой паре чисел x,y, различных по модулю η, и «выдает» в качестве значения некоторый номер множества, отделяющего x и y. Вычислимая перечислимость характеристической трансверсали негативной эквивалентности очевидна. Обратно, пусть η - равномерно вычислимо отделимая эквивалентность с перечислимой характеристической трансверсалью tr(η), t0,t1,... - фиксированный эффективный пересчет множества tr(η), f - функция из определения равномерно вычислимой отделимости, а χm обозначает функцию с характеристическим индексом m. Тогда определены и различны)). Отсюда следует перечислимость дополнения η. 2.3. Отделимые представления и эффективно отделимые аппроксимации. Мы условились называть нумерованную алгебру отделимой (эффективно отделимой), если таковой является ее нумерационная эквивалентность, и понимать под гомоморфизмами нумерованных алгебр обычные гомоморфизмы, одновременно являющиеся морфизмами соответствующих нумерованных множеств. Напомним, что для нумерованной алгебры (A,ν) все операции алгебры A, представленные вычислимыми операциями в нумерации ν (точнее, их действиями, индуцированными на классах нумерационной эквивалентности), являются непрерывными как в ν-перечислимо порожденном, так и в ν-вычислимо порожденном пространствах. Следующий факт позволяет свести изучение отделимых нумераций алгебр к вычислимым (в смысле Ю.Л. Ершова, т. е. к эффективно отделимым) нумерациям. Теорема 2.3. Нумерованная алгебра отделима тогда и только тогда, когда она аппроксимируется эффективно отделимыми алгебрами. Доказательство. Приведем набросок доказательства. Пусть (A,ν) - нумерованная алгебра эффективной сигнатуры Σ и ν - отделимая нумерация. Обогатим сигнатуру Σ счетным множеством констант C = {cn | n ∈ ω}, не пересекающимся с Σ, интерпретируя константу cn в элемент νn алгебры A. Переменной будем называть любой элемент множества X = {xn | n ∈ ω}, не пересекающегося с Σ ∪ C. Следуя А.И. Мальцеву [51], трансляцией t(x) назовем любой терм от одной переменной x, который можно получить из подходящего терма путем замены части переменных некоторыми константами и отождествления всех оставшихся переменных с буквой x. Таким образом, всякая трансляция алгебры A задает на ней одноместную операцию, однозначно определенную интерпретациями всех символов обогащенной сигнатуры. Множество всех трансляций будем обозначать через T(x). ν-Интерпретацией трансляции t(x) в нумерации ν алгебры A назовем одноместную функцию tν(x), получаемую из t(x) подстановкой вместо всех Σ-символов соответствующих вычислимых функций и натуральных чисел (для Σ-констант), представляющих операции алгебры A в нумерации ν. Таким образом, каждая ν-трансляция определяет одноместную вычислимую функцию, представляющую соответствующую трансляцию алгебры A. Множество ν-интерпретаций всех трансляций из T(x) обозначим через Tν(x). Хорошо известно (см. [51]), что отношение эквивалентности на основном множестве алгебры является ее конгруэнцией тогда и только тогда, когда она согласована со всеми трансляциями данной алгебры. Легко проверить, что в силу эффективности сигнатуры Σ и перечислимости T(x) множество Tν(x) вычислимо, т. е. существует эффективная процедура, равномерно трансформирующая номер ν-трансляции в способ вычисления соответствующей вычислимой функции. Более формально, в качестве нумерации соответствующего семейства вычислимых функций удобно принять нумерацию этого семейства синтаксическими выражениями из T(x), т. к. существует очевидное эффективное соответствие между трансляциями и ν-трансляциями. С использованием стандартных λ-обозначений Черча множество вычислимых ν-трансляций можно записать как Tν(x) = {λ.tν(x) | t(x) ∈ T(x)}, где все символы в t(x), за исключением переменной x, представлены интерпретациями сигнатурных символов в нумерации ν. Вполне очевидна вычислимость этого семейства, поэтому мы не будем вдаваться в детали построения конкретной вычислимой геделевской нумерации γ : ω → Tν(x). Пусть A0,A1 - разбиение основного множества алгебры A на две непустые непересекающиеся части и Θ(A) - решетка всех конгруэнций этой алгебры. Рассмотрим множество (A0,A1) всех тех конгруэнций алгебры A, никакая из которых не отождествляет никакой элемент из A0 ни с каким элементом из A1, т. е. Θ(A0,A1) = {θ | θ ∈ Θ(A) ∧ x = y (mod θ) → ((x ∈ A0 ∧ y ∈ A0) ∨ (x ∈ A1 ∧ y ∈ A1)))}. Следующий простой факт представляет самостоятельный интерес. Лемма 2.1. В (A0,A1) существует наибольший элемент. Используем лемму 2.1 следующим образом. Пусть Из отделимости ν следует существование η-замкнутого вычислимо перечислимого множества α (где η обозначает нумерационную эквивалентность нумерации ν), отделяющего эти элементы. Пусть, для определенности, m ∈ α и n /∈ α. Положим, тогда множества A0,A1 образуют разбиение основного множества алгебры A на две дизъюнктные части. По предыдущей лемме существует наибольшая конгруэнция θ, не «склеивающая» никакой элемент из A0 ни с каким элементом из A1. Очевидно, . Поскольку θ - наибольшая конгруэнция, различающая элементы νm,νn алгебры A, то всякая ненулевая конгруэнция фактор-алгебры A/θ содержит пару элементов. Рассмотрим нумерованную фактор-алгебру (A/θ,ν∗) нумерованной алгебры (A,ν), где ν∗ обозначает естественную нумерацию фактор-алгебры, индуцированную нумерацией ν, т. е. ν∗ = θν. Лемма 2.2. Нумерованная алгебра (A/θ,ν∗) эффективно отделима. Доказательство. Заметим, что алгебра A/θ подпрямо неразложима, т. к. пересечение всех ее ненулевых конгруэнций содержит пару. В частности, любая главная конгруэнция алгебры A/θ (т. е. порожденная парой различных ее элементов) также содержит эту пару. Следовательно, для любой пары различных элементов ν∗p,ν∗q алгебры A/θ найдется ν-трансляция t∗(x), переводящая номера одного из этих элементов в α, а другого - в т. е. t∗(p) ∈ α ∧ t∗(q) ∈/ α либо t∗(q) ∈ α∧t∗(p) ∈/ α. В противном случае существовала бы собственная конгруэнция алгебры A/θ, различающая элементы νm/θ,νn/θ, что невозможно. Обозначим t∗-прообраз множества α через t∗-1(α), т. е. t∗-1(α) = {x | t∗(x) ∈ α}. Ясно, что множество t∗-1(α) вычислимо перечислимо как вычислимый t∗-прообраз вычислимо перечислимого множества α. Если, далее, через η∗ обозначить нумерационную эквивалентность нумерации ν∗, то t∗-1(α) является η∗-замкнутым. Пусть t0,t1,..., - вычислимая последовательность всех ν-трансляций. Рассмотрим последовательность множеств t-0 1(α),t-1 1(α),... . Тогда эта последовательность, очевидно, вычислима и, с учетом вышесказанного, является отделяющей для нумерации ν∗. Следовательно, для любой пары различных элементов алгебры (A,ν) найдется эффективный на номерах гомоморфизм из этой алгебры на подходящую эффективно отделимую алгебру, различающий эти элементы. Обратная импликация в формулировке теоремы очевидна. Согласно теореме 2.1 нумерованная алгебра вычислимо отделима тогда и только тогда, когда она аппроксимируется негативными алгебрами. Таким образом, роль и место эффективно отделимых алгебр в классе отделимых родственна роли и месту негативных алгебр в классе рекурсивно отделимых. При этом, как показывает теорема 2.3, наиболее общая концепция отделимости, определяемая теоремой Ю.Л. Ершова о вычислимых нумерациях, дает готовый математический аппарат для развития структурной теории отделимых алгебр. Следствие 2.7. Отделимая нумерация подпрямо неразложимой алгебры эффективно отделима. Доказательство. Пусть алгебра A подпрямо неразложима и пара различных ее элементов содержится в любой ненулевой конгруэнции этой алгебры. Допустим, что ν : ω → A - отделимая нумерация алгебры A и ν(m) = a, ν(n) = b. По теореме 2.3 пара различается в некотором эффективно отделимом гомоморфном образе нумерованной алгебры (A,ν), но A вообще не имеет ненулевых конгруэнций, различающих пару , следовательно, эффективно отделимой конгруэнцией, различающей данную пару, необходимо является нулевая, т. е. ν эффективно отделима. Определение 2.4. Неединичная эквивалентность η на ω называется перечислимо простой (вычислимо простой), если не существует собственных η-замкнутых вычислимо перечислимых (вычислимых) подмножеств множества ω. Перечислимая простота (вычислимая простота) эквивалентности η означает, что ни для какого ее расширения η1, являющегося эквивалентностью, не существует собственных η1-замкнутых перечислимых (вычислимых) подмножеств. Нумерацию назовем перечислимо (вычислимо) простой, если таково ее ядро. Напомним, что для эквивалентности η семейство всех η-замкнутых перечислимых (вычислимых) множеств образует базу естественной перечислимой (вычислимой) топологии на множестве ω/η, которую будем называть эффективно порожденной перечислимой топологией (соответственно, вычислимой топологией). На языке эффективно порожденных пространств перечислимая простота означает, что соответствующее эффективно порожденное пространство (с естественной нумерацией- каждое число нумерует содержащий его класс эквивалентности) является пространством слипшихся точек. Точно так же, вычислимая простота эквивалентности равносильна тому, что соответствующее вычислимо порожденное пространство антидискретно. Следствие 2.8. Неединичная эквивалентность перечислимо проста тогда и только тогда, когда никакая алгебра определимая над ней не обладает эффективно отделимой факторалгеброй. Доказательство. Пусть эквивалентность η не является перечислимо простой. Тогда существует собственное η-замкнутое перечислимое подмножество α множества ω. Если алгебра A определима над η, то, по лемме 2.1 теоремы 2.3, существует такая наибольшая конгруэнция θ алгебры A, которая «не склеивает» никакой элемент из α/η ни с каким элементом из (ω \ α)/η, и именно фактор-алгебра A/θ алгебры A является эффективно отделимой, т. к. любая главная (т. е. порожденная парой различных элементов) конгруэнция этой фактор-алгебры такова, что найдется трансляция, переводящая один из элементов пары в α, а другой - в ω\α и, следовательно, множество всех трансляционных прообразов множества α является вычислимым семейством отделяющих перечислимых множеств для фактор-алгебры A/θ. Обратно. Если над эквивалентностью η определима алгебра A, обладающая эффективно отделимой нетривиальной фактор-алгеброй, то ядро этого гомоморфизма очевидно обеспечивает свойство «не быть перечислимо простой» для η. Следствие 2.9. Нумерованная простая алгебра эффективно отделима тогда и только тогда, когда она имеет собственное перечислимое подмножество. Доказательство. Пусть A - простая алгебра, ν - ее нумерация и α - нетривиальное ker(ν)замкнутое перечислимое множество. Тогда, так же как и в предыдущем следствии, существует наибольшая конгруэнция θ алгебры A («не склеивающая» никакой элемент из α ни с каким элементом из ω \ α), которая эффективно отделима в нумерации θν (θν обозначает композицию нумерации и проектирования). Единичная конгруэнция таковой быть не может, следовательно, сама нумерованная алгебра (A,ν) эффективно отделима. Обратное очевидно. Следствие 2.10. Всякая нумерация простой алгебры либо вычислимо проста, либо негативна. Доказательство. Пусть ν - не вычислимо простая нумерация простой алгебры A. Тогда существует собственное подмножество A0 ⊆ A такое, что ν-1(A0) вычислимо. Так как алгебра A проста, то для любой пары ее различных элементов a,b найдется такая трансляция λx.t(x), что либо t(a) ∈ A0 ∧ t(b) ∈/ A0, либо t(a) ∈/ A0 ∧ t(b) ∈ A0 (иначе главная конгруэнция, порожденная парой, была бы собственной, т. е. отличной от нулевой и единичной, т. к. она не «склеивала» бы никакой элемент из A0 ни с каким элементом из A \ A0). Остается заметить, что , где - вычислимо перечислимое множество всех вычислимых трансляций, представляющих трансляции алгебры A сигнатуры Σ в нумерации ν. Подчеркнем, что связки «либо..., либо» в формулировке следствия 2.10 взаимно исключающие. Другими словами, если нумерованная простая алгебра имеет вычислимое нетривиальное (отличное от ∅ и ω) подмножество, то она негативна. перечислимо простых нумераций алгебрыПусть A - простая алгебра, Λneg,Λcom-splA ,соответственно. ТогдаΛen-spl - классы негативных, вычислимо простых иΛneg ∩ Λcom-spl = ∅, при этом всякая нумерация алгебры A лежит в Λneg ∪Λcom-spl и Λen-spl ⊆ Λcom-spl. Далее будет показано, что любая алгебра имеет перечислимо простую нумерацию, однако неизвестно, будет ли включение Λen-spl ⊆ Λcom-spl собственным в случае конгруэнц-простых алгебр. Другими словами, вопрос о существовании вычислимо простых, но не перечислимо простых нумерованных конгруэнц-простых алгебр открыт. Для T1-отделимо нумерованных подпрямо неразложимых алгебр и алгебр с артиновыми решетками конгруэнций ответ на вопрос «?»- положительный (см. последний подраздел следующего раздела). Неодноэлементное топологическое пространств называется тривиальным, если открытыми множествами являются только само множество и ∅. Следствие 2.11. Для нумерованной простой алгебры эффективная отделимость перечислимо порожденного топологического пространства равносильна его нетривиальности. 2.4. Условия конечности. Среди трех основных инструментов исследования в универсальной алгебре - решеток конгруэнций, подалгебр и групп автоморфизмов- особую роль с точки зрения теории нумераций играют решетки конгруэнций. Так, если над эквивалентностью определима конечно порожденная алгебра, то, очевидным образом, над ней определяются алгебры, порожденные любым своим элементом (т. е. с одноэлементными решетками подалгебр). Семейства вычислимых автоморфизмов, играющие фундаментальную роль при изучении абстрактных свойств симметрии позитивных (в особенности вычислимых) систем, в случае произвольных нумерованных алгебр вообще не являются группами (см. [26, 71]). Более того, существуют естественные примеры негативных систем, полугруппы вычислимых автоморфизмов которых не являются группами (см. [42]). Иное дело решетки конгруэнций. Например, всякая алгебра, определимая над неразрешимой позитивной эквивалентностью, имеет весьма богатую решетку конгруэнций (см. [16, 18, 21], впрочем, справедливости ради, следует отметить, что, согласно следствию 2.5, над любой негативной эквивалентностью определимы конгруэнц-простые алгебры). Ниже будет показано, что множество конгруэнций всякой алгебры, имеющей отделимую невычислимую нумерацию, является бесконечным. Как было отмечено выше, нумерационная эквивалентность всякой эффективно отделимой нумерации принадлежит индуктивному классу арифметической иерархии Клини-Мостовского. В то же время, в каждой m-степени присутствует вычислимо отделимая (а значит, и отделимая) эквивалентность (см. [4]). Поскольку класс отделимых нумераций алгебр весьма обширен, то представляется целесообразным изучение подклассов этого класса в предположениях наличия ограничений тех или иных типов на решетки конгруэнций. Свидетельством полезности такого подхода является следующая теорема. Теорема 2.4. Всякая отделимая нумерация алгебры с артиновой решеткой конгруэнций является эффективно отделимой. Приведем основную идею доказательства, данного в [31]. Пусть решетка конгруэнций алгебры A удовлетворяет условию минимальности и ν - отделимая нумерация этой алгебры. Допустим, что ν не является эффективно отделимой. Покажем, что в этом случае можно построить бесконечно убывающую цепь конгруэнций алгебры A. Зафиксируем любую пару различных элементов a0,b0 алгебры A. По теореме 2.3 существует такая конгруэнция θ0(a0,b0) этой алгебры, различающая элементы a0 и b0, что нумерованная фактор-алгебра (A/θ0(a0,b0),ν0), где ν0 = θ0ν (θ0 обозначает естественное проектирование в классы θ0(a0,b0)-эквивалентности) является эффективно отделимой. Ядро гомоморфизма θ0 - ненулевое, т. к. ν, согласно предположению, не является эффективно отделимой. В силу того, что гомоморфизм θ0 является собственным, существует пара различных элементов a1,b1 алгебры A, которые равны по модулю θ0(a0,b0). Опять-таки, по теореме 2.3, эти элементы различаются в подходящем эффективно отделимом гомоморфном образе алгебры A по конгруэнции, которую обозначим через θ1(a1,b1). Положим θ = θ0(a0,b0) ∩ θ1(a1,b1). Очевидно, что θ - конгруэнция, для которой θ0(a0,b0) является собственным расширением. Рассмотрим нумерованную алгебру (A/θ,θν). Легко показать, что пересечение конечного числа эффективно отделимых эквивалентностей на ω является эффективно отделимым и потому нумерованная алгебра (A/θ,θν) эффективно отделима, причем θ0(a0,b0) является строгим расширением θ, т. к.. Далее, повторяем процедуру построения строго меньшей эффективно отделимой конгруэнции, рассматривая в качестве η0(a0,b0) конгруэнцию θ. Поскольку на каждом этапе построения получается эффективно отделимая конгруэнция, то, в силу предположения о том, что исходная нумерация не является эффективно отделимой, каждая конгруэнция из этой цепи является ненулевой. Следовательно, решетка конгруэнций алгебры A оказывается неартиновой, что противоречит исходному предположению. Следствие 2.12. Нумерация алгебры с артиновой решеткой конгруэнций отделима тогда и только тогда, когда она эффективно отделима. Таким образом, отделимые нумерации алгебр с артиновыми решетками конгруэнций являются вычислимыми в смысле Ю.Л. Ершова, т. е. класс таких нумераций содержится в классе вычислимых нумераций семейств перечислимых множеств. Можно показать, что не над всякой эффективно отделимой эквивалентностью определима алгебра с артиновой решеткой конгруэнций. Действительно, согласно замечанию, сделанному перед следствием 2.5, существует такая позитивная эквивалентность η, что всякая операция любой ηалгебры действует на η-классах либо как константа, либо как проектирующая. Поскольку любое разбиение основного множества такой алгебры допустимо относительно всех операций, то решетка ее конгруэнций неартинова (впрочем, и ненетерова тоже). В силу эффективной отделимости как позитивных, так и негативных эквивалентностей, эквивалентность η дает пример такого вычислимого семейства перечислимых множеств ({S|S ⊆ ω,∃x(S = x/η} с естественной проектирующей нумерацией ν(x) = x/η), над ядром которого не определима никакая алгебра со сколь-нибудь разумными условиями конечности для решетки ее конгруэнций. Отметим однако, что существуют невычислимые позитивные эквивалентности, над которыми определимы алгебры со счетными (даже нетеровыми) решетками конгруэнций. При этом все такие эквивалентности необходимо отделимы (даже вычислимо отделимы, см. [13-15]). Следствие 2.13. Отделимая нумерация алгебры с конечным числом конгруэнций является эффективно отделимой. Непосредственно вытекает из теоремы 2.4, т. к. если число конгруэнций алгебры конечно, то, очевидно, решетка конгруэнций артинова. В частности, эффективно отделимой является любая отделимая нумерация конечной алгебры эффективной сигнатуры. Еще более частным случаем (в случае пустой сигнатуры) является эффективная отделимость отделимой нумерации любого конечного множества. Следствие 2.14. Решетка конгруэнций всякой алгебры, обладающей отделимой, но не эффективно отделимой нумерацией, является бесконечной. Доказательство. В самом деле, в этом случае решетка конгруэнций не может быть артиновой, а значит, она бесконечна. Для алгебр с нетеровыми решетками конгруэнций теорема 2.4 не имеет места. Согласно следствию 2.14 такие алгебры должны быть бесконечными. Простейшей бесконечной алгеброй с нетеровой решеткой конгруэнций является алгебра следования. Оказывается, что уже эта алгебра имеет отделимые (даже вычислимо отделимые) нумерации, алгоритмические сложности нумерационных эквивалентностей которых превосходят любую наперед заданную арифметическую сложность, как показывает следующее предложение. Предложение 2.5. Алгебра следования S имеет континуум нумераций, ядра которых вычислимо отделимы. Доказательство см. в [31]. Следствие 2.15. Для любого класса арифметической иерархии Клини-Мостовского существует отделимая нумерация алгебры с нетеровой решеткой конгруэнций, алгоритмическая сложность нумерационной эквивалентности которой не принадлежит данному классу. В работе [70] доказано, что следующие алгебры имеют невычислимые негативные нумерации: (а) стандартная модель арифметики Пеано, где s- функция следования, а +,∗ имеют естественные интерпретации сложения и умножения на ω (в частности, вычислимой негативной нумерацией обладает стандартная модель арифметики Пресбургера в сигнатуре , а также, что особенно важно, алгебра следования , при этом любая позитивная нумерация алгебры следования и, тем более, стандартной модели арифметики Пресбургера и арифметики Пеано является, очевидно, вычислимой); (б) всякое бесконечное вычислимо представимое поле (заметим, что любое поле есть конгруэнц-простая алгебра); (в) всякая вычислимо представимая абелева группа без кручения; (г) всякое бесконечное вычислимо представимое векторное пространство над конечным полем; (д) абсолютно свободная алгебра термов эффективной сигнатуры от свободного эффективного множества порождающих. Примеры такого рода, которые легко умножить, показывают, что в определенном смысле негативные алгебры не менее естественны, нежели позитивные. В пользу этого наблюдения говорит также следующий факт. Пусть KES - класс вычислимых (т. е. эффективно отделимых) алгебр, KAS - класс отделимо нумерованных алгебр с артиновыми решетками конгруэнций. Все позитивные и негативные алгебры являются KES-алгебрами. Согласно теореме 2.4 всякая KAS-алгебра есть KES-алгебра, т. е. для класса алгебр с артиновыми решетками конгруэнций понятия отделимой и вычислимой нумерации совпадают. В классе KAS присутствует весьма обширный и важный подкласс KAN негативно нумерованных алгебр с артиновыми решетками конгруэнций, причем многие естественные KANалгебры невычислимы. Пусть KAP - класс позитивно нумерованных алгебр с артиновыми решетками конгруэнций, тогда KAP также есть подкласс класса KAS. Очевидно, что (например, связное двоеточие). Известно, что всякая KAP -алгебра, мощность решетки конгруэнций которой меньше континуума, вычислима (см. [35]), т. е. является KAN-алгеброй. Класс невычислимых негативных алгебр с условием минимальности для решетки конгруэнций, т. е., как следует из вышесказанного, весьма богат. Известно также, что существуют как невычислимые позитивные (см. [14]), так и невычислимые негативные алгебры с нетеровыми решетками конгруэнций (для негативных алгебр соответствующие примеры почти тривиальны). Насколько богат класс? Обширность указанной разности классов означала бы, что невычислимые позитивные алгебры с естественными условиями конечности встречаются «не менее часто», чем невычислимые негативные. Вопрос «?» в настоящий момент является открытым. Предложение 2.6. Среди нумерованных алгебр существуют как подпрямо неразложимые, так и алгебры с артиновыми решетками конгруэнций, нумерационные эквивалентности которых обладают собственными вполне перечислимыми подмножествами, но не являются отделимыми. Доказательство см. в [31]. Следствие 2.16. Существуют нумерации алгебр как с артиновыми решетками конгруэнций, так и подпрямо неразложимых, эффективно порожденные пространства которых нетривиальны, но неотделимы. Таким образом, следствие 2.9, верное для класса простых алгебр, нельзя обобщить на собственные расширения этого класса с более слабыми условиями конечности. 2.5. Аксиомы отделимости. В этом разделе рассмотрим некоторые усиления условия отделимости нумерации, которые, во многих естественных случаях, оказываются достаточными для ее эффективной отделимости и даже негативности. Определение 2.5. Нумерация называется T1-отделимой (T2-отделимой; T3-отделимой; T4отделимой), если для всякой пары натуральных чисел, различных по модулю ее нумерационной эквивалентности, найдется перечислимая окрестность первого числа, не содержащая второе, и перечислимая окрестность второго, не содержащая первое (найдутся непересекающиеся перечислимые окрестности этих чисел; для всякого элемента и замкнутого в эффективно порожденной топологии множества, не содержащего этот элемент, найдутся их непересекающиеся окрестности; для всякой пары непересекающихся замкнутых множеств найдутся их непересекающиеся окрестности). Обозначим через класс пространств, гомеоморфных эффективно порожденным пространствам, для которых выполняется аксиома Tm-отделимости. Предложение 2.7. для m ∈ {0,1}, K3 = K4. Доказательство. Для m = 0 тривиальный пример дается связным двоеточием, т. к. если α - вычислимо перечислимое невычислимое множество, то двухэлементное множество с естественной нумерацией, сопоставляющей каждому числу содержащее его множество, есть эффективно порожденное отделимое и не T1-отделимое пространство. Для m = 1 в [25] построен пример эффективно порожденного пространства, гомеоморфного счетно-бесконечному пространству Зарисского, т. к. непустыми перечислимыми подмножествами в этом примере являются все коконечные множества и только они. Для m = 3 вопрос, так же, как и для m = 0, тривиален, т. к. для счетных топологических пространств регулярность и нормальность равносильны (предполагается T1-отделимость). Для m = 2 вопрос открыт. В случае вычислимо порожденных пространств ситуацию полностью описывает Предложение 2.8. Нумерация вычислимо отделима тогда и только тогда, когда вычислимо порожденное топологическое пространство совершенно нормально. Доказательство см. в [25]. В частности, в этом случае выполняются все аксиомы Tm-отделимости (m ∈ {0,1,2,3,4}). Определение 2.6. Нумерация называется эффективно T1-отделимой (T2-отделимой), если для нее существует вычислимая последовательность T1-отделяющих (T2-отделяющих) множеств. Для T1-отделимых (T2-отделимых) нумераций естественно возникает вопрос о справедливости усиленных аналогов теоремы 2.3: всякая ли T1-отделимая (T2-отделимая) нумерованная алгебра аппроксимируется эффективно T1-отделимыми (T2-отделимыми)? Если (A,ν) - нумерованная алгебра и K - класс нумерованных алгебр, однотипных с A, то назовем A простой относительно класса K (K-простой), если никакая ее неединичная факторалгебра не принадлежит K. Через K1(K2) обозначим класс эффективно T1-отделимых (T2-отделимых) нумерованных алгебр. Для алгебр пустой сигнатуры (т. е. нумерованных множеств) верна Теорема 2.5. Существует T1-отделимое, но не T2-отделимое нумерованное множество, никакое фактор-множество которого не является эффективно T1-отделимым. Доказательство см. в [31]. Следствие 2.17. Существует K1-простая T1-отделимая нумерованная алгебра, эффективно порожденное топологическое пространство которой является пространством Зарисского. Доказательство. Приведем основную идею. В доказательстве теоремы 2.5 построен пример такой бесконечной эквивалентности η, что нетривиальными η-замкнутыми перечислимыми множествами являются все те, дополнения которых являются объединениями конечного числа классов η-эквивалентности (η-коконечные) и только они. Первые примеры таких эквивалентностей были построены в [25]. Далее, используя бесконечность характеристической трансверсали tr(η) и счетность множества эффективно отделимых эквивалентностей, можно построить (неэффективным диагональным методом) такое бесконечное α ⊆ tr(η), что всякое бесконечное подмножество α (претендующее на роль характеристической трансверсали в расширении эквивалентности η) заведомо не будет характеристической трансверсалью никакой эффективно отделимой эквивалентности. Пусть α = {a0 < a1 < ...}. «Склеим» все η-классы в полуинтервалах [an,an+1) и обозначим полученную эквивалентность через η∗ ⊇ η. Тогда не только η∗, но и никакой ее фактор не может быть эффективно отделимым (для бесконечных - в силу свойств α, для конечных- ввиду неперечислимости η∗-конечных множеств), но η∗ является T1-отделимой. При этом все η∗-замкнутые η∗-коконечные множества и только они являются перечислимыми (за исключением ∅), но никакой фактор η∗ не является эффективно T1-отделимым. Простейшими примерами эффективно T2-отделимых нумераций являются позитивные и негативные нумерации. Более того, ниже будет показано, что в этих случаях имеет место равномерная T2-отделимость, т. е. существует эффективная процедура, определенная на каждой паре чисел, различных по модулю нумерационной эквивалентности, значением которой является пара вычислимо перечислимых индексов непересекающихся множеств, замкнутых относительно нумерационной эквивалентности, отделяющих эту пару чисел. Приведем пример T2-отделимого нумерованного множества, не имеющего вычислимых факторов, эффективно порожденное пространство которого является дискретным. Предложение 2.9. Существует T2-отделимое нумерованное множество с перечислимыми элементами, никакое фактор-множество которого не является эффективно T1-отделимым. Доказательство см. в [31]. Следствие 2.18. Существует K1-простая T2-отделимая нумерованная алгебра, эффективно порожденное пространство которой дискретно. Доказательство. Идея сходна с построением в предыдущем следствии. Начинаем с совершенной эквивалентности η (т. е. позитивной и вычислимо простой). Выбираем бесконечное α ⊆ tr(η) такое, что ни α, ни какое-либо его бесконечное подмножество не лежат в Π03. Как и выше, пусть α = {a0 < a1 < ...}. «Склеив» все η-классы в полуинтервалах [an,an+1), получим η∗ ⊇ η, каждый смежный класс которой перечислим, но никакой ее фактор не может быть эффективно T1-отделимым. Для бесконечных это следует из свойств α, для конечных- из совершенности η (и из вычислимой простоты η∗). Следствия 2.17 и 2.18 дополнительно подчеркивают фундаментальную роль теоремы Ю.Л. Ершова о вычислимых нумерациях с точки зрения теории нумерованных алгебр, т. к. для приведенных выше естественных усилений аксиом отделимости теорема об аппроксимации T1-отделимых (T2отделимых) алгебр эффективно T1-отделимыми (T2-отделимыми) неверна. Заметим, что нумерованные множества, построенные в теореме 2.5 и в предложении 2.9, тривиально аппроксимируются эффективно отделимыми- связными двоеточиями. Предложение 2.10. Всякая алгебра, обладающая отделимой нумерацией с такой характеристической трансверсалью, всякое бесконечное подмножество которой не принадлежит классу Π03, является финитно аппроксимируемой. Доказательство. Действительно, если ν - отделимая нумерация алгебры A и ∀α ⊆ tr(ν) ∧ α бесконечно (α /∈ Π03), то любая бесконечная фактор-алгебра нумерованной алгебры (A,ν), в т. ч. по нулевой конгруэнции, также имеет характеристическую трансверсаль, никакое бесконечное подмножество которой не лежит в Π03 и потому не может быть эффективно отделимой. Однако по теореме 2.3, (A,ν) аппроксимируется эффективно отделимыми алгебрами, следовательно, все аппроксимирующие эффективно отделимые алгебры конечны, т. е. A финитно аппроксимируема. Особое место как в теории решеток конгруэнций универсальных алгебр, так и в теории вычислимых структур, принадлежит простым алгебрам. Оказалось, что свойство T1-отделимости (T2отделимости) тесно связано с негативностью нумераций не только простых алгебр, но и алгебр с артиновыми решетками конгруэнций, а также подпрямо неразложимых алгебр. В случае отделимых алгебр простейшим примером нумерованной простой алгебры, не являющейся негативной, является связное двоеточие (см. случай m = 0 предложения 2.7). Для T2-отделимых алгебр пример не негативной простой алгебры неизвестен. Если такая алгебра существует, то она не имеет собственных вполне вычислимых подмножеств [25], но, согласно следствию 2.13, является эффективно отделимой, а значит, сложность ее нумерационной эквивалентности не выходит за пределы индуктивного класса Π02 в иерархии Клини-Мостовского. С другой стороны (если такого примера нет), не видно явных причин, вынуждающих T2-отделимые нумерации простых алгебр быть негативными. Таким образом, естественный вопрос о существовании не негативной T2-отделимой (или хотя бы T1-отделимой) нумерованной простой алгебры на текущий момент остается открытым. Как обычно, через ω обозначается как множество натуральных чисел, так и тип его линейного упорядочения (т. е. изоморфизма естественного порядка натуральных чисел). В определенном смысле к простым алгебрам «близки» алгебры с условиями минимальности для решеток конгруэнций. Например, простейшей бесконечной подпрямо неразложимой алгеброй с артиновой решеткой конгруэнций является алгебра предшествования p(0) = 0 (любая ее ненулевая конгруэнция содержит пару). Хотя среди бесконечных подпрямо неразложимых алгебр с артиновыми решетками конгруэнций унар P является простейшим, в нем проявляются присущие ему вполне нетривиальные свойства, что демонстрирует следующее утверждение. Предложение 2.11. Для алгебры P справедливо следующее: 1. P имеет артинову и ненетерову решетку конгруэнций; 2. решетка конгруэнций алгебры P как частичный порядок- линейно упорядоченное множество порядкового типа ω + 1; 3. решетка подалгебр алгебры P также имеет порядковый тип ω + 1; 4. всякая фактор-алгебра P/θ по ненулевой конгруэнции θ изоморфна P; 5. группа автоморфизмов алгебры P тривиальна. Доказательство. Приведем набросок доказательства. 1. «Расклейка» любой пары элементов, лежащих в единичной конгруэнции, дает «прыжок» к почти нулевой конгруэнции, в которой все числа из множества будут образовывать одноэлементные смежные классы (артиновость). «Склейка» же любой пары элементов , порождает главную конгруэнцию с одним нетривиальным смежным классом . Поэтому цепь строго возрастающая (ненетеровость). 2 и 3. Каждая последующая конгруэнция θn+1 (подалгебра Pn+1) относительно вышеупомянутого дискретного линейного порядка для заданной конгруэнции (подалгебры) получается путем добавления к нетривиальному смежному классу (к подалгебре) элемента n+1. Поэтому и решетка конгруэнций, и решетка подалгебр алгебры P линейно упорядочена по типу ω+1. Единичная конгруэнция (алгебра) является наибольшим элементом соответствующей решетки, а нулевая когруэнция (алгебра) - наименьшим. Пункт 4 следует из доказательства пункта 1. Пункт 5: очевидно. Легко понять, что всякая T2-отделимая нумерация алгебры предшествования является негативной. В самом деле, пусть ν - T2-отделимая нумерация этой алгебры, α,β - пара непересекающихся вычислимо перечислимых ker(ν)-замкнутых множеств и ν-1(0) ⊆ α,ν-1(1) ⊆ β. Тогда . Очевидно, что всякая позитивная нумерация алгебры P является вычислимой. В то же время нетрудно построить негативные невычислимые нумерации этой алгебры. Легко построить пример отделимой нумерации алгебры предшествования, не являющейся негативной. Вопрос о существовании T1-отделимой, но не негативной нумерации этой алгебры получил положительное решение (см. следующий раздел). Сложность построения контрпримера связана как минимум с построением T1-отделимой нехаусдорфовой нумерации, что само по себе сопряжено с определенными трудностями. Заметим, что в некоторых важных частных случаях, для известных типов алгебр, наличие T1-отделимости (T2-отделимости) для нумераций может являться достаточным условием их негативности. 3. ТОПОЛОГИЧЕСКИЕ НУМЕРОВАННЫЕ АЛГЕБРЫ Для нумерованной алгебры (A,ν) семейство всех перечислимых (вычислимых) ν-замкнутых множеств образует базу естественной топологии на ω/ker(ν) (см. [4]), которое выше мы назвали эффективной (соответственно- вычислимой) ν-топологией и обозначили через τ(ν) (соответственно через τcomp(ν)). Если η - эквивалентность на ω, то для всякой η-алгебры также можно определить соответствующие топологические пространства: τ(η)-пространство и τcomp(η)-пространство, порожденные η-замкнутыми перечислимыми и вычислимыми множествами соответственно. Эти подходы равносильны, т. к. ker(ν) однозначно определяется нумерацией, а эквивалентность η задает естественную (проектирующую) нумерацию ν: ν(x) = x/η. Как отмечалось выше, замечательным свойством этих топологий для любой нумерованной алгебры (A,ν) (не обязательно эффективной сигнатуры) является факт непрерывности всех операций алгебры A как в τ(ν)-топологии, так и в τcomp(ν)-топологии, т. к. каждая операция алгебры поддерживается подходящей вычислимой функцией, представляющей данную операцию в нумерации ν (см. [46]). Повторимся также, что всякий гомоморфизм нумерованных алгебр также является непрерывным отображением, т. к. вычислимые прообразы вычислимых (перечислимых) множеств вычислимы (соответственно, перечислимы). Отметим, что в случае негативно нумерованных алгебр соответствующая τcomp(ν)-топология, заданная вычислимыми множествами, определяет T4-пространство (см. [25]). Поэтому, в случае τcomp(ν)-топологии (более слабой относительно τ(ν)-топологии) это пространство оказывается совершенно нормальным и вполне несвязным. Для отделимых нумераций это конечно не так, например: связное двоеточие, где один элемент представлен перечислимым невычислимым множеством, а второй - его дополнением. Так как топология вводится на нумерованном множестве, а не наоборот, то в названии раздела прилагательное «топологические» предшествует прилагательному «нумерованные». Определение 3.1. Нумерация ν универсальной алгебры A называется эффективно невырожденной, если пространство τ(ν) нетривиально (т. е. τ(ν)-топология содержит хотя бы один элемент, кроме ∅ и ω/ker(ν)). Нумерацию, не являющуюся эффективно невырожденной, будем называть эффективно вырожденной. Иначе говоря, эффективная вырожденность нумерации универсальной алгебры равносильна отсутствию нетривиальных перечислимых окрестностей ее элементов. 3.1. Эффективно невырожденные нумерации. Формулировке следующего результата предпошлем важное замечание, касающееся эффективности сигнатуры. Большинство результатов общей теории нумерованных алгебр предполагает эффективность сигнатуры (т. е. наличие равномерно эффективной процедуры, «выдающей» алгоритм вычисления соответствующей представляющей операцию функции по ее сигнатурному имени), т. к. семейство всех трансляций должно быть перечислимым. Однако многие принципиальные факты справедливы для произвольных счетных сигнатур. В начале раздела уже упоминалось, что свойство непрерывности операций не зависит от эффективности сигнатуры. Таковым же является и один из следующих «отрицательных» (с точки зрения возможности эффективного различения элементов) универсальных результатов для нумерованных алгебр. Предложение 3.1. Всякая не более чем счетная универсальная алгебра счетной сигнатуры имеет эффективно вырожденную нумерацию. Доказательство. Пусть - универсальная алгебра счетной сигнатуры Σ. Рассмотрим «универсальную» сигнатуру Σ∗, определенную следующим образом. В Σ∗ содержится бесконечное вычислимое множество константных символов, бесконечное вычислимое множество унарных функциональных символов, бинарных и т. д. Очевидно, что Σ∗ - вычислимая сигнатура, в то время как алгоритмическая сложность Σ может быть какой угодно. Таким образом, Σ∗ является обогащением Σ для любого счетного Σ. Интерпретируем произвольным образом на алгебре A все символы из и через A∗ обозначим полученное Σ∗-обогащение алгебры A. Если мы построим некоторую нумерацию для алгебры A∗, то, тем самым, эта же нумерация будет и представлением для, т. к. A является Σ-обеднением алгебры A∗ сигнатуры Σ∗. Пусть TΣ∗(X) - абсолютно свободная Σ∗-алгебра от свободного вычислимого бесконечного множества порождающих X = {x0,x1,...}. Зафиксируем произвольную вычислимую геделевскую нумерацию γ алгебры TΣ∗(X) (удобно считать сами Σ∗-термы (слова) от порождающего множества X их же γ-номерами, т. к. они вполне могут играть роль «натуральных чисел»). Выберем сжатое (т. е. бесконечное не разбиваемое на две бесконечные части никаким перечислимым множеством) множество α ⊆ ω и рассмотрим следующее подмножество Y множества порождающих X: Y = {xi|i ∈ α}. Разобьем множество Y на бесконечное число бесконечных непересекающихся подмножеств и затем расширим Y0 множеством Построим сюръективное отображение μ : X → A так, чтобы μx = μy ⇔ ∃n ∈ ω(x ∈ Yn ∧y ∈ Yn). Отображение μ абсолютно свободных порождающих X единственным образом продолжается до гомоморфизма μ∗ ⊇ μ алгебры. Искомая нумерация ν является композицией γ и μ∗, т. е. ν = μ∗γ (очевидно, что все операции исходной алгебры представлены вычислимыми функциями в нумерации ν, т. к. результат «вычисления» Σ∗-операции f на наборе элементов есть слово f(t1(x),...,tn(x))). Покажем, что нумерованная алгебра (A∗,ν) не имеет собственного подмножества, ν-прообраз которого перечислим (т. е. τ(ν)-пространство тривиально). Допустим противное. Пусть B - собственное подмножество A и β = ν-1(B) - перечислимое подмножество ω. Тогда существуют такие. Но тогда перечислимое множество β разделяет сжатое множество α на две бесконечные части. Противоречие. Следствие 3.1. Всякая не более чем счетная универсальная алгебра счетной сигнатуры представима над некоторой эквивалентностью. Таким образом, эффективно невырожденные нумерованные алгебры образуют достаточно узкий класс (в категории нумерованных алгебр с морфизмами), в рамках которого мы будем формулировать наши утверждения. Яркими примерами эффективно отделимых нумераций являются позитивные и негативные. В отличие от позитивности, которую при различных построениях приходится аккуратно поддерживать, свойство негативности, напротив, оказалось очень тесно связанным с сильными типами отделимости, и его ликвидация связана с определенными трудностями. В случае эквивалентностей (т. е. алгебр пустой сигнатуры) затруднений не возникает, т. к. любая позитивная эквивалентность (так же, как и негативная) является эффективно отделимой. Более того, покажем, что позитивные и негативные эквивалентности дают примеры равномерно T2-отделимых нумераций (т. е. существует эффективная процедура, которая по паре различных по модулю ядра эквивалентности натуральных чисел «выдает» алгоритмы перечисления пары замкнутых непересекающихся множеств, содержащих данную пару чисел). Предложение 3.2. Позитивные и негативные эквивалентности являются равномерно эффективно T2-отделимыми. Доказательство. Пусть η - позитивная эквивалентность. Рассмотрим следующую полуформальную процедуру. Для данных x,y (предположительно различных по модулю η) начинаем перечислять два множества, первое из которых есть класс x/η, а второе- y/η. Эти множества и являются искомыми. Для негативной эквивалентности можно равномерно эффективно переходить не просто к перечислимым индексам вычислимо перечислимых непересекающихся η-замкнутых множеств, отделяющих x,y, а к характеристическим индексам вычислимых непересекающихся η-замкнутых отделяющих множеств (см. [25]). 3.2. Перечислимые топологии и компактные расширения. Напомним, что всякая нумерованная алгебра эффективной сигнатуры вычислимо отделима тогда и только тогда, когда она аппроксимируется негативными алгебрами (см. [25], аппроксимации понимаются как морфизмы, т. е. эффективные на номерах гомоморфизмы). Как отмечалось выше, для позитивных алгебр вычислимые и перечислимые топологии могут максимально различаться в случае, когда, например, η - бесконечная позитивная эквивалентность, которая не имеет собственных η-замкнутых вычислимых подмножеств. Тогда η-пространство является дискретным, а ηcomp-пространство - тривиальным. Оказывается, что в случае негативных алгебр вычислимые и перечислимые топологии совпадают. Приведем это утверждение в наиболее общей формулировке. Теорема 3.1. Пусть (A,ν) - негативно нумерованное множество. Тогда τ(ν)-топология и τ(ν)comp-топология совпадают. Доказательство. В одну сторону это очевидно, т. к. всякое вычислимое множество перечислимо. Пусть α - ν-замкнутое подмножество ω, открытое в τ(ν)-топологии. Не ограничивая общности, можно считать, что α - базовая (т. е. перечислимая) окрестность. Пусть a ∈ α. Для доказательства теоремы достаточно построить разбиение ω на ν-замкнутые перечислимые непересекающиеся множества β и δ такие, что a ∈ β ⊆ α и β ∪δ = ω. Мы построим их с помощью пошаговой конструкции. Конечные части множеств β и δ, накопленные перед исполнением шага s + 1, будем обозначать соответственно через βs и δs. Заметим, что случай также учитывается предлагаемой конструкцией. Шаг 0. Положим β0 = {a}, δ0 = ∅. Шаг s+1. Пусть z - наименьшее натуральное число из. Одновременно перечисляя множества ждем, пока не подтвердится выполнение хотя бы одного из следующих условий (далее будет показано, что это обязательно случится): (a) (z отвергается множеством δs) ∧ (z ∈ α); (b) z отвергается множеством βs. Если выполнено (a), то добавляем z к перечислению β, иначе- к перечислению δ. Лемма 3.1. Справедливы следующие утверждения: 1. β ⊆ α; 2. β ∩ δ = ∅; 3. любой элемент из β отвергается всеми элементами из δ и наоборот; 4. β ∪ δ = ω. Доказательство. Пункты 1 и 2 очевидны. Пункт 3 следует из того, что, как нетрудно убедиться индукцией по шагам построения, каждый элемент из βs отвергается всеми элементами из δs и наоборот. Пусть не выполнено условие (b), т. е. z не отвергается множеством βs. Это означает, что z является ν-эквивалентным элементу из βs, а поскольку в силу уже доказанного в пункте 1 мы имеем βs ⊆ β ⊆ α и по условию α ν-замкнуто, то получим z ∈ α. Далее, поскольку z ν-эквивалентно некоторому элементу из βs, то, в силу уже доказанного в пункте 3, получаем, что z отвергается множеством δs. Для доказательства пункта 4 достаточно показать, что на каждом шаге s одно из условий (a), (b) в описании конструкции обязательно выполнится, и в результате очередное z попадет либо в β, либо в δ. Пусть не выполнено условие (b), т. е. z не отвергается множеством βs. Это означает, что z является ν-эквивалентным некоторому элементу из βs, а поскольку в силу уже доказанного в пункте 1 мы имеем βs ⊆ β ⊆ α и α по условию ν-замкнуто, то получим z ∈ α. Далее, т. к. z ν-эквивалентно некоторому элементу из βs, то, в силу уже доказанного в пункте 3, имеем факт отвержения z множеством δs. Таким образом, в случае невыполнения условия (b) будет выполнено условие (a). Замкнутость множеств β и δ относительно ядра нумерации легко следует из пункта 3 доказанной леммы. Теорема 3.1 доказана. Таким образом, вычислимо порожденная топология на негативной системе полностью охватывает все множества, являющиеся объединениями перечислимых. Завершим подраздел достаточно «универсальным» фактом существования компактного (в различных типах топологий) бесконечного расширения любой бесконечной эквивалентности. Предложение 3.3. Всякая бесконечная эквивалентность на ω имеет такое бесконечное расширение, перечислимое (вычислимое, арифметическое) фактор-пространство по модулю которого является компактным. Доказательство. Пусть η - бесконечная эквивалентность. Обозначим через {t0 < t1 < ...} ее характеристическую трансверсаль, выписанную в порядке строгого возрастания. Положим α0 = t0/η, т. е. α0 - это смежный η-класс, содержащий число 0. Следующее утверждение представляет самостоятельный интерес. Лемма 3.2. Пусть Σ - счетное семейство η-замкнутых множеств, дополнения которых ηбесконечны. Тогда существует такое бесконечное расширение η∗ эквивалентности η, что никакое η∗-замкнутое надмножество α0 не является Σ-множеством (т. е. множеством из Σ). Доказательство. Пусть Σ = {σ0,σ1,...}. Будем строить возрастающую последовательность ηзамкнутых и η-конечных множеств δ0,δ1,... по шагам. Шаг 0. Так как σ0 является η-кобесконечным, то существуют такие k,l, что tk ∈/ σ0 ∧ tl ∈/ σ0. Выберем среди таких чисел наименьшее (tk0) и следующее после наименьшего (tl0) и определим δ0 = α0 ∪ tk0/η (сразу отметим, что tl0 никогда не попадет в строящееся объединение Шаг n + 1. Этот шаг посвящен добавлению некоторого η-класса, являющегося подмножеством с гарантированным невключением в это объединение какого-то другого η-класса, входящего в (последнее нужно, чтобы η∗ имела бесконечное число смежных классов). Пусть - все упорядоченные пары трансверсальных чисел, использовавшихся для включения (tki) в построенные σ0,...,σn. Выберем такие tkn+1 < tln+1, что оба эти числа трансверсальны, принадлежат больше всех ранее использованных. Положим δn+1 = δn ∪ tkn+1/η. Конец шага n + 1. Определим. Пусть. Конструкция обеспечивает «склейку» бесконечного числа η-классов в один η∗-класс, содержащий число t0 (= 0). При этом все η∗-классы вне множества δ совпадают с η-классами, и число этих классов бесконечно. Наконец, никакое η∗-замкнутое расширение класса t0/η∗ = δ не является Σ-расширением, т. к. δ имеет непустое пересечение с дополнением каждого σm ∈ Σ,m ∈ ω. Согласно этой лемме, например, для семейства всех η-перечислимых кобесконечных множеств можно построить такое бесконечное расширение η∗ для η, что все η-перечислимые расширения некоторого η∗-класса β будут η∗-коконечны, т. е. η∗/ω-пространство будет компактным. При этом все η-замкнутые перечислимые кандидаты на окрестности β с бесконечными дополнениями нами ликвидированы, а новым η∗-замкнутым множествам взяться неоткуда, т. к. всякое η∗-замкнутое множество является одновременно и η-замкнутым. Таким образом, фактор-пространство ω/η∗ компактно относительно топологии, порожденной перечислимыми множествами. Для вычислимо и арифметически порожденных топологий ситуация аналогичная. Следствие 3.2. Всякая бесконечная эквивалентность имеет бесконечное компактное в перечислимой топологии расширение. Пусть (A,ν) - нумерованное бесконечное множество. Всякая эквивалентность θ на множестве A индуцирует расширение η∗ нумерационной эквивалентности η = ker(ν), смежные η∗-классы которого содержат в точности те натуральные числа, чьи ν-образы равны по модулю θ, т. е. . Ясно, что естественная проекция πθ(a) = a/θ для всех a ∈ A порождает нумерацию ν∗ фактор-множества A/θ, где ν∗(x) = ν(x)/θ. При этом тождественная вычислимая функция e будет осуществлять естественный морфизм (A,ν) на его фактор (A/θ,ν∗), т. е. πθν = ν∗e. Следствие 3.3. Для всякого нумерованного бесконечного множества (A,ν) существует такая эквивалентность θ на A с бесконечным числом смежных классов, что нумерованное фактор-множество (A/θ,ν∗) (где ν∗ = πθν) является компактным. Родственные вопросы, касающиеся топологических аспектов отделимо нумерованных алгебр, можно найти в [22, 37, 45, 68, 69]. 3.3. Отделимые представления подпрямо неразложимых алгебр и алгебр с условиями минимальности для решеток конгруэнций. Апеллируя к многократно упомянутому примеру связного двоеточия, алгоритмически реализуемого невычислимым перечислимым множеством, можно заключить, что особый интерес представляют T1-отделимые нумерации, т. к. именно в этом случае наблюдается тесная связь между негативностью и сильными типами отделимости (т. е. от T2 и выше). Таким образом, для T0-отделимо нумерованных подпрямо неразложимых (с артиновыми решетками конгруэнций и, вообще, с любыми мыслимыми условиями типа конечности) алгебр вопрос об их не негативной (но обязательно эффективно отделимой!) алгоритмической реализации бессодержателен. Поэтому мы рассматриваем вопросы существования T1-отделимо нумерованных подпрямо неразложимых алгебр, а также алгебр с условиями минимальности для решеток их конгруэнций с точки зрения порождения их представлений не негативными ядрами. Заметим при этом, что всякая T1-отделимая нумерация конечного множества вычислима (т. к. каждый смежный класс вычислимо перечислим), поэтому все наши рассмотрения в случае невычислимых нумераций будут касаться бесконечных множеств. Резюмируя вышесказанное, можно отметить «вездесущесть» свойства негативности в тех случаях, когда имеют место в совокупности как сильные типы алгоритмической отделимости нумераций алгебр, так и существенные ограничения на решетки их конгруэнций. Согласно теоремам 2.3 и 2.4 всякие T1-отделимые представления как подпрямо неразложимых алгебр, так и алгебр с артиновыми решетками конгруэнций эффективно отделимы, т. е. лежат в классе Π02. Все известные примеры отделимых нумераций алгебр данных типов оказывались негативными, т. е. находились в классе Π01. Потому вопрос состоит в нахождении нумерованных алгебр указанных типов в относительно узком диапазоне между негативными (Π01-) и Π02-нумерациями. Пусть - алгебра предшествования. Выше было отмечено, что P - подпрямо неразложимая алгебра с артиновой решеткой конгруэнций. Кроме того (см. конец предыдущего раздела) всякое T2-отделимое представление алгебры P является негативным. Теорема 3.2. Существует T1-отделимая не негативная нумерация алгебры P. Доказательство см. в [43]. Таким образом, одним примером решаются два вопроса. Следствие 3.4. Существует T1-отделимо нумерованная подпрямо неразложимая алгебра, не являющаяся негативной. Следствие 3.5. Существует T1-отделимо нумерованная алгебра с артиновой решеткой конгруэнций, не являющаяся негативной. Отметим, что для любой такой нумерации ν алгебры P имеется весьма богатое семейство вычислимо перечислимых ker(ν)-замкнутых множеств (в частности, в соответствующую топологию входит не только семейство всех ker(ν)-коконечных множеств, что очевидно, но и целое семейство ker(ν)-кобесконечных множеств). Тем не менее, не существует пары нетривиальных непересекающихся вычислимо перечислимых ker(ν)-замкнутых множеств. 4. ОТДЕЛИМЫЕ ПРЕДСТАВЛЕНИЯ ГРУПП, КОЛЕЦ И ТЕЛ Фундаментальные алгебраические понятия тела и области целостности являются классическими объектами исследования как в алгебре, так и в математической логике, которая, в частности, занимается описанием алгоритмических свойств колец, заданных теми или иными нумерациями (см. [3-5, 61, 62], там же есть и библиография по теме). Важнейшими среди нумераций (представлений) этих объектов являются вычислимые, т. е. изоморфные кольцам, носителями которых являются вычислимые подмножества множества натуральных чисел, а операции сложения и умножения представлены подходящими вычислимыми операциями. 4.1. Трансляционно полные и предполные алгебры. Напомним, что унарная термальная операция с фиксированными элементами алгебры в качестве параметров называется трансляцией (А.И. Мальцев [51]). Определение 4.1. Универсальная алгебра называется трансляционно полной, если всякая пара различных ее элементов переводится в любую другую пару различных элементов подходящей трансляцией (т. е. для любыхнайдется такая трансляция t, что либо t(a) = c∧t(b) = d, либо t(a) = d ∧ t(b) = c). Очевидно, что всякая трансляционно полная алгебра является простой. Обратное неверно. Например, пусть- трехэлементный унар, на котором f действует как цикл длины 3. Очевидно, что любая трансляция этой простой алгебры имеет вид fn(x) (при n = 0 имеем тождественную функцию) и действует на A = {a0,a1,a2}, скажем, так: f(a0) = a1, f(a1) = a2, f(a2) = a0. Ясно, что любая соседняя пара элементов (т. е. вида ) переводится любой трансляцией в соседнюю же (с учетом ориентации) пару, поэтому пара не переводится никакой трансляцией в пару. Приведем простейший пример когруэнц-простого кольца, не являющегося трансляционно полным. Пусть Z3 - группа вычетов по модулю 3 аддитивной группы целых чисел . Примем ее за аддитивную группу кольца, умножение в котором определим как нулевое. Легко убедиться в том, что построенное кольцо не имеет нетривиальных идеалов и не является трансляционно полным (ср. с предыдущим примером трехэлементного унара). Детали опускаем. Определение 4.2. Универсальная алгебра называется трансляционно предполной, если существует такая пара ее различных элементов, в которую переводится любая пара различных элементов подходящей трансляцией. Трансляционная предполнота алгебры влечет ее подпрямую неразложимость (т. к. пересечение всех ненулевых конгруэнций ненулевое). Например, легко понять, что алгебра предшествования P подпрямо неразложима (любая ее ненулевая конгруэнция содержит пару ) и является трансляционно предполной. Согласно данным определениям, всякая трансляционно полная алгебра трансляционно предполна. При этом первый класс собственным образом находится во втором хотя бы потому, что трансляционно полные алгебры конгруэнц-просты, а трансляционно предполные могут простыми и не быть. Как отмечалось выше, из теоремы 2.3 следует, что всякое отделимое алгоритмическое представление любой подпрямо неразложимой алгебры (как и всякой алгебры с условием минимальности для решетки ее конгруэнций) является эффективно отделимым, т. е. находится в Π02-классе иерархии Клини-Мостовского. Пусть АРК - класс алгебр с артиновыми решетками конгруэнций и ПНА - класс подпрямо неразложимых алгебр. Алгебра предшествования P лежит в пересечении этих классов. Нетрудно показать, что обе разности между этими классами непусты. Предложение 4.1. Всякая T2-отделимая нумерация трансляционно предполной алгебры является негативной. Доказательство приведено в [39]. Идея его в следующем. Пусть (A,ν) - T2-отделимо нумерованная трансляционно предполная алгебра и пара различных элементов этой алгебры содержится в любой ее ненулевой конгруэнции. Зафиксируем ν-номера этих элементов, скажем, νm = a, νn = b. По условию существуют такие ker(ν)-замкнутые перечислимые непересекающиеся множества α и β, что m ∈ α и n ∈ β. Теперь, если через Tν обозначим перечислимое множество всех трансляций алгебры A, заданных соответствующими вычислимыми представлениями операций этой алгебры в нумерации ν, то . Как отмечалось выше, алгебра следования , являющаяся в некотором смысле «противоположной» алгебре предшествования P, имеет нетерову решетку конгруэнций (более того, всякая ее ненулевая конгруэнция имеет конечный индекс). Очевидно, что эта алгебра не является трансляционно предполной. Ясно также, что всякая позитивная нумерация алгебры S (так же как и для P) является вычислимой. В то же время, выше также отмечалось существование невычислимых негативных нумераций алгебры следования. Предыдущее предложение дает достаточное (трансляционная предполнота), но не необходимое условие негативности любого T2-отделимого представления алгебры. Покажем, что существует естественный пример простой, но не трансляционно предполной бесконечной алгебры, всякая T1отделимая (не говоря уже о T2-отделимой) нумерация которой негативна (даже вычислима!). Алгеброй Мальцева назовем алгебру, удовлетворяющую тождествам ϕ(x,x,z)=z, ϕ(x,z,z)=x, где ϕ- термальный многочлен в сигнатуре исходной алгебры [51] (алгебра из конгруэнцперестановочного мальцевского многообразия). Рассмотрим алгебру M = (ω;f), где f(x,y,z) = z при x = y и f(x,y,z) = x при Очевидно, что M - алгебра Мальцева. Предложение 4.2. Всякая T1-отделимая нумерация алгебры M является вычислимой. Доказательство см. в [44]. Заметим, что алгебра M проста и не является трансляционно предполной (т. к. любая трансляция при равенстве первых двух аргументов есть тождественная функция от третьей переменной, а при различных первых двух - константа, равная первому аргументу). Пусть M - счетно-бесконечное множество и F - система алгебраических операций на нем. Разбиение (эквивалентность) на M будем называть F-допустимым, если оно является конгруэнцией алгебры . Тривиальной операцией на любом множестве назовем функцию-константу либо проектирующую. Легко заметить, что все тривиальные операции на множестве M и только они допустимы относительно любого разбиения множества M. Квазипроектирующей функцией от n переменных на множестве M назовем такую операцию, которая на любом наборе в качестве аргумента принимает в качестве значения один из элементов данного набора, т. е. . Известно существование такой позитивной эквивалентности η (совершенной с комаксимальной характеристической трансверсалью, см. Ю.Л. Ершов [4]), над которой определимы только тривиальные алгебры (т. е. всякая операция данной алгебры есть константа или проектирующая, см. [25]). Несмотря на, казалось бы, «близость» понятий проектирования и квазипроектирования верно следующее. Предложение 4.3. Существует простая алгебра с одной трехместной квазипроектирующей операцией. Таковой будет алгебра Мальцева из предыдущего предложения. Следствие 4.1. Существует алгебра с одной трехместной квазипроектирующей операцией, всякая T1-отделимая нумерация которой вычислима. Следующее предложение постулирует трансляционную полноту для важнейшего класса алгебраических систем. Предложение 4.4. Всякое тело является трансляционно полным. Доказательство см. в [39], суть его вкратце такова. Пусть даны два произвольных различных элемента a,b тела F. Зафиксируем произвольную пару различных элементов c и d. Покажем, что существует такая трансляция λx[t(x)] тела F, которая переводит элемент a в c, а элемент b в d. Для этого определим следующее множество трансляций T(a), имеющих очень простой вид линейных многочленов: T(a) = {λx[f(x - a) + c]|f ∈ F}. Очевидно, что всякая трансляция λx[t(x)] из T(a) переводит элемент a в c. В то же время, для любого найдется единственная трансляция которая переводит элемент b в d. Ясно, что этой трансляцией будет 0 - 0 = ( - c)( - a)-1. Заметим, что аналогичным образом существует такая трансляция λx[t∗(x)] тела F, которая переводит элемент a в d, а элемент b в c. В этом случае определим множество трансляций T∗(a) = {λx[f(x - a) + d]|f ∈ F}, всякая трансляция из которого переводит элемент a в d, но для найдется единственная трансляция , которая переводит элемент b в c, и этой трансляцией будет. Теорема 4.1. Всякая эффективно невырожденная нумерация любого тела является негативной. Доказательство. Пусть F - тело, ν - его эффективно невырожденная нумерация. По условию, существует нетривиальное ν-замкнутое собственное перечислимое подмножество α ⊆ ω. Зафиксируем элементы тела Пусть теперь даны два произвольных различных элемента a,b тела F. По предыдущему предложению существует такая трансляция λx[t(x)] тела F, которая переводит элемент a в c, а элемент b в d. Таким образом, для двух элементов a,b, заданных своими номерами m,n соответственно в невырожденном представлении ν тела F с фиксированной перечислимой ν-окрестностью α элемента d тела F, не содержащей c, будем вычислять ν-номера для всех трансляций вида ν(k)(ν(n) - ν(m)) + ν(l), где l - некоторый фиксированный ν-номер элемента c, пытаясь обнаружить их во множестве α, заставляя k пробегать множество всех ν-номеров элементов тела F. Если действительно то этот факт гарантированно подтвердится через конечное число шагов перечислением в α числа k0(n - m) + l, где k0 есть некоторый ν-номер элемента, являющегося произведением мультипликативно обратного к d - c и ν(n) - ν(m). Последнее и означает негативность ν. Более формально, . Сделаем три важных замечания, касающихся почти тривиального доказательства теоремы 4.1. Во-первых, хотя в любой конгруэнц-простой алгебре всякая главная (т. е. порожденная парой различных элементов) конгруэнция «склеивает» любую пару других элементов, вовсе не факт, что найдется такая трансляция, которая переводит один из порождающих этой конгруэнции в один из «склеиваемых» элементов, а второй - в другой из «склеиваемых». В общем случае можно лишь утверждать существование конечной цепи значений подходящих трансляций, через которые и «склеиваются» все пары элементов исходной алгебры. В случае тел, по теореме 4.1, существует полное (очень богатое) семейство трансляций, позволяющее «склеивать» любую пару элементов непосредственно в качестве значений подходящей трансляции. Во-вторых, негативность всякой невырожденной нумерации ν любого тела равносильна совершенной нормальности ν-пространства, порожденного ν-замкнутыми вычислимыми подмножествами ω (см. [25]), поэтому в случае нумерованных тел, согласно теореме 4.1, вычислимые и перечислимые топологии совпадают. Очевидно, что в случае произвольных алгебр вычислимая топология вообще говоря слабее перечислимой (простейший пример - упоминавшееся ранее связное двоеточие). Наконец, в-третьих, использование трансляций, содержащих унарную операцию взятия мультипликативно обратного элемента, вообще говоря, некорректно, т. к. эта операция частична (хотя и непрерывна), и значения некоторых трансляций (образующих коперечислимое множество) при этом оказываются неопределенными (впрочем, за счет усложнения доказательства можно обойти это препятствие). Следствие 4.2. Всякая отделимая нумерация любого конечного тела является вычислимой. Действительно, в этом случае имеем негативную нумерацию конечного множества, которая является вычислимой. Следствие 4.3. Для всякой эффективно невырожденной нумерации любого тела соответствующее перечислимое пространство совершенно нормально и вполне несвязно. Известно, что если (A,ν) - вычислимо отделимая нумерованная конгруэнц-простая универсальная алгебра и τ(ν)comp-пространство нетривиально, то ν негативна (см. [25]). Поскольку всякая простая (т. е. без нетривиальных идеалов) коммутативная область целостности является полем (иначе решетка ее идеалов была бы неартиновой), то, по теореме 4.1, автоматически, всякое эффективно невырожденное представление простой области целостности негативно. Однако принципиальный вопрос о негативности эффективно невырожденного представления всякого простого коммутативного кольца (разумеется, с делителями нуля) на настоящий момент открыт. 4.2. Локально позитивные и негативные группы. Определение 4.3. Нумерация алгебры называется локально позитивной (негативной), если хотя бы один смежный класс ядра этой нумерации является перечислимым (коперечислимым). Отметим, что в то время как позитивность и негативность являются «глобальными» понятиями, подразумевающими наличие единообразной эффективной процедуры порождения нумерационной эквивалентности или, соответственно, ее дополнения, «локальность», вообще говоря, означает отсутствие такой процедуры. При этом, к примеру, число локально позитивных (негативных) эквивалентностей даже с не более чем двухэлементными смежными классами есть континуум, тогда как число позитивных (негативных) эквивалентностей счетно. Очевидно, что всякая эквивалентность с конечными смежными классами является как локально позитивной, так и локально негативной, однако ее алгоритмическая сложность может быть какой угодно. Тем не менее, свойства симметрии в группах и полях позволяют равномерно эффективно переходить от локальной позитивности (негативности) их представлений к глобальной, т. е. алгоритмы позитивности (негативности) оказываются изначально присутствующими в структурах самих этих систем, что проявляется и в свойствах их алгоритмических представлений. Предложение 4.5. Для всякой локально позитивной (локально негативной) группы любой смежный класс ее ядра является перечислимым (коперечислимым). Доказательство. Пусть (G,ν) - локально позитивная (локально негативная) группа и ∗ есть вычислимая функция, представляющая групповую операцию группы G в нумерации ν. Допустим, что смежный ker(ν)-класс, ν-отображаемый в элемент a группы G по ядру ее нумерационной эквивалентности (т. е. ν-1(a) = α) перечислим (коперечислим). Возьмем любой другой элемент группы G, скажем, b, и обозначим через ν-1(b) = β множество его ν-номеров. Зафиксируем некоторый ν-номер n элемента b-1a группы G. Очевидно, что x ∈ β ⇔ x ∗ n ∈ α, что показывает перечислимость смежного ker(ν)-класса β. В случае локальной негативности истинность утверждения следует из соотношения. Предложение 4.6. Всякая локально позитивная нумерация любой группы является позитивной. Доказательство. Пусть (G,ν) - локально позитивная группа. Согласно предыдущему предложению множество ν-номеров единицы группы e перечислимо. Обозначим это множество через α = ν-1(e). Тогда νx = νy эквивалентно тому, что найдется такое z ∈ ω, что x∗z ∈ α∧y∗z ∈ α. Следствие 4.4. Всякая локально позитивная нумерация любого кольца является позитивной. До сих пор, по умолчанию, мы рассматривали группы в сигнатуре с одной бинарной операцией. Предложение 4.7. Всякая локально негативная нумерация любой группы в сигнатуре с бинарной групповой и унарной операцией взятия обратного элемента является негативной. Доказательство. Пусть - группа с бинарной групповой операцией ∗ и унарной операцией -1 взятия обратного элемента, ν - локально негативная нумерация группы G, в которой вычислимыми представлениями операций ∗ и -1 являются × и f соответственно. Обозначим через e единицу группы G. По предложению 4.5 α = ν-1(e) коперечислимо. Очевидно, . Авторам неизвестен ответ на вопрос: «всякая ли локально негативная группа в сигнатуре с одной бинарной групповой операцией является негативной?». Если существуют локально негативные, но не негативные группы, то, в силу ряда причин, их строение должно быть весьма специфическим с алгоритмической точки зрения. Следствие 4.5. Всякая локально позитивная нумерация любого тела является вычислимой. Действительно, из локальной позитивности, а значит, согласно следствию 4.4, из позитивности тела вытекает его вычислимость (напомним, см. работу Ю.Л. Ершова [5], что всякая позитивная нумерация любой конгруэнц-простой универсальной алгебры эффективной сигнатуры вычислима). Предложение 4.8. Всякая локально негативная нумерация любого тела является негативной. Непосредственно вытекает из теоремы 4.1, т. к. локальная негативность тела обеспечивает эффективную невырожденность соответствующего ему перечислимо порожденного пространства. 4.3. Критерий эффективной вложимости области целостности в поле. А.И. Мальцевым в [50] построен знаменитый пример ассоциативного кольца без делителей нуля, не вложимого в тело. Более того, мультипликативная полугруппа построенного им кольца не вложима в группу. Эти результаты стимулировали авторов настоящей статьи к изучению вопросов эффективной вложимости колец в поля. Основная часть рассмотренных в данном разделе вопросов и понятий примыкает именно к этой проблематике. По-видимому, в литературе по абстрактной вычислимости не уделялось должного внимания тому факту, что процедура вложения коммутативной области целостности в поле своих частных по существу является эффективной. Идея конструкции поля частных для нумерованной области целостности, так же, как и в классическом случае, заключается в построении отношения эквивалентности (идеала кольца) на множествах пар номеров, вторые члены которых («знаменатели» формальных дробей) могут принимать в качестве значений все элементы перечислимого множества, являющегося дополнением нулевого элемента исходного кольца. К этой идее апеллирует и введенное выше понятие локальной негативности кольца. Теорема 4.2. Для всякой локально негативной области целостности существует негативное представление поля ее частных, в которое она эффективно вложима. Доказательство. Пусть - ассоциативно-коммутативное кольцо без делителей нуля, ν - его локально негативная нумерация, 0 - нейтральный элемент аддитивной группы кольца R, а ⊕,⊗ - вычислимые представления операций +,∗ соответственно в нумерации ν. По предложению 4.1 множество α = ν-1(0) коперечислимо. Рассмотрим канторовскую свертку перечислимого множества и назовем два числа находящимися в отношении η, если ν(l(x) ⊗ r(y)) = ν(l(y) ⊗ r(x)) (здесь l,r - вычислимые функции взятия левого, соответственно правого, члена свертки). Неформально, правый член («знаменатель») упорядоченной пары строящегося поля частных отличен от нуля исходного кольца, а левый член («числитель») - может быть каким угодно. Из классического результата о вложимости области целостности в поле частных следует, что η - отношение эквивалентности и, более того, η - конгруэнция (идеал), согласованная с операциями ⊕,⊗ кольца . Вычислимые бинарные операции поля частных обозначим через g,h, где g представляет сложение в поле частных, а h - умножение. Тогда для любых функции g,h на паре элементов a,b (здесь g(a,b) и h(a,b) обозначают l(a) = x,r(a) = u;l(b) = y,r(b) = v) действуют следующим образом: g(c(x,u),c(y,v)) = c[(x ⊗ v) ⊕ (y ⊗ u),u ⊗ v] и h(c(x,u),c(y,v)) = c[x ⊗ y,u ⊗ v]. При этом нумерованным полем частных является - проектирующее отображение, т. е. μ(x) = x/η. Детали, связанные с вычислимым отображением перечислимого множества опускаем. Локальная негативность нумерации μ поля частных очевидна, т. к. дополнением множества ν-номеров нуля кольца R в поле частных является множество , которое является собственным μ-перечислимым подмножеством ω. Из локальной негативности поля частных, ввиду эффективной невырожденности нумерации μ, согласно теореме 4.1, следует негативность поля частных. Покажем эффективную вложимость области целостности в поле частных . Для этого, прежде всего, зафиксируем в кольце R некоторый ν-номер ненулевого элемента, скажем,, такой, что νl(n) = νr(n). Очевидно, что число m = c(l(n),r(n)) есть μ-номер смежного η-класса, являющегося мультипликативной единицей поля частных (заметим, что в самом кольце R мультипликативной единицы может и не быть). Вычислимое отображение λx[f(x) = c(x,n)] осуществляет изоморфное вложение (R,ν) в поле его частных . Детали, связанные с тем, что μ-номерным множеством поля частных является не ω, а перечислимое множество, так же, как и выше, опускаем. Следствие 4.6. Всякая локально негативная область целостности негативна. Следует из эффективной вложимости локально негативной области целостности в локально негативное (а значит, по предложению 4.8, и негативное) поле. Следствие 4.7. Нумерованная коммутативная область целостности эффективно вложима в эффективно невырожденное поле тогда и только тогда, когда она негативна. Предложение 4.9. Существует позитивная область целостности, эффективно не вложимая ни в какое эффективно невырожденное поле. Доказательство см. в [39]. В некотором уточняемом ниже смысле негативные модели приоритетнее позитивных. Например, всякое позитивное поле вычислимо, тогда как любое бесконечное вычислимо представимое поле, как уже отмечалось выше, имеет невычислимую негативную нумерацию (см. [70]). 5. ЛОГИЧЕСКИЕ СПЕЦИФИКАЦИИ И АЛГОРИТМИЧЕСКИЕ ПРЕДСТАВЛЕНИЯ МОДЕЛЕЙ ДАННЫХ Продемонстрируем возможности применения понятия отделимо нумерованной системы к решению некоторых вопросов теоретической информатики, расширения класса допустимых моделей данных и структурирования эффективно реализованных моделей данных. 5.1. Алгебраические спецификации и инициальные модели квазимногообразий. Одной из основных проблем теоретической информатики является проблема адекватного описания (спецификации) модели данных (т. е. алгебраической системы, отражающей законы изучаемой предметной области) в некотором формальном языке и реализации этой модели посредством некоторого семейства алгоритмов. Решение этой проблемы сводится к следующим двум вопросам: 1. выделение в классе моделей, удовлетворяющих спецификации (т. е. моделей, в которых выполняются все законы, заданные спецификацией), некоторых «стандартных» моделей, для которых гарантированно существуют эффективные реализации; 2. выбор наиболее рациональной (в тех или иных смыслах) алгоритмической реализации длямодели спецификации. Таким образом, речь идет о существовании и единственности эффективно реализуемой модели для спецификации. Подчеркнем, что говоря об эффективной реализации, мы подразумеваем наличие алгоритмических представлений (нумераций) модели, а не «эффективность» в практическом смысле, т. к. все наши рассмотрения проводятся в рамках дескриптивной теории алгоритмов. Спецификация, как правило, есть конечный текст в некотором языке. Язык спецификаций необходимо должен быть формальным, с жесткой семантикой, не допускающей различные толкования, т. е. он должен быть логическим. Таковыми являются как математические языки описания вычислимых функций (машины Тьюринга, частично-рекурсивные функции, нормальные алгоритмы Маркова и т. д. [55]), так и практические языки программирования. Наиболее изученным, простым и удобным языком, обладающим рядом полезных свойств, является язык исчисления предикатов первого порядка [54] и различные его фрагменты. Однако уже в этом языке наблюдаются эффекты существования разнообразных и весьма нежелательных моделей, удовлетворяющих спецификации. Рассмотрение в качестве спецификаций, например, счетно-категоричных теорий (т. е. теорий с единственными с точностью до изоморфизма счетными моделями) не решает проблему, т. к. таких теорий очень мало [54]. Для произвольных теорий в языке первого порядка понятия «стандартной» модели, вообще говоря, не существует, хотя для некоторых фрагментов этого языка такое возможно. Например язык квазитождеств (или, чуть шире, универсальных хорновских предложений) в качестве используемого фрагмента языка первого порядка в полной мере удовлетворяет как требованию наличия «стандартной модели», так и эффективной реализуемости этой модели, а также единственности данной реализации. В теории спецификаций программ можно считать достаточно утвердившимся тезис о позитивной представимости любой модели данных (см. [2]). Семантика таких моделей должна адекватно определяться их синтаксическими описаниями, которые, очевидно, обязаны иметь однозначно определенную интерпретацию и механизмы генерирования фактов о свойствах моделей. При этом реализация должна не просто существовать, но и строиться единообразным алгоритмическим методом, исходя из синтаксического материала, заключенного в спецификации (т. к. другого материала для построения модели попросту нет). Универсальные хорновские предложения, являющиеся основой языков логического программирования, очень удобны в качестве языка спецификаций для моделей данных, что связано с двумя обстоятельствами: 1. всякое непротиворечивое эффективное множество универсальных хорновских предложенийимеет позитивно представимую модель; 2. семантика этой модели заключена в устройстве инициальной модели данного множествапредложений, которая всегда существует, и, более того, существует алгоритм извлечения ее эффективной реализации из синтаксического описания. Эти факты являются классическими в математической логике (см. [54]), поэтому определение границ применимости данного языка, вопросы определимости моделей в классах их гомоморфных образов (инициальная семантика- строение свободной системы соответствующего ранга), а также о числе реализаций (эффективных, поскольку ничто другое нельзя считать реализацией в рамках идеологии теоретической информатики) являются основополагающими в этой парадигме программирования. Согласно этой парадигме алгоритм должен иметь не императивный, а декларативный характер, и решение задачи должно заключаться не в описании конкретных процедур достижения цели, а в формулировке желаемой цели, при предоставлении поиска реализующей процедуры самой машине (универсальному алгоритму), предпринимающей эти попытки, исходя из синтаксического материала описания модели данных. Введем, следуя [63, 64, 67], следующее Определение 5.1. Эквациональной спецификацией называется конечное множество тождеств. В [63] доказано, что всякая вычислимо представимая конечнопорожденная алгебра конечной сигнатуры имеет обогащение, обладающее эквациональной спецификацией. Другими словами, всякая конечно порожденная алгебра конечной сигнатуры имеет обогащение, являющееся инициальной системой подходящего конечно-базируемого многообразия алгебр. Идея использования эквациональных спецификаций восходит к этим же авторам (см. [63]). Однако выразительных возможностей языка исходной сигнатуры может оказаться недостаточно для эквационального описания. Примеров такого рода (как просматриваемый стек и т. д.) было много. Рассмотрим очень простой пример. Пусть - алгебра на множестве натуральных чисел ω, 0 - константа для нуля, s - функция следования (s(x) = x + 1) и f - функция квадрата числа (f(x) = x2). Учитывая существенно большую скорость роста f относительно s, нетрудно показать, что ни для какого конечного множества тождеств E в сигнатуре факторалгебра TΣ/ ≡E (где TΣ - алгебра замкнутых термов сигнатуры Σ, а ≡E - конгруэнция, порожденная на множестве Σ тождествами E) не является изоморфной алгебре A. Обогатим сигнатуру Σ до Σ∗ = Σ∪{d,h}, добавив символы унарной d и бинарной h функций, которые интерпретируем в A как функцию удвоения d(x) = 2x и сложения соответственно. Очевидно, что следующее множество из 6 тождеств верно в A: E∗ = {d(0) = 0, ds(x) = ssd(x), h(x,0) = x, h(x,s(y)) = sh(x,y), f(x) = 0, fs(x) = s(h(f(x),d(x). Заметим, что эти тождества по существу являются примитивно рекурсивными определениями упомянутых функций. В упомянутой выше работе [63] показано, что Σ-обеднение алгебры TΣ∗/ ≡E∗ изоморфно A, и A не является инициальной алгеброй ни в каком конечно базируемом многообразии в своей сигнатуре. Отметим также важнейший, с точки зрения приложений в теоретической информатике, факт. Для любого конечного множества тождеств инициальная алгебра строится единообразным эффективным «некреативно-механическим» способом, т. к., если два слова равны в инициальной алгебре (т. е. являются логическими следствиями определяющей системы тождеств), то этот факт рано или поздно обязательно подтвердится. Однако даже если инициальная алгебра вычислима (т. е. проблема равенства слов в ней алгоритмически разрешима), то по системе тождеств не всегда можно построить алгоритм, определяющий различные слова по модулю конгруэнции, индуцированной тождествами. То есть алгоритм, конечно же, может и существовать, но автоматически сгенерировать его из синтаксического материала, содержащегося в тождествах, нельзя, что соответствует невозможности равномерно эффективного перехода от перечислимых индексов вычислимых множеств к их характеристическим индексам (см. [57, 58]). Таким образом, метод эквационального специфицирования моделей данных оказался достаточно универсальным, т. к. всякая вычислимо представимая конечно порожденная алгебра конечной сигнатуры имеет эквациональное описание. Очевидно, что всякая инициальная алгебра любой эквационально спецификации имеет позитивное представление (перечислимую проблему равенства слов, т. е. термов), но вычислимым представлением может и не обладать. Например, конечно определенная полугруппа с неразрешимой проблемой равенства слов [55]. Добавление новых операций к сигнатуре может только сузить класс алгоритмических представлений, но никак не расширить. Это поставило следующую принципиальную проблему: «Всякая ли конечно порожденная позитивно представимая алгебра имеет обогащение, являющееся инициальной алгеброй некоторого конечно базируемого многообразия?» Отрицательное решение данной проблемы предполагало нахождение таких свойств алгебр, которые, с одной стороны, «мешают» им быть инициальными в конечно базируемых многообразиях, а с другой стороны- эти свойства должны быть инвариантными относительно их позитивных представлений. Теория эффективно отделимых алгебр предоставляет такие инструменты. Из предложения 2.3 и следствия 2.2 вытекает Теорема 5.1. Существует конечно порожденная позитивно представимая алгебра, никакое обогащение которой не является инициальной системой ни в каком конечно базируемом многообразии. Доказательство. Построенная в предложении 2.3 конечно порожденная алгебра A обладает вычислимо отделимой позитивной нумерацией μ с иммунной характеристической трансверсалью tr(ker(μ)). Покажем, что всякое позитивно представимое обогащение алгебры A является финитно аппроксимируемым. Прежде всего заметим, что если A∗ - позитивно представимое обогащение алгебры A и ν - любое позитивное представление этого обогащения, то, в силу вычислимой устойчивости относительно позитивных представлений конечно порожденных алгебр, эти представления вычислимо изоморфны, т. е. существуют такие вычислимые функции f,g, что μ = νf и ν = μg. Поэтому нумерация μ, с точностью до вычислимого изоморфизма, является также позитивным представлением обогащения A∗. Как было отмечено выше, (A∗,μ) аппроксимируется негативными алгебрами ввиду справедливости основной структурной теоремы теории вычислимо отделимых алгебр: нумерованная алгебра вычислимо отделима тогда и только тогда, когда она аппроксимируется негативными алгебрами. Пусть a,b - различные элементы алгебры A∗. Тогда существуют эффективный на μ-номерах сюръективный гомоморфизм ϕa,b из (A∗,μ) на некоторую негативную алгебру (B,ξ) (в сигнатуре алгебры A∗), различающий эти элементы (т. е. ), и такая вычислимая функция h, что ϕa,bμ = ξh. Ясно, что фактор-алгебра A∗/θ(a,b) (где через θ(a,b) обозначена конгруэнция, ) изоморфна B. Рассмотрим нумерованную алгебру (A∗/θ(a,b),μ∗), где μ∗ = θ(a,b)μ, которая вычислимо изоморфна негативной алгебре (B,ξ). При этом вычислимый изоморфизм осуществляется сводящей функцией h. Т.к. μ∗(x) = μ∗(y) ⇔ ξh(x) = ξh(y), а ξ - негативная, то и μ∗ также негативна. Теперь заметим, что ker(tr(μ∗)) ⊆ ker(tr(μ)), т. к. если эквивалентность η0 расширяется эквивалентностью η1, то характеристическая трансверсаль расширения η1 является подмножеством характеристической трансверсали расширяемой эквивалентности η0. Но ker(tr(μ) иммунна, а ker(tr(μ∗)) перечислима (т. к. μ∗ негативна). Следовательно, ker(tr(μ∗)), а значит и B конечна. Таким образом, A∗ финитно аппроксимируема. Именно алгебра A и является примером конечно порожденной позитивно представимой алгебры, никакое позитивно представимое обогащение которой не является инициальной ни в каком конечно базируемом многообразии. Предположим противное. Пусть A∗ - позитивно представимое обогащение алгебры A, инициальное в конечно базируемом многообразии, заданном конечной системой тождеств E. Через TΣ обозначим множество всех замкнутых термов конечной сигнатуры Σ обогащения A∗. Инициальность означает свободу ранга 0, т. е. A∗ порождена сигнатурными константами. Ясно, что A∗ изоморфна TΣ/ ≡E, где ≡E - конгруэнция на абсолютно свободной алгебре термов TΣ, порожденная системой тождеств E, т. е. A∗ |. Очевидно, что для любой конечной Σ-алгебры B, порожденной Σ-константами можно эффективно проверить, выполняется ли E в B или нет. Ясно также, что для всякого n ∈ ω имеется конечное число типов изоморфизма порожденных константами Σ-алгебр мощности n. Поэтому множество типов изоморфизма конечных Σ-алгебр, порожденных константами и принадлежащих многообразию M, порожденному системой E, является алгоритмически разрешимым. Если A∗ |= t1 = t2, то этот факт подтвердится через конечное число шагов в силу позитивности инициальной системы любого эффективно аксиоматизируемого многообразия. Если же , то, в силу финитной аппроксимируемости A∗, в последовательности конечных Σ-алгебр из многообразия M обязательно найдется такая конечная Σ-алгебра B, порожденная константами, в которой, т. е. A∗ негативна, а значит, и разрешима, что невозможно, т. к. A∗ не имеет разрешимых представлений. Противоречие. Отметим очень важный момент в доказательстве этой теоремы. Если, например, речь идет об инициальности в конечно базируемом квазимногообразии Q, заданном конечной системой квазитождеств QE, то метод не проходит, т. к. гомоморфные образы инициальной алгебры квазимногообразия не обязаны находиться в классе Q, поскольку квазитождества не являются устойчивыми относительно гомоморфизмов. Однако, как будет показано далее, в некоторых случаях возможно обобщение данного результата на более широкие классы формул, которые устойчивы относительно гомоморфизмов специальных видов. Далее под словом «спецификация» будем понимать вычислимо перечислимое множество предложений логики первого порядка. Спецификацию назовем хорновской (универсальной, экзистенциальной, индуктивной и т. д.), если каждое предложение из нее есть предложение хорновское (соответственно универсальное, экзистенциальное, индуктивное и т. д.). Определение 5.2. Бескванторная формула называется дизъюнктивно-импликативно-позитивной (ДИП-формулой), если она имеет один из следующих трех видов: 1. A1 ∨ ... ∨ An → Φ, 2. A1 ∨ ... ∨ An → F, 3. Φ, где Ai - атомарные, Φ- позитивная формулы, а F - «ложь». ДИП-формулами являются, в частности, конъюнкции отрицаний атомарных (случай 2), позитивные формулы (случай 3), а также бескванторные части однопосылочных квазитождеств вида A1 → B (при n = 1 и атомарности Φ). Универсальное замыкание ДИП-формулы называется универсальным ДИП-предложением. Негативные модели, опять-таки, образуют важный класс равномерно вычислимо отделимых моделей (см. [25]). Предложение 5.1. Для нумерованной модели (M,ν) равносильны следующие условия: 1. (M,ν) - равномерно вычислимо отделимая модель; 2. если Φ- перечислимое множество универсальных ДИП-предложений, реализующееся в M, то (M,ν) равномерно аппроксимируется негативными Φ-моделями (т. е. негативными моделями, в которых реализуется Φ). Доказательство см. в [23, 38]. Важность универсальных ДИП-формул для равномерно вычислимо отделимых моделей с точки зрения аппроксимируемости связана с тем, что если универсальное ДИП-предложение истинно в модели, но на каком-то наборе ложна правая часть, то на этом наборе ложна и левая часть, т. е. ни один из атомарных дизъюнктивных членов левой части не может быть истинным и, следовательно, каждый из них можно «расщепить» с помощью алгоритма равномерной отделимости. Процесс итерируется. При этом, если, скажем, значения какой-то операции попадают в разные классы, а аргументы остаются «склеенными», то эти аргументы «расклеиваются», причем эту процедуру можно выполнять через трансляции (согласованность которых определяется однопосылочными квазитождествами, т. е. ДИП-предложениями). Предельная конструкция будет негативной конгруэнцией, в факторе по которой реализуется исходное множество ДИП-предложений. Заметим, что уже для квазитождеств вида A∧B ⇒ C (не являющихся ДИПпредложениями) указанная процедура не работает, т. к. если C ложно на некотором наборе, то на этом наборе не могут одновременно реализовываться и A, и B, однако, вообще говоря, нельзя определить, который из двух конъюнктивных атомарных членов в действительности ложен. В формулировке этой теоремы нельзя заменить универсальные ДИП-предложения произвольными универсальными и экзистенциальными ДИП-предложениями, так же, как нельзя опустить условие равномерности (см. [23]). Предложение 5.2. Существует конечно порожденная равномерно вычислимо отделимая позитивная модель с иммунной характеристической трансверсалью. Общий метод построения таких моделей приведен в [23, 25]. Теорема 5.2. Существует конечно порожденная позитивно представимая алгебра конечной сигнатуры, никакое обогащение которой не является инициальной системой ни в каком конечно базируемом многообразии (квазимногообразии, задаваемом однопосылочными квазитождествами, позитивном классе). Доказательство см. в [23]. По поводу этой теоремы отметим, что она существенно обобщает теорему 5.1 и позволяет частично преодолеть трудности, связанные с неустойчивостью формул того или иного вида относительно гомоморфизмов. Таким образом, выразительная мощность естественных фрагментов языка логики предикатов первого порядка с хорошими интерпретациями оказывается недостаточной для адекватного алгебраического описания класса всех моделей данных. Если (M,ν) - нумерованная модель, то через Mν, будем обозначать следующее обогащение модели M счетным множеством констант, каждая из которых не принадлежит сигнатуре модели M: νn = cn. Модель Mν будем называть стандартным ν-обогащением модели M. Далее нумерованная модель (M,ν) и обогащение Mν модели M будут отождествляться, поскольку в рассматриваемых нами случаях эти представления вычислимо эквивалентны. Пусть (M,ν) - позитивная модель, Φ - универсальная хорновская спецификация в сигнатуре модели M, реализующаяся в M. Тогда, очевидно, Φ реализуется и в Mν. Известно (см. [25]), что если Φ не реализуется ни в каком эффективном гомоморфном образе модели Mν, то ν - вычислимая нумерация. Другими словами, если (M,ν) - позитивная невычислимая модель и Φ - универсальная хорновская спецификация, реализующаяся в M, то в классе Φ-моделей содержатся собственные позитивно представимые гомоморфные образы M. Следовательно, никакую позитивную невычислимую модель нельзя выделить в классе ее собственных позитивных гомоморфных образов никакой универсальной хорновской спецификацией. Известно также, что никакую позитивную невычислимую модель нельзя выделить в классе ее собственных гомоморфных образов никакой универсальной спецификацией (см. [12]). Сказанное выше поставило проблему определения тонкой грани (если она существует) между выразительными возможностями универсальных хорновских и универсальных спецификаций в рамках проблемы определимости модели в классе ее гомоморфных образов (проблема № 13 из [25]). Иначе говоря, можно ли в принципе выделить позитивную невычислимую модель в классе ее собственных эффективных гомоморфных образов подходящей универсальной спецификацией? Теорема 5.3. Существует позитивно представимая модель M, не обладающая вычислимыми представлениями, которая выделяется в классе своих собственных позитивно представимых гомоморфных образов подходящей универсальной спецификацией. Доказательство см. в [38]. Уникальность модели из теоремы 5.3 демонстрирует следующий факт. Следствие 5.1. Существуют позитивно представимая модель M и ее универсальная спецификация Φ со следующими свойствами: • M не имеет вычислимого представления; • всякая позитивно представимая Φ-модель, построенная из констант, изоморфна M; • M изоморфно вложима во всякую позитивно представимую Φ-модель. Заметим, что теорему 5.3 можно усилить. Следствие 5.2. Существует позитивно представимая модель, не обладающая вычислимыми представлениями, которая выделяется в классе своих собственных позитивно представимых гомоморфных образов подходящей бескванторной спецификацией. Очевидно, что такая спецификация не может быть хорновской. Таким образом, язык универсальных спецификаций оказывается существенно богаче языка универсальных хорновских предложений с точки зрения возможности адекватного описания эффективно представимых моделей. 5.2. Позитивные и негативные упорядоченные модели данных в рамках теоретической информатики. Общеизвестно, что всякое позитивное представление стандартной модели арифметики в сигнатуре обозначает множество натуральных чисел, а Σ-символы имеют очевидные естественные интерпретации) является вычислимым (см., например, [5]). Более того, вычислимы также любые позитивные представления обеднений Ω0, Ω1,Ω2 модели Ω в обедненных сигнатурах соответственно (заметим, что Σ1 является языком арифметики Пресбургера, а Σ2 - арифметики Пеано). Более того, любая пара позитивных представлений этой модели вычислимо изоморфна, т. е. Ω вычислимо устойчива относительно позитивных реализаций. Менее известен тот факт, что Ω обладает негативными невычислимыми представлениями (см. [70]). В теоретической информатике под реализационной полнотой некоторой «стандартной» модели программной спецификации понимается единственность позитивного представления этой модели, т. е. вычислимая изоморфность всех позитивных представлений упомянутой модели (см. [5]). С этой точки зрения стандартная модель арифметики Пеано не является реализционно полной относительно ее негативных представлений, поскольку имеется как минимум два негативных представления - общеизвестное вычислимое и негативное невычислимое. Следуя [2], под упорядоченной арифметикой будем понимать теорию первого порядка в сигнатуре обозначает константный символ, s - символ унарной операции, + и ∗ - имена бинарных операций, а - символ бинарного отношения), заданную следующими множеством AxGon аксиом: A1 (∀xy)(s(x) = s(y) ⇒ x = y); A2 A3 )); A4 (∀x)(x + 0 = x); A5 (∀xy)(x + s(y) = s(x + y)); A6 (∀x)(x ∗ 0 = 0); A7 (∀xy)(x ∗ s(y) = x ∗ y + x); A8 )); A9 )); A10 Φ(0) ∧ (∀x)(Φ(x) ⇒ Φ(s(x)) ⇒ (∀x)(Φ(x)), где Φ(x) - произвольная формула сигнатуры Σ с одной свободной переменной x (схема аксиом математической индукции). Под стандартной моделью упорядоченной арифметики понимается классическая модель арифметики , где ω обозначает множество натуральных чисел, а Σ-символы имеют очевидные естественные интерпретации. Заметим,что первые три аксиомы описывают инъективную функцию следования (A1) без неподвижных точек (A2), областью значений которой является все основное множество, кроме константы 0 (A3). Аксиомы с A4 по A7 задают примитивно рекурсивные определения функций сложения и умножения. A8 определяет согласованность сложения с отношением , являющимся линейным порядком, что постулируется A9. Наконец, A10 задает бесконечную, но вычислимую группу аксиом, позволяющих доказывать предложения в аксиоматической системе AxGon методом математической индукции, основанной на простейшем порядковом типе первого бесконечного ординала ω. В рамках сигнатуры Σ, являющейся ограничением сигнатуры Σ упорядоченной арифметики на сигнатуру арифметики Пеано, как уже отмечалось выше, существуют различные (вычислимо неизоморфные) алгоритмические представления. Однако оказалось, что всякое негативное представление стандартной модели упорядоченной арифметики в сигнатуре Σ является вычислимым (см. [33]), т. е. все алгоритмические представления стандартной модели упорядоченной арифметики, ядра нумераций которых принадлежат классу Σ01 ∪ Π01, являются вычислимо изоморфными. Другими словами, для стандартной модели упорядоченной арифметики существует единственная алгоритмическая реализация в классе как позитивных, так и негативных представлений. Предложение 5.3. Всякая негативная нумерация стандартной модели Ω теории AxGon является вычислимой. Доказательство. Пусть ν : ω → Ω - негативная нумерация стандартной модели - вычислимая функция, представляющая операцию s в нумерации ν, т. е. ∀x(sν(x) = νf(x)). По условию множество является перечислимым. Обозначим через sk(0) выражение s...s(0), в котором функциональный символ s встречается ровно k раз, зафиксируем m ∈ ν-1(0) и определим строгий линейный порядок , индуцированный порядком : Очевидно, что порядок < является ν-перечислимым. Достаточно показать позитивность ν. Ясно, что x = y ⇔ ∃k ∈ ω(fk(m) < x < fk+2(m) ∧ fk(m) < y < fk+2(m)). Следовательно, нумерация ν является вычислимой. Покажем позитивность порядка в нумерации ν. В самом деле,. Так как правая часть равносильности перечислима, то является ν-позитивной, а значит, и ν-вычислимой. Этот факт обуславливает целесообразность введения в рассмотрение дискретно упорядоченных структур, что существенно расширяет класс используемых моделей данных с сохранением единственности алгоритмической реализации. Рассмотрим упорядоченное унитарное кольцо в сигнатуре (предполагается выполнение условия согласованности кольцевых операций с линейным порядком). Допустим, что упорядочено отношением по типу целых чисел Z. Тогда верна Теорема 5.4. Всякое негативное представление кольца вычислимо, и любая пара таких представлений вычислимо изоморфна. Доказательство см. в [33]. С другой стороны, очевидно, что всякое позитивное представление такого кольца также вычислимо и все его вычислимые представления вычислимо изоморфны. Таким образом, введение согласованного линейного порядка для широкого класса естественных колец гарантирует единственность эффективного представления как в классе позитивных, так и негативных представлений. Следствие 5.3. Всякое негативное представление модели Ω вычислимо. Следствие 5.4. Модель Ω имеет единственное негативное представление. Следствие 5.5. Стандартная модель Ω теории AxGon вычислимо устойчива как относительно позитивных, так и относительно негативных представлений. Следствие 5.6. Стандартная модель Ω теории AxGon реализационно полна в классе позитивных и негативных представлений. Замечание 5.1. В теоретическом программировании одной из ключевых задач является проблема единственности эффективной реализации абстрактной модели данных, т. е. эквивалентности (=вычислимой изоморфности) различных реализаций некоторой стандартной модели для заданной спецификации. Под эффективным представлением модели обычно понимается позитивное. Однако негативные представления порой несут не менее важную семантическую информацию о свойствах стандартной модели спецификации (обоснования этого тезиса см. в [2, 25, 31, 38]), поэтому представляется целесообразным рассматривать в качестве представлений модели данных ее алгоритмические представления и в других нижних классах иерархии Клини-Мостовского. Одним из уточнений такого подхода является рассмотрение в качестве алгоритмических представлений не только позитивных, но и негативных. В рамках такого подхода стандартная модель арифметики Пеано (тем более, арифметики Пресбургера), как отмечено выше, не является реализационно полной. Тем не менее, при добавлении естественного порядка, реализационная полнота (как относительно позитивных, так и негативных представлений) может иметь место. Нумерованная модель называется отделимой, если всякая точка ложности любого отношения имеет перечислимую (в данной нумерации) окрестность, не пересекающуюся с областью истинности этого отношения. Если семейство отделяющих множеств имеет вычислимую нумерацию (т. е., неформально говоря, его можно задать посредством некоторого перечислимого множества перечислимых индексов), то нумерация называется эффективно отделимой. Наконец, равномерно эффективная отделимость означает, что по точке ложности отношения можно эффективно построить перечислимый индекс такой ее окрестности, которая не содержит точек истинности данного отношения. Эффективная отделимость предполагает наличие перечислимой окрестности из некоторого вычислимого семейства окрестностей, в то время как равномерно эффективная отделимость позволяет явно строить эти окрестности имея точки ложности. Покажем, что позитивные и негативные линейные порядки представляют собой классические образцы отделимых моделей. Предложение 5.4. Позитивные и негативные линейные порядки являются равномерно эффективно отделимыми. Доказательство. Пусть - позитивный линейный порядок. Допустим, что Тогда, в силу линейности порядка, имеет место μb < μa, где < - строгий порядок, индуцированный рефлексивным порядком на L. Рассмотрим множество упорядоченных пар , которое, очевидно, μ-замкнуто и перечислимо. По построению в μα нет точек истинности и Ясно также, что по данной паре отделяющее множество α строится равномерно эффективно. Эффективная отделимость ядра представления ker(μ) следует из предложения 3.2. Пусть теперь - негативный линейный порядок. Тогда ядро ker(μ), по предложению 3.2, эффективно (даже вычислимо) отделимо. Обозначим через γ множество, т. е. γ - μ-перечислимое дополнение порядка в нумерации μ. Заметим, что в этом случае строгий порядок < будет перечислимым, т. к. Пусть тогда μb < μa. Если между μb и μa есть пара различных соседних элементов (т. е. между которыми нет элементов порядка ), скажем, и , то сечение B|A, где B = x| является перечислимым (даже вычислимым, т. к. B ∪ A = ω ∧ B ∩ A = ∅), строится равномерно по a,b и a ∈ A ∧ b ∈ B. Тогда вычислимым расширением точки ложности порядка будет μ-вычислимое множество μ(A) × μ(B), которое, очевидно, не пересекается с областью истинности порядка . Если же между μb,μa соседних элементов нет, то интервал {μx|μb < μx < μa} упорядочен отношением по типу рациональных чисел. В этом случае, используя вычислимые строго возрастающие (убывающие) фундаментальные последовательности Коши, можно построить такое вычислимое сечение B|A, для которого в B нет наибольшего элемента, а в A - наименьшего и b ∈ B ∧ a ∈ A (см. [32]). Тогда μ(A)×μ(B), опять-таки, является даже вычислимым расширением точки μa,μb, не пересекающимся с областью истинности порядка на L. С некоторыми другими фактами об эффективно отделимых линейных порядках (в т. ч. об их вычислимо необратимых автоморфизмах, соотношениях между предельными точками порядков и алгоритмическими свойствами эквивалентностей, над которыми эти порядки определимы) можно ознакомиться в [27-30, 33, 40, 42]. 5.3. Степени представимости алгебраических систем. Здесь будут изучаться не тьюринговы степени представимости структур, а специфические степени, образованные эквивалентностями и отражающие потенциалы различных эквивалентностей для представлений над ними алгебраических систем. С точки зрения представимости систем над эквивалентностью «первичным» фиксированным понятием является эквивалентность (что порождает проблему описания общих свойств всех систем, представимых над заданной эквивалентностью), в то время как в рамках теории нумерованных систем основной объект есть сама система, по отношению к которой все ее нумерации «вторичны» (соответственно, в этом случае основная проблематика - описание свойств нумераций с теми или иными качествами и соотношений между ними). Однако эти понятия двойственны, что мы и будем использовать в дальнейшем без каких-либо ограничений и оговорок, если из контекста будет явно вытекать то, что имеется в виду (см. [10, 25]). Далее в качестве допустимых моделей мы будем понимать линейно упорядоченные модели. Важнейшими типами эффективно отделимых (даже равномерно эффективно отделимых, см. предложение 3.2) линейных порядков являются позитивные и негативные. При этом негативные модели в определенном смысле даже более предпочтительны, чем позитивные, что обуславливается по меньшей мере тремя причинами. Во-первых, согласно [65] существует линейный порядок, обладающий позитивным представлением, но не имеющий вычислимой реализации. С другой стороны, классическим фактом является то, что для всякого негативно представимого линейного порядка существует его вычислимое представление (см. [4]). Напомним (см. определение 1.2), что линейный порядок называется определимым над позитивной (негативной) эквивалентностью η, если существует такая позитивная (соответственно негативная) нумерация ν : ω → L этого порядка с перечислимым (коперечислимым) ядром ker(ν) = η, что множество обозначает представление порядка в нумерации ν) является перечислимым (соответственно коперечислимым). Замечание 5.2. При этом позитивная определимость линейного порядка над негативной эквивалентностью (равно как и негативная определимость линейного порядка над позитивной эквивалентностью) автоматически влечет вычислимость как отношения эквивалентности, так и отношения порядка (см. [32]). Поэтому далее мы рассматриваем лишь содержательные случаи, неявно предполагая позитивную определимость линейного порядка над позитивной же эквивалентностью (соответственно, негативную определимость линейного порядка над негативной эквивалентностью). Второе важное наблюдение состоит в следующем. Существует такая позитивная эквивалентность, над которой вообще не определим никакой линейный порядок (см. [32]). Для негативных эквивалентностей ситуация диаметрально противоположная: Над всякой негативной эквивалентностью определим линейный порядок. Более того, над всякой бесконечной негативной эквивалентностью определимы все типы изоморфизмов плотных линейных порядков (и не только они! - см. [32]). В-третьих, существует такая позитивная эквивалентность η, над которой определим порядковый тип рациональных чисел, однако множество вычислимых нетривиальных дедекиндовых сечений этого порядка пустое (более того, вычислимая η-топология тривиальна, а перечислимая- дискретна, см. [71]). Над всякой же бесконечной негативной эквивалентностью не только определим линейный порядок, изоморфный порядку рациональных чисел, но и множество вычислимых сечений данного порядка «эффективно неисчерпаемо», т. е. для всякого «вычислимого» (в смысле Ю.Л. Ершова [4]) семейства вычислимых сечений (заданного некоторым алгоритмом перечисления индексов этих сечений) данного нумерованного порядка можно «некреативно-механически» построить алгоритм разрешения некоторого вычислимого сечения, находящегося вне данного семейства (см. [32]). Это свойство есть не что иное, как вариант теоремы Геделя о неполноте, сформулированной им для арифметики (о продуктивности множества арифметических истин; см., например, [57]). Для полноты картины повторим в тезисной форме важнейшие факты о продуктивности, приведенные в [32]. Факт эффективной реализуемости плотных линейных порядков над любой бесконечной негативной эквивалентностью особо значим как на фоне отмеченного выше утверждения о существовании бесконечных позитивных эквивалентностей, над которыми вовсе не представимы никакие линейные порядки, так и в свете следующего предложения о существовании богатых семейств вычислимых сечений негативных плотных порядков. Предложение 5.5. Для любого негативного плотного линейного порядка существует эффективная процедура, сопоставляющая всякой паре различных элементов этого порядка вычислимую щель, отделяющую эти элементы. Доказательство см. в [32]. Таким образом, в негативных плотных линейных порядках для любой пары различных элементов отделяющая их вычислимая щель не просто существует, но, более того, разрешающий алгоритм соответствующей щели дается равномерно эффективной процедурой по данной паре элементов. Дадим точное определение вычислимого семейства вычислимых сечений негативного линейного порядка. Пусть χ - фиксированная вычислимая нумерация семейства всех одноместных частично вычислимых функций. Например, если k - бинарная клиниевская функция, универсальная для класса унарных частично вычислимых функций (т. е. семейство одноместных частично вычислимых функций есть множество объектов {λx.k(x,n)|n ∈ ω}), то можно положить χ(n) = λx.k(x,n). Следующие определения содержат неизбежные коллизии, возникающие при различных толкованиях вездесущего прилагательного «вычислимый», о чем было упомянуто выше. Определение 5.3. Нумерация γ семейства вычислимых сечений негативного линейного порядка называется вычислимой, если существует такая вычислимая функция f, что γ = χf (т. е. по любому γ-номеру сечения эффективно определяется некоторый его χ-номер, являющийся индексом характеристической функции нижнего класса данного сечения). Семейство вычислимых сечений негативного линейного порядка называется вычислимым, если существует его вычислимая нумерация. Неформально, вычислимость семейства вычислимых сечений означает перечислимость алгоритмов разрешения для сечений данного семейства. Назовем семейство вычислимых щелей негативного линейного порядка относительно полным, если любая пара различных элементов этого порядка отделяется подходящей щелью из данного семейства. Следствие 5.7. Для всякого негативного плотного линейного порядка существует вычислимая (даже негативная) нумерация относительно полного семейства вычислимых щелей. Доказательство см. в [32]. Перечисляя множество всех пар различных по модулю негативной эквивалентности натуральных чисел и сопоставляя каждой такой паре индекс характеристической функции нижнего класса отделяющей их щели, получим искомую вычислимую нумерацию. В действительности, всякая такая вычислимая нумерация будет негативной, т. к. для двух различных сечений гарантированно найдется элемент, принадлежащий верхнему классу для одного из этих сечений и нижнему классу - для другого. Детали опускаем. В связи с существованием относительно полной системы отделяющих вычислимых щелей, задаваемой равномерно эффективной процедурой, возникает естественный и принципиальный вопрос об алгоритмической природе совокупности всех вычислимых сечений негативного плотного линейного порядка. Определение 5.4. Семейство вычислимых сечений нумерованного линейного порядка называется продуктивным, если существует эффективная процедура, позволяющая по каждому вычислимому подсемейству строить вычислимое сечение из. Теорема 5.5. Семейство всех вычислимых сечений негативного плотного линейного порядка является продуктивным. Доказательство см. в [32]. Следствие 5.8. Множество всех вычислимых сечений произвольного негативного плотного линейного порядка не является вычислимым. Как отмечалось выше, понятие представимости (определимости) алгебраической системы над эквивалентностью η над ω оказалось полезным для решения ряда задач логики и теоретического программирования. Мы хотим ввести на фактор-множестве множества отделимых эквивалентностей по модулю отношения «реализовывать равнообъемные классы моделей данных» частичный порядок, который неформально можно интерпретировать как «степень универсальности эквивалентности» с точки зрения возможности определения над ней различных моделей данных. Каждый такой класс эквивалентных эквивалентностей (по модулю равнообъемности определимых над ними классов моделей данных) будем называть степенью представимости моделей данных или, если ясно из контекста, просто степенью представимости. Продемонстрируем введенное понятие на примере негативных и позитивных линейных порядков. Для негативной эквивалентности η обозначим через L(η) класс всех линейных порядков, негативно представимых над η. На множестве негативных эквивалентностей на ω введем следующее бинарное отношение NLO: . Очевидно, что NLO является предпорядком (т. е. рефлексивным и транзитивным отношением) на множестве всех негативных эквивалентностей на ω. Тогда его симметричное замыкание ≡NLO есть эквивалентность, факторизация по которой разбивает множество всех негативных эквивалентностей на ≡NLO-классы эквивалентности. Содержательно, ≡NLO-эквивалентность двух эквивалентностей означает совпадение представимых над ними классов порядковых типов. Если Π - семейство всех негативных эквивалентностей, то на Π/≡NLO действует частичный порядок, индуцированный предпорядком NLO, который мы будем обозначать так же (корректность очевидна). Частично упорядоченное множество будем называть структурой негативной представимости линейных порядков, а его элементы- степенями негативной представимости линейных порядков. Далее, если будет ясно о чем идет речь, структуру негативной представимости линейных порядков будем называть просто структурой негативной представимости, а ее элементы- степенями. Для сокращения обозначений через d(η) будем обозначать степень эквивалентности η. Будем также говорить, что линейный порядок представим над заданной степенью, если он представим над некоторой (а значит, и над любой) эквивалентностью из этой степени. Строение структуры негативной представимости линейных порядков отражает алгоритмическую природу эквивалентностей с точки зрения предоставляемых возможностей для реализации над ними важных объектов, каковыми являются линейные порядки. Ясно, что чем NLO-выше расположена степень, тем больше реализационных возможностей она предоставляет. Такой подход может оказаться также полезным в рамках теоретической информатики. Отметим, что конечные негативные эквивалентности (которые в данном случае, очевидно, будут вычислимыми) порождают изолированные степени в структуре негативной представимости, т. к. если число классов эквивалентности есть n, то над ней представим только порядковый тип, изоморфный конечному ординалу n. Отбросив все ≡NLO-классы, порожденные конечными эквивалентностями, получим ограничения отношений NLO,≡NLO на бесконечные негативные эквивалентности. Всюду далее нас будет интересовать только структура, образованная степенями, содержащими бесконечные эквивалентности. Пусть Σ - множество бесконечных позитивных эквивалентностей, и отношение на Σ означает, что всякий линейный порядок, позитивно представимый над η1, позитивно представим и над η2. Совершенно аналогично негативному случаю, путем симметричного замыкания предпорядка и факторизации относительно полученного отношения эквивалентности на множестве всех бесконечных позитивных эквивалентностей, получим структуру позитивной представимости линейных порядков, которая оказалась совершенно отличной от структуры негативной представимости линейных порядков. Так, в структуре позитивной представимости имеется бесконечная позитивная степень, над которой не определим никакой линейный порядок (т. е. соответствующий класс порядков пустой и данная степень - наименьшая относительно NLO, см. [32]), в то время как над любой бесконечной негативной степенью представим плотный порядок. Изучению структуры посвящена работа [66], в которой, в частности, показано, что эта структура не имеет наибольшего элемента, но имеет максимальный (им будет степень d(id ω)), существует бесконечно убывающая цепь позитивных степеней и имеются несравнимые степени (аналог теоремы Фридберга-Мучника). Некоторые принципиальные вопросы, рассмотренные в работе [66], являются в настоящий момент открытыми для структуры . Относительно структуры на настоящий момент известно следующее. Предложение 5.6. Структура негативной представимости линейных порядков имеет наибольший элемент. Доказательство вытекает из отмеченного выше почти очевидного факта, что всякий негативно представимый линейный порядок имеет вычислимую нумерацию. Таким образом, всякий негативно представимый бесконечный линейный порядок представим над степенью idω/≡NLO, которая и является наибольшей в структуре негативной представимости. Еще раз подчеркнем (см. [65]), что наличие позитивного представления линейного порядка вовсе не влечет существование его вычислимого представления. Предложение 5.7. Существует бесконечно убывающая цепь степеней негативной представимости линейных порядков. Доказательство см. в [32]. Следствие 5.9. Структура бесконечных степеней негативной представимости линейных порядков содержит множество степеней, упорядоченное по типу 1 + ω∗. Многие принципиальные вопросы, касающиеся структуры, в настоящий момент открыты. Например, • существуют ли две несравнимые ≡NLO-степени (аналог проблемы Поста о существовании несравнимых тьюринговых степеней, см. [57])? • существует ли в наименьший элемент? • разрешима ли элементарная теория структуры ? • и ряд других. Каждый из этих вопросов обладает емким содержанием. Например, положительный ответ на первый вопрос означал бы, что имеются две существенно различные степени (реализации), над каждой из которых принципиально нельзя алгоритмически определить некоторый негативно представимый линейный порядок, определимый над другой. Существование наименьшего элемента означало бы наличие некоторого «общего знаменателя» для степеней с точки зрения реализуемости порядков, т. е. все, что реализуется над наименьшей степенью, реализуется и над любой другой. Вместо линейных порядков можно также рассматривать другие объекты, в т. ч. универсальные алгебры (не фиксируя сигнатуру), которые широко используются в абстрактных типах данных и объектно-ориентированном программировании. Так, например, как уже отмечалось, над любой негативной эквивалентностью представима конечно-порожденная конгруэнц-простая алгебра [24], тогда как существуют позитивные эквивалентности, над которыми представимы только тривиальные структуры [25] (заданные проектирующими функциями и функциями-константами, которые, очевидно, представимы над любой эквивалентностью). С другой стороны, разумные расширения класса рассматриваемых эквивалентностей также позволяют получать структуры с содержательными свойствами. Так, для эффективно отделимых эквивалентностей (которые содержат и негативные, и позитивные) соответствующая структура весьма богата. Пусть Ω - множество эффективно отделимых эквивалентностей. Очевидно, что Ω счетно, хотя множество отделимых эквивалентностей имеет мощность континуума. Рассмотрим структуру , где для γ1,γ2 ∈ Ω отношение означает, что всякая универсальная алгебра (конечной сигнатуры), представимая над γ1, представима и над γ2, и ≡ES обозначает эквивалентное замыкание предпорядка ES. Такой подход ближе по духу к парадигме объектно-ориентированного программирования, когда над одним носителем можно вводить новые операции, не фиксируя язык (сигнатуру) системы (см. [25, 63, 64]), хотя в нашем определении ES-сводимости мы не требуем конечной порожденности. Всякая подпрямо неразложимая алгебра и алгебра с артиновой решеткой конгруэнций, обладающая отделимой нумерацией, представима над некоторой ≡ES-степенью, т. к. согласно следствию 2.7 и теореме 2.4 любое такое представление эффективно отделимо. Все бесконечные позитивные и негативные эквивалентности лежат в некоторых ≡ES-степенях. При этом в имеется наименьший элемент d(γ) (где γ - бесконечная позитивная эквивалентность, над которой определимы только функции-константы и проектирующие, см. замечание перед следствием 2.5). Можно показать, что в частичный порядок изоморфно вкладывается ординал ω + 1. Приведем идею доказательства. Пусть η0 - бесконечная позитивная эквивалентность, по модулю которой всякая вычислимая функция f, согласованная с ней (т. е. ∀x,y[x = y (mod η0) ⇒ f(x) = f(y) (mod η0)]), действует либо как константа, либо как проектирующая. О существовании такой эквивалентности упоминалось в предыдущем абзаце. Через η1 обозначим эквивалентность где s(x) = x + 1, т. е. η1 - фактически есть «расширение» η0 одним разрешимым η1-классом, содержащим одноэлементный класс, состоящим из числа 0. Нетрудно заметить, что всякая алгебра, определимая над η0, определима и над η1, но не наоборот, т. к., например, над η1 определима вычислимая функция, не действующая на η1-классах ни как константа, ни как проектирующая. Рассмотрим взаимоотношения ≡ES-степеней для эквивалентностей ηn+1 и ηn+2 в случае одноместных функций. Для этого разобьем ω на две вычислимые ηn+1-замкнутые части- A = {0,... ,n} и B = ω \{0,... ,n}, т. е. A - совокупность всех тривиальных классов эквивалентности ηn+1. Эти же множества являются объединениями ηn+2-замкнутых классов, но в этом случае одноэлементный класс (n+1)/ηn+2 оказывается включенным в множество B. Покажем, что для всякой одноместной вычислимой функции, согласованной с ηn+1, найдется такая вычислимая функция g, согласованная с ηn+2, что алгебры изоморфны (с точностью до обозначения операций). В самом деле, рассмотрим действие функции f по модулю ηn+1. Ограничение f на A можно изоморфно перенести в качестве действия g на A очевидным образом. Есть лишь один нетривиальный момент- когда значение f на каких-то элементах из A есть n + 1. В этом случае значением g объявляем любой элемент, ηn+1-эквивалентный числу n+1 из B. Далее, ограничение f на B может быть либо тождественной функцией, либо константой (с фиксированным значением из A либо B). И в том, и в другом случае понятно, как определять g с сохранением изоморфизма. Таким образом, всякая алгебра с одной одноместной операцией, определимая над ηn+1, является определимой и над ηn+2. Случай многоместных операций сводится к вычислимым семействам элементарных трансляций. Для того, чтобы показать строгость отношения, достаточно заметить, что над ηn+2 представима унарная алгебра Un+3, имеющая ровно один цикл длины n+3 и все остальные длины 1 (неподвижные точки). Очевидно, что Un+3 нельзя определить над ηn+1. Понятно, что получаем строго возрастающую цепь позитивных степеней, но они же, порождая эффективно отделимые степени, так же образуют бесконечную цепь типа ω. Добавим эквивалентность ηω = id ω, ≡ES-степень которой собственным образом содержит все ηn, и получаем цепь типа ω + 1. Легко также понять, что существуют ≡ES-несравнимые степени. В самом деле, рассмотрим степень d1 = id ω/ ≡ES и d2, где d2 - степень, содержащая позитивную эквивалентность η, над которой представима алгебра A, не имеющая вычислимого представления. Тогда A не определима над степенью d1. С другой стороны, алгебра следования представима над d1, но не представима над степенью d2, т. к. в силу конечной порожденности S позитивно устойчива и ее представимость над d2 означала бы вычислимость эквивалентности η ∈ d2. Противоречие. Конечно, хотя любая алгебра (даже с сигнатурой любой алгоритмической сложности) имеет нумерацию (см. предложение 3.1), далеко не всякая алгебра определима над подходящей ≡ESстепенью. Однако класс эффективно отделимо представимых алгебр, являющийся базисом структурной теории отделимых алгебр, дает широкие возможности с точки зрения построения алгоритмических представлений, т. к., с одной стороны, такие наиболее важные типы представлений, как позитивные и негативные, являются эффективно отделимыми, а с другой стороны, сами эффективно отделимые алгебры расположены довольно низко в арифметической иерархии, т. е. представляют не только абстрактный, но и практический интерес.

Об авторах

Н. Х. Касымов

Национальный университет Узбекистана им. М. Улугбека

Автор, ответственный за переписку.
Email: nadim59@mail.ru
Ташкент, Узбекистан

Р. Н. Дадажанов

Национальный университет Узбекистана им. М. Улугбека

Email: dadajonovrn@mail.ru
Ташкент, Узбекистан

Ф. Н. Ибрагимов

Национальный университет Узбекистана им. М. Улугбека

Email: farkh-i@yandex.com
Ташкент, Узбекистан

Список литературы