Сильная конструктивизируемость булевых алгебр тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

Леонл-еяи-Леонтьева Маргарита Николаевна

СИЛЬНАЯ КОНСТРУКТИВИЗИРУЕМОСТЬ БУЛЕВЫХ АЛГЕБР

01.01.06 — математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск-2013 1 Я МАР 20,3

005051169

005051169

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

Научный руководитель:

доктор физико-математических наук Алаев Павел Евгеньевич Официальные оппоненты:

Морозов Андрей Сергеевич, доктор физико-математических наук, профессор, Федеральное государственное бюджетное учреждение науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук, заведующий лабораторией

Коровина Маргарита Владимировна, кандидат физико-математических наук, Федеральное государственное бюджетное учреждение науки Институт систем информатики им. А. П. Ершова Сибирского отделения Российской академии наук, старший научный сотрудник

Ведущая организация: федеральное государственное автономное образовательное учреждение высшего профессионального образования «Казанский (Приволжский) федеральный университет»

<6 ОО

Защита состоится «24» апреля 2013 г. вД0 часов 30" минут на заседании диссертационного совета Д 003.015.02 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090, Новосибирск, пр. Акад. Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИИ

Тематика диссертации. Диссертация посвящена решению некоторых проблем теории вычислимых (конструктивных) моделей. Её основные результаты относятся к вычислимым булевым алгебрам. Теория вычислимых (конструктивных) моделей берет истоки в 50-х годах прошлого века в трудах А. И. Мальцева [13], М. О. Рабина. [23], Р. Воота [24],

B. А. Кузнецова, А. Фрёлиха и Дж. Шефердсона [18]. Изучению вычислимых булевых алгебр в частности посвящен ряд работ Ю. Л. Ершова,

C. С. Гончарова и их учеников, а также многочисленных зарубежных исследователей.

Напомним, что модель конечного языка называется вычислимой, если её носитель — вычислимое множество натуральных чисел, операции — вычислимые функции, и отношения вычислимы. Вычислимая модель называется п-вычислимой, если существует алгоритм, определяющий по конечной Е„-формуле и набору элементов, истинна ли эта формула на этом наборе. Сильно вычислимая модель — та, для которой подобный алгоритм существует для всех формул исчисления предикатов. Мы будем называть модель сильно конструкгпивизируемой, если у неё существует сильно вычислимая изоморфная копия.

Понятие сильно вычислимой (сильно конструктивной) модели было введено Ю. Л. Ершовым ]10] в 1968 году. Заметим, что данная теория активно разрабатывалась в математической школе А. Нероуда на основе аналогичного (по существу, эквивалентного) понятия разрешимой модели, изучаемого также Л. Харрингтоном [21] и М. Морли [22].

В диссертации рассматриваются 63'левы алгебры — дистрибутивные решетки с наибольшим и наименьшим элементами, и дополнениями. В решетке у каждых двух элементов хну есть точная нижняя и верхняя грань, которые, следуя [19], будем символически обозначать как х ■ у и ж -г у, соответственно. Дополнение элемента х до наибольшего элемента булевой алгебры обозначаем (—ж). Говоря о вычислимой булевой алгебре, будем подразумевать, что она вычислима как модель в языке £в а — {+,-,— ,0,1}, где 0 и 1 соответствуют наименьшему и наибольшему элементам.

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

справочника [19]. Мы будем работать со счетными булевыми алгебрами, иногда называя их кратко алгебрами; в качестве источника предварительных сведений но теории булевых алгебр будем использовать [6]. С точки зрения теории вычислимых моделей одним из наиболее естественных вопросов является описание тех булевых алгебр, которые являются сильно конструктивизируемыми.

Перейдем к описанию задач, которым посвящена данная диссертация. Для этого сначала сформулируем ряд понятий и обозначений.

Для произвольных идеалов Ii и I2 булевой алгебры будем использовать следующее обозначение: Ii + I2 = {х + у\х е у е 12}.

Пусть 25 — алгебра. Ненулевой элемент а е 25 называется атомом, если Vb(b < а =Ф» b = 0). Множество атомов алгебры 23 обозначим Ato (25). Элемент а е. 25 называется атомным, если

Ух < а(х ф 0 => (3у К* х(у е At0(Ü5)))). .

Атомные элементы образуют идеал, который мы будем обозначать как Atm0(23). Элемент а £ 23 называется безатомным, если \/х < а (,х Ato(23)); безатомные элементы также образуют идеал, и он обозначается Als0(23). Через F0(23) обозначим идеал Фре-ше (идеал, порожденный атомами), Е(23) = Also(25) 4- Atmo(23) — идеал Ершова-Тарского. Пусть {Ета}п6ш — последовательность итерированных идеалов Ершова-Тарского, то есть Ео(25) = {0}, Еп+1(23) = (Е„оЕ)(Ш) = {х е 23| х/Е n € Е(23/Еп)}. Для каждого fc£u обозначим через Atfc предикат, выделяющий в каждой алгебре множество таких элементов х, что х/Еk — атом. Аналогично определяются предикаты Ffc, Alsfc и Atm*.. Для предикатов At0,Fo, Als0, Atmo,Ei будут иногда использоваться обозначения At, F, Ais, Atm, Е, соответственно.

Определим некоторые наборы одноместных предикатных символов. Пусть Ф0 = {Е0}, Фп = Ф0 U {Ato,Also,Atmo,E1,...,At„_i,Alsn_i, Atm„_i,E„} для n > 1 и Фи = {Е0, At0, Als0, Atm0, Еь ...}.

Важную роль в теории булевых алгебр играет понятие элементарной характеристики. Наименьшее п, для которого En+i(23) = 23, называется первой (элементарной) характеристикой алгебры 23 и обозначается chi(23). Если таких п нет, полагаем c/¿i(23) = 00. При c/ij (23) = 00 считаем, что вторая с/12 (25) и третья с/гз(23) (элементарные) характеристики алгебры 23 равны нулю. В противном случае (т.е. если c/¡i(23) = п), вторая характеристика с/г2(23) равна числу атомов алгебры 23/Е„. если это

число конечно, и eh,2{(3) = со, если в 23/Е„ бесконечно много атомов. Третья характеристика c/i3 (23) равна 1, если в 23/Е„ есть ненулевой безатомный элемент, и равна 0 в противном случае.

Элементарная характеристика c/i(23) алгебры 23 — это тройка (с/гх(?В),с/г2(5В), с/г3(03)). Определенная таким образом элементарная характеристика обладает тем свойством, что две булевы алгебры элементарно эквивалентны (имеют одну и ту же элементарную теорию) тогда и только тогда, когда их элементарные характеристики равны.

Для каждой элементарной теории булевой алгебры Т, кроме той, которая соответствует элементарной характеристике (оо,0,0), Ю.Л.Ершов в [9] построил конечный набор предикатов Ф(Т), определяемых формулами первого порядка, такой, что булева алгебра 23 с элементарной теорией Т является сильно вычислимой тогда и только тогда, когда 23 вычислима и вычислимы все предикаты из набора Ф(Т). Позже С.С.Гончаровым было показано, что при п < Ф(Т)| вычислимость 2} вместе с вычислимостью первых п + 1 предикатов набора Ф(Т) равносильна вычислимости £„-диаграммы 23, т.е. п-вычислимости.

В терминах приведенных выше обозначений и понятий, набор предикатов Ф(Т), представленный Ю. Л. Ершовым в [9] имеет вид Фп+ъ где п (Е lü является первой элементарной характеристикой, соответствующей теории Т.

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

Задача 1. Если SCf(I) и известно, что 23 вычислима и в 23 вычислимы все предикаты из S, то можно ли утверждать, что 23 сильно копструктивизируема ?

Данная проблема привлекала серьезное внимание широкого круга исследователей. В работах С. С. Гончарова, С. П. Одинцова, В. Н. Власова и П. Е. Алаева был получен ряд результатов о связи п-вычислимости с сильной конструктивизируемостыо, то есть для случая, когда S является начальным отрезком Ф(Т). В частности, П. Е. Алаевым был получен окончательный ответ для этого случая. Приведем здесь краткий обзор этих результатов.

В [8] приводится пример О-вычислимой (то есть просто вычислимой) алгебры характеристики (0, ос,0), не имеющей сильно вычислимого представления. При этом из [9] следует, что в этом случае 1-вычислимость влечет не только сильную конструктивизируемость, но и сильную вычислимость. Для (0,т,0) и (0,т,1), т G и, ответ сразу

следует из [9]: вычислимость означает и сильную вычислимость.

В [9] указаны достаточные условия сильной вычислимости (а значит, и сильной конструктивизируемости) и для всех остальных характеристик вида (т, *■,*), где т € и>. Например, для характеристик (то, оо,0) и (т, оо,1) сильная вычислимость следует из (4т + 1)-вычислимости. Небольшая модификация примера из [8], выполненная в [6], показывает, что 4т-вычис.лимости недостаточно и для сильной конструктивизируемости.

В [14] было показано, что для характеристики (1,1,0) 2-вычисли-мость влечет сильную конструктивизируемость, а для (1,0,1) 3-вычис-лимость влечет сильную конструктивизируемость. В [6] было завершено доказательство того, что для (1,1,0) уже 1-вычислимость влечет сильную конструктивизируемость. В [5] для характеристики (1,0,1) был построен пример 1-вычислимой алгебры, не имеющей сильно вычислимого представления. В [1] было доказано, что для характеристики (1,0,1) уже 2-вычислимость влечет сильную конструктивизируемость. В [2] получено, что для характеристики (ш, 1,0), то > 2, сильная конструктивизируемость следует из (4т — 3)-вычислимости, а для (т, 0,1), то > 2, — из (4т— 2)-вычислимости. В [25] доказано, что в случае алгебры характеристики (т,0,1), то > 0 из (4т — 3)-вычислимости и вычислимости предиката также следует сильная конструктивизируемость.

В диссертации ответ найден для всех возможных подмножеств 5 С Ф(Т), сформулированный в теореме 1, и тем самым завершено исследование, имеющее столь длинную историю.

Теорема 1. Пусть п,р Є ш, 93 — вычислимая булева алгебра с первой элементарной характеристикой п, 5 С Ф,1+і и в '■В вычислимы все предикаты из 5.

(1) Пусть элементарная характеристика равна (п,р, 1). Если для каждого к < п в 5 содержится А^ и хотя бы один из предикатов АЬн и Аітпі- , то *В имеет сильно вычислимое представление; в противном случае она не является, вообще говоря, сильно конструк-тивизируемой.

(2) Пусть элементарная характеристика 03 равна (п,р+1,0). Если для каждого к <п в Б содержится А^ и для каждого т < п — 1 хотя бы один из предикатов А1нт и А І.гпт, то Ш имеет сильно вычислимое представление; в противном случае она не является, вообще говоря, сильно конструктивизируемой.

(3) Пусть элементарная характеристика 18 равна (п, оо, 0) или

(?i, oo, 1). Если для каждого k < п в S содержится Atk и для каждого т < п хотя бы один из предикатов Alsm и Atmm, то 23 имеет сильно вычислимое представление; в противном случае она не является, вообще говоря, сильно конструктивизируемой.

Отметим также, что в диссертации рассматривается и случаи характеристики (оо,0,0). Что же известно о связи вычислимости рассматриваемых предикатов и сильной конструктивизируемости булевой алгебры, когда элементарная характеристика есть (ос, 0,0)? В [7] построен пример алгебры с характеристикой (оо,0,0), которая n-вычислима для всех п е uj (без равномерности по п), но не имеет сильно вычислимого представления. Тем самым для алгебры характеристики (со, 0,0) не существует конечного набора предикатов, определяемых формулами первого порядка, который мог бы обеспечить сильную конструктивизиру-емость. Однако Ю. Л. Ершов [9] показал, что если последовательность Фш равномерно вычислима, то булева алгебра характеристики (оо,0,0) будет сильно вычислима. Требование равномерной вычислимости здесь существенно, как было показано в предыдущем примере. Данные результаты подводят нас к вопросу, аналогичному задаче 1: Задача 2. Если Ф — подпоследовательность Фш и известно, что 23 — вычислимая булева алгебра элементарной характеристики (ос, 0,0) и в 25 равномерно вычислима последовательность Ф, то можно ли утверждать, что 23 сильно конструктивизируема?

Эта задача также полностью исследована в диссертации, результат сформулирован в виде теоремы 2.

Теорема 2. (1) Для любой булевой алгебры 21 элементарной характеристики (оо,0,0) и любой вычислимой функции h(i), принимающей значения из {0,1}, верно следующее утверждение. 21 UAieem сильно вычислимое представление тогда и только когда, когда 21 имеет вычислимое представление, в котором равномерно вычислима последовательность предикатов Ato, Ro, At\, R\,..., где

ÍAIsí, если h{i) — 0;

Atmi, если h(i) = 1.

(2) Условия, сформулированные в пункте (1), минимальны в следующем смысле: для каждого г € и) существует вычислимая булева алгебра, в которой равномерно вычислима последовательность предикатов Ф' = Ф^Д]^*}, не имеющая сильно вычислимого пред-

оглавления; и аналогичное утверждение верно для, последовательности Ф" = Ф u\{AlsuAtmi}.

Научная новизна. Все основные результаты диссертации являются новыми.

Основные результаты диссертации.

1. Для каждой элементарной теории Т, кроме теории, соответствующей элементарной характеристике (ос, 0,0), перечислены все множества S С Ф(Т) такие, что если булева алгебра ЯЗ данной теории вычислима ив® вычислимы все предикаты из S, то можно утверждать, что 58 сильно конструктивизируема (теорема 1, опубликовано в [25], [26], [27], [28] и [29]).

2. Получена некоторая характеризация Д"-вычислимых булевых алгебр (теорема 9, приведена ниже, опубликована в [26]) .

Теоретическая и практическая ценность. Диссертация имеет теоретический характер, её результаты могут использоваться в дальнейших исследованиях по теории вычислимых булевых алгебр.

Апробация работы. По результатам диссертации были сделаны доклады на следующих конференциях: «Computability in Europe 2012» (Кембридж, Англия), «Logic Colloquium 2011» (Барселона, Испания), «Logic Colloquium 2010» (Париж, Франция), «Logic Colloquium 2009» (София, Болгария), «Мальцевские чтения 2010 и 2009» (Новосибирск). Кроме того, результаты неоднократно докладывались на совместных семинарах IIM СО РАН и НГУ "Конструктивные модели" и "Алгебра и логика".

Публикации. Основные результаты опубликованы в работах [2533], из них [25-29] входят в перечень ВАК российских рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней доктора и кандидата наук.

Структура и объем диссертации. Диссертация состоит из введения, четырёх глав и списка литературы (39 наименований), глава 2 дополнительно разбита на параграфы. Теоремы и леммы пронумерованы независимо, сквозным образом. Известные утверждения, используемые в работе, формулируются в виде лемм и теорем, и имеют непосредственно после номера ссылку на источник. Объём диссертации — 67 страниц.

ОБЗОР СОДЕРЖАНИЯ ДИССЕРТАЦИИ

Главы 1, 2 и 3 посвящены решению задачи 1, результат которой сформулирован в виде теоремы 1. В частности, глава 1 посвящена доказательству достаточности приведенных в теореме 1 требований для сильной конструктивизируемости булевых алгебр элементарных характеристик (п. 0,1), (п, 1,0) и (п, со, 0), которое можно найти в теоремах 4, 5 и б, соответственно.

Теорема 4. Пусть п£ш, 1В — вычислимая алгебра элементарной характеристики (п,0,1). Если для каждого к < п в 23 вычислим предикат. АЬк и хотя бы. один из предикатов АЫк и А1тк, то 23 - сильно конструктивизируемая алгебра.

Теорема 5. Пусть п Є и>. 93 — вычислимая алгебра элементарной характеристики (їі, 1,0). Если для каждого к < п в 23 вычислим предикат Аік и для каэ/сдого т < п — 1 вычислим хотя бы один из предикатов АЬт и АШт, то 93 — сильно конструктивизируеліая алгебра.

Теорема 6. Пусть п Є ш, 23 — вычислимая алгебра элементарной характеристики (л, оо,0). Если для каждого к <п в 23 вычислим предикати АЬк и для каждого т < п вычислим хотя бы один из предикатов А1згп и АШт, то 23 — сильно конструктивизируемая алгебра.

Результаты, сформулированные в теоремах 4, 5 и 6, получены автором лично и опубликованы в [27]. Кроме того, теорема 4 для случая п — 1 была ранее опубликована в статье автора [25].

В главе 2 показывается минимальность некоторых из сформулированных в теореме 1 требований для сильной конструктивизируемости булевых алгебр характеристик (п, 0,1) и (п, оо, 0) в следующем смысле: доказано, что если опустить некоторое из требований, то существует контрпример, то есть булева алгебра, удовлетворяющая всем оставшимся условиям, но не имеющая сильно вычислимого представления.

Глава 2 начинается с параграфа 2.1, где показывается существование следующего контрпримера булевой алгебры элементарной характеристики (1,0,1).

Теорема 8. Существует вычислимая алгебра элементарной характеристики (1,0,1) с вычислимыми множеством атомов и идеалом разложимых элементов, у которой нет сильно вычислимой изоморфной копии.

В параграфе 2.2 также приведена следующая характеризация Д{?-

вычислимых булевых алгебр, практически полученная в ходе доказательства теоремы 8.

Определим обозначение для идеала Тх = (Аі:т —» Г) + Аіт, где АШі —> Г = {х\Чг < х(г Є А<;т =^гЄ Г)}.

Теорема 9. Алгебра 21 является вычислимой алгеброй тогда и только тогда, когда существует вычислимая алгебра € характеристики (1,0,1) такая, что С/Ті =21.

Результаты, сформулированные в теоремах 8 и 9, получены автором лично и опубликованы в [26].

В параграфе 2.3 показывается существование следующего контрпримера булевой алгебры элементарной характеристики (п, оо,0). Теорема 10. Для любого п Є ш существует 4п-вычислимая алгебра элементарной характеристики (п, оо.О), у которой пет сильно вычислимой изоморфной копии.

В параграфе 2.4 теорема 8 продолжается на случай булевых алгебр элементарных характеристик (п, 0.1). где п > 1, следующим образом. Теорема 11. Для любого п > 0 существует вычислимая алгебра элементарной характеристики (п,0,1) с вычислимыми предикаталш из множества а = Ф„\{Лкп_1, Літ„_і}, не имеющая сильно вычислимого представления.

В параграфе 2.5 приводится очередная серия контрпримеров для булевых алгебр элементарных характеристик вида (п,оо,0), представленная в теоремах 12 и 13.

Теорема 12. Существует вычислилшя алгебра характеристики (1,оо,0) с вычислимыми предикатами Е\ и АЬне имеющая сильно вычислимого представления.

Теорема 13. Для любого п > 1 существует вычислимая алгебра элементарной характеристики (п, оо,0) с вычислимыми предикатами из множества Фп+Л {^п-ъ АЬтп^\}, не илїеющая сильно вычислимого представления.

В главе 3 показано, что результатов глав 1 и 2 достаточно, чтобы показать достаточность и минимальность требований для всех остальных элементарных характеристик, кроме (оо, 0,0) и, тем самым, завершить доказательство теоремы 1.

Результаты, сформулированные в теоремах 10, 11, 12 и 13, а также результаты главы 3, получены автором лично и опубликованы в [28]. Кроме того, результаты глав 1-3 опубликованы в обзорной статье [29].

Глава 4 посвящена решению задачи 2, результат которой сформулирован в виде теоремы 2. Сначала приведено доказательство минимальности найденных условий существования сильной конструктиви-зации для булевых алгебр элементарной характеристики (оо,0,0), то есть пункта (2) теоремы 2, что является несложным следствие результатов глав 1-3. Основную часть главы 4 занимает доказательство пункта 1 теоремы 2, для чего приведены две конструкции для построения нужной сильной конструктивизации. Результат, сформулированный в теореме 2, получен автором лично.

Главы 1 п 2 являются независимыми по содержанию, глава 3 является простым следствием глав 1 и 2, завершающим доказательство теоремы 1. Глава 4 опирается на результаты глав 1-3 в вопросах доказательства пункта (2) теоремы 2.

Литература

Алаев П. Е. Разрешимые булевы алгебры характеристики (1,0,1) // Математические труды, том 7, N1 (2004). С. 3-12.

Алаев П. Е. Сильно конструктивные булевы алгебры // Алгебра и логика, том 44, N1 (2005). С. 3-23.

Алаев П. Е. Гиперарифметические булевы алгебры с выделенным идеалом // Сиб. мат. журн. 45, N5(2004). С. 963-976.

Алаев П. Е. Вычислимые однородные булевы алгебры и одна ме-татеорема //' Алгебра и логика. 43, N2(2004). С. 133-158.

Власов В. Н. Конструктивизируемосгь булевых алгебр элементарной характеристики (1,0,1) // Алгебра и логика. 37, N5 (1998). С. 499-521.

Гончаров С. С. Счетные булевы алгебры и разрешимость. Новосибирск. Научная книга (НИИ МИОО НГУ). 1996.

Гончаров С. С. Ограниченные теории конструктивных булевых алгебр // Сиб. мат. журн. 17, N4 (1976). С. 797-812.

Гончаров С. С. Некоторые свойства конструктивизации булевых алгебр // Сиб. мат. журн. 16, N2 (1975). С. 264-278.

Ершов Ю. Л. Разрешимость элементарной теории дистрибутивных структур с относительными дополнениями и теории фильтров // Алгебра и логика. т.З, N3. 1964. С. 17-38.

Ершов Ю. Л. Конструктивные модели /'/ Избранные вопросы алгебры и логики. Наука. Новосибирск. 1973. С. 111-130.

Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. М.: Наука. 1980.

Логическая тетрадь. Нерешенные вопроси математической логики. Оперативный информационный материал. Под редакцией Ю. Л. Ершова и С. С. Гончарова. Новосибирск: Институт математики СО АН СССР. 1986.

13] Мальцев А. И. О рекурсивных абелевых группах / / Доклады АН СССР. т. 1-16, N5. 1962. С. 1009-1012.

14] Одинцов С. П. Ограниченные теории конструктивных булевых алгебр нижнего слоя // препринт N21. Ип-т матем. СО АН СССР. 1986.

15] Ash С. J., Knight J. Computable structures and the hyperarithmetical hierarchy. Elsevier. 2000.

16] Barivise J. Back-and-forth through infinitary logic // Studies in Model Theory, ed. by M.D.Morley. M.A.A. Studies in Mathematics, vol. 8 (1973). P. 5-34.

17] Feiner L. Hierarchies of Boolean algebras // J. Symb. Log. 35. N3 (1970). P. 365-374.

181 Frohlich A., Shepherdson J. Effective procedures in field theory // Philos. Trans. Soc. London, ser. A. v. 248, 1956. P. 407-432.

191 Monk J. D., Koppelberg S., Bonnet R. (eds.) Handbook of Boolean algebras. Elsevier. 1989.

20] Ershov Yu. L., Goncharov S. S., Nerode A., Remmel J. B. (eds.) Handbook of Recursive Mathematics. Elsevier. 1998.

21] Harrington L. Recursively presentable prime models //J. Symb. Log. 39 (1974) P. 305-309.

22] Morley M. Decidable models ,// Israel J. Math. 25 (1976). P. 233-240.

23] Rabin M. O. Effective computability of winning strategies // Contributions to the Theory of Games, v. 3. Princeton Univ. Press. Princeton. 1957. P. 147-157.

[24] Vaught R. L. Sentences true in all constructive models // J. Symb. Log. v. 25, N1. 1960. P. 39-58.

Работы автора по теме диссертации

Оригинальные статьи

[25] Леонтьева М. Н. Булевы алгебры элементарной характеристики (1,0,1) с вычислимыми множеством атомов и идеалом атомных элементов // Вестник НГУ. Серия.: матем., механика, информ. 2010. Т.10. вып.1. С. 65-69.

[26] Леонтьева М. Н. Булевы алгебры элементарной характеристики (1,0,1) с вычислимыми множеством атомов и идеалом Ершова-Тарского // Алгебра и логика. Т.50, N2 (2011). С. 133-151.

[27] Леонтьева М. Н. Достаточные условия разрешимости для булевых алгебр // Вестник НГУ. Серия.: матем., механика, информ. 2011. Т.11. вып. 4. С. 63-68.

[28] Леонтьева М. Н. Минимальность некоторых условий разрешимости для булевых алгебр // Сиб. мат. журн. 2012. Т.53, N1. С. 132-147.

[29] Леонтьева М. Н. Существование сильно вычислимых представлений в классе булевых алгебр // Доклады АН. 2012. Т.445, N2. С. 132-134.

Переводы оригинальных статей на английский язык

[30] Leonticva М. N. Boolean algebras of elementary characteristic (1, 0, 1) whose set of atoms and Ershov-Tarski ideal are computable // Algebra and Logic. Volume 50, Issue 2. May 2011. P. 93-105.

[31] Leontyeva M. N. The minimality of certain decidability conditions for Boolean algebras // Siberian Mathematical Journal. Volume 53, Issue 1. January 2012. P. 106-118.

[32] Leontyeva M. N. The existence of strongly computable representations in the class of Boolean algebras // Doklady Mathematics. Volume 86, Issue 1. July 2012. P. 469-471.

[33] Leont'eva M. Boolean algebras of elementary characteristic (1, 0, 1) with computable set of atoms and computable ideal of atomic elements // Journal of Mathematical Sciences. Volume 186, Issue 3 (2012). P. 461-465.

Тезисы конференций

[34] Леонтьева М. Н. Разрешимые булевы алгебры характеристики (1,0,1) // Материалы XLVI Международной научной студенческой конференции "Студент и научно-технический прогресс": Математика. Новосибирск. НГУ. 2008. С. 82.

[35] Leoniyeva М. Decidable Boolean Algebras of Elementary Characteristics (1,0,1) // Abstracts of "Logic Colloquium 2009" "St. Kliment Ohridski" University Press. Sofia University. Faculty of Mathematics and Informatics. P. 62-63.

[36] Leontyeva M. Decidable Boolean Algebras of Elementary Characteristics (1,0,1) // Bull. Symb. Log. Volume 16, Issue 01. March 2010. P. 123-124.

[37] Leontyeva M. Decidability of Boolean algebras with fixed elementary theory // Bull. Symb. Log. Volume 17. Issue 02. June 2011. P. 306.

[38] Leontyeva M. Strongly computable copies of Boolean algebras with elementary characteristic (infinity, 0,0) // Abstracts of "Logic Colloquium 2011". Barcelona. Spain. P. 75.

[39] Leontyeva M. Strongly computable copies of Boolean algebras with elementary characteristic (infinity, 0,0) // Bull. Symb. Log. Volume 18, Issue 03. September 2012. P. 452-453.

Леонтьева Маргарита Николаевна

СИЛЬНАЯ КОНСТРУКТИВИЗИРУЕМОСГЬ БУЛЕВЫХ АЛГЕБР

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 15.02.13. Формат 60x84 1/16. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ № 5.

Отпечатано в ООО «Омега Принт» 630090, Новосибирск, пр.Лаврентьева, 6

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. СОБОЛЕВА

На правах рукописи

СО

Леонтьева Маргарита Николаевна

СИЛЬНАЯ КОНСТРУКТИВИЗИРУЕМОСТЬ БУЛЕВЫХ

АЛГЕБР

01.01.06 — математическая логика, алгебра и теория чисел

Диссертация на соискание ученой степени {ф кандидата физико-математических наук

ю ю ю

ю ^

со я

Ю Научный руководитель

^ ^ доктор физико-математических наук

СМ Алаев Павел Евгеньевич

Новосибирск 2013

л

Оглавление

Введение 3

1 Достаточность условий сильной конструктивизируемости для булевых алгебр

с сН і < оо 10

2 Минимальность условий сильной конструктивизируемости для булевых алгебр

с сКі < оо 14

2.1 Булева алгебра характеристики (1,0,1) с вычислимыми

предикатами Аі и Е, не имеющая сильно вычислимого представления . 14

2.2 Одно описание Д^-вычислимых алгебр................... 27

2.3 Булева алгебра характеристики (п, оо, 0) с вычислимыми предикатами из Ф„+1\{А^}, не имеющая сильно

вычислимого представления......................... 29

2.4 Булева алгебра характеристики (гг, 0,1) с вычислимыми предикатами из Фп+і\{АІ8„_і, Аіт„_і}, не имеющая

сильно вычислимого представления..................... 33

2.5 Булева алгебра характеристики (п, оо, 0) с вычислимыми предикатами из Фгг+і\{АІ8п_і, Аіт„_і}, не имеющая сильно вычислимого представления ...................................... 38

3 Сильная конструктивизируемость булевых алгебр элементарных характеристик (п, к + 1, 0), (п, к, 1) и

(п, оо, 1) для к > 0 45

4 Сильная конструктивизируемость булевых алгебр

элементарной характеристики (оо,0,0) 47

Литература 64

Введение

Теория вычислимости начала развиваться в 30-х годах прошлого века в работах Гёделя, Тьюринга, Поста и др., и, будучи исследованием общих свойств алгоритмов, продолжает и сейчас привлекать внимание широкого круга исследователей. В данной работе речь пойдет об изучении алгоритмических свойств некоторого класса моделей на основе их представления на множестве натуральных чисел, то есть о вопросах теории вычислимых (конструктивных) моделей, которая берет истоки в 50-х годах прошлого века в трудах А.И. Мальцева [13], М.О. Рабина [23], Р. Воота [24], В.А. Кузнецова, А.Фрёлиха и Дж. Шефердсона [18]. Полученные результаты относятся к классу вычислимых булевых алгебр, изучению которых в частности посвящен ряд работ Ю.Л. Ершова, С.С. Гончарова и их учеников, а также многочисленных зарубежных исследователей.

Модель конечного языка называется вычислимой, если её носитель — вычислимое множество натуральных чисел, операции — вычислимые функции, и отношения вычислимы. Вычислимая модель называется п-вычислимой, если существует алгоритм, определяющий по конечной Е„-формуле и набору элементов, истинна ли эта формула на этом наборе. Сильно вычислимая модель — та, для которой подобный алгоритм существует для всех формул исчисления предикатов. Мы будем называть модель конструктивизируемой, если у нее существует вычислимое представление (изоморфная копия), и сильно конструктивизируемой, если у неё существует сильно вычислимая изоморфная копия.

Понятие сильно вычислимой (сильно конструктивной) модели было введено Ю. Л. Ершовым [10] в 1968 году. Заметим, что данная теория активно разрабатывалась в математической школе А. Нероуда на основе аналогичного (по-существу, эквивалентного) понятия разрешимой модели, изучаемого также Л. Харрингтоном [21] и М. Морли [22].

В диссертации рассматриваются булевы алгебры - дистрибутивные решетки с наибольшим и наименьшим элементами, и дополнениями. В решетке у каждых двух

элементов х и у есть точная нижняя и верхняя грань, которые, следуя [19], будем символически обозначать как х ■ у и х + у, соответственно. Дополнение элемента х до наибольшего элемента булевой алгебры обозначаем (—ж). Говоря о вычислимой булевой алгебре, будем подразумевать, что она вычислима как модель в языке Ева = {+, •, —,0,1}, где 0 и 1 соответствуют наименьшему и наибольшему элементам.

Булевы алгебры являются классическими объектами, возникающими в различных разделах математики и привлекающими внимание исследователей уже в течении полутора веков. Попытка собрать хотя бы основные достижение в этой области привела к появлению трехтомного справочника [19]. Мы будем работать со счетными булевыми алгебрами, называя их кратко алгебрами; в качестве источника предварительных сведений по теории булевых алгебр будем использовать [6]. С точки зрения теории вычислимых моделей одним из наиболее естественных вопросов является описание тех булевых алгебр, которые являются сильно конструктивизируемыми.

Перейдем к описанию задач, которым посвящена данная диссертация. Для этого сначала сформулируем ряд понятий и обозначений.

Для произвольных идеалов 11 и I2 булевой алгебры будем использовать следующее обозначение: Ii + I2 = {ж + у\х £ Ii, у £ I2}.

Пусть 03 — алгебра. Ненулевой элемент а £ 03 называется атомом, если \/b(b < а => Ь = 0). Множество атомов алгебры 03 обозначим Ato(03). Элемент а £ 03 называется атомным, если Ух ^ а(х ^ 0 =>■ (3у ^ ж(у £ Ato(03)))). Атомные элементы образуют идеал, который мы будем обозначать как Atmo(03). Элемент а £ 03 называется безатомным, если Уж ^ а (ж $ Ato(03)); безатомные элементы также образуют идеал, и он обозначается Also(03). Через Fo(03) обозначим идеал Фреше (идеал, порожденный атомами), E(Q3) = Also(03) + Atm0(03) — идеал Ершова-Тарского. Пусть {En}necü — последовательность итерированных идеалов Ершова-Тарского, то есть Ео(03) = {0}, En+i(03) = (Е„ о Е)(03) = {х £ 03| х/Еп £ Е(03/Еп)}. Для каждого к £ lo обозначим через At*, предикат, выделяющий в каждой алгебре множество таких элементов х, что ж/Ек — атом. Аналогично определяются предикаты Ffc, Als^ и Aim*;. Для предикатов At0. Fq. Also, Atm0, Ei будут иногда использоваться обозначе-

ния At, F, Als, Atm, Е, соответственно.

Определим некоторые наборы одноместных предикатных символов. Пусть Фо = {Е0}, Ф„ = Фо U {At0, Also, Atm0, Еь ..., Atn_i, Alsn_i, Atmn_i, E„} для n > 1 и Фш =

{E0, Ato,Also,Atmo,Eb...}.

Важную роль в теории булевых алгебр играет понятие элементарной характеристики. Наименьшее п, для которого Еп+1(03) = 03, называется первой (элементарной) характеристикой алгебры 05 и обозначается c/ii(03). Если таких п нет, полагаем c/ii(Q3) = оо. При chi(55) = 00 считаем, что вторая с/12 (23) и третья с/13(53) (элементарные) характеристики алгебры 58 равны нулю. В противном случае (т.е. если ch\(%$) = п), вторая характеристика сЛ,г(03) равна числу атомов алгебры 03/ЕП, если это число конечно, и c/i2(23) = 00, если в 23/Еп бесконечно много атомов. Третья характеристика с/гз(03) равна 1, если в 23/Еп есть ненулевой безатомный элемент, и равна 0 в противном случае.

Элементарная характеристика с/г(03) алгебры 03 — это тройка (c/ii(23), c/i2(®), с/гз(03)). Определенная таким образом элементарная характеристика обладает тем свойством, что две булевы алгебры элементарно эквивалентны (имеют одну и ту же элементарную теорию) тогда и только тогда, когда их элементарные характеристики равны.

Для каждой элементарной теории булевой алгебры Т, кроме той, которая соответствует элементарной характеристике (оо, 0,0), Ю.Л.Ершов в [9] построил конечный набор предикатов Ф(Т), определяемых формулами первого порядка, такой, что булева алгебра 03 с элементарной теорией Т является сильно вычислимой тогда и только тогда, когда 03 вычислима и вычислимы все предикаты из набора Ф(Т). Позже С.С.Гончаровым было показано, что при п < |Ф(Т)| вычислимость 03 вместе с вычислимостью первых n + 1 предикатов набора Ф(Т) равносильна вычислимости Еп-диаграммы 03, т.е. п-вычислимости.

В терминах приведенных выше обозначений и понятий, набор предикатов Ф(Т), представленный Ю. JI. Ершовым в [9] имеет вид Фп+ъ где п Е си является первой элементарной характеристикой, соответствующей теории Т.

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

Задача 1. Если 5" С Ф(Т) и известно, что 03 вычислима и в 55 вычислимы все предикаты из Б, то можно ли утверждать, что 23 сильно конструктивизируема ?

Данная проблема привлекала внимание широкого круга исследователей. В работах С. С. Гончарова, С. П. Одинцова, В. Н. Власова и П. Е. Алаева был получен ряд результатов о связи п-вычислимости с сильной конструктивизируемостью, то есть для случая, когда 5 является начальным отрезком Ф(Т). В частности, П. Е. Алаевым был получен окончательный ответ для этого случая. Приведем здесь краткий обзор этих результатов.

В [8] приводится пример 0-вычислимой (то есть просто вычислимой) алгебры характеристики (0, оо, 0), не имеющей сильно вычислимого представления. При этом из [9] следует, что в этом случае 1-вычислимость влечет не только сильную конструк-тивизируемость, но и сильную вычислимость. Для (0, т,0) и (0,ш, 1), 777 € ш, ответ сразу следует из [9]: вычислимость означает и сильную вычислимость.

В [9] указаны достаточные условия сильной вычислимости (а значит, и сильной конструктивизируемости) и для всех остальных характеристик вида (т, *, ★), где 777 € и. Например, для характеристик (т, оо, 0) и (т, оо, 1) сильная вычислимость следует из (4тп+ 1)-вычислимости. Небольшая модификация примера из [8], выполненная в [6], показывает, что 4т-вычислимости недостаточно и для сильной конструктивизируемости.

В [14] было показано, что для характеристики (1,1,0) 2-вычислимость влечет сильную конструктивизируемость, а для (1,0,1) 3-вычислимость влечет сильную конструктивизируемость. В [6] было завершено доказательство того, что для (1,1,0) уже 1-вычислимость влечет сильную конструктивизируемость. В [5] для характеристики (1,0,1) был построен пример 1-вычислимой алгебры, не имеющей сильно вычислимого представления. В [1] было доказано, что для характеристики (1,0,1) уже 2-вычислимость влечет сильную конструктивизирз'емость. В [2] получено, что для характеристики (777, 1,0), 777 > 2, сильная КОНСТруКТИВИЗИрувМОСТЬ следует ИЗ (4777 — 3)"

вычислимости, а для (т, 0,1), т > 2, — из (4т — 2)-вычислимости. В [25] доказано, что в случае алгебры характеристики (ш, 0,1), т > 0 из (4т — 3)-вычислимости и вычислимости предиката также следует сильная конструктивизируемость.

В диссертации ответ найден для всех возможных подмножеств 5 С Ф(Т), сформулированный в теореме 1, и тем самым завершено исследование, имеющее столь длинную историю.

Теорема 1. Пусть п,р Е ш, 53 — вычислимая булева алгебра с первой элементарной характеристикой п, Б С Ф„+1 и в 05 вычислимы все предикаты из 5.

(1) Пусть элементарная характеристика © равна (п,р, 1). Если для каждого к < п в 5 содержится АЬь и хотя бы один из предикатов АЬк и А1ть, то 03 имеет сильно вычислимое представление; в противном случае она не является, вообще говоря, сильно конструктивизируемой.

(2) Пусть элементарная характеристика 03 равна (п,р+1,0). Если для каждого к < п в 5 содержится АЬк и для каждого т, < п — 1 хотя бы один из предикатов А1зт и АШт, то 03 имеет сильно вычислимое представление; в противном случае она не является, вообще говоря, сильно конструктивизируемой.

(3) Пусть элементарная характеристика 03 равна (п, оо,0) или (п,оо,1). Если для каждого к < п в 5 содержится АЬк и для каждого т < п хотя бы один из предикатов АЬтп и А1тт, то 03 имеет сильно вычислимое представление; в противном случае она не является, вообще говоря, сильно конструктивизируемой.

Отметим также, что в диссертации рассматривается и случай характеристики (оо,0,0). Что же известно о связи вычислимости рассматриваемых предикатов и сильной конструктивизируемости булевой алгебры, когда элементарная характеристика есть (оо,0,0)? В [7] построен пример алгебры с характеристикой (оо,0,0), которая п-вычислима для всех п € ш (без равномерности по п), но не имеет сильно вычислимого представления. Тем самым для алгебры характеристики (оо, 0,0) не существует конечного набора предикатов, определяемых формулами первого порядка, который мог бы обеспечить сильную конструктивизируемость. Однако Ю. Л. Ершов [9] показал, что если последовательность равномерно вычислима, то булева

алгебра характеристики (оо, 0,0) будет сильно вычислима. Требование равномерной вычислимости здесь существенно, как было показано в предыдущем примере. Данные результаты подводят нас к вопросу аналогичному задаче 1:

Задача 2. Если Ф — подпоследовательность Фш и известно, что 03 — вычислимая булева алгебра элементарной характеристики (оо, 0,0) и в 03 равномерно вычислима последовательность Ф, то можно ли утверждать, что 53 сильно конструктивизируе-ма?

Эта задача также полностью исследована в диссертации, результат сформулирован в виде теоремы 2.

Теорема 2. (1) Для любой булевой алгебры 21 элементарной характеристики (сю, 0, 0) и любой вычислимой функции h(i), принимающей значения из {0,1}, верно следующее утверждение. 21 имеет сильно вычислимое представление тогда и только когда, когда 21 имеет вычислимое представление, в котором равномерно вычислима последовательность предикатов Ato, Ro, At\, Ri,..., где

АЬг, если h(i) = 0;

Atmt, если h(i) = 1.

(2) Условия, сформулированные в пункте (1), минимальны в следующем смысле: для каждого i € ш существует вычислимая булева алгебра, в которой равномерно вычислима последовательность предикатов Ф' = Фш\{Л£г}, не имеющая сильно вычислимого представления; и аналогичное утверждение верно для последовательности Ф" = Фu\{Alsu Atmt}.

В диссертации также получен ряд результатов по описанию отношения на булевых алгебрах (это так называемое "standard back-and-forth relation" на булевых алгебрах, в языке, обогащенном предикатными символами из а), которые использованы для доказательства теоремы 1. Это описание имеет ценность и само по себе, так как может применяться для получения новых результатов, например, с помощью теоремы 2 из [3]. Дадим определение этому отношению.

Через Па(ШТ) обозначим множество всех бесконечных Па-предложений, истинных в модели Ш. через Ш <а - то, что Па(9Л) С П„(0Я). Базовую теоретико-модельную

Яг =

информацию об этом отношении можно найти в [15] и [16].

Пусть а - некоторый конечный набор 1-местных предикатных символов (может быть, пустой), для каждого из которых заранее определена его реализация в любой алгебре, причем эта реализация сохраняется при изоморфизмах. Тогда 21ст означает единственное обогащение алгебры 21 предикатами из а. Если 21, 03 - алгебры, то запись вида 21 <аа © означает, что 21ст <Л Результаты, касающиеся описания отношения <аа на булевых алгебрах, полученные в данной работе, представлены в леммах 7, 9, 14, 16 и 17.

Скажем несколько слов о структуре диссертации. Глава 1 посвящена доказательству достаточности приведенных в теореме 1 требований для сильной кон-структивизируемости булевых алгебр элементарных характеристик (п, 0,1), (п, 1,0) и (п, оо,0). В главе 2 показывается минимальность сформулированных в теореме 1 требований для сильной конструктивизируемости булевых алгебр характеристик (п, 0,1) и (п, оо,0) в следующем смысле: доказано, что если опустить любое из требований, то существует контрпример, то есть булева алгебра, удовлетворяющая всем оставшимся условиям, но не имеющая сильно вычислимого представления. Кроме того, в главе 2 приведены результаты, касающиеся описания отношения на булевых алгебрах и некоторая характеризация Д^-вычислимых булевых алгебр, полученная в ходе доказательства основных результатов главы. В главе 3 показано, что результатов глав 1 и 2 достаточно, чтобы показать достаточность и минимальность требований для всех остальных элементарных характеристик, кроме (оо, 0,0) и, тем самым, завершить доказательство теоремы 1. И, наконец, в главе 4 приводится доказательство теоремы 2, то есть достаточность и минимальность условий сильной конструктивизируемости для булевых алгебр элементарной характеристики (оо, 0,0).

Главы 1, 2 и 4 являются независимыми по содержанию, глава 3 является простым следствием глав 1 и 2, завершающим доказательство теоремы 1. Результаты главы 1 опубликованы в [25] и [27]; результаты главы 2 — в [26] и [28]. Кроме того, результаты, представленные в теореме 1 опубликованы в обзорной статье [29].

1 Достаточность условий сильной

конструктивизируемости для булевых алгебр

с сН 1 < оо

Следуя [19], булевы алгебры будем рассматривать как модели языка £ва = {+, — ,0,1}, где "+" соответствует объединению элементов, " •" — пересечению, и " —" означает дополнение. Если ...,ап,Ь £ 21, то ..,ап\Ь означает, что а\ + ... + ап = Ь и аг ■ а.] = 0 при г ф Выражение а — Ь равно а ■ (—Ь). Определим ещё один набор одноместных предикатных символов Ф* = Фп и {Ео,..., ^-1} для п > 0. В этом разделе мы будем работать с моделями, являющимися обогащением некоторой алгебры до языка ЕВа и Ф„ или Т,Ва и Ф*. Если 03 — алгебра, то через будем обозначать такое обогащение алгебры 03 до языка Т,ва и Фп; в котором все символы из Ф„ интерпретируются в соответствии со своими определениями. То же самое касается обозначения Когда речь будет идти о конкретной алгебре 93, мы не будет раз-

личать набор предикатных символов Ф„ и набор предикатов на алгебре 53, который является интерпретацией символов из Ф„; для обоих наборов будет использоваться обозначение Фп.

Лемма 1. Если 03 — вычислимая алгебра с первой характеристикой п с вычислимыми предикатами Фгг+1\{£^о,..., Еп-\], то 03 — сильно вычислимая алгебра. Доказательство. Достаточно �