Классификация счётных моделей полных теорий: в 2 ч. Ч. 1

 
РЕДАКЦИОННАЯ КОЛЛЕГИЯ 
СЕРИИ «МОНОГРАФИИ НГТУ» 

 

д-р техн. наук, проф. (председатель)  А.А. Батаев 

д-р техн. наук, проф. (зам. председателя)  А.Г. Вострецов 

д-р техн. наук, проф. (отв. секретарь)  В.Н. Васюков 

 

д-р техн. наук, проф. А.А. Воевода 

д-р техн. наук, проф. В.И. Денисов 

д-р физ.-мат. наук, проф. А.К. Дмитриев 

д-р физ.-мат. наук, проф. В.Г. Дубровский 

д-р филос. наук, проф. В.И. Игнатьев 

д-р физ.-мат. наук, проф. О.В. Кибис 

д-р филос. наук, проф. В.В. Крюков 

д-р соц. наук, проф. Л.А. Осьмук 

д-р техн. наук, проф. Н.В. Пустовой 

д-р техн. наук, проф. Г.И. Расторгуев 

д-р физ.-мат. наук, проф. В.А. Селезнев 

д-р техн. наук, проф. Ю.Г. Соловейчик 

д-р техн. наук, проф. А.А. Спектор 

д-р техн. наук, проф. А.Г. Фишов 

д-р экон. наук, проф. М.В. Хайруллина 

д-р техн. наук, проф. В.А. Хрусталев 

д-р техн. наук, проф. А.Ф. Шевченко 

 
УДК 510.67 
         С892 
Рецензенты: 
член-корр. НАН Республики Казахстан,  
д-р физ.-мат. наук, проф. Б. С. Байжанов, 
д-р физ.-мат. наук, проф. Е. А. Палютин, 
д-р физ.-мат. наук, проф. А. Г. Пинус 
 
Судоплатов С. В. 
С892       Классификация счётных моделей полных теорий: монография в 2 ч. / 
С. В. Судоплатов.– 2-е изд., доп. – Новосибирск: Изд-во НГТУ, 2018. – 
(Серия «Монографии НГТУ») 
ISBN 978-5-7782-3523-6 
Ч.1. – 376 с. 
ISBN 978-5-7782-3524-3 
Книга является первой частью монографии «Классификация счётных 
моделей полных теорий»', состоящей из двух частей. В монографии 
излагается классификация счётных моделей полных теорий относительно 
двух основных характеристик (предпорядков Рудин–Кейслера и функций 
распределения числа предельных моделей) применительно к важнейшим 
классам счётных теорий. К таким классам относятся класс эренфойхтовых 
теорий (т. е. полных теорий с конечным, но большим единицы числом 
попарно неизоморфных счетных моделей), класс малых теорий (т. е. полных 
теорий, имеющий счётное число типов) и класс счётных теорий с 
континуальным числом типов. Для реализации основных характеристик 
счётных 
полных 
теорий 
приводятся 
синтаксические 
генерические 
конструкции, обобщающие конструкции Йонсона–Фраиссé и конструкции 
Хрушовского. На основе этих конструкций представляется решение 
проблемы Гончарова–Миллара о существовании эренфойхтовой теории, 
имеющей счётные, не почти однородные модели. С помощью модификации 
генерической конструкции Хрушовского–Хервига приводится решение 
проблемы Лахлана о существовании стабильной эренфойхтовой теории. В 
первой части рассмотрена характеризация эренфойхтовости, свойства 
эренфойхтовых теорий, генерические конструкции, а также алгебры 
распределений бинарных полуизолирующих формул полной теории.  
Для интересующихся математической логикой. 
УДК 510.67 
ISBN 978-5-7782-3524-3 (Ч.1)                              © Судоплатов С. В., 2014, 2018 
ISBN 978-5-7782-3523-6                                      © Новосибирский государственный 
технический университет, 2014, 2018 
 
 

 
УДК 510.67 
          С892 
Reviewers: 
Member Corresponding of National Academy of Sciences at Republic  
of Kazakhstan, Professor B. S. Baizhanov, D.Sc. (Phys. & Math.), 
Professor E. A. Palyutin, D.Sc. (Phys. & Math.), 
Professor A. G. Pinus, D.Sc. (Phys. & Math.) 
 
Sudoplatov S. V. 
С892     Classification of countable models of complete theories: monograph, 2nd 
revised edition in two parts / S. V. Sudoplatov. – Novosibirsk : NSTU 
Publisher, 2018. – (“NSTU Monographs” series) 
ISBN 978-5-7782-3523-6 
Рart 1. – 376 p. 
ISBN 978-5-7782-3524-3 
The book is the first part of the monograph “Classification of countable models 
of complete theories” consisting of two parts. In the monograph, a classification of 
countable models of complete theories with respect to two basic characteristics 
(Rudin–Keisler preorders and distribution functions for numbers of limit models) is 
presented and applied to the most important classes of countable theories such as the 
class of Ehrenfeucht theories (i. e., complete first-order theories with finitely many 
but more than one pairwise non-isomorphic countable models), the class of small 
theories (i. e., complete first-order theories with countably many types), and the 
class of countable first-order theories with continuum many types. For realizations 
of basic characteristics of countable complete theories, syntactic generic 
constructions, generalizing the Jonsson–Fraïssé construction and the Hrushovski 
construction, are presented. Using these constructions a solution of the Goncharov–
Millar problem (on the existence of Ehrenfeucht theories with countable models 
which are not almost homogeneous) is described. Modifying the Hrushovski–
Herwig generic construction, a solution of the Lachlan problem on the existence of 
stable Ehrenfeucht theories is shown. In the first part, a characterization of 
Ehrenfeuchtness, properties of Ehrenfeucht theories, generic constructions, and 
algebras for distributions of binary semi-isolating formulas of a complete theory are 
considered. 
The book is intended for specialists interested in Mathematical Logic. 
 
УДК 510.67 

ISBN 978-5-7782-3524-3 (Part 1)                                  © Sudoplatov S. V., 2014, 2018 
ISBN 978-5-7782-3523-6                                              © Novosibirsk State Technical 
University, 2014, 2018 

 
 

Оглавление

Предисловие ко второму изданию . . . . . . . . . . . . .
13

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . .
14

Введение и исторический обзор
. . . . . . . . . . . . . .
20

Глава 1. Характеризация эренфойхтовости. Свойства

эренфойхтовых теорий . . . . . . . . . . . .
34

§ 1.1.
Синтаксическая характеризация класса полных

теорий с конечным числом сч¨eтных моделей
.
34

§ 1.2.
Несущественные совмещения и раскраски систем 67

§ 1.3.
Т´иповая редуцированность, властные типы и

свойство строгого порядка . . . . . . . . . . . .
91

§ 1.4.
Властные орграфы
. . . . . . . . . . . . . . . .
113

§ 1.5.
Теоремы Цубои и Кима . . . . . . . . . . . . . .
127

Глава 2.
Генерические конструкции . . . . . . . . . . .
136

§ 2.1.
Семантические генерические конструкции . . .
136

§ 2.2.
Синтаксические генерические конструкции . .
138

§ 2.3.
Самодостаточные классы . . . . . . . . . . . . .
154

§ 2.4.
Генеричность сч¨eтных однородных систем . . .
162

§ 2.5.
Свойство однородного t-амальгамирования и на-

сыщенные генерические системы . . . . . . . .
167

§ 2.6.
О свойстве конечных замыканий в слияниях ге-

нерических классов . . . . . . . . . . . . . . . .
175

§ 2.7.
О порождающих элементах в генерических ал-

гебрах . . . . . . . . . . . . . . . . . . . . . . . .
185

§ 2.8.
О многообразиях генерических классов
. . . .
190

Глава 3.
Алгебры распределений бинарных полуизо-

лирующих формул полной теории
. . . .
194

§ 3.1.
Предварительные понятия, обозначения и свой-

ства . . . . . . . . . . . . . . . . . . . . . . . . .
194

§ 3.2.
Примеры . . . . . . . . . . . . . . . . . . . . . .
201

§ 3.3.
Алгебра распределений бинарных изолирующих

формул на множестве реализаций типа
. . . .
207

§ 3.4.
Характеризация транзитивности отношения Ip.

Детерминированные, почти детерминированные

Iν(p)-группоиды и элементы . . . . . . . . . . .
213

§ 3.5.
Композиции графов и композиции моноидов .
221

§ 3.6.
I-группоиды . . . . . . . . . . . . . . . . . . . .
224

§ 3.7.
Группоиды бинарных изолирующих формул на

множестве реализаций типов специальных теорий
. . . . . . . . . . . . . . . . . . . . . . . . .

231

§ 3.8.
Частичный группоид бинарных изолирующих

формул на множестве реализаций семейства 1-

типов полной теории
. . . . . . . . . . . . . . .
235

§ 3.9.
IR-системы . . . . . . . . . . . . . . . . . . . . .
239

§ 3.10. Понятия, обозначения и свойства . . . . . . . .
242

§ 3.11. Предупорядоченные алгебры распределений бинарных 
полуизолирующих формул . . . . . . .
249

§ 3.12. Ранги и степени полуизолированности . . . . .
252

§ 3.13. Моноид распределений бинарных полуизолиру-

ющих формул на множестве реализаций типа .
258

§ 3.14. α-Детерминированные и почти α-детерминированные 
SIν(p)-моноиды
. . . . . . . . . . . . . .
260

§ 3.15. POSTC-моноиды
. . . . . . . . . . . . . . . . .
267

§ 3.16. Частичный POSTC-моноид на множестве реализаций 
семейства 1-типов полной теории . . .
271

§ 3.17. POSTCR-системы . . . . . . . . . . . . . . . . .
277

§ 3.18. Алгебры распределений бинарных полуизоли-

рующих формул для семейств изолированных

типов и для сч¨eтно категоричных теорий
. . .
282

§ 3.19. Форсирование бесконечности и алгебры распределений 
бинарных полуизолирующих формул

для сильно минимальных теорий . . . . . . . .
284

§ 3.20. Поглощающие системы . . . . . . . . . . . . . .
290

§ 3.21. Системы распределений изолирующих формул

как производные системы: для ациклических

графов
. . . . . . . . . . . . . . . . . . . . . . .
295

Библиографический список . . . . . . . . . . . . . . . . .
304

Именной указатель . . . . . . . . . . . . . . . . . . . . . .
354

Указатель терминов . . . . . . . . . . . . . . . . . . . . . .
360

Указатель обозначений . . . . . . . . . . . . . . . . . . . .
370

Contents

Preface to second edition
. . . . . . . . . . . . . . . . . . .
13

Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14

Introduction and historical survey . . . . . . . . . . . . . .
20

Chapter 1. Characterization of Ehrenfeuchtness. Properties

of Ehrenfeucht theories . . . . . . . . . . . . .
34

§ 1.1.
Syntactic characterization of the class of complete

theories with finitely many countable models
. .
34

§ 1.2.
Inessential combinations and colorings of structures 67

§ 1.3.
Type reducibility, powerful types, and the strict

order property
. . . . . . . . . . . . . . . . . . .
91

§ 1.4.
Powerful digraphs
. . . . . . . . . . . . . . . . .
113

§ 1.5.
The Tsuboi and Kim theorems
. . . . . . . . . .
127

Chapter 2.
Generic constructions . . . . . . . . . . . . . .
136

§ 2.1.
Semantic generic constructions
. . . . . . . . . .
136

§ 2.2.
Syntactic generic constructions . . . . . . . . . .
138

§ 2.3.
Self-sufficient classes . . . . . . . . . . . . . . . .
154

§ 2.4.
Genericity of countable homogeneous structures .
162

§ 2.5.
The uniform d-amalgamation property and saturated

generic structures . . . . . . . . . . . . . . . . . .
167

§ 2.6.
On the finite closure property in fusions of generative

classes . . . . . . . . . . . . . . . . . . . . . . . .
175

§ 2.7.
On generating elements in generic algebras . . . .
185

§ 2.8.
On varieties of generative classes . . . . . . . . .
190

Chapter 3.
Algebras of distributions for binary semi-

isolating formulas of a complete theory
. .
194

§ 3.1.
Preliminary notions, notations, and properties . .
194

§ 3.2.
Examples . . . . . . . . . . . . . . . . . . . . . .
201

§ 3.3.
Algebra of distributions for binary isolating formulas

on a set of realizations of a type
. . . . . . . . .
207

§ 3.4.
Characterization for transitivity of the relation Ip.

Deterministic, almost deterministic Iν(p)-groupoids

and elements
. . . . . . . . . . . . . . . . . . . .
213

§ 3.5.
Graph and monoid compositions
. . . . . . . . .
221

§ 3.6.
I-groupoids . . . . . . . . . . . . . . . . . . . . .
224

§ 3.7.
Groupoids of binary isolating formulas on sets of

realizations of types of special theories . . . . . .
231

§ 3.8.
Partial groupoid of binary isolating formulas on

a set of realizations for a family of 1-types of a

complete theory . . . . . . . . . . . . . . . . . . .
235

§ 3.9.
IR-structures . . . . . . . . . . . . . . . . . . . .
239

§ 3.10. Notions, notations, and properties
. . . . . . . .
242

§ 3.11. Preordered algebras of distributions of binary semi-

isolating formulas . . . . . . . . . . . . . . . . . .
249

§ 3.12. Ranks and degrees of semi-isolation . . . . . . . .
252

§ 3.13. Monoid of distributions of binary semi-isolating

formulas on a set of realizations of a type
. . . .
258

§ 3.14. α-deterministic and almost α-deterministic SIν(p)-

monoids . . . . . . . . . . . . . . . . . . . . . . .
260

§ 3.15. POSTC-monoids . . . . . . . . . . . . . . . . . .
267

§ 3.16. Partial POSTC-monoid on a set of realizations for

a family of 1-types of a complete theory . . . . .
271

§ 3.17. POSTCR-structures . . . . . . . . . . . . . . . .
277

§ 3.18. Algebras of distributions of binary semi-isolating

formulas for families of isolated types and for count-

ably categorical theories . . . . . . . . . . . . . .
282

§ 3.19. Forcing of infinity and algebras of distributions of

binary semi-isolating formulas for strongly minimal

theories . . . . . . . . . . . . . . . . . . . . . . .
284

§ 3.20. Absorbing structures . . . . . . . . . . . . . . . .
290

§ 3.21. Structures of distributions of isolating formulas as

derivative structures: for acyclic graphs
. . . . .
295

References
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
304

Index of names
. . . . . . . . . . . . . . . . . . . . . . . . .
354

Index of terms . . . . . . . . . . . . . . . . . . . . . . . . . .
360

Index of symbols
. . . . . . . . . . . . . . . . . . . . . . . .
370

ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ

В настоящем издании устранены выявленные неточности,
несколько усовершенствован и расширен текст.
Автор благодарен коллегам за полезные замечания, способствовавшие 
улучшению содержания книги.

ПРЕДИСЛОВИЕ

Проблема классификации сч¨eтных моделей полных теорий
является одной из основных проблем современной теории моделей. 
Сама теория моделей, сформировавшаяся в самостоятельную 
область в 1950-х годах, находится на стыке математической 
логики и алгебры. Предмет е¨e изучения — синтаксические 
объекты (теории, представляющие описания реальных
объектов) и семантические объекты (алгебраические системы,
или структуры, отражающие взаимосвязь элементов реальных 
объектов), а также классификация синтаксических объектов 
по свойствам объектов семантических и наоборот. При
описании полных теорий (т. е. теорий с недополняемой непротиворечивой 
информацией в рамках
фиксированного языка) 
возможны существенно различные (неизоморфные) реализации 
этих теорий алгебраическими системами (моделями) При
этом число таких реализаций может быть различным в разных 
бесконечных мощностях (т. е. с разным бесконечным числом 
элементов) алгебраических систем. Так возникает функция 
спектра, отражающая число неизоморфных моделей данной 
теории в зависимости от мощности моделей, и одна из основных 
проблем теории моделей — проблема описания всех возможных 
спектральных функций как для класса всех теорий,
так и для различных существенных подклассов этого класса.
Как это ни удивительно, спектральная проблема решена
для больших (несчетных) мощностей в классе всех теорий.
Здесь основные достижения связаны с работами С. Шелаха
[56] и в окончательном виде представлены в работе Б. Харта,
Э. Хрушовского и М. Ласковского [256].
Для сч¨eтной (минимальной бесконечной) мощности ситуация 
оказалась значительно сложнее. Во-первых, до сих пор

ПРЕДИСЛОВИЕ
15

неизвестно, существуют ли теории с несч¨eтным, но не максимальным 
числом сч¨eтных моделей (проблема Воота). Во-вторых, 
построенные А. Эренфойхтом (см. [466]) первоначальные
примеры теорий с конечным, но большим единицы числом
сч¨eтных моделей (сейчас такие теории в его честь называются
эренфойхтовыми) долгое время оставались по существу единственными: 
все модификации сводились к надстройкам на бесконечные 
плотные линейно упорядоченные множества. В связи 
с последним обстоятельством и возникла проблема Лахла-
на о существовании других, не имеющих бесконечных линейных 
порядков эренфойхтовых теорий. В краткой формулировке 
проблема Лахлана звучит так: определить, существует ли
стабильная эренфойхтова теория.
Эта проблема была частично решена самим А. Лахланом
[325], опубликовавшим в 1973 году доказательство отсутствия
эренфойхтовых теорий в классе суперстабильных теорий, который 
является важным подклассом класса стабильных теорий.
Долгое время предполагалось, что это утверждение верно и для
стабильных теорий, и в литературе наряду с проблемой Лахла-
на называлось гипотезой Лахлана (см., например, [60, c. 202]).
Гипотеза Лахлана частично подтверждалась для многих подклассов 
класса стабильных теорий в работах Д. Ласкара [330],
С. Шелаха [56], А. Пилая [374, 378, 381, 383], Т. Г. Мустафи-
на [102], Ю. Заффе [399], А. Цубои [462], Э. Хрушовского [282],
А. А. Викентьева [3], Б. Кима [315], П. Тановича [449, 450]. Вместе 
с тем происходила наработка структурных свойств, которыми 
должен обладать контрпример, если таковой существует.
С этим связаны работы М. Г. Перетятькина [107, 108], М. Бен-
ды [197], Р. Вудроу [61, 475, 476], А. Пилая [375, 376], Б. Ома-
рова [103], А. Цубои [461], С. С. Гончарова, М. Пурмахдиана
[79], Б. Хервига [266] и автора. Решение проблемы, а именно
доказательство существования стабильной эренфойхтовой теории, 
стало возможно лишь после появления в 1988 году тонкой
конструкции, созданной Э. Хрушовским [281] и примен¨eнной
для решения многих теоретико-модельных проблем. Сейчас эта
известная конструкция называется генерической конструкцией 
Хрушовского и позволяет “собирать” требуемые алгебраические 
системы, исходя из конечных объектов с помощью амальгам.

ПРЕДИСЛОВИЕ

Другой важной составляющей стала созданная автором теория 
полигонометрий групп [27, 418, 419] обобщающая классические 
тригонометрии.
Класс
полигонометрий групп
оказался 
удобным и геометрически наглядным “полигоном”, позволившим 
реализовать многие структурные свойства стабильных 
эренфойхтовых теорий. Вместе с тем сейчас, когда стал
понятен общий механизм построения эренфойхтовых теорий,
явное описание неявно присутствующего в конструкции полигонометрического 
аппарата представляется избыточным, и поэтому 
как сама полигонометрическая теория, так и е¨e применения 
в книге не отражены.
Для построения стабильных эренфойхтовых теорий была
привлечена тонкая модификация конструкции Хрушовского,
предложенная Б. Хервигом [266] для реализации одного из основных 
структурных свойств — бесконечного веса. Вместе с тем
эта модификация в первоначальном виде оказалась недостаточной, 
поскольку конструкция Хрушовского–Хервига является 
семантической и не учитывает возможность появления
внешних связей по отношению к данному конечному объекту,
служащему “кирпичиком” общей конструкции. Для устранения
этого недостатка автором была развита теория синтаксических
генерических конструкций [130]. В основе синтаксического построения 
лежат не конечные объекты, а типы, т. е. описания
(возможно и внешние) конечных объектов, которые затем шаг
за шагом позволяют сформировать модели требуемых теорий.
Использование указанного выше аппарата позволило построить 
достаточно богатое семейство стабильных эренфойх-
товых теорий, а также решить ряд сопутствующих проблем,
включая проблему Гончарова–Миллара о существовании эрен-
фойхтовой теории, имеющей сч¨eтные, не почти однородные модели. 
Наличие широкого класса примеров теорий повлекло создание 
классификации сч¨eтных моделей полных теорий, о которой 
пойд¨eт речь в книге.
Первоначальная моя работа проходила во время учебы в Новосибирском

государственном
университете,
где
работали
и продолжают работать первоклассные специалисты по математической 
логике и алгебре. Появление Сибирской школы алгебры 
и логики, к которой я отношу и себя, стало возможным
с образованием в 1957 году Института математики в Новоси-