Содержание к диссертации
Введение
1 Определения 20
1.1 Основные обозначения 20
1.2 Теории и алгебраические системы 20
1.3 Арифметические теории 25
1.4 Автоматные системы 28
1.5 Свойство коллапса к сигнатуре 30
2 Термально изолированные множества 37
2.1 Определения 37
2.2 Существование термально изолированных множеств 39
2.3 Коллапс к порядку для арифметики Семёнова 42
2.4 Свойства предикатных обогащений начального фрагмента нестандартных моделей арифметики Пресбургера 48
2.5 Коллапс к порядку для обогащений начального фрагмента нестандартных моделей арифметики Пресбургера 53
3 Случайный граф 55
3.1 Определения 55
3.2 Состояния над случайным графом 56
3.3 Разрешимое упорядочение случайного графа 58
3.4 Монадические сигнатуры 61
4 Сводимые теории 67
4.1 Основные определения 67
4.2 Свойства сводимых алгебраических систем 70
4.3 (к, /)-формулы 73
4.4 Тотальная сводимость систем 84
4.5 Достаточные условия сводимости 91
4.6 Сводимость, изолированность и псевдоконечная однородность 94
5 Автоматные системы и их обобщения 104
5.1 Сложное обогащение арифметики Пресбургера 104
5.2 Элиминация кванторов в теории TR 106
5.3 Начальные фрагменты системы я 117
5.4 Состояния >() над системой Е 123
5.5 Обобщения теории ТЕ 127
6 Эффективная трансляция 141
6.1 Достаточные условия эффективной трансляции 141
6.2 Приложения к классическим теориям 149
6.3 Арифметика Пресбургера 152
6.4 Теория действительных чисел 153
6.5 Эффективные обогащения Семёнова арифметики Пресбургера155
Заключение 165
Основные результаты 165
Направления дальнейших исследований 166
- Теории и алгебраические системы
- Коллапс к порядку для обогащений начального фрагмента нестандартных моделей арифметики Пресбургера
- Разрешимое упорядочение случайного графа
- Достаточные условия сводимости
Введение к работе
Актуальность
В настоящее время средства и методы математической логики находят всё более широкое применение при проектировании и анализе программного обеспечения ЭВМ. Одним из наиболее тесно связанных с информатикой разделом математической логики является теория языков первого порядка. Особенно интенсивно развивается теория языков для конечных алгебраических систем. Это обусловлено тем, что такие языки широко используются в системах управления базами данных, где служат средством извлечения информации из баз данных.
Сейчас типичной моделью базы данных является предложенная Э.Коддом реляционная модель, в которой база данных мыслится как собрание конечного числа конечных таблиц (см. [27, 28]). Количество строк в этих таблицах и сами строки могут меняться, но количество столбцов постоянно. Таким образом, база данных может рассматриваться как некоторая конечная сигнатура, а состояние базы данных — как конечная алгебраическая система этой сигнатуры.
Для извлечения информации используются языки запросов. В качестве такого языка обычно используются различные версии языка SQL1, который, по сути дела, является стилизацией языка логики предикатов первого порядка. Эта традиция тоже восходит к Э.Кодду, который в качестве языка
:SQL — сокращение Structured Query Language (язык структурированных запросов). Язык разработан фирмой IBM в 1970 году. В настоящее время является стандартным языком для взаимодействия с системами управления базами данных.
запросов предложил использовать язык реляционных выражений, практически эквивалентный языку логики предикатов первого порядка.
Хорошо известно, что не всякое свойство конечных алгебраических систем может быть выражено формулами логики предикатов, то есть не всякая информация может быть получена из базы данных при помощи языков первого порядка. Например, если сигнатура базы данных содержит только один одноместный предикатный символ Р, то невозможно записать в этой сигнатуре формулу первого порядка, выделяющую среди конечных алгебраических систем этой сигнатуры в точности те, в которых количество элементов Р является чётным. Другой пример: для двухместного предиката Е, задающего конечный граф, невозможно записать формулу, которая будет истинной тогда и только тогда, когда этот граф является связным (см. [18]).
Обычно, элементы отношений базы данных выбираются из фиксированного множества, называемого универсумом. Например, в конечном итоге, вся информация в компьютерах хранится в виде натуральных чисел, поэтому в качестве универсума можно рассматривать множество натуральных чисел. Другие примеры — множество всех слов некоторого алфавита или множество действительных чисел. Поскольку размер самих таблиц хоть и конечен в каждый момент времени, но не ограничен, то универсум должен быть бесконечным.
Так как не всякое свойство конечных алгебраической системы может быть выражено формулой языка первого порядка сигнатуры этой системы, то активно ведётся поиск методов увеличения выразительной силы этих языков. Один из путей состоит в следующем (см. [37]). Обычно, на универсуме, элементы которого хранятся в таблицах, определены какие-либо стандартные отношения. Например, для множеств натуральных или действительных чисел такими отношениями являются операции сложения и умножения, отношение порядка и т.д. Рассматривая множество слов, мож-
но использовать операцию конкатенации или отношение лексикографического порядка. Таким образом, универсум тоже является алгебраической системой, но, в отличие от базы данных, бесконечной. Другое отличие — если состояние базы данных меняется, то универсум является фиксированным.
Можно предполагать, что если при построении формул первого порядка использовать не только отношения базы данных, но и отношения универсума (такие формулы называются расширенными), то в этом расширенном языке можно будет выразить какие-то свойства базы данных, которые невозможно выразить, используя только отношения базы данных (такие формулы называют ограниченными). Разумеется, для сравнения имеет смысл рассматривать только такие формулы, истинность которых определяется исключительно отношениями базы данных, а не способом связи между этими отношениями и отношениями универсума. Говоря другими словами, истинность формул, которые используются для сравнения выразительной силы, не должна зависеть от способа вложения базы данных в универсум. Формулы, обладающими этим свойством, называются локально =-генерическими или =-инвариантными. Если для некоторого универсума любая ^-инвариантная расширенная формула эквивалентна ограниченной, то говорят, что имеет место коллапс к равенству. Таким образом, коллапс к равенству означает, что используемые в расширенных формулах отношения универсума не позволяют выразить никаких новых свойств базы данных по сравнению с ограниченными формулами.
В результате возникло новое направление исследований в теории моделей — теория конечных алгебраических систем, вложенных в бесконечные. Одним из главных вопросов этого направления является задача сравнения выразительной силы ограниченных и расширенных языков.
Некоторые отношения универсума действительно увеличивают выразительную силу языка первого порядка. Так Ю.Ш.Гуревич продемонстриро-
вал, что примером такого отношения является обычное отношение линейного порядка. Он предложил свойство базы данных, которое нельзя выразить, используя только отношения базы данных, но можно, если добавить к ним произвольный линейный порядок. Иначе говоря, для упорядоченных универсумов не выполняется коллапс к равенству. Естественно рассматривать следующую задачу:
«Какие отношения можно добавить к отношению линейного порядка, чтобы ещё увеличить выразительную силу языка?»
Поскольку теперь мы будем сравнивать выразительную силу расширенного языка с выразительной силой языка, включающего порядок, то нужно рассматривать не только ^-инвариантные формулы, но и те, истинность которых зависит от отношений базы данных и способа упорядочения её элементов. Такие формулы называют локально <-генерическими или <-инвариантными.
Оказывается, что ряд универсумов обладает следующим свойством:
«Всякая расширенная <-ипвариантная формула эквивалентна некоторой <-ограничешюй (то есть формуле с использованием только отношений базы данных и порядка).»
Такое свойство универсума называют коллапсом к порядку (или трансляционной теоремой для универсума). Известно, например, что эта теорема верна для арифметики Пресбургера, теории действительных чисел, коммутативных групп и других разрешимых теорий (см. [21, 20, 43]).
С другой стороны, имеются неразрешимые системы, в которых эта теорема не выполняется, например, арифметика натуральных чисел со сложением и умножением или теория множеств.
Диссертация посвящена изучению свойств коллапса и его связи с другими свойствами алгебраических систем, например, сводимостью (см. [19]). Мы изучаем различные универсумы на предмет наличия коллапса. Мы
находим примеры систем с разрешимой теорией, в которых коллапс к порядку отсутствует. Так же нами получен метод, который позволяет в некоторых случаях получить эффективное доказательство трансляционной теоремы, то есть построение Оограниченной формулы эквивалентной Оинвариантной расширенной можно выполнить алгоритмически. Таким образом, мы отвечаем на ряд открытых вопросов, сформулированных и опубликованных разными авторами.
Обзор литературы
Реляционная модель базы данных предложена Э.Коддом в [27, 28]. Там же высказана мысль о том, что для извлечения информации можно использовать алгебру отношений (реляционную алгебру). В своей статье [28] он доказал, что выразительная сила реляционной алгебры не меньше, чем у логики первого порядка. В статье [18] показано обратное: логика предикатов позволяет извлечь любую информацию, которую можно извлечь с помощью операций реляционной алгебры. Таким образом, предложенная Э.Коддом модель языка для извлечения информации из баз данных эквивалентна логике первого порядка.
В [18] показано, что существуют простые свойства алгебраических систем, которые с помощью логики предикатов выразить невозможно. Классическими примерами таких свойств являются чётность количества элементов конечного множества и связность графа. П.Канеллакис с соавторами в [37] высказали идею об использовании в формулах кроме отношений базы данных также отношений универсума, в который база данных вложена. Предполагалось, что использование внешних, «универсальных», не зависящих от базы данных знаний может увеличить выразительную силу языка запросов. Естественно, для сравнения выразительной силы необходимо рассматривать только формулы, истинность которых не зависит
от способа вложения базы данных в универсум. Они должны сохранять свое истинностное значение при произвольных изоморфизмах базы данных внутри универсума. Впервые такой класс формул был выделен в статье [26].
В некоторых случаях увеличение выразительной силы действительно возможно. Один из самых замечательных результатов получен Ю.Ш.Гуревичєм в 1990 году. Он доказал (см.[20, 9]),2 что наличие среди отношений универсума линейного порядка действительно расширяет множество свойств базы данных, выразимых формулами логики предикатов. Этот результат совершенно не зависит от типа линейного порядка и от того, как при вложении упорядочиваются элементы базы данных.
После получения этого результата стали рассматривать формулы, инвариантные относительно сохраняющих порядок изоморфизмов (см. [39, 21]), и изучать, в каких случаях эти формулы эквивалентны формулам с использованием лишь отношений базы данных и порядка. Сам термин «коллапс к порядку» появился в предварительных вариантах работ [20] и [19]
В работах [33, 34, 21] приведены примеры, когда использование отношений универсума приводит к дальнейшему увеличению выразительной силы языка. В [22] показано, что коллапса к порядку нет в арифметике натуральных чисел со сложением и умножением. Аналогичная этой структура — натуральные числа со сложением и возведением в квадрат, в ней выразимо умножение (см. [24, 43]). Каждая из этих теорий неразрешима. Другой приведённый в [22] пример — упорядоченный универсальный случайный граф, теория которого, как показано там же, неразрешима, если порядок дискретный.
С другой стороны, для многих разрешимых теорий было установлено, что они обладают свойством коллапса к порядку. Так, например, в [21] показано, что коллапс к порядку имеет место для всех о-минимальных теорий (которые были введены в [40, 38, 41]), в частности, для теории действи-
2Сам Ю.Ш.Гуревич свои результаты не опубликовал.
тельных чисел. Там же продемонстрировано, что коллапс к порядку имеет место в любой системе вида ([/, ^, Pi, Р2, ), гДе ^ — линейный порядок, a Pi, Р2,... — произвольные одноместные предикаты.
В работе [39] доказано, что трансляция расширенных Оинвариантных формул в Оограниченные может выполняться эффективно в системе действительных чисел со сложением (Ш, ^,+). В [45] этот результат обобщён на произвольные упорядоченные абелевы группы с делением.
В работе [20] О.В.Белеградека, А.П.Столбоушкина и М.А.Тайцлина приведены необходимые и достаточные условия для того, чтобы заданная Оинвариантная формула была эквивалентна оограниченной. Далее там приводится несколько достаточных признаков, позволяющих установить для теории свойство коллапса к порядку, в частности, в этой работе введены понятия псевдоконечной однородности и изолированности (позже, в работе [17], эти свойства будут уточнены и названы первыми свойствами псевдоконечной однородности и изолированности соответственно). Доказательства используют теоретико-модельные построения и теорему компактности, из них невозможно получить алгоритм, который выполнял бы построение такой оограниченной формулы. Показано, что первое свойство псевдоконечной однородности является более широким, чем первое свойство изолированности. В качестве открытых проблем в этой работе, в частности, указаны:
Задача 1. Поиск эффективного алгоритма трансляции расширенных <-инвариантных формул в <-ограниченные для арифметики Пресбургера (проблема 1).
Задача 2. Верно ли, что для любой разрешимой теории, для которой имеет место коллапс к порядку, существует эффективный алгоритм трансляции (проблема 2)?
Задача 3. Верно ли, что для любого разрешимого обогащения системы
натуральных чисел с порядком (ш, ^) имеет место коллапс к порядку (проблема 3)? Высказано предположение, что это верно.
Задача 4. Усиление предыдущего, Верно ли, что если для некоторого обогащения системы (и>, ^) коллапса к порядку нет, то в этом обогащении существует формула ip(x,y), которая способна из любого мноэюества векторов длины \х\ выделить произвольное конечное подмножество (проблема 4)? Точнее, для любого множества A = {a"i,..., а^} наборов натуральных чисел существует вектор Ьа такой, что
(Va) (if (а, Ьа) ^ а Є A).
Авторы предполагали, что это имеет место.
Дальнейшие результаты связаны с использованием этих необходимых и достаточных признаков. Например, введённые в [20] первые свойства псевдоконечной однородности и изолированности гарантируют наличие коллапса к порядку для универсума. В [46] предложены более общие условия (21, /)-псевдоконечной однородности и (21, /)-изолировашюсти, из которых следует то же самое. Используя этот метод, в [20] удалось доказать коллапс к порядку для введённых авторами квази-о-минимальных теорий, которые являются обобщениями о-минимальных теорий. В частности, коллапс к порядку был установлен для коммутативных упорядоченных групп и вещественно замкнутых полей.
В работе [16] коллапс к порядку установлен для обогащений арифметики Пресбургера слабо монотонными согласованными со сложением функциями (см. [13]). Там же сформулированы более слабые варианты гипотез из (20):
Задача 5. Для любого разрешимого обогащения арифметики Пресбургера (о;, 0,1, ^, +) имеет место коллапс к порядку (гипотеза 1).
Задача 6. Если для некоторого обогащения арифметики Пресбургера коллапса к порядку нет, то в этом обогащении существует формула (р (х, у),
которая способна из любого множества векторов длины \х\ выделить произвольное конечное подмножество (гипотеза 2). Точнее, для любого множества A = {a~i,... ,1/-} наборов натуральных чисел существует вектор Ьа такой, что
(Va) (<р (о, Ьа) ^> а Є А).
В [17] кроме первых свойств псевдоконечной однородности и изолированности были введены их аналоги — вторые свойства псевдоконечной однородности и изолированности. Подобно первым свойствам, вторые тоже влекут коллапс к порядку.
Другой подход, который, однако, всё ещё использует неэффективные теоретико-модельные построения, предложен в работе [19] Дж.Болдвипа и М.Бенедикта и усовершенствован в [46]. В [19] рассматриваются теории без независимой формулы (о самом понятии независимой формулы можно прочитать в [44]). В этой работе введены /-сводимые алгебраические системы, которые используются как техническое средство для доказательства коллапса к порядку в теориях без независимой формулы, / является неразличимой последовательностью в алгебраической системе. В [19] показано, что каждая теория, в которой отсутствует независимая формула, имеет /-сводимые модели. В работе в виде открытого вопроса высказана следующая задача:
Задача 7. Верно ли, что коллапс к порядку для универсума имеет место тогда и только тогда, когда в нём существует бесконечное определимое множество без независимой формулы?
Основной целью работ [46] и [17] было доказательство того, что определённый класс теорий (имеющих /-сводимые модели, в которых каждая формула эквивалентна Р-ограниченной формуле) обладает свойством коллапса к порядку. Однако для доказательства этого в [46] и [17] использовано не только свойство /-сводимости моделей, но и ещё одно условие: каждая
формула должна быть эквивалентна Р-ограниченной формуле. В работе [19] показано, что существование таких моделей также следует из отсутствия в теории независимой формулы. Но связи между этим свойством и /-сводимостью в [19] так и не было найдено. Осталась не установленной и связь между псевдоконечной однородностью, сводимостью и отсутствием независимой формулы, что было отмечено в [20].
В работах А.Л.Семёнова [14, 15] доказано, что обогащение арифметики Пресбургера согласованными со сложением предикатами и функциями разрешимы, если «согласование» осуществляется эффективно. К таким функциям относятся, например, показательная функция по натуральному основанию или факториал числа.
Понятие (универсального) случайного графа введено в работе [42]. В [23, 22] показано, что для упорядоченного универсального случайного графа свойство коллапса к порядку отсутствует. Если база данных содержит одноместный предикат, то возможно записать чётность количества его элементов. Хорошо известно (см., например, [24]), что дискретное упорядочение случайного графа не разрешимо, он не может служить опровержением гипотез о коллапсе к порядку для разрешимых теорий (задачи 3, 4). После опубликования работы автора [7] О.В.Белеградек (в устной форме) сформулировал следующую задачу.
Задача 8. Имеет ли место коллапс к равенству для неупорядоченного случайного графа?
В [43] приводится прямой метод установления коллапса к порядку. Н.Швайкардт демонстрирует использование непосредственно игр Эрен-фойхта. Метод этот, к сожалению, не обладает никакой универсальностью, в каждом конкретном случае приходится определять стратегию повторителя. Не указано никаких признаков для теории, но которым можно было бы распознать, применим ли этот метод.
Одним из интереснейших достижений последнего времени в области арифметических теорий явилось оригинальное обогащение арифметики Пресбургера, предложенное в [25] А.Блюменсатом и Э.Гределем. Это обогащение разрешимо и, в то же время, имеет независимую формулу (чем была опровергнута гипотеза из [19], что таких обогащений не существует). В построенной системе каждая формула эквивалентна (в определённом смысле) некоторому конечному автомату и наоборот, поэтому введённые в [25] системы названы автоматными. В [17] предложено аналогичное обогащение при помощи предиката Е (см. определение в главе 1) и показано, что такое обогащение не обладает свойствами изолированности. Далее, в [17] ставится следующий вопрос.
Задача 9. Обладает ли теория системы (uj, ^, Е) свойством коллапса к порядку?
Цели работы
Установить, имеет ли место коллапс к порядку в семёновских обогащениях арифметики Пресбургера.
Установить, существуют ли разрешимые теории в которых коллапса к порядку нет (задачи 3, 4),
в частности, установить, есть ли такие системы среди обогащений арифметики Пресбургера (задачи 5, 6),
в частности, установить, имеет ли место коллапс к порядку для системы (ш, <,Е) (задача 9).
Детально исследовать случайный граф на предмет свойства коллапса (задача 8).
Установить связь между сводимостью, изолированностью, псевдоконечной однородностью и коллапсом к порядку.
Установить, имеются ли сводимые обогащения арифметики Пресбургера с независимой формулой (задача 7).
Разработать механизмы эффективной трансляции для расширенных <-инвариантных формул в <-ограниченные (задачи 1, 2).
Апробация работы
Содержание диссертации опубликовано в журналах: «Математические заметки» (см.[3, 4]), «Известия РАН. Серия математическая» (см.[6]), «Фундаментальная и прикладная математика» (см.[10]), «Успехи математических наук» (см.[9]), «Вестник Тверского государственного университета» (см.[7, 11]), «Вестник Новгородского государственного университета» (см. [8]), других изданиях (см. [5]).
Содержание диссертации многократно излагалось в 2001-2006 годах на семинаре «Теоретические основы информатики», проходящем в Тверском государственном университете, семинаре по математической логике Московского университета, семинаре по математической логике Санкт-Петербургского отделения математического института РАН.
Доклад, посвященный одному из разрабатываемых в диссертации вопросов, был сделан на международной конференции по теоретической информатике CSR-2006 (Санкт-Петербург, июнь 2006, см. [29]).
Структура диссертации
Диссертация состоит из введения, шести глав основной части, заключения, списка литературы и предметного указателя.
Теории и алгебраические системы
Основные сведения о теориях и алгебраических системах можно найти, например, в [1, 12]. Если в данной главе у какого-то определения или тео ремы не указан автор, то о них можно прочитать в только что упомянутых книгах. Знак равенства мы всюду будем считать логическим символом и не будем включать его в состав сигнатур. Определение 1.1. Если t — терм, то запись t(xi,... ,хп) означает, что все переменные терма t содероісатся среди Х\,..., хп. Если 21 — алгебраическая система сигнатуры Е, то с помощью 21 будем обозначать её носитель. Если аі,...,а„ Є 2l, a L(xi,... ,хп) — терм сигнатуры Е, то запись (ai,..., ап) означает значение терма і на состоянии а, в котором о {х\) = г\, ..., а(хп) = ап. Определение 1.2. Формула первого порядка без свободных переменных называется ЗАМКНУТОЙ. Запись (р(х\,..., хп) означает, что все свободные переменные формулы (f содероісатся среди х\,..., хп. Если 21 — алгебраическая система сигнатуры Е; р(хі,... ,хп) — формула сигнатуры Е и ai,...,аге Є \Щ, то запись (аі, ?а„) — это значение формулы (р в алгебраической системе 21 на состоянии а, в котором а{х\) = Зі, ..., о (хп) — эп. Если /?(аі, . -,ап) истинно (ложно), то говорят, что формула (р истинна (ложна) на наборе (a i,..., an). Для краткости, набор однородных объектов, например, (ai,...,an); будем записывать в векторной форме: а.
Если 21 — алгебраическая система сигнатуры Е, X С 21, то Ех — сигнатура, получетшя из Е добавлением константного символа Са для каждого а Є X. 21х — алгебраическая система сигнатуры Ех, в которой каждая константа С3 интерпретируется как а. В дальнейшем мы часто будем отождествлять константу Са и элемент а, который она обозначает. Определение 1.3. ТЕОРИЯ — множество замкнутых формул первого порядка, замкнутое относительно логического следования. Если 21 — алгебраическая система сигнатуры , то Th(2l) — теория алгебраической системы 21, то есть множество, содероісащее все замкнутые формулы сигнатуры истинные в 21. Определение 1.4. Множество формул К сигнатуры называется ТИПОМ б теории Т (в алгебраической система %) сигнатуры Е, если выполняются следующие условия: 1) существует переменная х такая, что каоїсдая формула множества К или замкнута, или содержит только одну свободную переменную — х; 2) мнооїсество К является конечно совместным, то есть для любых принадлежит Т (истинна в 21J; 3) множество К является максимальным, то есть никакое расшире ние множества К сигнатуры , удовлетворяющее пункту I), не является конечно совместным. Если 21 — алгебраическая система, X — подмножество её носителя, то тип в алгебраической системе 21х также называется ТИПОМ НАД МНОЖЕСТВОМ X в системе 21. Если в алгебраической системе 21 существует элемент а такой, что для любой формулы (р(х) из типа
К значением /?(а) является истина, то тип К РЕАЛИЗУЕТСЯ в 21. Если а — элемент алгебраической системы 21, то множество формул (f{x), для которых /?(а) истинно, является типом — ТИПОМ ЭЛЕМЕНТА а, обозначаемым tpa(a) или просто tp(a), если понятно, о какой алгебраической системе идет речь. Если X С 21, то тип tpa (а) называется также ТИПОМ ЭЛЕМЕНТА а НАД МНОЖЕСТВОМ X в системе 21 и обозначается такоісе через tp%(a/X) или tp(a/X), если попятно, о какой алгебраической системе идет речь. Определение 1.5. Если N — кардинал, то алгебраическая система 21 называется -НАСЫЩЕННОЙ, если для каждого подмножества X носителя системы 21 мощности меньшей К и каждого типа К над X тип К реализуется в 21. Определение 1.6. Если К — кардинал, то алгебраическая система 21 мощности К называется СПЕЦИАЛЬНОЙ, если она является объединением элементарной цепи (21г-)г- к (г являются кардиналами меньшими К/ в которой каждая система 21 является i+-насыщенной. С помощью iv обозначается кардинал, следующий за кардиналом і. Основные теоремы о специальных моделях: Теорема 1.1. Пусть Т — непротиворечивая теория сигнатуры Е, имеющая бесконечные модели. Пусть К — кардинал, К \Т\, и Тогда Т имеет специальную модель мощности К. Теорема 1.2. Любые две элементарно эквивалентные специальные алгебраические системы одной мощности изоморфны. Определение 1.7. Если I — подмножество носителя алгебраической системы 21, и среди отношений системы 21 есть линейный порядок , то I называется НЕРАЗЛИЧИМЫМ МНОЖЕСТВОМ или НЕРАЗЛИЧИМОЙ ПОСЛЕДОВАТЕЛЬНОСТЬЮ, если для любых двух одинаково упорядоченных наборов х Є / и у Є / одинаковой длины на х и у в системе 21 истинны одни и те же формулы. Множество формул, которые истинны па любых наборах элементов из I, упорядоченных по возрастанию, назовём ТИПОМ этой последовательности.
Коллапс к порядку для обогащений начального фрагмента нестандартных моделей арифметики Пресбургера
Теперь покажем, что система (23, /) обладает первым свойством изолированности, где 23 и / такие же как и в предыдущей лемме. Теорема 2.8. Пусть 23 — произвольная модель Т". Пусть Г — произвольное термально изолированное неразличимое множество в 23 , все элементы которого больше иР . Тогда система (93 , V) обладает первым свойством изолированности. Доказательство. Рассмотрим любую специальную систему (23, /) = (23 ,/ ). Тогда / — термально изолированное неразличимое множество в 23, все элементы которого больше UJ2,. Предположим, что D С I — псевдоконечное множество в 23 и Е С 23 — конечное множество. Рассмотрим произвольный х Є 15331 и тип tp(x/F), где F = D U Е. Мы уже доказали, что V допускает элиминацию кванторов, следовательно, можно ограничиться рассмотрением только бескванторных формул. Формула р (х) из tp (x/F) в общем случае имеет вид: Пусть d — элементы F в этой формуле. Будем считать, что элементы па-бора d различны и упорядочены по убыванию. Если k = 0, то мы имеем только неравенства Из-за псевдоконечности D среди всевозможных L\ (d) и s\ (d) существуют наибольшие, меньшие x, а среди (d) и 52 (d) существуют наименьшие, ко торые больше х. Все остальные неравенства будут следовать из неравенств с этими d.
Пусть теперь к 1. Для каждого г\ тип должен содержать или г] 0, или г\ 0. Из первого автоматически следует, что -iPj. (f ), и всё сводится к случаю с меньшим количеством вхождений Pi. Во втором (А) л случае если гг- не содержит d, то все сводится к случаю с меньшим количеством d. Если же содержит, то из предыдущей леммы следует, что может существовать не более одного набора d , для которого выполняется Используя эти свойства для каждой формулы ір (ж, d) можно найти ко нечное количество d, значение формулы на которых определяют её значе ние и на остальных наборах из D. Составим из элементов всех этих наборов счётное множество, объединим его с Е и получим G такое, что тип tp (x/F) изолируется типом tp (х/С). Теорема 2.9. Пусть теория Т — Th(w,0,1, ,+, {РІ)І), где Pj — произвольные предикаты, допускает элиминацию кванторов. Пусть 21 У {и, 0,1, , +) — элементарное (строгое) расширение арифметики Прес-бургера. Тогда в теории V — Th (21, {Р{){) имеет место коллапс к порядку. Доказательство. Следует из теорем 2.8 и 1.4. Алгебраическая система этой сигнатуры называется ГРАФОМ. Элементы графа называют ВЕРШИНАМИ. В работе [42] определён некоторый граф со счётно бесконечным множеством вершин, называемый (универсальным) случайным графом.1 1) Определение 3.1 (Радо). Назовём граф 0 = (V,E) СЛУЧАЙНЫМ, если для любых четырёх конечных множеств вершин Аі, Л 2, Лз, А\, для которых А\ П 1Англ. the random graph. Очевидно, что любой случайный граф бесконечен. Более того (см. [31]) теория случайного графа без петель является счётно категоричной и, следовательно, полной.
Если случайный граф упорядочен, то есть на его вершинах определён некоторый линейный порядок , то, очевидно, в системе (0, ) отсутствует свойство коллапса к порядку. Следующий результат получен в [23]. Приведём его доказательство, так как в последующем будем ссылаться па этот метод. Теорема 3.1 (Бенедикт, Либкин). Теория Th(0, ) не обладает свойством коллапса к порядку. Доказательство. Покажем, например, что существует расширенная формула, истинная в состоянии базы данных с сигнатурой, состоящей из имени одного одноместного отношения Р, тогда и только тогда, когда количество элементов в Р четно. Действительно, это свойство выражается формулой Формула утверждает, что в множестве Р можно выделить подмножество Р , которое содержит каждый элемент Р тогда и только тогда, когда оно не содержит следующий за ним по порядку элемент Р, Р содержит минимальный элемент Р и не содержит максимальный. Но, как известно, никакая Оограниченная формула чётность числа эле ментов Р выразить не может.
Разрешимое упорядочение случайного графа
Рассмотрим множество рациональных чисел Q. Пронумеруем его элементы натуральными числами: Определим на множестве Q бинарный предикат Е так, чтобы система (Q, Е) стала случайным графом без петель. Индукцией по п определим отношения Еп. Изначально полагаем IQ% — Q,zE0 = 0. Рассмотрим определение Еп. По индукции считаем, что значение предиката Еп-\ определено на тех парах (q , c\j), для которых і п или j п. Для остальных пар рациональных чисел отношение En-i ложно. При этом построены множества In-\L для всевозможных К, L С {q0,... ,q„_i}, которые являются всюду плотными в Q и образуют разбиение Q. Для всех г п выполнено (qj,q;) . Еп-\. Для всех г п и т і таких, что цт Є Іп-іь предикат Еп-\ определён так, что Итак, начнём определять отношение Еп. Если для пары рациональных чисел вида (qi,4j) выполнено min{i,j} п, то Определим Еп для пар (qi,qj), в которых minfi,]} = п. 1)
Полагаем (q„,q„) . Еп. 2) Каждое из существующих множеств 1п-\І разобьём на два множества 1 пь и I nL- кажДое из которых было бы плотно в Q. Для т п положим (qm, q„) Є Еп для qm G/;f{q"}n(qm,qn) для qm Є I nL . 3) Каждое из полученных на шаге 2) множеств I nL разобьём на два множества ІпшіцЛ и Inl, каждое из которых было бы плотно в Q. Для т п положим (q„,qm) Є Еп для qm Є Іпш{Цп} и Ы Цт) І Еп для Цт Є nL Если min {г, j} п, то считаем, что Еп (q , qj) ложно. Очевидно, что построенные таким образом множества снова будут удовлетворять условиям индукционного предположения. Следовательно, этот процесс построения можно продолжать бесконечно и определить отношения Еп для любого п. Пусть Мы будем рассматривать систему (Q, Е, ). Покажем, что отношение Е образует на множестве рациональных чисел случайный граф. Лемма 3.3. Пусть а, Ь, сь ..., ск, db ..., dj, еь ..., em, fb ..., f„ такие рациональные числа, что 1) существует рациональное число х; такое, что 1) a х b; Доказательство. Все рациональные числа из условия леммы имеют неко торые номера в нумерации (q . Пусть натуральное число S превышает все эти номера. На шаге S при построении Es мы получим в том числе такое множество ISL , что К = {ci, ...,} и L = {ei,..., em}. Это множество будет плотно в Q. Следовательно, между а и b располагается бесконечно много элементов этого множества. Выберем в качестве х такое q Є ISL лежащее между а и Ь, чтобы М S. Тогда q будет удовлетворять всем условиям леммы. Следствие 3.3.1. Система (Q,E) — случайный граф. Доказательство. Условия 2)-5) заключения леммы повторяют определе ние случайного графа. Теорема 3.4. Теория Th (Q, Е, ) допускает эффективную элиминацию кванторов. Доказательство. Так как Е(х,х) для всех х, то такие формулы можно исключить. В общем случае формула, в которой мы должны удалять квантор, имеет вид: В самом деле, при наличии формул х = g переменная х просто заменяется на д. Формула - х = д эквивалентна х g\J д х. Если СІ — dj или ЄІ = fj для некоторых i,j, то формула (3.1), очевидно, ложна. Также она ложна, если а Ь. Иначе, по лемме 3.3, она истинна. Таким образом, формула (3.1) эквивалентна следующей:
Следствие 3.4.1. Теория Th (Q, Е, ) разрешима. Теперь докажем, что если сигнатура базы данных является МОНАДИ-ЧЕСКОЙ (то есть все её отношения являются одноместными), то использование неупорядоченного случайного графа не увеличивает выразительной силы языка логики первого порядка. В частности, нельзя ответить на вопрос о чётности количества элементов какого-либо конечного множества. Если сигнатура О, базы данных состоит из п унарных предикатных символов, то в любой алгебраической системе сигнатуры Q их значения разбивают носитель в общем случае на 2п непересекающихся частей. Поэтому мы всегда можем считать, что вместо монадической сигнатуры базы данных Г2 = (Р\,...,Рп) мы оперируем с монадической сигнатурой О, = IPQ,PI,..., P in-\), такой, что предикаты, означаемые символами Рг-, не пересекаются. Предикат PQ соответствует ложности всех Pi,..., Рп, как мы указали при определении активной области состояний, всегда пуст, поэтому не нужен, в дальнейшем мы будем его опускать. Легко показать, что любая формула в сигнатуре (Q, EG) эффективно транслируется в формулу сигнатуры Ш,с). В самом деле, достаточно каждую атомную формулу вида Д (х) заменить на дизъюнкцию формул вида Pj (х), где дизъюнкция берется по тем j, для которых Pj С Р{. Обратное преобразование так же легко осуществимо: если есть формула сигна туры U, то она преобразуется в формулу сигнатуры Q с помощью замены каждой атомной формулы вида Pj (х) на конъюнкцию формул вида Р; (.г1) и -іД (х). Таким образом, мы можем ограничиться рассмотрением только формул в сигнатурах О, и Рассмотрим произвольное свойство 5 состояний базы данных сигнатуры U, которое невыразимо ограниченными формулами. Определение 3.2. Пару алгебраических систем 21 и 03 сигнатуры ІЇ будем называть («S,jo)-nAPOM, если 21 обладает свойством S, 03 — пе обладает свойством S, мощности множеств Pj в 21 и 03 равны, если j ф jo, и отличаются на 1, если j = jo- Мощность предиката PjQ в 21 будем называть РАЗЛИЧАЮЩЕЙ МОЩНОСТЬЮ пары. Теорема 3.5. Для любого свойства S, не выразимого ограниченными формулами, существует номер jo, для которого существуют (S,jo)-napu сколь угодно большой различающей мощности. Доказательство. Допустим, что это не так, и для некоторого свойства S, которое не выразимо ограниченными формулами, такого jo не существует. Это означает, что для каждого номера j различающая мощность ( S, j)-nap ограничена некоторым числом Mj. Так как различных j конечно много, то существует наибольшее из этих Mj, обозначим его М. Очевидно, что количество (неизоморфных) алгебраических систем сигнатуры 1, в которых каждый из предикатов имеет мощность, не превышающую М+1, конечно. Следовательно, существует формула ір (Сі), которая выражает свойство S для всех таких систем. Рассмотрим произвольную алгебраическую систему сигнатуры U, в которой есть предикаты с мощностью большей М + 1:
Достаточные условия сводимости
Напомним, что мы рассматриваем систему (21,7) сигнатуры (Е, Р), где I — неразличимая в 21 последовательность. Определение 4.11. Пусть р{х,у) — формула сигнатуры (Е,Р). Пусть а Є 21 — произвольный набор длины \у\. Пусть di, d2 — наборы элементов I длины \х\. Будем пару (di, ) называть РАЗЛИЧАЮЩЕЙ для формулы Lp и набора а, если элементы наборов d\ и 62 одинаково упорядочены, и существует номер г о такой, что dj = d; для всех і Ф г о и Без ограничения общности считаем, что df d . Тогда отрезок d ;d будем называть РАЗЛИЧАЮЩИМ ОТРЕЗКОМ и обозначать diff[di,d2]. Две различающих пары (di, сіг) и (d , dQ назовём НЕПЕРЕСЕКАЮЩИМИСЯ, если не пересекаются их различающие отрезки cliff [di,d2] и diff№,d2]. Определение 4.12. Элемент є Є I будем называть ОПРЕДЕЛЯЮЩИМ для набора а и формулы р, если для любой открытой окрестности 0(e) в I существует различающая пара (di, 82) для ipua, для которой diff[di,d2]cO(e). Теорема 4.23. Пусть в системе (21,/) сигнатуры (Е,Р) множество I является неразличимым в 21 и плотно полно упорядоченным без концевых элементов. Для того, чтобы формула р(х, у) сигнатуры (Е, Р) была 1-сводимой необходимо и достаточно, чтобы существовала константа М Є и и для любого набора а Є 21 количество определяющих элементов для (риа было ограничено М. Доказательство. Необходимость очевидна: если формула р(х, у) является /-сводимой при помощи бескванторной порядковой формулы ifi(x,z), то есть для каждого а є 21 существует с5 Є / такой, что то все определяющие для а и (р элементы могут находиться только среди элементов набора Са, а их количество ограничено длиной набора z. Докажем достаточность. Для этого продемонстрируем, что если с Є / — набор из всех определяющих элементов для а и формулы (f(x,y), то для любых двух наборов di,d2 Є /, которые имеют одинаковый порядковый тип над с формула р (di, а) и ір (сЗг,а) имеет одно и то же значение. Используем индукцию по количеству неравных компонент наборов di и d2 Базис. Пусть di и d2 различаются только одной компонентой: х\ ф U2 Для некоторого го- Предположим, что на di и сЬ значение формулы различно. Будем рассматривать множество
Пусть для любого f Є С запись df обозначает набор, полученный из di заменой элемента d-p на f. Пусть С\ — множество элементов f Є С, для которых а 02 — множество элементов f є С, для которых Так как (Ci,C2) — разбиение С, в котором оба множества непусты, а порядок на С полный и плотный, то, очевидно, хотя бы одно из множеств С\ или С2 содержит хотя бы одну граничную точку е. Но тогда точка е будет определяющей для а и формулы (р, следовательно, она лежит в наборе с, и наборы di и d2 имеют разный порядковый тип над с. Противоречие. Пусть теперь наборы различаются более чем одной компонентой. Пусть, например, dj — наименьшая из неравных компонент обоих наборов. Пусть набор d2 получен из d2 заменой d2 па Щ Тогда наборы d2 и d2 различаются одной компонентой. Так как di и d2 имеют одинаковый порядковый тип над с, то, согласно базису индукции, Но наборы di и d2 различаются меньшим числом компонент и тоже имеют одинаковый порядковый тип над с. Согласно индукционному предположению, мы можем считать, что и, следовательно, Теорема доказана. Теорема 4.24. Пусть в системе (21,/) сигнатуры (Е, Р) мнооїсество I является неразличимым в 21. Пусть для любой формулы ср сигнатуры Е существует константа М Є и и для любого набора а Є 21 количество непересекающихся различающих пар для if и а ограничено Mv. Тогда существует J-сводимая система (93, J), где 93 = 21. Доказательство. Пусть система (93, J ) = (21, /) является (2 )+-насыщен ной. Тогда существует множество J С J , порядок на котором изоморфен обычному порядку на действительных числах. Если допустить, что какая нибудь формула ср не ./-сводима в (93, J), то, согласно теореме 4.23, коли чество определяющих элементов для неё не ограничено, и, следовательно, можно построить сколь угодно много непересекающихся различающих пар. Но тогда то же самое можно сделать в (93,«/ ), потому что J С J , и в (21, /), поскольку (93,«/ ) = (21, /). Противоречие. Будем считать, что сигнатура Е является счётной.
Лемма 4.25. Пусть (21,/) — алгебраическая система сигнатуры (Е, Р), / — неразличимая в 21 (соответственно, в (21,1)) последовательность, которая плотно полно упорядочена. Пусть в системе (21, /) существует формула сигнатуры Е (соответственно, сигнатуры (Е, Р)), которая не является I-сводимой. Тогда существует формула Ф(ги,у, z) сигнатуры Е (соответственно, сигнатуры (Е, Р)) такая, что для любого кардинала N 121 , для которого и для любой специальной системы (23, J) У (21, /) мощности Н выполнено следующее: существует набор а Є 1] длины у; существует мнооїсество D наборов d Є / длины \w\, мощность В равна Н; и при этом для любого отображения є : D — {0; 1} множество конечно совместно в 03 (соответственно, в (03, J)j. Здесь Ф1 — салш формула Ф, а Ф — её отрицание. Доказательство. Пусть формула р(:с, у ) не является /-сводимой, если х — /-ограниченные переменные. Считаем, что количество не /-ограниченных переменных, то есть у , в формуле Lp является минимально возможным. Если бы длина набора у была равна нулю, то, в силу неразличимости /, её значение определялось бы исключительно порядковым типом набора х, то есть она была бы сводимой. Значит переменные, то все формулы Фт(йт, у) содержат меньше не /-ограниченных переменных чем /?, поэтому все они являются /-сводимыми в алгебраической системе (21, /). Пусть формула Ф(щ,ЇІ)2, у, z) говорит, что (wi,W2) — различающая пара для формулы (р и набора (у, z). Так как формула p(x,y,z) не /-сводима, то, согласно теореме 4.23, существует последовательность наборов (а , Ь;);Єа; из 21 таких, что количество различных определяющих элементов / для формулы ір и набора (a"j, bf) не меньше г. Обозначим эти определяющие элементы через ец:...,ец. Для удобства всегда считаем, что определяющие элементы е , , &ц упорядочены по возрастанию. По определению, мы можем для каждого е выбрать различающую пару (d i, ), Для которой diff[diji,dy2] С О(е ),
