Автоустойчивые I-алгебры

Алгебра и логика, 43, N 5 (2004), 511—550

УДК 510.5+510.6+512.563

АВТОУСТОЙЧИВЫЕ I-АЛГЕБРЫ∗) П. Е. АЛАЕВ Работа посвящена описанию автоустойчивых I-алгебр, т. е. булевых алгебр с конечным числом выделенных идеалов. Исследования свойств I-алгебр тесно связаны с исследованием булевых алгебр и проводились многими авторами. В данной работе для этого класса моделей в чисто алгебраических терминах описываются его автоустойчивые элементы, т. е. решается классическая задача теории конструктивных моделей: для каких структур проблема существования различных алгоритмических представлений не возникает. Ранее было найдено описание автоустойчивых булевых алгебр, независимо в [1] и [2], а также булевых алгебр с одним выделенным идеалом [3]. В исследованиях по автоустойчивости моделей большую роль выполняют общие методы доказательства неавтоустойчивости моделей, например, теорема о ветвлении из [2]. Впоследствии в [4] было предложено некоторое обобщение этой теоремы, в доказательстве которого содержится ошибка. К сожалению, она не была вовремя замечена и проникла во многие другие публикации, напр., в [5]. В настоящей работе предлагается другое обобщение упомянутой теоремы, которое, в частности, уточняет некоторые идеи из [4]. § 1. Теорема о ветвлении Хотя работа [4] содержит ошибки, в ней высказан ряд интересных суждений по обобщению теоремы о ветвлении, напр., использование в ∀∗)

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

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

512

П. Е. Алаев

формулах констант из модели. Однако, как уже было сказано, доказательство из [4] в этом случае оказывается неверным, хотя контрпример к формулировке теоремы автору неизвестен. Не углубляясь в детали этого доказательства, укажем лишь неточность из [5]: в теореме 19 главы 6 ошибочно указано, что Ψm может содержать константы для элементов из Aνm . Конечно, в будущем может быть найдено исправленное доказательство. Но в любом случае приводимая ниже теорема 1 содержит в себе некоторые новые элементы, в частности, отказ от требования конечности. На ее основе далее строится описание автоустойчивых I-алгебр. Вычислимой (конструктивной) моделью языка L называем модель, носитель которой — вычислимое подмножество в ω, а функции и предикаты — вычислимые объекты на этом подмножестве. Если язык L бесконечен, то необходимо дополнительное условие их равномерной вычислимости. Основы теории вычислимых моделей изложены, напр., в [1]. Пусть A — вычислимая модель. Она автоустойчива, если для любых двух ее вычислимых изоморфных копий (конструктивизаций) A1 , A2 найдется вычислимый изоморфизм f : A1 → A2 , т. е. изоморфизм, одновременно являющийся частично вычислимой функцией (ч.в.ф.). Отношение вычислимого изоморфизма разбивает семейство вычислимых копий A на классы эквивалентности. Число таких классов обозначают dimC (A) и называют алгоритмической размерностью модели A. Говорим, что класс конструктивизаций A эффективно бесконечен, если по любой вычислимой последовательности {An }n∈ω конструктивизаций модели A можно эффективно построить новую конструктивизацию B, не вычислимо изоморфную ни одной An , n ∈ ω. Ясно, что в этом случае dimC (A) = ω. Более подробное определение этого понятия содержится в [1]. Пусть L — конечный предикатный язык. Если A, B — модели L, то через A ≤ B обозначается то, что A является подмоделью в B. Запись A ≡1 B означает, что в A и B верны одни и те же ∃-предложения L. Пусть A — бесконечная вычислимая модель языка L, {Ap }p∈ω — такая вычислимая последовательность конечных моделей L, что Ap ≤

Автоустойчивые I-алгебры ≤ Ap+1 6 A и A =

S

513

Ap . Пусть также {¯ cp }p∈ω — вычислимая после-

p∈ω

довательность конечных наборов из A (может быть, пустых) со свойством c¯p ∈ Ap , и {ψp (¯ xp , y¯p )}p∈ω — вычислимая последовательность ∀-формул L, где |¯ yp | = |¯ cp |. Говорим, что система {Ap , c¯p , ψp (¯ xp , y¯p )}p∈ω ветвится на уровне p, если для любого набора d¯p из A со свойством (A, c¯p ) ≡1 (A, d¯p ) верно (1) {¯b | A |= ψp (¯b, d¯p )} = 6 ∅; (2) если {¯bi }i∈I — некоторое 1-1 перечисление множества {¯b | A |= |= ψp (¯b, d¯p )}, где I — начальный сегмент в ω, {¯ ai }i∈I — последовательность наборов из A, для которой A |= ψp (¯ an , c¯p ) и (A, c¯p , a ¯0 , . . . , a ¯ n ) ≡1 ≡1 (A, d¯p , ¯b0 , . . . , ¯bn ) при всех n ∈ I, то существует n ∈ I со следующим свойством: (∗) найдется бесконечно много чисел t > p, для которых a ¯0 , . . . , a ¯n ∈ ∈ At и существует изоморфное вложение β : At → At+1 такое, что At+1 |= |= ¬ψp (β(¯ an ), c¯p ) и β тождественно на Ap , a ¯0 , . . . , a ¯n−1 . ТЕОРЕМА 1. Если система {Ap , c¯p , ψp (¯ xp , y¯p )}p∈ω ветвится на всех уровнях p ∈ ω, то A не автоустойчива. Более того, класс конструктивизаций A эффективно бесконечен. ДОКАЗАТЕЛЬСТВО опирается на схему из [2]. Для простоты изложения покажем, как, имея вычислимую копию B модели A, можно эффективно по B построить другую вычислимую копию C модели A, не вычислимо изоморфную B. Доказательство для эффективной бесконечности можно получить из него легкой модификацией. Считаем, что ω — носитель моделей A и B. Найдем вычислимую последовательность конечных моделей {Bt }t∈ω такую, что Bt ≤ Bt+1 ≤ B, S B= Bt и носитель Bt — начальный отрезок в ω. В конце каждого шага t∈ω

t строим конечную модель Ct языка L и изоморфизм γt : Ct → At . По S свойствам конструкции, Ct ≤ Ct+1 и C = Ct — модель с носителем ω. t∈ω

Цель конструкции — добиться того, чтобы γ(x) = lim γt (x) осуществляла t→∞

изоморфизм C и A, а между B и C не существовало вычислимого изоморфизма. С этой целью вводятся требования (далее ϕk (x) — универсальная ч.в.ф., ϕk,t (x) — результат ее вычисления после t шагов)

514

П. Е. Алаев Rk : ϕk не является изоморфизмом B и C; Sx : существует t0 такое, что γt0 (x) = γt (x) для всех t > t0 ; Oy : существуют такие t0 и x, что y = γt (x) для всех t > t0 . Поскольку ϕk будет использоваться только для удовлетворения тре-

бования Rk , можно считать, что dom(ϕk,t ) — начальный отрезок в ω, dom(ϕk,t ) ⊆ Bt , ran(ϕk,t+1 ) ⊆ Ct и ϕk,t+1 : dom(ϕk,t+1 ) → Ct — изоморфное вложение для всех t ∈ ω; если ϕk,t не удовлетворяет этим условиям, то остановим ее рост. Значит, существует ”истинная“ универсальная функция ϕ∗k,t и ϕk,t ⊆ ϕ∗k,t , используемая в конструкции. Поэтому можно также счиS S тать, что ran(ϕk,t ) = ω, если dom(ϕk,t ) = ω; для этого необходимо t∈ω

t∈ω

следить, чтобы условие |dom(ϕk,t )| > k было верным только тогда, когда [0, k] ⊆ ran(ϕ∗k,t ). В конце любого шага t каждое требование может быть или обра-

ботано, или нет. С каждым требованием можно связать конечный набор элементов из Ct . Смысл этого в том, что младшие требования на шаге t+1 не могут менять значение γt на этом наборе (считаем, что требования упорядочены в порядке убывания старшинства как R0 > S0 > O0 > R1 > . . .). Кроме того, для требования Rk на некоторые наборы из dom(ϕk,t ) может быть выставлено конечное семейство меток вида [k, 0], . . . , [k, n], каждая метка [k, i] — на какой-то один набор. Ш а г 0. Все требования считаем необработанными, все метки неопре∼ A0 , γ0 : C0 → A0 — некоторый изоморфизм. Наборов, деленными, C0 = связанных с требованиями, в C0 нет. Ш а г t+1. Сначала полагаем γt+1 = γt . В дальнейшем γt+1 может измениться. Последовательно перебираем все требования с номерами 0, . . . , t и для каждого выполняем указанные ниже действия. После рассмотрения текущего требования переходим к следующему или к п. [End], завершающему шаг t + 1. Если все требования рассмотрены, то тоже переходим к п. [End]. Обозначим текущее требование через T . Выражение ”сброс младших требований для T “ означает, что все младшие требования переводятся в необработанные, все метки для них снимаются (становятся неопределен-

Автоустойчивые I-алгебры

515

ными), а наборы, связанные с ними, освобождаются. Пусть T = Sx . Если Sx обработано или x 6∈ Ct , то переходим к следующему требованию. Если же Sx необработано и x ∈ Ct , то сбрасываем младшие требования, переводим Sx в обработанные, связываем с ним набор {x} и переходим к [End]. Пусть T = Oy . Поступаем аналогично: если оно обработано или y 6∈ At , то переходим к следующему требованию. Если же Oy необработано и y = γt (x), то сбрасываем младшие требования, переводим Oy в обработанные, связываем с ним {x} и переходим к [End]. Пусть T = Rk . Найдем наименьшее p такое, что γt (x) ∈ Ap , если x ∈ Ct и x связан с некоторым старшим требованием. Ясно, что p 6 t. Если γt−1 (¯ cp ) не лежит в ran(ϕk,t+1 ), то переходим к следующему требованию. Если же γt−1 (¯ cp ) лежит в ran(ϕk,t+1 ) и не входит в связанные с Rk элементы, то связываем γt−1 (¯ cp ) с Rk , сбрасываем младшие требования и переходим к [End]. Оставшийся случай: в dom(ϕk,t+1 ) есть набор d¯p такой, что γt (ϕk,t+1 (d¯p )) = c¯p и ϕk,t+1 (d¯p ) связан с Rk . Пусть для Rk выставлены метки [k, 0], . . . , [k, n] на наборы ¯b0 , . . . , ¯bn соответственно. Из описания конструкции следует, что все ¯bi имеют длину |¯ xp |. Говорим, что метка [k, m], указывающая на набор ¯bm , установлена правильно, если Bt+1 |= ψp (¯bm , d¯p ), ¯bm отличается от всех наборов, на которые установлены меньшие метки [k, m1 ], m1 < m, и любой набор ¯b′ из dom(ϕk,t+1 ) с меньшим номером, для которого Bt+1 |= ψp (¯b′ , d¯p ), уже помечен некоторой меньшей меткой [k, m1 ]. Говорим, что метка [k, m] может быть использована для обработки Rk , если существует изоморфное вложение β : At → At+1 такое, что At+1 |= |= ¬ψp (β ◦ γt ◦ ϕk,t+1 (¯bm ), c¯p ) и β тождественно на Ap и на γt ◦ ϕk,t+1 (¯bi ) для всех i < m. В а р и а н т 1. В конце шага t требование Rk было обработанным. Проверяем, все ли метки [k, 0], . . . , [k, n] установлены правильно. Если нет, то пусть [k, m] — наименьшая метка, установленная неправильно. Сбрасываем младшие требования, снимаем все метки [k, i] для i > m, переводим

516

П. Е. Алаев

Rk в необработанные и оставляем связанными с ним наборы ϕk,t+1 (d¯p ) и ϕk,t+1 (¯bi ) для i < m. Переходим к [End]. Пусть все метки стоят правильно. Смотрим, существует ли такое m < < n, что [k, m] может быть использована для обработки Rk . Если нет, то переходим к следующему требованию. В противном случае выберем наименьшее m с таким свойством. Сбрасываем младшие требования и снимаем все метки [k, i] для i > m. Пусть β : At → At+1 — соответствующее изоморфное вложение. Заменяем γt+1 на β ◦γt+1 ; считаем связанными с Rk наборы ϕk,t+1 (d¯p ) и ϕk,t+1 (¯bi ) для i 6 m; говорим в этом случае, что Rk обработано за счет метки [k, m]. Переходим к [End]. В а р и а н т 2. Требование Rk не было обработано в конце шага t. Проверяем, есть ли среди [k, 0], . . . , [k, n] метки, стоящие неправильно. Если m — такое наименьшее число, что [k, m] стоит неправильно, то снимаем все метки [k, i] для i > m. Далее, независимо от того, были ли сняты какиелибо метки, пытаемся на наборы из dom(ϕk,t+1 ) правильно расставить максимальное количество меток из последовательности [k, 0], [k, 1], . . . . Поскольку разные метки должны стоять на разных наборах, эта операция определена корректно. Пусть теперь установлены метки [k, 0], . . . , [k, n′ ]. Проверяем, есть ли среди них те, которые могут быть использованы для обработки Rk . Возможны три случая. (a) Таких меток нет, и в результате описанной выше переустановки меток [k, i] ни одна метка не изменила своего состояния и набора, на который она указывает, тогда переходим к следующему требованию. (b) Таких меток нет, но какие-то метки изменились; в этом случае сбрасываем все младшие требования и считаем, что с Rk связаны наборы ϕk,t+1 (d¯p ) и ϕk,t+1 (¯b) для всех ¯b, на которые указывают метки [k, i]; переходим к [End]. (c) Существует наименьшее число m такое, что Rk может быть обработано за счет [k, m]; тогда сбрасываем младшие требования и снимаем [k, i] для i > m. Пусть β : At → At+1 — соответствующее изоморфное

Автоустойчивые I-алгебры

517

вложение. Заменяем γt+1 на β ◦ γt+1 ; наборы ϕk,t+1 (d¯p ) и ϕk,t+1 (¯bi ) для i 6 m, где [k, i] указывает на ¯bi , считаем связанными с Rk ; переводим Rk в обработанные и переходим к [End]. В этом случае также говорим, что Rk обработано за счет метки [k, m]. [End]. В данный момент построено изоморфное вложение γt+1 : Ct → → At+1 . Продолжаем его до изоморфизма γt+1 : Ct+1 → At+1 , используя для образования множества Ct+1 \ Ct первые элементы из ω \ Ct . Конец шага t + 1. Описание конструкции завершено. Нетрудно заметить, что разные требования Rk никак не взаимодействуют друг с другом, за исключением двух моментов: (a) если у старшего требования что-то меняется, то младшее сбрасывается; (b) если со старшим требованием связан какой-то набор в Ct , то младшее не может менять γt на этом наборе. Отсюда легко понять, что для того, чтобы доказать эффективную бесконечность класса конструктивизаций A, можно рассмотреть вычислимую последовательность {Bm }m∈ω копий A, заменить Rk на требование Rhk,mi : ϕk не является изоморфизмом Bm и C, а метки для Rhk,mi выставлять на наборы из Bm , и по существу ничего не изменится. ЛЕММА 1. Каждое требование, начиная с некоторого шага, стабилизируется, т. е. его состояние и связанные с ним наборы и метки перестают меняться. ДОКАЗАТЕЛЬСТВО проводится индукцией по номеру требования. Пусть дано некоторое требование T и в конце шага t0 все старшие требования стабилизировались. Из конструкции ясно, что действия, выполняемые на каждом шаге t для старших требований, могут повлиять на состояние T или его метки и наборы только тогда, когда эти старшие требования сами меняют свои состояния или метки. Тем самым, после шага t0 старшие требования не будут влиять на T , а младшие вообще не могут этого делать.

518

П. Е. Алаев Пусть T = Sx . После первого шага t, большего t0 и такого, что

x ∈ Ct−1 , требование Sx будет обработано навсегда и тем самым стабилизируется. Аналогичное верно для Oy . Пусть T = Rk . Выберем наименьшее число p такое, что если x ∈ Ct0 и x связан с некоторым старшим требованием в конце t0 , то γt0 (x) ∈ Ap . Если γt−1 (¯ cp ) не лежит в ran(ϕk,t+1 ) для всех t > t0 , то Rk навсегда останется необработанным, ни одна метка для Rk не будет выставлена и требование стабилизируется. Допустим, что γt−1 (¯ cp ) попало в ran(ϕk,t1 +1 ) для некоторого t1 > t0 . 1 После шага t1 + 1 набор e¯p = γt−1 (¯ cp ) будет навсегда связан с Rk , а если 1 ϕk,t +1 (d¯p ) = e¯p , то γt ◦ ϕk,t+1 (d¯p ) = c¯p для всех t > t1 . 1

Рассмотрим поведение меток [k, m] на шагах t > t1 + 1. Говорим, что метка [k, m] стабилизируется после шага t, если она либо неопределена после всех шагов t′ > t, либо определена и указывает на один и тот же набор. Если в некоторый момент Rk будет навсегда обработано, то, как нетрудно заметить, оно стабилизируется (может быть, после конечного числа уменьшений меток, за счет которых оно обработано). Предположим, что Rk не стабилизируется. Тогда указанные в варианте 2 действия по коррекции меток будут выполняться бесконечно часто. Метка [k, m] может быть снята с набора ¯b на шаге t + 1 в четырех случаях: (a) Bt+1 |= ¬ψp (¯b, d¯p ); (b) снимается меньшая метка; (c) требование Rk обрабатывается за счет меньшей метки; (d) существует набор b¯′ из dom(ϕk,t+1 ) с меньшим номером такой, что Bt+1 |= ψp (b¯′ , d¯p ) и b¯′ не помечен меньшими метками. При этом если все метки [k, 0], . . . , [k, i] стабилизировались и Rk на шаге t + 1 обрабатывается за счет [k, i], то Rk оказывается обработанным навсегда (это противоречит предположению). Теперь индукцией по m легко показать, что каждая метка [k, m] либо стабилизируется, либо стремится к бесконечности (т. е. устанавливается на всё б´ольшие и б´ольшие

Автоустойчивые I-алгебры наборы). Если dom(ϕk ) =

S

519

dom(ϕk,t ) конечен, то в некоторый момент

t∈ω

все метки стабилизируются. Если после этого Rk будет обработано, то навсегда, а если нет, то навсегда останется необработанным. В любом случае Rk стабилизируется. Рассмотрим теперь случай, когда dom(ϕk ) = ω = B. Тогда ran(ϕk ) = = ω = C и если e¯p = ϕk,t+1 (d¯p ), то (C, e¯p ) ∼ = (B, d¯p ). Ясно, что (C, e¯p ) ≡1 ≡1 (A, c¯p ), так как γt является изоморфизмом Ct и At для всех t, при этом γt (¯ ep ) = c¯p . Следовательно, (A, c¯p ) ≡1 (B, d¯p ). Пусть {¯bi }i∈I — перечисление множества {¯b | B |= ψp (¯b, d¯p )} в порядке возрастания номеров, где I — начальный сегмент в ω. По условию существует изоморфизм f : B → A. Тогда (A, c¯p ) ≡1 (A, f (d¯p )), множество {¯b | A |= ψp (¯b, f (d¯p ))} непусто и I 6= ∅. Индукцией по i ∈ I легко показать, что [k, i] в некоторый момент стабилизируется на наборе ¯bi . Пусть после шага t + 1 метки [k, 0], . . . , [k, n] уже стабилизировались на ¯b0 , . . . , ¯bn . Из конструкции следует, что после этого γt+1 ◦ϕk,t+1 (¯bi ) не будет меняться для всех i 6 n. Положим a ¯i = γt+1 ◦ϕk,t+1 (¯bi ). Легко показать, что (A, c¯p , a ¯0 , . . . , a ¯n ) ≡1 (B, d¯p , ¯b0 , . . . , ¯bn ) и, следовательно, A |= ψp (¯ ai , c¯p ) для всех i ∈ I. Тогда (A, c¯p , a ¯0 , . . . , a ¯n ) ≡1 (A, f (d¯p ), f (¯b0 ), . . . , f (¯bn )) для всех n ∈ I, {f (¯bi )}i∈I — некоторое 1-1 перечисление множества {¯b | A |= |= ψp (¯b, f (d¯p ))} и для какого-то n′ ∈ I возможность обработать Rk за счет метки [k, n′ ] появится на некотором шаге. Лемма доказана. ЛЕММА 2. Построенная модель C изоморфна A, а между C и B нет вычислимого изоморфизма. ДОКАЗАТЕЛЬСТВО. Если все требования стабилизируются, то все Sx и Oy в некоторый момент окажутся обработанными. Поэтому γ(x) = = lim γt (x) будет ∆02 -изоморфизмом C и A. Допустим, что ϕk : B → C t→∞

является изоморфизмом, тогда dom(ϕk ) = B, а γ ◦ ϕk — изоморфизм B и A. Как и в предыдущей лемме, рассмотрим шаг t0 , к завершению которого все требования, старшие Rk , уже стабилизировались, и такое наименьшее число p, что если x ∈ Ct0 и x связан с некоторым старшим требованием в завершении шага t0 , то γt0 (x) ∈ Ap . В некоторый момент γt−1 (¯ cp ) перестанет меняться и попадет в ran(ϕk,t+1 ). Пусть γt ◦ ϕk,t+1 (d¯p ) = c¯p при

520

П. Е. Алаев

t > t1 > t0 . Если в некоторый момент Rk будет навсегда обработан за счет метки [k, m], указывающей на ¯b, то B |= ψp (¯b, d¯p ) и A |= ¬ψp (γ ◦ ϕk (¯b), c¯p ), получаем противоречие. Допустим, что Rk на бесконечном числе шагов не будет обработанным. Тогда ”корректировка“ меток [k, i], описанная в варианте 2, будет происходить бесконечно часто и метки [k, 0], [k, 1], . . . будут стабилизироваться на наборах ¯b0 , ¯b1 , . . . , соответственно (используем обозначения из предыдущей леммы). Рассуждая как выше, получаем, что в некоторый момент возникнет возможность для окончательной обработки Rk , приходим к противоречию. Лемма, а тем самым и теорема доказаны. Теорема 1 сформулирована для конечного предикатного языка L и последовательности ∀-формул {ψp (¯ xp , y¯p )}p∈ω и далее будет использоваться именно в таком виде. Приведем также ее усложненную версию, использующую бесконечный предикатный язык и формулы, являющиеся конъюнкцией бесконечного семейства ∀-формул. Пусть L — произвольный вычислимый предикатный язык, {Lt }t∈ω — вычислимая последовательность конечных языков такая, что Lt ⊆ Lt+1 ⊆ S t ⊆LиL= L . Пусть A — бесконечная вычислимая модель L, {Ap }p∈ω — t∈ω

вычислимая последовательность конечных моделей такая, что Ap — модель

Lp , Ap ≤ Ap+1 |Lp ≤ A|Lp и A =

S

Ap (через A|Lp обозначаем обеднение

p∈ω

A до Lp ). Пусть также {¯ cp }p∈ω — вычислимая последовательность конеч(s)

ных наборов из A со свойством c¯p ∈ Ap , {ψp (¯ xp , y¯p )}p,s∈ω — вычислимая (s)

последовательность ∀-формул языка L, где |¯ yp | = |¯ cp | и ψp — формула V (s) языка Ls , а ψp (¯ xp , y¯p ) = ψp (¯ xp , y¯p ) (рассматриваем ψp как ”особую“ s∈ω

xp , y¯p ) обозначим формулу). Через ψpt (¯

t V

(s)

ψp (¯ xp , y¯p ) (это формула язы-

s=0

ка Lt ). Говорим, что система {Ap , c¯p , ψp (¯ xp , y¯p )}p∈ω ветвится на уровне p, если для любого набора d¯p из A со свойством (A, c¯p ) ≡1 (A, d¯p ) верно (1) {¯b | A |= ψp (¯b, d¯p )} = 6 ∅; (2) если {¯bi }i∈I — некоторое 1-1 перечисление множества {¯b | A |= |= ψp (¯b, d¯p )}, где I — начальный сегмент в ω, {¯ ai }i∈I — последовательность наборов из A такая, что A |= ψp (¯ an , c¯p ) и (A, c¯p , a ¯0 , . . . , a ¯ n ) ≡1

Автоустойчивые I-алгебры

521

≡1 (A, d¯p , ¯b0 , . . . , ¯bn ) для всех n ∈ I, то существует n ∈ I со свойством (∗) найдется бесконечно много чисел t > p, для которых a ¯0 , . . . , a ¯n ∈ ∈ At и существует изоморфное вложение β : At → At+1 |Lt такое, что At+1 |= ¬ψpt (β(¯ an ), c¯p ) и β тождественно на Ap , a ¯0 , . . . , a ¯n−1 . ТЕОРЕМА 2. Если система {Ap , c¯p , ψp (¯ xp , y¯p )}p∈ω ветвится на всех уровнях p ∈ ω, то A не автоустойчива. Более того, класс конструктивизаций A эффективно бесконечен. ДОКАЗАТЕЛЬСТВО аналогично доказательству предыдущей теоремы. На шаге t + 1 работа будет вестись с объектами языка Lt . Это означает, что Ct и Bt+1 будут моделями Lt , γt : Ct → At — изоморфизмом моделей Lt , Ct ≤ Ct+1 |Lt , а ϕk,t+1 : dom(ϕk,t+1 ) → Ct — изоморфным вложением моделей Lt . Кроме того, в описании работы с Rk на шаге t + 1 все вхождения ψp следует заменить на ψpt , а все изоморфные вложения β : At → At+1 рассматривать как вложения в языке Lt . На шаге t + 1 к моменту перехода к [End] построено изоморфное вложение γt+1 : Ct → At+1 |Lt . Расширим носитель Ct до Ct+1 , обогатим Ct+1 новыми символами из Lt+1 \ Lt и продолжим γt+1 до изоморфизма Ct+1 и At+1 . Теорема доказана. Укажем кратко еще некоторые возможные пути ослабления условий теоремы 1. Последовательность ∀-формул {ψp (¯ xp , y¯p )}p∈ω может быть не вычислимой, а ∆02 -последовательностью, т. е. вид каждой формулы ψp (¯ xp , y¯p ) может меняться конечное число раз. Кроме того, метки [k, i] расставляются в конструкции на наборы просто в порядке возрастания номеров, что порождает произвольную последовательность {¯bi }i∈ω . Этот способ можно заменить на какой-либо более сложный.

§ 2. Необходимые условия автоустойчивости Основным объектом оставшейся части работы будут булевы алгебры с конечным числом выделенных идеалов, или I-алгебры. С основами теории булевых алгебр можно познакомиться по [2]. Просто булевы алгебры

522

П. Е. Алаев

рассматриваются в языке {+, ·, 0, 1, C}, где + соответствует объединению элементов, а · соответствует пересечению. Выражение x − y эквивалентно x · C(y), запись x1 , . . . , xn | x означает, что x1 + . . . + xn = x и xi · xj = 0 при i 6= j. Через n, кроме натурального числа, обозначается также конечная булева алгебра с n атомами. Если I1 , I2 ⊳ A — два идеала в булевой алгебре A, то можно ввести три операции: I1 ∩ I2 = I1 · I2 , I1 + I2 и I1 → I2 = {x ∈ A | ∀y 6 x y ∈ I1 → y ∈ I2 }. Для a ∈ A обозначим через b a булеву алгебру, образованную множеством {b ∈ A | b 6 a}. Нетрудно про-

верить, что эти операции будут перестановочны с переходом A 7→ b a, напр., (I1 →A I2 ) ∩ b a = (I1 ∩ b a) →a (I2 ∩ b a). В силу этого будем опускать индексы,

связанные с A и b a. Запись A = A1 ⊕ . . . ⊕ An означает, что A1 , . . . , An — главные идеалы в A, Ai ∩ Aj = {0} при i 6= j и A = A1 + . . . + An .

I-алгебра — это модель вида (A, I1 , . . . , Iλ ), где A — булева алгеб-

ра, λ > 0 и I1 , . . . , Iλ — идеалы в A. I-алгебры рассматриваются как модели языка Lλ = {+, ·, 0, 1, C, Q1 , . . . , Qλ }, где Q1 , . . . , Qλ — одноместные предикаты, выделяющие идеалы I1 , . . . , Iλ , соответственно. В дальнейшем, как правило, λ будет фиксировано (исключения будут специально оговариваться). Кроме того, все рассматриваемые I-алгебры счетны. Поэтому иногда вместо слов ”счетная I-алгебра“ будем употреблять термин ”алгебра“ и обозначать просто A, предполагая идеалы фиксированными. Если a ∈ A, то через b a обозначается I-алгебра (b a, I1 ∩ b a, . . . , Iλ ∩ b a).

Пусть (A, I1 , . . . , Iλ ) — это I-алгебра и x ∈ A. Характеристикой x

называем множество Px = {n ∈ [1, λ] | x 6∈ In }. Легко проверить, что

P0 = ∅, Px ≤ Py при x 6 y, Px+y = Px ∪ Py (считаем, что порядок ≤ на характеристиках совпадает с включением ⊆). Если, например, Px = [1, q], то используем запись Px = (I¯1 , . . . , I¯q , Iq+1 , . . . , Iλ ). Данная работа посвящена изучению алгоритмической размерности I-алгебр. Нетрудно заметить: если (A, I1 , . . . , Iλ ) — I-алгебра, а L ⊳ A — некоторый идеал, определимый в (A, I1 , . . . , Iλ ) бескванторной формулой, то при добавлении в язык нового предиката Qλ+1 , выделяющего L, алгоритмическая размерность (A, I1 , . . . , Iλ ) не изменится. Будем говорить, что (A, I1 , . . . , Iλ ) замкнута относительно пересечений идеалов, если любое

Автоустойчивые I-алгебры

523

конечное пересечение Ii1 ∩ . . . ∩ Iik , {i1 , . . . , ik } ⊆ [1, λ], совпадает с In для некоторого n и, кроме того, Im = {0} и Is = A для некоторых m, s ∈ [1, λ]. Ясно, что из любой алгебры (A, I1 , . . . , Iλ ) можно получить замкнутую относительно пересечений идеалов алгебру, добавив в язык новые идеалы для {0}, A и всех конечных пересечений; алгоритмическая размерность от этого не изменится. Поэтому далее считаем, что все рассматриваемые I-алгебры замкнуты, если не оговорено противное. ЛЕММА 3. Пусть B — булева алгебра, M, L1 , . . . , Ln ⊳ B — некоторые идеалы, x ∈ B. (1) Если x 6∈ M, L1 , . . . , Ln , а x/M — безатомный элемент, то найдутся такие y, z | x, что y 6∈ L1 , . . . , Ln , M и z 6∈ M . (2) Если x 6∈ L1 , . . . , Ln , а x/L1 , . . . , x/Ln — безатомные элементы, то найдутся такие y, z | x, что y, z 6∈ L1 , . . . , Ln . ДОКАЗАТЕЛЬСТВО. (1) Воспользуемся индукцией по n. Б а з а и н д у к ц и и: n = 1. Найдем x1 , x2 | x такие, что x1 , x2 6∈ M , тогда либо x1 6∈ L1 , либо x2 6∈ L1 . П е р е х о д (n → n + 1). Найдем x1 , x2 | x со свойством x1 , x2 6∈ M . Пусть x1 6∈ Ln+1 . Если x1 6∈ L1 , . . . , Ln , то y = x1 и z = x2 — искомая пара. Если же, например, x1 ∈ L1 , . . . , Ls и x1 6∈ Ls+1 , . . . , Ln , то x2 6∈ L1 , . . . , Ls . По предположению индукции найдется такое разбиение x′2 , x′′2 | x2 , что x′2 6∈ L1 , . . . , Ls , M и x′′2 6∈ M . Тогда можно взять y = x1 + x′2 и z = x′′2 . (2) Положим M = L1 и, пользуясь (1), найдем y1 , z1 | x такие, что y1 6∈ L1 и z1 6∈ L1 , . . . , Ln . Далее, найдем y2 , z2 | z1 такие, что y2 6∈ L2 и z2 6∈ L1 , . . . , Ln . Продолжая в том же духе, дойдем до yn , zn , где yn 6∈ Ln и zn 6∈ L1 , . . . , Ln . Тогда y = y1 + . . . + yn , и z = zn — искомое разбиение. Лемма доказана. СЛЕДСТВИЕ 1. Пусть A — I-алгебра, x ∈ A — элемент характеристики P . (1) Если x 6∈ Iq для некоторого q ∈ [1, λ], а x/Iq — безатомный элемент, то найдутся y, z | x такие, что Py = P и z 6∈ Iq . (2) Если P = (I¯1 , . . . , I¯q , Iq+1 , . . . , Iλ ), а x/I1 , . . . , x/Iq — безатомные

524

П. Е. Алаев

элементы, то найдутся y, z | x такие, что Py = Pz = P . Элемент x I-алгебры A называем разложимым, если существует представление x = x1 + . . . + xn , где n > 1 и Pxi < Px для всех i ∈ [1, n], и неразложимым в противном случае. ЛЕММА 4. Для любого x ∈ A найдется такой набор неразложимых элементов x1 , . . . , xn , что x1 , . . . , xn | x. ДОКАЗАТЕЛЬСТВО проводится индукцией по |Px |. Если Px = ∅, то x = 0 и лемма, очевидно, верна. Если Px = P и x разложим, то x = x1 + . . . + xn , где Pxi < P . Можно считать, что xi · xj = 0 при i 6= j, поскольку можно перейти к сумме вида x1 +(x2 −x1 )+. . . . По предположению индукции каждое xi раскладывается в сумму неразложимых. Лемма доказана. P

Im ⊂In

Пусть (A, I1 , . . . , Iλ ) — I-алгебра, n ∈ [1, λ]. Через In+ обозначается Im . Если In = {0}, то считаем In+ = {0}. Тогда In+ является идеалом.

Говорим, что A n-регулярна, если выполняется одно из условий: (1) In+ = Ik для некоторого k ∈ [1, λ]; (2) In = A и A/I + ∼ = 1. n

I-алгебра A регулярна, если она n-регулярна для всех n ∈ [1, λ]. Заметим, что хотя понятие n-регулярности является достаточно наглядным (оно описывает связь идеала со всеми меньшими) и легко проверяется, работать с ним очень неудобно, так как операция In 7→ In+ не перестановочна с переходом A 7→ b a, а n-регулярность не сохраняется при этом переходе. Определим регулярность в других терминах.

Если P — некоторая характеристика, то P -идеал — это {x | Px ≤ P },

P -сумма — сумма P ′ -идеалов для всех P ′ < P . Если P = ∅, то считаем, что P -сумма равна P -идеалу (который равен {0}). Легко проверить, что P -идеал и P -сумма являются идеалами, а операции образования P -идеала и P -суммы перестановочны с переходом A 7→ b a. Отметим также, что P идеал сохраняется при переходе к подалгебрам (если B ≤ A, то P -идеал в B равен пересечению B и P -идеала в A), а для P -суммы это неверно. Алгебра A P -регулярна, если выполняется одно из условий:

Автоустойчивые I-алгебры

525

(1) P -сумма равна P -идеалу; (2) P -сумма равна Ik для некоторого k ∈ [1, λ]; (3) P -идеал совпадает со всей A, а P -сумма — максимальный собственный идеал в A. ЛЕММА 5. A регулярна ⇔ A P -регулярна для всех P ⊆ [1, λ]. ДОКАЗАТЕЛЬСТВО. Предположим, что A регулярна, P — некоторая характеристика. Если в A нет элементов a с Pa = P , то P -идеал совпадает с P -суммой. Пусть существует a ∈ A такой, что Pa = P . Если P = (I1 , . . . , Iq , I¯q+1 , . . . , I¯λ ), то P -идеал, очевидно, равен I1 ∩ . . . ∩ Iq , а потому некоторому In , n ∈ [1, q]. Нетрудно проверить, что в этом случае P -сумма совпадает с In+ : если P ′ < P , то P ′ -идеал равен Im для некоторого m ∈ [1, λ] и Im ⊂ In . Если же Im ⊂ In , то m ∈ [q + 1, λ] и Px < P для всех x ∈ Im . Обратно, пусть A P -регулярна для всех P и n ∈ [1, λ]. Рассмотрим характеристику P = [1, λ] \ {m | In ⊆ Im }. Пусть для простоты P = = (I1 , . . . , In , I¯n+1 , . . . , I¯λ ). Как уже было замечено, P -идеал совпадает с I1 ∩ . . . ∩ In = In . Вновь P -сумма совпадает с In+ : если x ∈ Im и Im ⊂ In , то m ∈ [n + 1, λ] и Px < P . Наоборот, если Px < P , то x ∈ Im для некоторого m ∈ [n + 1, λ], In 6⊆ Im , x ∈ In ∩ Im ⊂ In и x ∈ In+ . Получаем, что A n-регулярна. Лемма доказана. Говорим, что A кусочно P -регулярна, если A = A1 ⊕ . . . ⊕ An , где все Ai P -регулярны, и кусочно регулярна, если все Ai регулярны. ЛЕММА 6. Пусть A — I-алгебра, P — некоторая характеристика. Верно по крайней мере одно из двух утверждений: (1) A кусочно P -регулярна; (2) найдутся b1 , b2 , b3 ∈ A такие, что bi · bj = 0 при i 6= j, b1 , b2 — неразложимые элементы характеристики P , а b3 — разложимый элемент характеристики P . ДОКАЗАТЕЛЬСТВО. Пусть P = (I1 , . . . , Ip , I¯p+1 , . . . , I¯λ ). Обозначим через M P -идеал, через L — P -сумму, через N — идеал (L → → Ip+1 ) + . . . + (L → Iλ ). Нетрудно заметить, что неразложимые элементы

526

П. Е. Алаев

характеристики P — это в точности элементы M \ L. Предположим сначала, что существует дизъюнктный набор b1 , b2 , d, для которого b1 , b2 ∈ M \L, а d 6∈ N . Тогда d 6∈ L → Ik для всех k ∈ [p + 1, λ] и найдутся d(k) 6 d, лежащие в L \ Ik . Если b3 = d(p+1) + . . . + d(λ) , то b1 , b2 , b3 — требуемый в (2) набор. Предположим теперь, что таких b1 , b2 , d нет, но найдется дизъюнктный набор b′ , b′′ , b′′′ ∈ M \ L. Рассмотрев b1 = b′ , b2 = b′′ и d = 1 − (b′ + b′′ ), получим, что 1 − (b′ + b′′ ) ∈ N . Поступая аналогично с парами b′′ , b′′′ и b′ , b′′′ , придем к выводу, что 1 ∈ N . Если a ∈ L → Ik для некоторого k ∈ [p + 1, λ], то b a P -регулярна, поскольку P -сумма в b a совпадает с Ik ∩ M . Следовательно, A — сумма P -регулярных алгебр.

Рассмотрим последний случай — такого набора b′ , b′′ , b′′′ нет. Легко

показать, что найдутся c1 , c2 ∈ M , для которых c1 · c2 = 0, M = L в 1 −\ (c1 + c2 ), а в каждом b ci либо M = L, либо L — максимальный соб-

ственный идеал. Вновь получаем, что A — сумма трех P -регулярных алгебр. Лемма доказана.

Если (A, I1 , . . . , Iλ ) является I-алгеброй, и L (⊳A) — некоторый идеал, P то назовем L с-определимым, если L = Im для некоторого S ⊆ [1, λ], m∈S

S 6= ∅. Назовем L кусочно с-определимым, если существует такое разло-

жение A = A1 ⊕. . .⊕An , что L∩Ai с-определим в Ai для каждого i ∈ [1, n]. ЛЕММА 7. Пусть (A, I1 , . . . , Iλ ) — I-алгебра и λ > 2. Верно хотя бы одно из двух утверждений: (1) I1 → I2 c-определим в A; (2) найдутся b1 , b2 ∈ A такие, что b1 ·b2 = 0, b1 , b2 6∈ I2 , b1 ∈ I1 → I2 , b1 неразложим, b2 ∈ I1 и Pb2 ≤ Pb1 . ДОКАЗАТЕЛЬСТВО. Предположим, что (2) неверно, и докажем, что I1 → I2 с-определим в A. Положим S = {m ∈ [1, λ] | Im ∩ I1 ⊆ ⊆ I2 }. Рассмотрим произвольный b ∈ I1 → I2 . Существуют неразложимые b(1) , . . . , b(n) | b. Докажем, что любой b(i) лежит в Im для некоторого m ∈ S. Если b(i) ∈ I2 , то это верно, поскольку 2 ∈ S. Пусть b(i) 6∈ I2 и Pb(i) = (I¯1 , . . . , I¯q , Iq+1 , . . . , Iλ ). Если (Iq+1 ∩ . . . ∩ Iλ ) ∩ I1 ⊆ I2

Автоустойчивые I-алгебры

527

и Im = (Iq+1 ∩ . . . ∩ Iλ ), то искомое m получено. Иначе найдется такой d ∈ (Iq+1 ∩ . . . ∩ Iλ ) ∩ I1 , что d 6∈ I2 . Очевидно, b(i) · d ∈ I2 . Положив b1 = b(i) P и b2 = d−b(i) , получим (2). Значит, Im ⊇ I1 → I2 . Обратное включение m∈S

очевидно. Лемма доказана.

Пусть B — булева алгебра, L ⊳ B и a ∈ B. Говорим, что a — L-атом, L-безатомный и т. п., если a/L — атом в B/L, безатомный и т. п. ПРЕДЛОЖЕНИЕ 1. Пусть (A, I1 , . . . , Iλ ) — вычислимая I-алгебра, λ > 2, а в I1 содержится лишь конечное число непересекающихся I2 -атомов. Если dimC (A) < ∞, то идеал I1 → I2 кусочно c-определим в A. ДОКАЗАТЕЛЬСТВО. Если A ∼ = 1, то I1 → I2 с-определим в A. Следовательно, I1 → I2 кусочно с-определим во всех конечных алгебрах. Предположим, что A бесконечна и I1 → I2 не является кусочно сопределимым в A, и применим теорему 1. По условию существует дизъюнктный набор I2 -атомов e0 , . . . , en ∈ I1 со свойством: если x ∈ I1 и x · (e0 + . . . + en ) = 0, то x/I2 безатомен. Рассмотрим некоторую вычислимую последовательность конечных I-алгебр {A∗p }p∈ω со свойствами S ∗ A∗p ≤ A∗p+1 ≤ A и Ap = A. Можно считать, что e0 , . . . , en ∈ A∗0 . Поp∈ω

строим другую последовательность конечных I-алгебр {Ap }p∈ω , для кото-

рой A∗p ≤ Ap ≤ A и Ap ≤ Ap+1 при p ∈ ω. Положим A0 = A∗0 . Допустим, что Ap уже определена. Найдем конечную алгебру A0p+1 , для которой Ap ≤ A0p+1 ≤ A и A∗p+1 ≤ A0p+1 . Далее, построим Ap+1 так, чтобы 1) A0p+1 ≤ Ap+1 и 2) если y — атом A0p+1 , y · (e0 + . . . + en ) = 0 и y ∈ I1 \ I2 , то в Ap+1 нашлись y ′ , y ′′ | y, для которых Py′ = Py и y ′′ 6∈ I2 (это возможно в силу следствия 1). Если x — атом Ap , x · (e0 + . . . + en ) = 0 и x ∈ I1 \ I2 , то в Ap+1 существуют x′ , x′′ | x такие, что Px = Px′ и x′′ 6∈ I2 . Действительно, пусть y0 , . . . , yk — атомы A0p+1 и y0 , . . . , yk | x. Тогда yi 6∈ I2 для некоторого i ∈ [0, k]. Пусть y0 6∈ I2 . В Ap+1 справедливо y0 = y0′ + y0′′ , где Py0′ = Py0 и y0′′ 6∈ I2 . Полагая x′ = y0′ + y1 + . . . + yk и x′′ = y0′′ , получаем требуемое разбиение.

528

П. Е. Алаев Перейдем теперь от языка I-алгебр к предикатному языку, заменяя

функции на их графики, и рассмотрим A, Ap как модели конечного предикатного языка. Пусть c¯p = (e0 , . . . , en , c0 , . . . , cs ), где c0 , . . . , cs — все атомы модели Ap , а формула ψp (x1 , x2 , e0 , . . . , en , c0 , . . . , cs ) выражает, что xi · (e0 + . . . + en ) = 0 для i = 1, 2, x1 , x2 6 ci для некоторого i ∈ [0, s], x1 · x2 = 0, x1 , x2 6∈ I2 , x1 ∈ I1 → I2 , x2 ∈ I1 , Px2 ≤ Px1 и x1 неразложим. Если некоторый элемент a разложим, то существует его представление в виде суммы слагаемых с меньшими характеристиками, число которых не превосходит 2λ . Это следует из того, что если в сумме есть два слагаемых одной характеристики, то их можно сложить и заменить на одно, а число возможных характеристик равно 2λ . Поэтому ψp является ∀-формулой. Докажем, что система {Ap , c¯p , ψp (x1 , x2 , c¯p )}p∈ω ветвится на уровне p. Пусть (A, c¯p ) ≡1 (A, d¯p ), d¯p = (g0 , . . . , gn , d0 , . . . , ds ). Тогда d0 , . . . , ds | 1 в A, g0 , . . . , gn — I2 -атомы и gi · gj = 0 при i 6= j (поскольку свойство ”быть I2 -атомом“ записывается ∀-формулой). В каждом gbi идеал I1 → I2

с-определим, поскольку I2 ⊆ I1 → I2 . Следовательно, найдется такое i ∈ [0, s], что в di − (g0\ + . . . + gn ) идеал I1 → I2 не будет с-определим. В силу леммы 7 существуют b1 , b2 6 di − (g0 + . . . + gn ), для которых A |= ψp (b1 , b2 , d¯p ). Пусть a1 , a2 ∈ A таковы, что A |= ψp (a1 , a2 , c¯p ). Если a1 , a2 ∈ At и t > p, то найдется такое изоморфное вложение β : At → At+1 , что At+1 |= |= ¬ψp (β(a1 ), β(a2 ), c¯p ) и β тождественна на Ap . Проверим это. Добьемся того, чтобы β(a1 ) 6∈ I1 → I2 . Пусть u0 , . . . , uk , z0 , . . . , zm — атомы At , z0 , . . . , zm | a1 , u0 , . . . , uk | a2 и характеристика a1 равна P . Поскольку a1 неразложим и a2 6∈ I2 , можно считать, что Pz0 = P и u0 ∈ I1 \ I2 . Если x · (z0 + u0 ) = 0, то полагаем β(x) = x. По построению в At+1 найдутся такие u′0 , u′′0 | u0 , что Pu0 = Pu′0 и u′′0 ∈ I1 \ I2 . Положим β(z0 ) = z0 + u′′0 и β(u0 ) = u′0 . Поскольку Pu′′0 ≤ Pu0 ≤ Pa2 ≤ Pa1 = P , то β сохраняет характеристики атомов At . Следовательно, оно осуществляет изоморфное вложение At в At+1 , и β(a1 ) = β(z0 ) + . . . + β(zm ) 6∈ I1 → I2 в At+1 . Все условия теоремы 1 проверены. Получаем dimC (A) = ∞. Предложение доказано.

Автоустойчивые I-алгебры

529

Проверим, что A/Ik содержит конечное число атомов для любого k ∈ ∈ [1, λ], если dimC (A) < ∞. Для упрощения обозначений будем доказывать, что в A/I2 число атомов конечно. Пусть P — некоторая характеристика. Элемент a ∈ A назовем P -атомарным над I2 , если a 6∈ I2 , Pa = P и все b 6 a, b 6∈ I2 , имеют характеристику P . Считая I2 фиксированным, будем называть их также просто P -атомарными. Отметим: если a — I2 атом, то для некоторой характеристики P найдется P -атомарный I2 -атом b 6 a (поскольку существует набор неразложимых элементов a1 , . . . , an | a, и если a1 6∈ I2 и Pa1 = P , то a1 — это P -атомарный I2 -атом, как нетрудно проверить). ПРЕДЛОЖЕНИЕ 2. Пусть (A, I1 , . . . , Iλ ) — вычислимая I-алгебра, P — некоторая характеристика и нет x, y | 1 таких, что в x b все P -

атомарные элементы I2 -конечны, а в yb все P -атомарные I2 -безатомны. Тогда dimC (A) = ∞.

ДОКАЗАТЕЛЬСТВО. Воспользуемся теоремой 1. Пусть {Ap }p∈ω — S такая последовательность конечных I-алгебр, что Ap ≤ Ap+1 , A = Ap p∈ω

и число атомов в Ap+1 на 1 больше, чем в Ap (значит, один атом Ap — сумма двух атомов в Ap+1 , а остальные будут атомами и в Ap+1 ). Набор c¯p = (c0 , . . . , cs ) — это все атомы Ap . Формула ψp (x, z, c¯p ) выражает, что x — I2 -атом, P -атомарный над I2 , x · z = 0, z P -атомарен над I2 и x, z 6 ci для некоторого i ∈ [0, s]. Покажем, что система {Ap , c¯p , ψp }p∈ω ветвится на уровне p. Если (A, c¯p ) ≡1 (A, d¯p ), то d¯p = (d0 , . . . , ds ) — разбиение 1 в A. Из условия следует, что для некоторого i ∈ [0, s] в dbi найдутся такие x, z, x · z = 0,

что x — P -атомарный I2 -атом, а z — P -атомарный I2 -бесконечный элемент. Предположим, что {¯bk }k∈ω — 1-1 перечисление множества {¯b = = hbx , bz i | A |= ψp (bx , bz , d¯p )}. Тогда ¯bm = hx, zi для некоторого m ∈ ω. ¯m = haxm , azm i — соответствующая последовательПусть a ¯0 = hax0 , az0 i, . . . , a ность из {¯ a | A |= ψp (¯ a, c¯p )}. Тогда azm — P -атомарный над I2 элемент, а из (A, azm ) ≡1 (A, z) следует, что он I2 -бесконечен (I2 -бесконечность выражается бесконечной конъюнкцией ∃-формул). Пусть azm 6 c0 , найдем

530

П. Е. Алаев

наименьшее n 6 m, при котором axn , azn 6 c0 . Докажем, что для бесконечного числа шагов t найдется такое изоморфное вложение β : At → At+1 , ¯0 , . . . , a ¯n−1 . что At+1 |= ¬ψp (β(axn ), β(azn ), c¯p ) и β тождественно на Ap , a Пусть e = azm − axn . Тогда axn (6 c0 ) — P -атомарный I2 -атом, axn · e = 0, e (6 c0 ) P -атомарен и I2 -бесконечен. Если axn , e ∈ At , то e = e(0) + . . . + e(y) , где e(i) — атомы At , и каждый e(i) либо лежит в I2 , либо имеет характеристику P . Из I2 -бесконечности e следует, что при бесконечно многих t некоторый e(i) будет равен e′ + e′′ в At+1 , где e′ , e′′ — разные атомы At+1 характеристики P . Пусть t — такой шаг. В свою очередь, axn = a′ + a′′ в At , где a′ — атом At , Pa′ = P и a′′ ∈ I2 . Положим β(a′ ) = a′ + e′ , β(e(i) ) = e′′ и β(u) = u при u · (a′ + e(i) ) = 0. Очевидно, β сохраняет характеристики атомов At . Кроме того, β(a′ + e(i) ) = a′ + e(i) , следовательно, β(cj ) = cj для всех j = 0, . . . , s, т. е. β тождественно на Ap . Все наборы a ¯0 , . . . , a ¯n−1 лежат в b cj для некоторых j 6= 0, и β тождественно на b cj . Тем самым, β —

искомое вложение, поскольку β(axn ) не является I2 -атомом. Предложение доказано.

Пусть P — некоторая характеристика. Говорим, что идеал In P атомарен над Im , если In 6⊆ Im и любой элемент a ∈ In \ Im имеет характеристику P . ЛЕММА

8.

Пусть (A, I1 , . . . , Iλ ) — вычислимая I-алгебра,

dimC (A) < ∞ и A/I2 содержит бесконечное число атомов. Тогда существуют такие a ∈ A, характеристика P и j ∈ [1, λ], что Ij P -атомарен над I2 в b a и Ij ∩ b a содержит бесконечно много непересекающихся I2 -

атомов.

ДОКАЗАТЕЛЬСТВО. Очевидно, найдется такой идеал Ij , в котором

есть бесконечно много непересекающихся I2 -атомов, а в любом Ik ⊂ Ij их число конечно. Докажем, что Ij — искомый идеал. По предложению 1, если Ik ⊂ Ij , то Ik → I2 кусочно с-определим в A. Из того, что (In + Im ) → → I2 = (In → I2 ) ∩ (Im → I2 ) и с-определимость идеала сохраняется при ! P Ik → I2 в переходе от A к b a, следует кусочная с-определимость Ik ⊂Ij

A. Пусть a1 , . . . , an | 1 — такое разбиение, что этот идеал с-определим в

Автоустойчивые I-алгебры

531

каждом b ai , и пусть в b a1 ∩ Ij существует бесконечно много I2 -атомов. Пусть P P Ik и L → I2 = Im в b a1 . Нетрудно проверить: если в каждом L= m∈S Ik ⊂Ij P Ik оно Ik , k ∈ K, число непересекающихся I2 -атомов конечно, то и в k∈K

тоже конечно. Если p — I2 -атом, то либо p ∈ L + I2 , либо p ∈ L → I2 .

Следовательно, L → I2 содержит бесконечно много непересекающихся I2 атомов из b a1 ∩ Ij , то же самое верно для Im ∩ Ij при некотором m ∈ S.

Случай Im ∩ Ij ⊂ Ij невозможен, поэтому Ij ⊆ Im , Ij ⊆ L → I2 в b a1 , и если

Ik ⊂ Ij , то Ik ⊆ I2 в b a1 .

Покажем, что Ij является P -атомарным над I2 в b a1 . Возьмем произ-

вольный b из Ij \ I2 , b 6 a1 . Если Ij ⊆ In , то b ∈ In . Если же Ij 6⊆ In , то

Ij ∩ In = Ik ⊂ Ij , Ik ⊆ I2 в b a1 и b 6∈ In . Получаем, что все такие b имеют одинаковую характеристику. Лемма доказана.

ПРЕДЛОЖЕНИЕ 3. Пусть (A, I1 , . . . , Iλ ) — вычислимая I-алгебра, P — некоторая характеристика и верно следующее: (1) существует a ∈ A такой, что I1 ∩b a содержит бесконечное число непересекающихся I2 -атомов, I1 является P -атомарным над I2 в b a и если

x ∈ I1 ∩ b a, то x/I2 конечен;

(2) в A нет такого y, P -атомарного над I2 , что y/I2 содержит

бесконечное число атомов. Тогда dimC (A) = ∞.

ДОКАЗАТЕЛЬСТВО. Не представляется возможным непосредственно использовать здесь теорему 1. Однако изложенная ниже прямая конструкция будет во многом напоминать ее доказательство. Предварительно найдем такую вычислимую последовательность конечных I-алгебр S {Ap }p∈ω , что a ∈ A0 , Ap ≤ Ap+1 и A = Ap . Можно считать: если p∈ω

x0 , . . . , xn — атомы Ap и x0 , . . . , xn | a, то для некоторого i ∈ [0, n] в Ap+1

найдутся такие атомы x′i , x′′i 6 xi , что x′i ·x′′i = 0 и x′i , x′′i ∈ I1 \I2 , поскольку вb a ∩I1 бесконечно много I2 -атомов. Вновь, как и в теореме 1, покажем, как

по вычислимой копии B модели A можно эффективно построить другую вычислимую копию C модели A, которая не будет вычислимо изоморфной B.

532

П. Е. Алаев Считаем, что носителем и в A, и в B является множество ω. Най-

дем вычислимую последовательность конечных I-алгебр {Bt }t∈ω такую, S что Bt ≤ Bt+1 ≤ B и B = Bt . Поскольку теперь используется язык t∈ω

I-алгебр, условие Bt ≤ B противоречит требованию о том, чтобы носитель

Bt был начальным отрезком в ω. Однако можно найти алгебру B ′ , вычислимо изоморфную B, с таким свойством. Поэтому будем считать, что носитель Bt — начальный отрезок в ω. В конце каждого шага t строятся конечная I-алгебра Ct и изоморфизм γt : Ct → At . Из свойств конструкции S следует, что Ct ≤ Ct+1 и C = Ct — I-алгебра с носителем ω. Налагаем

требования

t∈ω

Rk : ϕk не является изоморфизмом B и C; Sx : существует такое t0 , что γt0 (x) = γt (x) для всех t > t0 ; Oy : существуют такие t0 и x, что y = γt (x) для всех t > t0 . Можно считать, что dom(ϕk,t ) — подалгебра в Bt и одновременно начальный отрезок в ω, ran(ϕk,t+1 ) ≤ Ct , ϕk,t+1 : dom(ϕk,t+1 ) → Ct — изоморфное вложение для всех t ∈ ω. В конце каждого шага t каждое из требований Sx и Oy может быть обработанным или нет, Rk считаем все время необработанным. С каждым требованием можно связать некоторый конечный набор элементов из Ct , и младшие требования не могут менять γt на этом наборе на шаге t + 1. Для требования Rk на элементы из dom(ϕk,t ) может быть выставлено конечное число меток из семейства {[k, m, i]}i,m∈ω , каждая метка — на какой-то один элемент. Через c¯p обозначим набор тех атомов c0 , . . . , cs алгебры Ap , для которых c0 , . . . , cs | a. Ш а г 0. Все требования необработаны, метки неопределены, наборов, связанных с требованиями, нет, C0 ∼ = A0 и γ0 : C0 → A0 — некоторый изоморфизм. Ш а г t+1. Вначале полагаем γt+1 = γt . Последовательно перебираем все требования с номерами 0, . . . , t, для каждого выполняя указанные ниже действия и после этого переходя либо к п. [End], завершающему шаг t + 1, либо к следующему требованию. Работа с требованиями Sx и Oy полностью повторяет ту, которая указана в доказательстве теоремы 1. Предположим, что текущее требо-

Автоустойчивые I-алгебры

533

вание — Rk . Найдем наименьшее p такое, что если x принадлежит Ct и связан с некоторым старшим требованием, то γt (x) ∈ Ap . Ясно, что p 6 t. Если γt−1 (¯ cp ) не лежит в ran(ϕk,t+1 ), то переходим к следующему требованию. Если же γt−1 (¯ cp ) лежит в ran(ϕk,t+1 ) и не входит в связанные с Rk элементы, то связываем γt−1 (¯ cp ) с Rk , сбрасываем младшие требования и переходим к [End]. Оставшийся случай — в dom(ϕk,t+1 ) есть такой набор d¯p , что γt ◦ ◦ ϕk,t+1 (d¯p ) = c¯p и ϕk,t+1 (d¯p ) связан с Rk . Пусть d¯p = (d0 , . . . , ds ), положим b = d0 +. . .+ds . Тогда d0 , . . . , ds | b и γt ◦ϕk,t+1 (b) = a. Если для некоторого m ∈ [0, s] в b cm ∩ At существует элемент из I1 \ I2 , а в dbm ∩ dom(ϕk,t+1 ) —

нет, то переходим к следующему требованию.

Предположим, что последнее условие не выполняется, в b c0 , . . . , b cq есть

элементы At из I1 \ I2 , а в b cq+1 , . . . , b cs их нет. Тогда в db0 , . . . , dbq тоже есть элементы dom(ϕk,t+1 ) из I1 \ I2 . Допустим, что для некоторого m ∈ [0, q] ни

одна метка вида [k, m, i] не определена. Для каждого такого m находим в dbm ∩ dom(ϕk,t+1 ) некоторый элемент из I1 \ I2 и устанавливаем на него метку [k, m, 0]. Связываем с Rk набор ϕk,t+1 (d¯p ) и ϕk,t+1 (e) для всех эле-

ментов e, на которые указывают метки вида [k, m, i], m, i ∈ ω, сбрасываем младшие требования и переходим к [End]. Рассмотрим теперь случай, когда для каждого m ∈ [0, q] на элементы dom(ϕk,t+1 ) уже выставлены метки [k, m, 0], . . . , [k, m, rm ], rm > 0. Пусть [k, m, rm ] указывает на bm (тогда bm 6∈ I2 ). Проверяем, существует ли m ∈ ∈ [0, q] такое, что bm является I2 -атомом в dom(ϕk,t+1 ), а γt ◦ ϕk,t+1 (bm ) не будет I2 -атомом в At+1 . Если существует, то переходим к следующему требованию. Допустим, что такого m нет. Возможны два варианта. (a) Для некоторого m ∈ [0, q] элемент bm не является I2 -атомом в dom(ϕk,t+1 ). Для каждого такого m находим некоторые b′ , b′′ ∈ dom(ϕk,t+1 ) со свойствами b′ , b′′ | bm и b′ , b′′ 6∈ I2 , перемещаем метку [k, m, rm ] на b′ и устанавливаем [k, m, rm + 1] на b′′ . Затем связываем с Rk набор ϕk,t+1 (d¯p ) и ϕk,t+1 (e) для всех элементов e, на которые указывают метки [k, m, i], m, i ∈ ω, сбрасываем младшие требования и переходим к [End]. (b) Пусть bm — I2 -атом в dom(ϕk,t+1 ), и γt ◦ ϕk,t+1 (bm ) — I2 -атом в

534

П. Е. Алаев

At+1 для всех m ∈ [0, q]. Проверяем, существуют ли изоморфное вложение β : At → At+1 и m ∈ [0, q] такие, что β◦γt ◦ϕk,t+1 (bm ) не является I2 -атомом в At+1 , β тождественно на Ap и на всех элементах вида γt ◦ϕk,t+1 (e), где на e указывает некоторая метка [k, m′ , i], отличная от [k, m, rm ]. Если такого β нет, то переходим к следующему требованию. Если же такое β существует, то заменяем γt+1 на β ◦ γt+1 , связываем с Rk те же элементы, что и в варианте (a), сбрасываем младшие требования и переходим к [End]. [End]. На этот момент построено изоморфное вложение γt+1 : Ct → → At+1 . Продолжаем его до изоморфизма γt+1 : Ct+1 → At+1 , используя для образования множества Ct+1 \ Ct первые элементы из ω \ Ct . Шаг t + 1 завершен. ЛЕММА 9. Каждое требование с некоторого шага стабилизируется, т. е. связанные с ним наборы и метки перестают меняться, а при работе с ним на шаге t + 1 не сбрасываются младшие требования и не меняется γt . ДОКАЗАТЕЛЬСТВО проводится индукцией по номеру требования. Пусть дано некоторое требование T и в конце шага t0 все старшие требования стабилизировались. Рассмотрим только случай T = Rk . Пусть p — наименьшее число такое, что если x лежит в Ct и связан с некоторым старшим требованием, то γt (x) ∈ Ap . Если γt−1 (¯ cp ) не лежит в ran(ϕk,t+1 ) для всех t > t0 , то ни одна метка для Rk не будет выставлена и оно стабилизируется. Допустим, что γt−1 (¯ cp ) попало в ran(ϕk,t1 +1 ) для некоторого t1 > t0 . 1 После шага t1 + 1 набор γt−1 (¯ cp ) = e¯ будет навсегда связан с Rk , а 1 если ϕk,t1 +1 (d¯p ) = e¯, то γt ◦ ϕk,t+1 (d¯p ) = c¯p для всех t > t1 . Пусть a, b, c0 , . . . , cs , d0 , . . . , ds — обозначения из конструкции, при этом в b c0 , . . . , b cq

есть элементы из I1 \ I2 , а в b cq+1 , . . . , b cs их нет. Тогда при некотором

t2 > t1 + 1 для всех m ∈ [0, q] в b cm ∩ At2 появятся элементы из I1 \ I2 . Если найдется m ∈ [0, q], при котором в dbm ∩ dom(ϕk,t+1 ) такие элементы не

появятся ни для какого t > t2 , то требование, очевидно, стабилизируется. Пусть при t > t3 , где t3 > t2 , для всех m ∈ [0, q] в dbm ∩ dom(ϕk,t+1 ) найдется элемент из I1 \ I2 . После шага t3 + 1 все метки [k, 0, 0], . . . , [k, q, 0]

Автоустойчивые I-алгебры

535

будут определены. Рассмотрим поведение меток [k, m, i] на шагах t > t3 +1 t ] указывают для m ∈ [0, q]. Пусть после шага t метки [k, m, 0], . . . , [k, m, rm (m)

(m)

соответственно на элементы e0 , . . . , ert . m

t → ∞ при t → ∞. Из конструкции ясПредположим, что rm (m) (m) (m) но, что e , равный e0 + . . . + ert , не зависит от t, e(m) ∈ I1 \ I2 , m (m) e(m) 6 dm и каждое ei не лежит в I2 и не меняется при тех t, для t > i. Поскольку разные метки ставятся на разные элеменкоторых rm

ты, dom(ϕk ) = принадлежит

S

dom(ϕk,t ) = ω. Очевидно, что элемент γt ◦ ϕk,t+1 (e(m) )

t b cm ∩

(I1 \ I2 ) и, следовательно, является P -атомарным над

I2 в A и в At для всех t. Поэтому и e(m) будет P -атомарным (так как (m) ∩ dom(ϕ γt ◦ ϕk,t+1 изоморфно вкладывает ed k,t+1 ) в At ). Нетрудно про(m)

верить, что γt ◦ ϕk,t+1 (ei

) перестает меняться при t → ∞ для всех i ∈ ω.

Поскольку этот элемент лежит в (I1 \ I2 ) ∩ b cm , он является I2 -конечным. (m)

Рассматривая изоморфное вложение γt ◦ ϕk,t+1 , получаем, что ei

также

является I2 -конечным в B. Тем самым e(m) — это P -атомарный элемент, (m)

содержащий бесконечно много I2 -атомов (поскольку ei

(m)

и ej

в пределе

не пересекаются при i 6= j). Это противоречит условию (2) и тому, что B∼ = A. t = r при t → ∞ для всех m ∈ [0, q]. Пусть Остался случай, когда rm m

метки [k, m, rm ] остановились на элементах bm при t → ∞. Предположим, что Rk не стабилизировалось. Тогда условия варианта (a) будут проверяться бесконечно часто и bm должен быть I2 -атомом в dom(ϕk,t+1 ) при t → ∞, а тогда и γt ◦ϕk,t+1 (bm ) является I2 -атомом в At при всех достаточно больших t. Значит, замена γt+1 на β ◦ γt+1 из варианта (b) перестанет выполняться и Rk все же стабилизируется. Лемма доказана. ЛЕММА 10. Построенная модель C изоморфна A, а между C и B нет вычислимого изоморфизма. ДОКАЗАТЕЛЬСТВО. Поскольку все требования стабилизируются, каждый из Sx и Oy в некоторый момент станет навсегда обработанным, а γ(x) = lim γt (x) будет изоморфизмом между C и A. Допустим, что t→∞

ϕk : B → C — изоморфизм. Тогда dom(ϕk ) = ran(ϕk ) = ω, и γ ◦ ϕk : B → A тоже является изоморфизмом. Далее следует повторить рассуждения из

536

П. Е. Алаев

леммы 9 для требования Rk , отбрасывая те варианты, которые не могут реализоваться. Пусть c¯p = (c0 , . . . , cs ), d¯p = (d0 , . . . , ds ), в b c0 , . . . , b cq есть элементы из I1 \ I2 , а в b cq+1 , . . . , b cs их нет. Тогда все метки [k, m, 0] для m ∈

∈ [0, q] в какой-то момент будут выставлены, и набор меток {[k, m, i]}m,i∈ω

стабилизируется, при этом условия вариантов (a) и (b) будут проверяться бесконечно часто. (m)

Пусть после стабилизации [k, m, i] указывает на ei

; наибольшее i,

(m) rm ; erm

= bm . Тогда bm —

для которого [k, m, i] определена, обозначим как I2 -атомы в B, а

(m) γt ◦ ϕk,t+1 (ei )

— I2 -конечные элементы из I1 \ I2 в b cm при

t → ∞. Для каждого t в At найдется атом xt , лежащий в b cm для некоторо-

го m ∈ [0, q], под которым в At+1 есть элементы x′ , x′′ из I1 \ I2 . Ясно, что (m)

такой xt не будет пересекаться с элементами вида γt ◦ ϕk,t+1 (ei

) при до-

статочно больших t. Тогда найдется изоморфное вложение β : At → At+1 со свойством β(γt ◦ ϕk,t+1 (bm )) = γt ◦ ϕk,t+1 (bm ) + x′ и β(xt ) = xt − x′ , которое будет удовлетворять всем условиям из варианта (b), и γt+1 ◦ ϕk,t+1 (bm ) не будет I2 -атомом при t → ∞. После этого требование Rk стабилизируется. В результате найдется m ∈ [0, q], при котором bm будет I2 -атомом, а γ ◦ ϕk (bm ) — нет; получаем противоречие. Лемма, а вместе с ней и предложение доказаны. ПРЕДЛОЖЕНИЕ 4. Пусть (A, I1 , . . . , Iλ ) — вычислимая I-алгебра. Если dimC (A) < ∞, то в A/In число атомов конечно для любого n ∈ ∈ [1, λ]. ДОКАЗАТЕЛЬСТВО. Докажем, что число атомов в A/I2 конечно. Предположим противное. Согласно лемме 8, найдутся элемент c ∈ A, характеристика P и j ∈ [1, λ], для которых Ij P -атомарен над I2 в b c и Ij ∩b c со-

держит бесконечно много непересекающихся I2 -атомов. Пусть j = 1. Если

нет x, y | 1 таких, что в x b все P -атомарные над I2 элементы I2 -конечны, а

в yb — I2 -безатомны, то, применяя предложение 2, получаем dimC (A) = ∞,

что противоречит условию.

Допустим, что такие x и y существуют. В A не может быть P -

атомарного над I2 элемента z, для которого z/I2 содержит бесконечное число атомов, поскольку в этом случае z · x и z · y будут P -атомарными

Автоустойчивые I-алгебры

537

над I2 или элементами I2 , в z · y/I2 не будет атомов, а в z · x/I2 найдется бесконечное семейство атомов. Положим a = x · c. Ясно, что в I1 ∩ b a содержится бесконечное семейство непересекающихся I2 -атомов (так как

в c − a = c · y нет I2 -атомов из I1 ), что I1 P -атомарен над I2 в b a и что

любой b ∈ I1 ∩ b a является I2 -конечным. Применяя предложение 3, вновь получаем dimC (A) = ∞. Предложение доказано.

ПРЕДЛОЖЕНИЕ 5. Пусть (A, I1 , . . . , Iλ ) — вычислимая I-алгебра, P — некоторая характеристика, dimC (A) < ∞. Тогда A кусочно P регулярна. ДОКАЗАТЕЛЬСТВО. Если P = (I1 , . . . , Iλ ), то и P -идеал, и P сумма равны {0}, поэтому будем считать, что P = (I¯1 , . . . , I¯q , Iq+1 , . . . , Iλ ), где q > 1. Заметим: если A/Ik ∼ = 1 для некоторого k ∈ [1, q], то A кусочно P -регулярна. Если P -идеал содержится в Ik , то P -сумма и P -идеал совпадают. Если же найдется x ∈ A, который лежит в P -идеале и не лежит в Ik , то 1−x ∈ Ik и 1[ − x P -регулярна, а для x b верно (2) или (3) из определе-

ния P -регулярности. В силу предложения 4 получаем, что в A/I1 , . . . , A/Iq число атомов конечно.

Очевидно, что любая конечная алгебра кусочно P -регулярна. Предположим, что A бесконечна и заключение предложения неверно. Докажем, что dimC (A) = ∞. Воспользуемся теоремой 1. Нетрудно найти такие e0 , . . . , en ∈ A, что ei · ej = 0 при i 6= j, ei — Iα(i) -атом, где α : [0, n] → [1, q], и если g = 1 − (e0 + . . . + en ), то g/I1 , . . . , g/Iq — безатомные элементы. Пусть {A∗p }p∈ω — вычислимая последовательность конечных I-алгебр S ∗ такая, что A∗p ≤ A∗p+1 и A = Ap . Можно считать, что e0 , . . . , en ∈ A∗0 . p∈ω

Построим другую последовательность {Ap }p∈ω , для которой A∗p ≤ Ap ≤ S ≤ Ap+1 , A = Ap , а если x — атом Ap , Px ≤ P , x·(e0 +. . .+en ) = 0 и в Ap p∈ω

ровно k атомов, то в Ap+1 найдутся x(0) , . . . , x(k) | x такие, что Px(i) = Px

для всех i ∈ [0, k]. Рассуждая как при доказательстве предложения 1, предположим, что Ap уже определена, и сначала найдем A0p+1 ≤ A, для которой Ap ≤ A0p+1 и A∗p+1 ≤ A0p+1 . Пусть y — некоторый атом в A0p+1 , Py ≤ P и y · (e0 + . . . + en ) = 0. Тогда либо y ∈ Im , либо y/Im безатомен

538

П. Е. Алаев

для всех m ∈ [1, q] и по следствию 1 в A найдутся y (0) , . . . , y (k) | y такие, что Py(i) = Py для всех i ∈ [0, k]. Можно добиться того, чтобы для любого такого y указанные y (0) , . . . , y (k) существовали в Ap+1 . Докажем, что {Ap }p∈ω — искомая последовательность. Предположим, что x — атом Ap , Px ≤ P , x · (e0 + . . . + en ) = 0 и в Ap ровно k атомов. Пусть y0 , . . . , yt — атомы в A0p+1 и y0 , . . . , yt | x. Тогда (0)

Py0 ∪ . . . ∪ Pyt = Px и yi = yi

(k)

+ . . . + yi

Py(0) = . . . = Py(k) = Pyi . Полагая x(j) = i

i

в Ap+1 для каждого i ∈ [0, t], где (j) (j) y0 + . . . + yt , получим требуемое

разбиение x(0) , . . . , x(k) | x. Перейдем теперь от языка I-алгебр к предикатному языку, как в предложении 1. Положим c¯p = (e0 , . . . , en , c0 , . . . , cs ), где c0 , . . . , cs — все атомы Ap . Пусть формула ψp (x1 , x2 , x3 , u1 , . . . , u2λ , e0 , . . . , en , c0 , . . . , cs ) выражает, что x1 , x2 , x3 6 ci для некоторого i ∈ [0, s], xi · xj = 0 при i 6= j, xi · (e0 + . . . + en ) = 0 для i = 1, 2, 3, Px1 = Px2 = Px3 = P , x1 , x2 неразложимы, а x3 разложим и u1 , . . . , u2λ — его разложение, т. е. x3 = u1 + . . . + u2λ и каждый um имеет характеристику, меньшую, чем P . Ясно, что ψp можно считать ∀-формулой. Докажем, что система {Ap , ψp , c¯p }p∈ω ветвится на уровне p. Пусть (A, c¯p ) ≡1 (A, d¯p ), d¯p = (g0 , . . . , gn , d0 , . . . , ds ). Тогда d0 , . . . , ds | 1 в A, gj — Iα(j) -атомы для j ∈ [0, n] и gi · gj = 0 при i 6= j. Как уже было замечено, все gbj являются кусочно P -регулярными, поэтому найдется i ∈ [0, s] такое, что алгебра di − (g0\ + . . . + gn ) не будет кусочно P -регулярной. По лемме 6 в ней существуют b1 , b2 , b3 , удовлетворяющие формуле ψp (x1 , x2 , x3 , u ¯, d¯p ) (поскольку b3 разложим в A, есть и соответствующее разложение). Пусть t > p и a1 , a2 , a3 , u ¯ ∈ At таковы, что A |= ψp (a1 , a2 , a3 , u ¯, c¯p ). Покажем, что найдется изоморфное вложение β : At → At+1 , тождественное на Ap , для которого At+1 |= ¬ψp (β(a1 ), β(a2 ), β(a3 ), β(¯ u), c¯p ). Добьемся того, чтобы β(a1 ) стал разложимым в At+1 . Пусть a1 = d(0) + . . . + d(x) и a3 = h(0) + . . . + h(y) — разложение элементов a1 и a3 на атомы At , c 6 a2 — атом At характеристики P (он существует в силу неразложимости a2 ). Допустим, что d(0) , . . . , d(z) имеют характеристику P , а d(z+1) , . . . , d(x) — меньшие характеристики. Достаточно задать β на ато-

Автоустойчивые I-алгебры

539

мах At . Если u · (d(0) + . . . + d(z) + c + h(0) + . . . + h(y) ) = 0, то полагаем β(u) = u. Обозначим характеристику h(m) как P (m) для m ∈ [0, y], тогда P (m) < < P и P (0) ∪ . . . ∪ P (y) = P . По построению в At+1 для каждого m ∈ [0, y] (m)

найдется разложение h(m) = h0

(m)

+ . . . + hz+1 , где Ph(m) = P (m) . Полагаем i

 (0) (z)    β(c) = c + d + . . . + d , (0) (y) β(d(i) ) = hi + . . . + hi для i ∈ [0, z],    (m) β(h(m) ) = hz+1 для m ∈ [0, y].

Нетрудно проверить, что β сохраняет характеристики атомов At и, следовательно, является изоморфным вложением. Очевидно, что β(a1 ) = = β(d(0) )+. . .+β(d(x) ) разложим в At+1 . Все условия теоремы 1 проверены, и dimC (A) = ∞. Предложение доказано. ЛЕММА 11. Пусть (A, I1 , . . . , Iλ ) — вычислимая регулярная Iалгебра. Тогда все c-определимые в ней идеалы вычислимы. ДОКАЗАТЕЛЬСТВО. Пусть L = Ii1 + . . . + Iik — некоторый сопределимый идеал, x ∈ A — элемент характеристики P . Индукцией по мощности P построим алгоритм, определяющий, лежит ли x в L. Если P = ∅, то x = 0 и x ∈ L. Пусть Px = P = (I1 , . . . , Iq , I¯q+1 , . . . , I¯λ ) и для всех P ′ < P алгоритм уже построен. Будем считать, что P -идеал, равный I1 ∩ . . . ∩ Iq , совпадает с I1 . Если x ∈ Iis для некоторого s ∈ [1, k], то x ∈ L. Предположим, что x 6∈ Iis для всех s ∈ [1, k]. Тогда I1 ∩ Iis содержится в P -сумме для всех s. Условие x ∈ L равносильно тому, что x ∈ (I1 ∩ Ii1 ) + . . . + (I1 ∩ Iik ). Поскольку A P -регулярна, верен один из трех следующих вариантов. (1) P -сумма равна I1 . Находим для x разложение x = x1 +. . .+xn , где Pxm < P для всех m, и сводим вопрос к меньшим характеристикам Pxm . (2) P -сумма равна It ⊂ I1 . Характеристики элементов It , очевидно, меньше P , x 6∈ It и x 6∈ L. (3) P -сумма — максимальный собственный идеал в A. Начинаем одновременно для x и 1 − x искать разложение y1 + . . . + yn , где Pym < P (оно обязательно найдется). Если оно нашлось для 1 − x, то x 6∈ L. Если же

540

П. Е. Алаев

оно нашлось для x, вопрос сводится к меньшим характеристикам. Лемма доказана.

§ 3. Критерий автоустойчивости Сформулируем теперь критерий автоустойчивости, что является целью данной работы. Он будет верен только для алгебр, замкнутых относительно пересечений идеалов, но поскольку в язык всегда можно добавить новые идеалы для пересечений, из него будет следовать и критерий для любых I-алгебр: все вхождения слова ”идеал“ заменим на фразу ”конечное пересечение идеалов, {0} или A“. Назовем замкнутую относительно пересечений идеалов I-алгебру (A, I1 , . . . , Iλ ) устойчивой, если она регулярна, идеал L1 → L2 с-определим в A для любых с-определимых L1 , L2 ⊳ A и выполняется одно из условий (a) A/L безатомна для любого с-определимого L ⊳ A; (b) существует такой с-определимый идеал L0 , что A/L0 ∼ = 1, и если L ⊳ A с-определим, то либо L = A, либо L = L0 , либо L ⊂ L0 и A/L безатомна. Напомним, что идеал с-определим, если он имеет вид Ii1 + . . . + Iik , где {i1 , . . . , ik } ⊆ [1, λ]. В приводимой ниже теореме условие (3) достаточно легко проверяется, в то время как (4) дает много информации о строении автоустойчивых алгебр. ТЕОРЕМА 3. Пусть (A, I1 , . . . , Iλ ) — вычислимая I-алгебра, замкнутая относительно пересечений идеалов. Эквивалентны следующие условия: (1) A автоустойчива; (2) dimC (A) < ∞; (3) A кусочно P -регулярна для любой характеристики P ⊆ [1, λ], идеалы вида L1 → L2 кусочно c-определимы в A для любых c-определимых L1 , L2 ⊳ A, и A/In содержит конечное число атомов для всех n ∈ [1, λ]; (4) A — конечное прямое произведение устойчивых алгебр. ДОКАЗАТЕЛЬСТВО. (1) ⇒ (2). Очевидно.

Автоустойчивые I-алгебры

541

(2) ⇒ (3). Из предложения 4 следует конечность числа атомов в A/In , из предложения 5 — кусочная P -регулярность для любого P . Поскольку число различных характеристик конечно и P -регулярность сохраняется при переходе от A к b a, последнее влечет кусочную регулярность A в силу леммы 5. Из предложения 1 получаем, что идеалы вида Ij → Im

кусочно с-определимы в A. Все с-определимые в A идеалы вычислимы в силу леммы 11.

Если в некоторой вычислимой модели есть отношение, которое сохраняется при автоморфизмах и вычислимо в любой ее вычислимой копии, то добавление в язык нового предиката для этого отношения не меняет алгоритмическую размерность. Следовательно, если обогатить язык A новыми предикатами, выделяющими все с-определимые идеалы, получая I-алгебру A∗ , то dimC (A∗ ) тоже будет конечной. Нетрудно проверить, что A∗ замкнута относительно пересечений идеалов, а с-определимые и кусочно с-определимые идеалы в A и A∗ совпадают. Повторяя для A∗ все приведенные выше рассуждения, получим, что L1 → L2 кусочно с-определим в A для любых с-определимых L1 , L2 ⊳ A. (3) ⇒ (4). Легко показать, что A является конечным прямым произведением алгебр B, каждая из которых обладает следующими свойствами: B регулярна, с-определимые идеалы в B замкнуты относительно →, а число атомов в B/In конечно для любого n ∈ [1, λ]. Заканчивает доказательство следующая ЛЕММА 12. Пусть (A, I1 , . . . , Iλ ) регулярна, с-определимые идеалы в A замкнуты относительно →, а число атомов в A/In конечно для любого n ∈ [1, λ]. Тогда A изоморфна конечному прямому произведению устойчивых алгебр. ДОКАЗАТЕЛЬСТВО. Сначала проверим свойство: если идеал L сопределим, то в A/L число атомов конечно. Пусть L = I1 + . . . + Ik . Допустим, что в A есть бесконечная последовательность L-атомов {an }n∈ω , в которой an · am = 0 при n 6= m. Можно считать, что все они неразложимы и имеют характеристику P . Тогда каждый an лежит в P -идеале и не принадлежит P -сумме. Ясно, что L является подмножеством P -суммы

542

П. Е. Алаев

вb an для всех n ∈ ω. Следовательно, an — атомы по P -сумме. Поскольку A P -регулярна, это возможно только в случае, когда P -сумма равна Im

для некоторого m ∈ [1, λ]. По условию A не может содержать бесконечно

много Im -атомов, получаем противоречие. Предположим, что L0 — с-определимый идеал в A, A/L0 ∼ = 1 и A/L безатомна для всех с-определимых L ⊳ A, L 6= L0 . Индукцией по числу нетривиальных (т. е. не равных {0} и A) с-определимых идеалов докажем, что A — прямая сумма устойчивых алгебр. Если нетривиальных идеалов ∼ 1 и очевидно, что A — устойчивая I-алгебра. нет, то L0 = {0}, A = Ш а г и н д у к ц и и. Предположим, что в A есть с-определимый идеал L 6= A, не являющийся подмножеством L0 . Если a ∈ L \ L0 и b = 1 − a, то b ∈ L0 , bb удовлетворяет свойству (a) и является устойчивой, а в b a число

нетривиальных идеалов меньше, следовательно, к ней можно применить индукционное предположение.

Пусть теперь L0 , . . . , Ln — все различные с-определимые идеалы в A. Индукцией по сумме числа атомов в A/L0 , . . . , A/Ln докажем, что A изоморфна прямой сумме устойчивых алгебр. Если таких атомов нет, то A устойчивая. Ш а г и н д у к ц и и. Предположим, что такие атомы есть, и рассмотрим два случая. (1) Существуют a, b ∈ A, a · b = 0 такие, что a/Lm и b/Lk — атомы для некоторых k, m ∈ ω. Тогда к b a и 1[ − a применимо индукционное предположение.

(2) Таких a, b нет. В частности, A/Lm содержит не более одного

атома для всех m ∈ [0, n]. Пусть A/L0 , . . . , A/Lq содержат один атом, A/Lq+1 , . . . , A/Ln — безатомны. Если a0 /L0 и a1 /L1 — атомы, то варианты a0 · a1 ∈ L0 и a0 · a1 ∈ L1 невозможны, поэтому a0 · a1 /L0 — атом и L0 = L1 в a\ 0 · a1 . Рассуждая далее таким же образом, получим существование a ∈ A со свойствами: a/L0 — атом, L0 = L1 = . . . = Lq в b a, а 1[ − a/Lk безатомны для всех k ∈ [0, n]. К b a можно применить полученное выше утверждение. Лемма доказана.

Далее будет показано, что при фиксированном λ число неизоморф-

Автоустойчивые I-алгебры

543

ных устойчивых I-алгебр (A, I1 , . . . , Iλ ) конечно, и те из них, которые являются вычислимыми, автоустойчивы. Последнее позволит завершить доказательство теоремы, так как автоустойчивые I-алгебры замкнуты относительно прямых произведений. ЛЕММА 13. Если (A, I1 , . . . , Iλ ) — устойчивая алгебра, и L ⊳ A — c-определимый идеал, то (A/L, I1 /L, . . . , Iλ /L) тоже устойчива. ДОКАЗАТЕЛЬСТВО. Напомним, что a/L ∈ In /L ⇔ a ∈ In + L. Если P = (I1 , . . . , Iq , I¯q+1 , . . . , I¯λ ) — некоторая характеристика, то P -идеал в A/L равен {a/L | a/L ∈ I1 /L ∩ . . . Iq /L} = {a/L | a ∈ (I1 ∩ . . . ∩ Iq ) + L} = {a/L | a — элемент P -идеала в A}. Аналогично, P -сумма равна {a/L | a — элемент P -суммы в A}. Отсюда легко следует, что алгебра A/L P -регулярна.

Нетрудно проверить: если M1 , M2 ⊳ A, то (M1 /L) → (M2 /L) = ((M1 + +L) → (M2 +L))/L. Следовательно, с-определимые идеалы в A/L замкнуты относительно →. Любой с-определимый идеал M ⊳A/L имеет вид M0 /L, ∼ A/(M0 + L). Рассмотрев где M0 — с-определимый идеал в A, и (A/L)/M = несколько случаев, из этого легко вывести последнее свойство устойчивых I-алгебр. Лемма доказана. Идеал In называем атомарным, если In 6= {0} и In ∩Ik ∈ {In , {0}} для любого k ∈ [1, λ]. Нетрудно проверить, что In атомарен тогда и только тогда, когда он P -атомарен над {0} для некоторой характеристики P в смысле данного ранее определения. Очевидно, что два атомарных идеала либо равны, либо пересекаются по {0}, и для каждого Ik 6= {0} найдется атомарный In ⊆ Ik . Если (A, I1 , . . . , Iλ ) — I-алгебра, то ее атомарный набор — ¯ = (Ii , . . . , Iiq ), включающий в себя все атомарные идеалы A это набор E 1

с точностью до равенства, где i1 < . . . < iq , все Iim атомарны и Iim 6= Ik при k < im . Последнее означает, что для любого класса равных атомарных идеалов из {I1 , . . . , Iλ } в этот набор включается идеал с наименьшим номером. В любой ненулевой I-алгебре есть непустой атомарный набор. ¯ Назовем E-характеристикой идеала Ik множество {m ∈ [1, q] | Iim ⊆ Ik }. ЛЕММА 14. Пусть (A, I1 , . . . , Iλ ), (B, I1 , . . . , Iλ ) — две устойчи¯ = (I1 , . . . , Iq ) — атомарный набор как в A, так и в B, вые I-алгебры, E

544

П. Е. Алаев

M = I1 + . . . + Iq . Алгебры (A, I1 , . . . , Iλ ) и (B, I1 , . . . , Iλ ) изоморфны тогда и только тогда, когда (A/M, I1 /M, . . . , Iλ /M ) ∼ = (B/M, I1 /M, . . . , Iλ /M ), ¯ мощности A и B совпадают и E-характеристики идеалов In в A и B равны для любого n ∈ [1, λ]. ДОКАЗАТЕЛЬСТВО. (⇒). Очевидно. (⇐). Алгебра A устойчива и {0} с-определим в A, поэтому A ∼ = 0, или A ∼ = 1, или A — ненулевая безатомная. В первом случае B ∼ = 0 и ¯ = (I1 ), где I1 — вся алгебра. изоморфизм очевиден, во втором B ∼ = 1, а E ¯ Из равенства E-характеристик следует, что (A, I1 , . . . , Iλ ) ∼ = (B, I1 , . . . , Iλ ). Далее предполагаем, что A, B — ненулевые безатомные алгебры. Пусть f : A/M → B/M — изоморфизм, сохраняющий идеалы In /M , ¯ а E-характеристики любого идеала In в A и B совпадают. Построим критерий изоморфизма (см. [2]) V = {ha, bi ∈ A × B | f (a/M ) = b/M и b a ∩ Ik = {0} ⇔ bb ∩ Ik = {0} для любого k ∈ [1, q]}. Поскольку все элементы атомарного набора не равны {0}, пара h1, 1i принадлежит V . Если

ha, 0i ∈ V , то a/M = 0, т. е. a ∈ I1 + . . . + Iq , и b a ∩ Ik = {0} для любого k ∈ [1, q]. Очевидно, a = 0.

Предположим, что ha, bi ∈ V и a1 , a2 | a. Докажем существование

таких b1 , b2 | b, что ha1 , b1 i, ha2 , b2 i ∈ V . Вначале найдем пару b∗1 , b∗2 | b, a1 является для которой f (a1 /M ) = b∗1 /M и f (a2 /M ) = b∗2 /M . Идеал Ik ∩ b ∗ главным тогда и только тогда, когда Ik ∩ bb — главный, для любого k ∈ 1

∈ [1, q]. Предположим, что Ik ∩ b a1 — главный. Тогда a1 /M = a′1 /M , где P a′1 ∈ Ik → {0}. Поскольку A — устойчивая алгебра, Ik → {0} = Im P m∈S для некоторого S ⊆ [1, λ], S 6= ∅. Следовательно, a1 /M ∈ Im /M и m∈S

¯ k не входит в E-характеристику Im ни для какого m ∈ S. По условию P P Im ∩Ik = {0} и в B, а b∗1 /M ∈ Im /M , т. е. b∗1 /M = b′1 /M , где b′1 ∈ Im . m∈S

m∈S

Получаем, что bb∗1 ∩ Ik — главный идеал. Рассуждения в обратную сторону

аналогичны. То же самое верно и для пары (a2 , b∗2 ).

Осталось найти b1 , b2 | b, для которых b1 /M = b∗1 /M , b2 /M = b∗2 /M и

ai ∩ Ik = {0} ⇔ bi ∩ Ik = {0} при любом k ∈ [1, q]. Покажем, как добиться последних эквивалентностей для фиксированного k ∈ [1, q]. Поскольку

Автоустойчивые I-алгебры

545

разные атомарные идеалы не пересекаются, общий случай следует из этого. Рассмотрим три варианта: (1) b a1 ∩ Ik = {0}, b a2 ∩ Ik = {0}, тогда b a ∩ Ik = bb ∩ Ik = {0} и требуемое

очевидно;

(2) b a1 ∩ Ik 6= {0}, b a2 ∩ Ik = {0}, тогда bb∗2 ∩ Ik — главный идеал; если

он равен b c, то следует переместить c из b∗2 в b∗1 ;

(3) b a1 ∩ Ik 6= {0}, b a2 ∩ Ik 6= {0}, тогда b a ∩ Ik 6= {0} и bb ∩ Ik 6= {0}; если, например, bb∗ ∩ Ik = {0}, то найдем в bb∗ элемент c ∈ Ik \ {0}, разделим его 2

1

на ненулевые c1 , c2 | c и переместим c2 в b∗2 .

Тем самым показано, что V — критерий Воота для булевых алгебр A и B без идеалов. Чтобы он стал критерием изоморфизма I-алгебр, требуется проверить, что a ∈ In ⇔ b ∈ In для любых пар ha, bi ∈ V и n ∈ [1, λ]. Предположим, что a ∈ In . Тогда b ∈ In + (I1 + . . . + Iq ). Допустим, что b 6∈ In . Тогда найдутся такие c 6 b и k ∈ [1, q], что c ∈ Ik \ In . Следователь¯ но, bb ∩ Ik 6= {0} и k не входит в E-характеристику In . Тогда Ik ∩ In = {0} вAиb a ∩ Ik 6= {0}, получаем противоречие. Лемма доказана.

СЛЕДСТВИЕ 2. Пусть (A, I1 , . . . , Iλ ) — ненулевая устойчивая I¯ = (I1 , . . . , Iq ) — атомарный набор в A, M = I1 + . . . + Iq , алгебра, E a ¯ = a0 , . . . , an , ¯b = b0 , . . . , bn и a ¯ | 1, ¯b | 1 в A. Модели (A, I1 , . . . . . . , Iλ , a ¯) и (A, I1 , . . . , Iλ , ¯b) изоморфны тогда и только тогда, когда (A/M, I1 /M, . . . , Iλ /M, a ¯/M ) ∼ = (A/M, I1 /M, . . . , Iλ /M, ¯b/M ) и для любых c-определимого идеала L ⊳ A и i ∈ [0, n] верна эквивалентность ai ∈ L ↔ ↔ bi ∈ L. ДОКАЗАТЕЛЬСТВО. (⇒). Очевидно. (⇐). Воспользуемся доказательством предыдущей леммы, полагая B = A. Пусть f : A/M → A/M — автоморфизм I-алгебры A/M , переводящий a ¯/M в ¯b/M . Ясно, что пары hai , bi i лежат в V : если b ai ∩ Ik = {0} для некоторого k ∈ [1, q], то ai ∈ Ik → {0} и bi ∈ Ik → {0}, так как Ik → {0} — с-определимый идеал в A. В силу критерия Воота найдется автоморфизм A, переводящий a ¯ в ¯b. Следствие доказано.

ЛЕММА 15. Пусть (A, I1 , . . . , Iλ ) — устойчивая I-алгебра, a ¯ = = a0 , . . . , an , ¯b = b0 , . . . , bn и a ¯ | 1, ¯b | 1 в A. Тогда (A, I1 , . . . , Iλ , a ¯) ∼ =

546

П. Е. Алаев

∼ = (A, I1 , . . . , Iλ , ¯b) в том и только том случае, если для любого cопределимого L ⊳ A верны эквивалентности ai ∈ L ⇔ bi ∈ L. ДОКАЗАТЕЛЬСТВО. (⇒). Очевидно. (⇐). Докажем утверждение индукцией по числу не равных {0}, сопределимых идеалов в A. Если их нет, то A = {0} и лемма верна. Ш а г и н д у к ц и и. Допустим, что число различных с-определимых идеалов равно k > 0. Тогда A 6= {0} и в A есть непустой атомарный ¯ Пусть E ¯ = (I1 , . . . , Iq ) и M = I1 + . . . + Iq . Тогда A/M — набор E. устойчивая алгебра с меньшим числом с-определимых идеалов. Любой сопределимый идеал L ⊳ A/M имеет вид L0 /M , где L0 ⊳ A с-определим, и ai /M ∈ L ⇔ ai ∈ M + L0 . Применяя индукционное предположение, получим (A/M, I1 /M, . . . , Iλ /M, a ¯/M ) ∼ = (A/M, I1 /M, . . . , Iλ /M, ¯b/M ). Следствие 2 позволяет завершить индукционный шаг. Лемма доказана. Завершим доказательство теоремы 3. (4) ⇒ (1). Это следует из последней леммы: отношение (A, I1 , . . . ¯, ¯b из A тоже зада. . . , Iλ , a ¯) ∼ = (A, I1 , . . . , Iλ , ¯b) на произвольных наборах a ется явной формулой через с-определимые идеалы. Если (A, I1 , . . . , Iλ ) — вычислимая устойчивая I-алгебра, то все с-определимые идеалы в ней будут вычислимы в силу леммы 11. Отсюда легко получить автоустойчивость (A, I1 , . . . , Iλ ). Теорема доказана. СЛЕДСТВИЕ 3. Для любого λ число (счетных) устойчивых Iалгебр вида (A, I1 , . . . , Iλ ) конечно. ДОКАЗАТЕЛЬСТВО вытекает из леммы 14 индукцией по числу различных с-определимых идеалов в (A, I1 , . . . , Iλ ). Если идеал один, то A = {0} — такая I-алгебра единственна. Если фиксированы атомарный ¯ и фактор-алгебра (A/M, I1 /M, . . . , Iλ /M ), то тип изоморфизма набор E (A, I1 , . . . , Iλ ) определяется выбором из конечного набора параметров. По-видимому, на основе леммы 14 можно построить индуктивное описание класса устойчивых I-алгебр. В качестве примера кратко охарактеризуем автоустойчивые алгебры A с двумя выделенными идеалами I1 , I2 . Необходимо сделать A замкнутой относительно пересечений идеалов. Будем считать, что I3 = I1 ∩ I2 , I4 = {0} и I5 = A. Опишем ненулевые

Автоустойчивые I-алгебры

547

устойчивые алгебры (A, I1 , I2 , I3 , I4 , I5 ) такого вида. Назовем идеал In тривиальным, если он равен {0} или A. Алгебра A изоморфна A/I4 , поэтому она либо двухэлементна, либо безатомна. В первом случае все идеалы тривиальны и существуют четыре такие алгебры. Описание требуется лишь для второго случая. Если все идеалы снова тривиальны, то получаем еще четыре алгебры. ¯ = (I1 ) будет атоДопустим, что I2 тривиален, а I1 — нет. Тогда E марным набором, и если M = I1 , то в силу леммы 14 тип изоморфизма будет однозначно определяться алгеброй (A/M, I1 /M, . . . , I5 /M ). Последняя тоже устойчива, в ней уже все идеалы тривиальны, она входит в перечень описанных выше алгебр, и возможны четыре варианта. Заметим, что идеал I1 → {0} должен быть с-определимым в A, поэтому он равен {0}. Замена I1 на I2 дает еще четыре варианта. Тем самым, в частности, получается описание автоустойчивых алгебр с одним выделенным идеалом, совпадающее с приведенным в [3]. Допустим теперь, что оба идеала I1 , I2 нетривиальны. Рассмотрим ¯ = (I1 , I2 ) будет атосначала случай, когда I3 = I1 ∩ I2 = {0}. Здесь E марным набором и если M = I1 + I2 , то (A/M, I1 /M, . . . , I5 /M ) — снова алгебра с тривиальными идеалами. Если A/M ∼ = 0, то A — сумма двух уже описанных алгебр. Остаются два варианта: A/M ∼ = 1 и A/M — безатомна. Из определения устойчивости следует, что I1 → {0} = I2 и I2 → {0} = I1 . Этот набор условий однозначно определяет A, такие алгебры существуют и являются конструктивизируемыми. При этом 5-регулярность и безатомность A/M противоречат друг другу, поэтому остается вариант A/M ∼ = 1. ¯ = Последняя возможность: I3 6= {0}. Здесь I3 → {0} = {0} и E = (I3 ) — атомарный набор. Алгебра (A/I3 , I1 /I3 , . . . , I5 /I3 ) входит в число уже описанных — это дает еще семь вариантов. Тем самым указан набор из двадцати четырех алгебр, конечные суммы элементов которого образуют класс автоустойчивых алгебр. Из леммы 15 следует, что элементарная теория любой устойчивой I-алгебры (A, I1 , . . . , Iλ ) ω-категорична, так как для любого n > 1 в An найдется лишь конечное число определимых подмножеств (см. описание

548

П. Е. Алаев

ω-категоричных теорий в [8]). В [9] построена некоторая характеризация I-алгебр с ω-категоричными и конечно аксиоматизируемыми теориями. В частности, там доказано: если элементарная теория I-алгебры ωкатегорична, то она конечно аксиоматизируема. Приводимое ниже следствие 4 вытекает из того, что модели с ω-категоричными теориями замкнуты относительно прямых произведений. Заметим, что далее речь идет уже о произвольных I-алгебрах, без свойства замкнутости. СЛЕДСТВИЕ 4. Элементарная теория любой автоустойчивой I-алгебры ω-категорична, конечно аксиоматизируема и, следовательно, разрешима. СЛЕДСТВИЕ 5. Для любого λ существует конечный набор C1 , . . . , Cn I-алгебр вида (C, I1 , . . . , Iλ ) со следующим свойством: I-алгебра (A, I1 , . . . , Iλ ) автоустойчива тогда и только тогда, когда она является конечной прямой суммой алгебр из {C1 , . . . , Cn }. ДОКАЗАТЕЛЬСТВО. Для произвольной I-алгебры A с λ идеалами через A∗ обозначим результат добавления в язык A новых предикатов для {0}, A и всех конечных пересечений идеалов. Можно считать, что число идеалов в A∗ равно 2λ +1. Если A автоустойчива, то A∗ ∼ = B ∗ ×. . .×B ∗ , где 1

Bi∗

— устойчивые алгебры. Пусть Bi — результат удаления из

k

Bi∗

новых

предикатов, тогда Bi автоустойчивы. В качестве {C1 , . . . , Cn } можно взять множество всех таких Bi . Идеал в I-алгебре назовем Lωω -определимым, если он может быть определен формулой первого порядка (в языке I-алгебры). В последнем следствии говорится о классе всех I-алгебр, с любым числом идеалов. СЛЕДСТВИЕ 6. Класс автоустойчивых I-алгебр совпадает с классом (счетных) I-алгебр с ω-категоричной элементарной теорией, с точностью до добавления в язык конечного числа новых Lωω -определимых идеалов. ДОКАЗАТЕЛЬСТВО. Если I-алгебра автоустойчива, то ее теория ω-категорична в том же языке. Допустим, что теория (A, I1 , . . . , Iλ ) ωкатегорична. Тогда она разрешима, а сама алгебра конструктивизируема.

Автоустойчивые I-алгебры

549

Добавим к набору {I1 , . . . , Iλ } идеалы {0} и A, а затем начнем добавлять новые идеалы, которые могут быть получены из исходных операциями ∩, + и →. Все такие идеалы будут Lωω -определимы, и через конечное число шагов мы получим набор {I1′ , . . . , Iµ′ }, замкнутый относительно ∩, + и →, в силу конечности числа Lωω -определимых подмножеств. Легко проверить, что (A, I1′ , . . . , Iµ′ ) будет удовлетворять п. (3) из теоремы 3: все с-определимые идеалы, P -идеалы и P -суммы будут лежать в {I1′ , . . . , Iµ′ }, а в A/In′ число атомов будет конечным, так как иначе в ней найдется бесконечное число неэквивалентных формул. Тем самым (A, I1′ , . . . , Iµ′ ) будет автоустойчива. Следствие доказано. В заключение автор выражает благодарность С. С. Гончарову, О. В. Кудинову и Н. Т. Когабаеву за полезные обсуждения и анализ работы. Идея использования отношения ≡1 в формулировке теоремы 1 была высказана О. В. Кудиновым (исходный вариант содержал ≤1 ). Работа также опирается на многие идеи из [10].

ЛИТЕРАТУРА 1. J. B. Remmel, Recursive isomorphism types of recursive Boolean algebras, J. Symb. Log., 46, N 3 (1981), 572—594. 2. С. С. Гончаров, В. Д. Дзгоев, Автоустойчивость моделей, Алгебра и логика, 19, N 1 (1980), 45—58. 3. Н. Т. Когабаев, Автоустойчивость булевых алгебр с выделенным идеалом, Сиб. матем. ж., 39, N 5 (1998), 1074—1084. 4. Ю. Г. Венцов, Алгоритмические свойства ветвящихся моделей, Алгебра и логика, 25, N 4 (1986), 369—383. 5. Handbook of recursive mathematics, Y. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel (eds.), vol. 1 (Stud. Logic Found. Math., 139), Amsterdam, Elsevier Science B.V., 1998. 6. С. С. Гончаров, Ю. Л. Ершов, Конструктивные модели (Сибирская школа алгебры и логики), Новосибирск, Научная книга, 1999. 7. С. С. Гончаров, Счетные булевы алгебры и разрешимость (Сибирская школа алгебры и логики), Новосибирск, Научная книга (НИИ МИОО НГУ), 1996.

550

П. Е. Алаев 8. Г. Кейслер, Ч. Ч. Чэн, Теория моделей, М., Мир, 1977. 9. Д. Е. Пальчунов, Конечно-аксиоматизируемые булевы алгебры с выделенными идеалами, Алгебра и логика, 26, N 4 (1987), 435—455.

10. A. Touraille, Th´eories d’alg`ebres de Boole munies d’id´eaux distingu´es. I: Th´eories ´el´ementaires, J. Symb. Log., 52, N 4 (1987), 1027—1043.

Поступило 19 февраля 2003 г. Окончательный вариант 18 июля 2003 г. Адрес автора: АЛАЕВ Павел Евгеньевич, Институт математики СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, РОССИЯ. e-mail: [email protected]