Алгебраические свойства булевых алгебр тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

7

/ /

/

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ВЛАСОВ Владимир Николаевич

Алгоритмические свойства Булевых Алгебр

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

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

На правах рукописи УДК 512.8

Научный руководитель член-корр. РАН, профессор Сергей Савостьянович Гончаров

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

Введение

Представленная работа посвящена теории конструктивных булевых алгебр, и в ней исследуются проблемы нахождения критерия сильной конструктивизируемости булевых алгебр, & также проблемы построения конструктивных линейных порядков и булевых алгебр с некоторыми заданными алгебраическими и алгоритмическими свойствами. •. •'.'■' "М?*>>'-;"•'• : Л;* ;

Понятие сильно конструктивной модели было введено в 1968 году Ю.Л. Ершовым в его курсе лекций в Казахском университете в г. Алма-Ате, которые были опубликованы в посвященных А.И. Мальцеву трудах [5]. С этого понятия начинается ряд исследований, посвященных естественной проблеме нахождения критерия совпадения конструктивности и сильной конструктивности, а также необходимых и достаточных условий сильной конструктивизируемости. В случае булевых алгебр такие исследования были проведены в работах Н.Г. Хисамиева, С.С. Гончарова, С.П. Одинцова [8, 1, 12]. Н.Г. Хисамиевым был открыт один из первых признаков сильной конструктивности атомных булевых алгебр, состоящей в рекурсивности множества атомов [8]. Как было замечено в [6], этот признак является следствием сильной конструктивности конструктивных моделей модельно полных разрешимых теорий. В работе [4] С.С. Гончарова доказано, что от этого условия нельзя отказаться.

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

алгебр так называемого нижнего слоя, т.е. элементарных характеристик (0, оо,1), (1,1,0) и (1,0,1) в терминах ограниченных теорий [3].

Дальнейшее развитие исследований в этом направлении оказалось связанным с оригинальной идеей Л. Фейнера [15, 16], предложившего специальные оценки для булевых алгебр с заданными алгоритмическими свойствами и также общую идею построения рекурсивных булевых алгебр, опровергающих эти оценки, и, таким образом, заданные алгоритмические свойства, при любом изоморфизме. Как указывает сам Л. Фейнер, его работа и постановка проблемы была инициирована А. Неро-удом, и некоторая помощь была оказана В. Ханфом. Указанный выше результат С.С. Гончарова [4] — его пример атомной конструктивной, но не сильно конструк-тивизируемой булевой алгебры, — опирается на метод Фейнера и существенно его модернизирует, так что в дальнейшем мы называем его метод "методом Фейнера-Гончарова". Но стоит отметить, что сам метод Л. Фейнера так и остался мало-используемым в разделах современной теории конструктивных моделей — известен результат Дж. Реммела [17] о существовании конструктивной булевой алгебры с разрешимым множеством атомов, но с неразрешимым в любой конструктивизации идеалом Фреше, и также известна интересная работа Дж. Тёрбера [18], о которой будет подробнее сказано ниже.

Ряд положительных решений о возможности сильной конструктивизируемости булевых алгебр нижнего слоя, в частности, с элементарными характеристиками (1,1,0) и (1,0,1), был получен С.П. Одинцовым [12, 13]:

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

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

С.П. Одинцовым были анонсированы без доказательства [13] утверждения о возможности обобщения указанных выше результатов на высокие характеристики.

Автором диссертации В.Н. Власовым совместно с С.С. Гончаровым [21] был получен результат о сильной конструктивизируемости булевых алгебр элементарной

характеристики (1,1,0) с разрешимым множеством атомов и с некоторым естественным условием (разложимости данной алгебры в эффективную прямую сумму конструктивных булевых алгебр с первой характеристикой 0), эквивалентному в данном случае разрешимости идеала Ершова-Тарского; это исследование и новый вариант доказательства предложены в первой главе. С.С. Гончаровым: было получено [2] и окончательное решение проблемы характеризации для случая характеристики (1,1,0) — конструктивная булева алгебра сильно конструктивизируема если, и только если, множество атомов в данной конструктивизации разрешимо, которое существенно опирается на теорему Гончарова-Власова [21].

Краткий обзор

Сделаем краткий обзор представляемой работы. Диссертация состоит из введения, трех глав, и заключения. Во введении также присутстует сводка основных обозначений и определений. Каждая глава состоит из нескольких параграфов. Основные результаты изложены в первых двух главах, третья глава носит более методологический характер.

Первая глава описывает положительные результаты о сильной конструктивизиру-емости булевых алгебр в общем случае с нулевой третьей характеристикой Ершова-Тарского и равной единице второй, при некоторых условиях на разрешимость ограниченных теорий. Исследования автора были инициированы следующей открытой проблемой, сформулированной С.П. Одинцовым [1, 12, с. 170]:

"Существует ли конструктивная, но не сильно конструктивизируемая булева алгебра характеристики Ершова-Тарского (1,1,0), допускающая конструк-тивизацию с разрешимым множеством атомов?".

Как уже было указано выше, из работ С.С. Гончарова следует, что от требования разрешимости атомов нельзя отказаться.

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

слагаемыми меньшей характеристики. Основная идея эффективной схемы "атомиза-ции" заключается в том, что мы отслеживаем равномерно по всем слагаемым (в их порождающих рекурсивно перечислимых бинарных деревьях) возможных кандидатов на безатомные элементы и до тех пор, пока они будут оставаться кандидатами, на их месте пошагово будем строить ¿¿-ветвь (т.е. помещать элементы, дающие в пределе эту ветвь). Если же на каком-то шаге выяснится, что под кандидатом на безатомность появился при перечислении дерева атом — восстаналиваем фргамент и при этом добавляется лишь конечное новое число атомов, что не влияет на изоморфизм в целом (лемма Реммела [21]). Первоначальный вариант схемы опубликован в [21].

Параграф 1.2 в некоторым смысле повторяет значительно упрощенную схему предыдущего параграфа для случая произвольной характеристики (га+ 1,1,0) при (4га + 2)-конструктивности, — при обобщении пришлось потребовать и разрешимость множества безатомных элементов га-ой булевой алгебры (точнее, множества его прообраза при каноническом эпиморфизме) при факторизации по идеалам Ершова-Тарского. Но с другой стороны, пришлось особо заботиться о сохранении типа изоморфизма, так как в га-ых факторах булевых алгебр атомы и безатомные элеметы начинают иметь "свое лицо". Результат параграфа 1.2 является новым и был анонсирован в [21].

Вторая глава описывает интересный результат, построенный на базе глубокой переработки и адаптации метода Фейнера к жестким требованиям сохранения элементарной характеристики (1,0,1) (все известные примеры применения данного метода были либо атомными алгебрами, либо имели характеристику (1,оо,0), и это было необходимым признаком конструкций по типу Фейнеровских) и требованию на разрешимость атомных элементов. Исследования в этом направлении также были вызваны размышлениями над открытой проблемой, сформулированной С.П. Одинцовым [12, 1, с.170]:

"Существует ли конструктивизируемая, но не сильно конструктивизируемая булева алгебра В характеристики (1,0,1), допускающая конструктивизацию с разрешимыми множествами атомов и безатомных элементов?"

Примером конструктивной булевой алгебры, но не сильно конструктивизируемой,

(с неразрешимым множеством атомов в любой конструктивизации) с элементарной характеристикой (1,0,1), будет булева алгебра Вь, порожденная линейным порядком Ь = 1 + {ьвопыг + 1 + »7 + 1)х?7 + 1, где Ьаопсн — конструктивный, но не сильно кон-структивизируемый линейный порядок, не содержащий плотных интервалов (типа г/), построенный С.С. Гончаровым [1, с.119].

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

Параграф 2.2 обобщает конструкцию предыдущего параграфа на произвольные характеристики (га+ 1,0,1) и дает пример (4п + 1,0,1)-конструктивизируемой, но не сильно конструктивизируемой булевой алгебры.

Оба результата являются новыми и опубликованы в [23, 24]

В третьей главе рассматриваются проблемы дальнейшего применения метода Фейнера-Гончарова. В параграфе 3.1 на базе идей из второй главы построен пример конструктивной булевой алгебры элементарной характеристики (1,0,1) с разрешимым множеством атомов, безатомных элементов и разрешимым идеалом Фреше, причем в данной конструктивизации множество атомных элементов не рекурсивно, и, следовательно, построенная конструктивизация не является сильной. Но, к сожалению, пока нельзя утверждать, что эти алгоритмические свойства сохранятся в любой конструктивизации (иначе, это было бы решением 2-ой проблемы Одинцова), будем считать это гипотезой. Тем не менее, можно утверждать, что в любой конструктивизации одновременно все вышеперечисленные множеств а не будут разрешимы. Данная работа опубликована в [22].

Второй параграф этой главы систематизирует все известные (автору) к настоящему моменту результаты применения метода Фейнера в единую схему (теорема 6). Результат полезен как для представления конструкций на базе метода иерархий Фенйера с единой точки зрения (для чего приводятся специальные примеры), так и для использования метода в более широком классе задач. Дргой результат, теорема 7 дает пример нахождения для произвольной формулы К(х) теории слабого второго порядка, задающей идеал на Б А, такой конструктивной Б А, что в любой её конструктивизации предикат К{х) не разрешим. И приведен пример использования последней теоремы — построение конструктивной Б А, у которой в любой конструк-

тивизации идеал Ершова-Тарского не разрешим. Стоит отметить, что результат Реммела [17] можно рассматривать как следствие теоремы 6.

Необычным и стоящим в некотором смысле в стороне от основного направления исследований, связанных с методом Фейнера, является направление исследований Дж. Тёрбера. Им было построено обобщение иерерхии Фейнера от оценок на базе ограничений используемого оракула последовательностью 0а+пЬ для вычислений с аргументом п. как это было первоначально у Фейнера, до ограничений 0"", где {ап}пеш — последовательность рекурсивных ординалов. И на основании результатов Фейнера, Эша [19] и Лава [20] был получен результат, что для любого вида введенных оценок существует рекурсивная булева алгебра, удовлетворяющая их.

Основные определения и обозначения

Основные используемые обозначения являются общепринятыми и могут быть найдены в монографиях [1, 2, б, 10] и статьях [3, 9]. Понятия модели, булевой алгебры, частичного и линейного порядка, понятия теории рекурсивных функций и другие общематематические, логические и теоретико-множественные понятия также могут быть найдены в этих работах и здесь, как правило, не определяются.

Далее в представляемой работе будем обозначать булевы алгебры — каллиграфическими латинскими буквами В, Л, (также каллиграфическими латинскими буквами мы иногда будем обозначать некоторые специальные множества) линейные порядки — полужирными латинскими буквами Ь, М, если не оговаривается противное. Аббревиатура Б А обозначает "булева алгебра".

Определение 1 Определим понятие конструктивной модели. Нумерованная система [1, с.85] (Л4, где М. — модель сигнатуры £ = (Р0,.. ., Рп, /0,..., Со,..., ст), называется конструктивной, если множества

т/г, ^ {(п, т) | ип = ит},

1/_1(Л) ^ {(к,-- ■, 1гщ) | ("к, ■ • е Рг}, г < п,

{(п,г) | ип = с4-}, г < т

рекурсивны, и существуют рекурсивные функции /¿, % < к такие, что для любых

Если сигнатура £ бесконечна, то мы должны в этих определениях требовать равномерную рекурсивность.

Определим понятие сильно конструктивной модели. В соотвествии с [1, с.86], условимся говорить, что бескванторная формула имеет 0 чередующихся кванторов, а формула Ф, имеющая в пренексной нормальной форме п групп чередующихся кванторов — имеет п чередующихся кванторов, и обозначать как Би множество формул с п чередующимися кванторами, а через Бш — множество всех формул.

Пусть Б — некоторое множество формул сигнатуры Е. Нумерованная система (Л4, и) называется Б-конструктивной, если множество

рекурсивно.

В данных обозначениях Б конструктивность в точности соотвествует ранее введенному понятию конструктивности. Б^-конструктивные системы мы будем называть сильно конструктивными, а Бш-конструктивные — п-конструктивными.

Используем следующие обозначения для множеств атомов, безатомных и атомных элементов, идеалов Ершова-Тарского и Фреше

Те же самые буквы используем для обозначения формул, определяющих эти множества:

/!,..., 1Щ € N

"Ши ■ ■ -Л,) = ^¿(гЛъ ..., у1щ).

{(5, /1,..., 1к) | 5 — номер формулы Ф(жх,..., из Б с к свободными переменными и Л4 |= Ф(ж1,...,

АЩ, А1(В), Аз(В), /(В), Р{В).

АЬ(х) ^ Уу < х(у = 0 V (з/Лж = 0)) к ж^О;

п

п

и At(B) = {хев I At(x)}, и т.д.

Определение 2 В литературе термин а-атомная БА используется для обозначения факта, что для данной Б А В фактор-алгебры B/Fß(B) атомные для всех ß < а, где a,ß — ординалы. Мы будем использовать аналогичные термины в ином смысле: будем говорить, что БА В является п-атомной или п-6езатомной, если ее элементарная характеристика равна соответственно ch[В) = (п + 1, к, 0), или ch(B) = (п +1,0,1), где к 6 N или к = оо. Аналогичное определение вводим для отдельных элементов — будем говорить, что данный элемент х Е В является п-атомом, п-безатомным элементом или п-атомным элементом, если его элементарная характеристика равна соответственно ch(cc) = (п +1,1,0), сЬ(ж) = (п + 1, 0) или сЬ(ж) = (та + 1, 0,1), где к £ N или к = оо.

Пусть Е(х) — произвольная формула слабой теории второго порядка БА такая, что для произвольной БА В, если Е(В) ^ {х 6 В \ В |=Е(ж)}, то Е(В) < В. И будем полагать:

£о-{0}, Ег-Е, Еп+1^^-г{Е{В1Еп)), где <рп : В —> В / Еп — канонический эпиморфизм.

Если R — это одно из имен At, AI, Аз, I, то

Re"{B) ^ ^-\R{ß/En)\ REn(B) = {xeß\B^ Re"(x)}.

Таким образом, например, определение AtEn(x) будет выглядеть

AtEn{x) ^ Vy (y<Enx->(y = Eri0Vy>Enx)) к х^еЛ

где у <еп х означает (у Л ж) G Еп, равенство у =еп 0 означает у £ Еп, а если <р : В —> В/Еп — канонический эпиморфизм, то это будет соответствовать ip(y) < <р(х) и<р(р) = <р(х).

В случае, когда Еп — 1п — цепь идеалов Ершова-Тарского, будем писать Rn вместо RE" т.е.

At0(B), Al0(B), Aso(B), h(B), ..., АЦВ), ..., In+1(B) .

Замечание 1 Отметим, что данное выше определение AtEn(x) можно записать и в несколько ином, эквивалентном виде (и такого рода запись мы будем использовать в дальнейшем):

AtE"(x) ^ Уу (у <x^(y = En0Vy>Enx)) к хфЕпО,

В самом деле, это следует из того, что для любого идеала G <В, любого предиката А и любого Жо еВ равносильно:

Уу е В (В b у < gxo B/G b АШ)); (*)

Уу € в (В н У < B/G h А{у{у))\ (**)

и равносильно

Зуев {B\=y<Gxo к B/G\=A{<p(y))y, Зуев (В ^ у <х0 к B/G^A(<p(y))),

Докажем эквивалентность первой пары. Тогда, если верно определение (*), и мы имеем у < х0, то и ср(у) < и следовательно, A(tp(y)).

Обратно, пусть верно определение (**), и если у < х0, то доказывать нечего. Пусть -I (у < х0), тогда положим ^ (хо V у), г ^ (у \ х0). Так как у <д Хо, то г eG. Кроме того, уi < ж, и следовательно, A(^(?/i)). Но

4>{у) = v{y\ V г) = у{у 1) V ¥>(г) = (р(уг),

следовательно, А(<р(у)), и доказательство завершено.

Техника работы с двоичными деревьями {£),</?), понятия частичного порядка на них и высоты элемента h(d), стандартные функции L, R, S, Н, а также порождение булевых алгебр В\+ь+\ заданным линейным порядкам 1 + L + 1 с минимальным и максимальным элементом как систем полуоткрытых справа интервалов — может быть найдена в [2, 9]. Иногда, для удобства, мы будем рассматривать булевы алгебры, порожденные линейными порядками без максимального элемента Bi+ь как систему полуоткрытых справа интервалов и интервалов вида [а, оо). Напомним некото�