Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Основная коллекция
Артикул: 713423.02.99
Книга является второй частью монографии «Классификация счётных моделей полных теорий», состоящей из двух частей. В книге рассмотрены генерические эренфойхтовы теории и реализации предпорядков Рудин-Кейслера в этих теориях; решение проблемы Гончарова-Миллара о существовании эренфойхтовой теории, имеющей счётные, не почти однородные модели; стабильные генерические эренфойхтовы теории (решение проблемы Лахлана); гиперграфы простых моделей и распределения счётных моделей малых теорий, а также распределения счётных моделей теорий с континуальным числом типов. Для интересующихся математической логикой.
Судоплатов, С. В. Классификация счетных моделей полных теорий: в 2 ч. Ч.2 : монография / С. В. Судоплатов. - 2-е изд., доп. - Новосибирск : Изд-во НГТУ, 2018. - 452 с. - (Серия «Монографии НГТУ»). - ISBN 978-5-7782-3525-0. - Текст : электронный. - URL: https://znanium.com/catalog/product/1867811 (дата обращения: 28.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
 
 
 

 

 

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

 

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 
 
 

 

 
УДК 510.67 
         С892 
Рецензенты: 
член-корр. НАН Республики Казахстан, 
д-р физ.-мат. наук, проф. Б. С. Байжанов, 
д-р физ.-мат. наук, проф. Е. А. Палютин, 
д-р физ.-мат. наук, проф. А. Г. Пинус 
 
 
Судоплатов С. В. 
С892       Классификация счётных моделей полных теорий: монография в 2 ч. / 
С. В. Судоплатов.– 2-е изд., доп. – Новосибирск: Изд-во НГТУ, 2018. – 
(Серия «Монографии НГТУ») 
 
ISBN 978-5-7782-3523-6 
Ч.2. – 452 с. 
ISBN 978-5-7782-3525-0 
 
Книга является второй частью монографии «Классификация 
счётных моделей полных теорий», состоящей из двух частей. В книге 
рассмотрены генерические эренфойхтовы теории и реализации 
предпорядков Рудин–Кейслера в этих теориях; решение проблемы 
Гончарова–Миллара 
о 
существовании 
эренфойхтовой 
теории, 
имеющей счётные, не почти однородные модели; стабильные 
генерические эренфойхтовы теории (решение проблемы Лахлана); 
гиперграфы простых моделей и распределения счётных моделей 
малых теорий, а также распределения счётных моделей теорий с 
континуальным числом типов. 
Для интересующихся математической логикой. 
 
 
 
 
УДК 510.67 
 
 
ISBN 978-5-7782-3525-0 (Ч.2)                                   © Судоплатов С. В., 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 
Part 2. – 452 p. 
ISBN 978-5-7782-3525-0 
 
The book is the second part of the monograph “Classification of 
countable models of complete theories” consisting of two parts. In the 
book, generic Ehrenfeucht theories and realizations of Rudin–Keisler 
preorders are considered as well as a solution of Goncharov–Millar 
problem on the existence of Ehrenfeucht theories with countable models 
which are not almost homogeneous, stable Ehrenfeucht theories solving the 
Lachlan problem, hypergraphs of prime models, distributions of countable 
models of small theories, and distributions of countable models of theories 
with continuum many types. 
The book is intended for specialists interested in Mathematical Logic. 

 
 
УДК 510.67 
 
ISBN 978-5-7782-3525-0 (Part 2)                                   © Sudoplatov S. V., 2014, 2018 
ISBN 978-5-7782-3523-6                                                  © Novosibirsk State Technical 
University, 2014, 2018 

Оглавление

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

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

Глава 4.
Генерические эренфойхтовы теории и пред
порядки Рудин–Кейслера
. . . . . . . . . .
17

§ 4.1.
Генерические теории с несимметричными отно
шениями полуизолированности . . . . . . . . .
17

§ 4.2.
Генерические теории с неглавными властными

типами
. . . . . . . . . . . . . . . . . . . . . . .
50

§ 4.3.
Теории с тремя сч¨eтными моделями
. . . . . .
61

§ 4.4.
Реализации основных характеристик полных тео
рий с конечным числом сч¨eтных моделей . . .
65

§ 4.5.
Предпорядки Рудин–Кейслера в малых теориях
75

§ 4.6.
Разрозненные теории. Теорема Морли . . . . .
81

§ 4.7.
Теории с конечными предпорядками Рудин–Кей
слера
. . . . . . . . . . . . . . . . . . . . . . . .
85

§ 4.8.
Распределения сч¨eтных однородных моделей тео
рий с конечными предпорядками Рудин–Кейслера 92

§ 4.9.
Графы, получаемые факторизациями последо
вательностей по множествам словарных тож
деств
. . . . . . . . . . . . . . . . . . . . . . . .
96

§ 4.10. Эренфойхтовы теории со сч¨eтными, не почти

однородными моделями (решение проблемы Гон
чарова–Миллара) . . . . . . . . . . . . . . . . .
114

§ 4.11. Теории с неплотными структурами властных

орграфов и теории с властными типами, не име
ющие властных орграфов
. . . . . . . . . . . .
152

Глава 5.
Стабильные генерические эренфойхтовы

теории (решение проблемы Лахлана)
. .
159

§ 5.1.
Малые стабильные генерические графы

с бесконечным весом. Двудольные орграфы . .
159

§ 5.2.
Малые стабильные генерические графы

с бесконечным весом. Безразвилочные орграфы 181

§ 5.3.
Малые стабильные генерические графы

с бесконечным весом. Властные орграфы . . .
200

§ 5.4.
Об обогащениях властных орграфов . . . . . .
239

§ 5.5.
Описание особенностей генерической конструк
ции стабильных эренфойхтовых теорий. Сли
яния
Хрушовского
для
предикатов
и
их

оболочек
. . . . . . . . . . . . . . . . . . . . . .
244

§ 5.6.
Стабильные графовые расширения цветных

властных орграфов . . . . . . . . . . . . . . . .
251

§ 5.7.
Стабильные эренфойхтовы теории . . . . . . .
257

§ 5.8.
Реализации основных характеристик стабиль
ных эренфойхтовых теорий
. . . . . . . . . . .
273

Глава 6.
Гиперграфы простых моделей и распреде
ления сч¨eтных моделей малых теорий . .
280

§ 6.1.
Гиперграфы простых моделей . . . . . . . . . .
280

§ 6.2.
HPKB-гиперграфы и теорема о структуре типа 284

§ 6.3.
Графовые связи между типами . . . . . . . . .
291

§ 6.4.
Предельные модели . . . . . . . . . . . . . . . .
295

§ 6.5.
λ-модельные гиперграфы . . . . . . . . . . . . .
305

§ 6.6.
Распределения простых и предельных моделей

малых теорий
. . . . . . . . . . . . . . . . . . .
310

§ 6.7.
Несущественные совмещения малых теорий . .
319

§ 6.8.
О предельных моделях теорий с конечным

весом
. . . . . . . . . . . . . . . . . . . . . . . .
329

§ 6.9.
Некоторые примеры и операции с теориями,

имеющими ≤ ω сч¨eтных моделей . . . . . . . .
347

Глава 7.
Распределения сч¨eтных моделей теорий

с континуальным числом типов
. . . . . .
343

§ 7.1.
Примеры . . . . . . . . . . . . . . . . . . . . . .
344

§ 7.2.
Предпорядки Рудин–Кейслера . . . . . . . . . .
346

§ 7.3.
Предмодельные множества . . . . . . . . . . . .
355

§ 7.4.
Распределения сч¨eтных моделей теории по ≤RK
последовательностям . . . . . . . . . . . . . . .
357

§ 7.5.
Три класса сч¨eтных моделей . . . . . . . . . . .
360

§ 7.6.
Операторы, действующие на классе алгебраи
ческих систем
. . . . . . . . . . . . . . . . . . .
365

§ 7.7.
Распределения простых и предельных моделей

для конечных предпорядков Рудин–Кейслера .
371

§ 7.8.
Распределения простых и предельных моделей

для сч¨eтных предпорядков Рудин–Кейслера . .
375

§ 7.9.
Взаимосвязь классов P, L и NPL в теориях с

континуальным числом типов. Распределения

троек cm3(T) в классе Tc . . . . . . . . . . . . .
378

§ 7.10. Реализации предмодельных множеств . . . . .
381

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

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

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

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

Contents

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

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

Chapter 4.
Generic Ehrenfeucht theories and Rudin–

Keisler preorders
. . . . . . . . . . . . . . . .
17

§ 4.1.
Generic theories with non-symmetric relations of

semi-isolation . . . . . . . . . . . . . . . . . . . .
17

§ 4.2.
Generic theories with non-principal powerful types
50

§ 4.3.
Theories with three countable models
. . . . . .
61

§ 4.4.
Realizations for basic characteristics of complete

theories with finitely many countable models
. .
65

§ 4.5.
Rudin–Keisler preorders in small theories
. . . .
75

§ 4.6.
Scattered theories. Morley Theorem
. . . . . . .
81

§ 4.7.
Theories with finite Rudin–Keisler preorders . . .
85

§ 4.8.
Distributions of countable homogeneous models of

theories with finite Rudin–Keisler preorders . . .
92

§ 4.9.
Graphs corresponding to quotients of sequences

by sets of word identities . . . . . . . . . . . . . .
96

§ 4.10. Ehrenfeucht theories with countable models which

are not non-almost homogeneous (a solution of

Goncharov–Millar problem) . . . . . . . . . . . .
114

§ 4.11. Theories with non-dense structures of powerful

digraphs, and theories with powerful types and

without powerful digraphs . . . . . . . . . . . . .
152

Chapter 5. Stable generic Ehrenfeucht theories (a solution

of the Lachlan problem) . . . . . . . . . . . .
159

§ 5.1.
Small stable generic graphs with infinite weight.

Bipartite digraphs
. . . . . . . . . . . . . . . . .
159

§ 5.2.
Small stable generic graphs with infinite weight.

Digraphs without furcations . . . . . . . . . . . .
181

§ 5.3.
Small stable generic graphs with infinite weight.

Powerful digraphs
. . . . . . . . . . . . . . . . .
200

§ 5.4.
On expansions of powerful digraphs . . . . . . . .
239

§ 5.5.
Description of features for generic construction

of stable Ehrenfeucht theories. Hrushovski fusions

for predicates and their envelopes . . . . . . . . .
244

§ 5.6.
Stable
graph
extensions
of
colored
powerful

digraphs . . . . . . . . . . . . . . . . . . . . . . .
251

§ 5.7.
Stable Ehrenfeucht theories . . . . . . . . . . . .
257

§ 5.8.
Realizations for basic characteristics of stable

Ehrenfeucht theories . . . . . . . . . . . . . . . .
273

Chapter 6. Hypergraphs of prime models and distributions

of countable models of small theories . . . .
280

§ 6.1.
Hypergraphs of prime models . . . . . . . . . . .
280

§ 6.2.
HPKB-hypergraphs and theorem on structure of

type . . . . . . . . . . . . . . . . . . . . . . . . .
284

§ 6.3.
Graph links between types . . . . . . . . . . . . .
291

§ 6.4.
Limit models . . . . . . . . . . . . . . . . . . . .
295

§ 6.5.
λ-model hypergraphs . . . . . . . . . . . . . . . .
305

§ 6.6.
Distributions of prime and limit models of small

theories . . . . . . . . . . . . . . . . . . . . . . .
310

§ 6.7.
Inessential combinations of small theories
. . . .
319

§ 6.8.
On limit models of theories with finite weight . .
329

§ 6.9.
Some examples and operations for theories with

≤ ω countable models
. . . . . . . . . . . . . . .
341

Chapter 7. Distributions of countable models of theories

with continuum many types . . . . . . . . . .
343

§ 7.1.
Examples . . . . . . . . . . . . . . . . . . . . . .
344

§ 7.2.
Rudin–Keisler preorders . . . . . . . . . . . . . .
346

§ 7.3.
Premodel sets . . . . . . . . . . . . . . . . . . . .
355

§ 7.4.
Distributions for countable models of a theory by

≤RK-sequences . . . . . . . . . . . . . . . . . . .
357

§ 7.5.
Three classes of countable models . . . . . . . . .
360

§ 7.6.
Operators acting on a class of structures . . . . .
365

§ 7.7.
Distributions of prime and limit models for finite

Rudin–Keisler preorders . . . . . . . . . . . . . .
371

§ 7.8.
Distributions of prime and limit models for count
able Rudin–Keisler preorders
. . . . . . . . . . .
375

§ 7.9.
Interrelations of classes P, L, and NPL in theories

with continuum many types. Distributions of triples

cm3(T) in the class Tc . . . . . . . . . . . . . . .
378

§ 7.10. Realizations of premodel sets . . . . . . . . . . .
381

References
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
389

Index of names
. . . . . . . . . . . . . . . . . . . . . . . . .
439

Index of terms . . . . . . . . . . . . . . . . . . . . . . . . . .
440

Index of symbols
. . . . . . . . . . . . . . . . . . . . . . . .
446

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

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

ПРЕДИСЛОВИЕ

Эта книга — продолжение первой части “Классификации
сч¨eтных моделей полных теорий”. Нумерация глав первой и
второй частей сквозная. Основной текст (главы 4–7) включает
темы, продолжающие темы глав 1–3 первого тома. Библиография второй части включает в себя библиографию первой части
и для удобства чтения сохранена нумерация ссылок.
Опишем краткое содержание глав настоящей книги.
В главе 4 на основе синтаксической генерической конструкции и несущественной упорядоченной раскраски бесконтурного орграфа строятся пример и модификации нестабильного
генерического властного орграфа, имеющего неограниченные
длины кратчайших маршрутов и допускающего обогащение до
структуры неглавного властного типа (§ 4.1). Затем на основе
генерического властного орграфа строятся теории с властными типами (§ 4.2), генерические эренфойхтовы теории с тремя
сч¨eтными моделями (§ 4.3), а также приводится модификация
генерической конструкции, позволяющая реализовать всевозможные характеристики эренфойхтовых теорий по предпорядкам Рудин–Кейслера и функциям распределения числа предельных моделей (§ 4.4). В § 4.5 приводится описание предпорядков Рудин–Кейслера в малых теориях. В § 4.6 доказывается, что теории, имеющие менее континуума сч¨eтных моделей,
являются разбросанными. Из этого свойства следует теорема
Морли [358] о возможных значениях числа сч¨eтных моделей
теории. В § 4.7 основные характеристики эренфойхтовых теорий распространяются на произвольные малые теории с конечными предпорядками Рудин–Кейслера по модулю гипотезы
Воота. В § 4.8 приводится описание распределений однородных
моделей малых теорий с конечными предпорядками Рудин–

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

Кейслера. В § 4.9, написанном на основе работ И. В. Шулепова
[142, 143, 144], излагаются результаты о существовании некоторых графов, получаемых факторизациями последовательностей по множествам словарных тождеств. В § 4.10 на основе факторизаций символьных последовательностей да¨eтся положительное решение проблемы Гончарова–Миллара [80, 250,
253, 352, 354] о существовании эренфойхтовых теорий со сч¨eтными, не почти однородными моделями. В § 4.11 приводятся
модификации генерической конструкции эренфойхтовых теорий, основанные на неплотных структурах властных орграфов,
а также на структурах властных типов, не имеющих властных
орграфов. Основные результаты главы 4 представлены в работах [125, 129, 140, 422, 424, 425, 442].
Ряд параграфов из главы 4 написан на основе первой главы
докторской диссертации автора [23].
В главе 5 на основе генерической конструкции Хрушовского–Хервига c предранговыми функциями в три этапа строятся
примеры стабильных генерических властных орграфов. Сначала генерическая конструкция переносится на двудольные орграфы с цветными дугами (§ 5.1), затем, с двудольных цветных
орграфов, — на безразвилочные орграфы (§ 5.2), и, наконец,
с безразвилочных — на властные орграфы (§ 5.3). В § 5.4 объясняется недостаток упрощ¨eнной конструкции эренфойхтовых
теорий, которая в силу е¨e особенности помимо нестабильности
структуры властного орграфа порождает формульную нестабильность через т´иповую нестабильность. В § 5.5 описываются особенности генерической конструкции, позволяющей строить стабильные эренфойхтовы теории. В §§ 5.6–5.9 на основе
стабильных генерических властных орграфов с помощью слияний Хрушовского генерических конструкций властных орграфов с генерическими конструкциями сч¨eтного семейства неорграфов строятся искомые стабильные эренфойхтовы теории
со всевозможными предпорядками Рудин–Кейслера и функциями распределения числа предельных моделей. Тем самым,
в частности, устанавливается существование стабильных эренфойхтовых теорий, что решает проблему Лахлана. Результаты
главы 5 изложены в работах [126, 128, 131, 138, 139, 423].
В главе 6 рассматривается семейство гиперграфов
простых
моделей
произвольной
малой
теории
и
представ
ПРЕДИСЛОВИЕ

ляется
механизм
структурного
описания
моделей теории
по этим семействам. Тем самым обосновывается, в частности,
ключевая роль теоретико-графовых конструкций в построении
приводимых в книге примеров эренфойхтовых теорий. Кроме того, обобщаются результаты предыдущих глав на класс
всех малых теорий Результаты главы 6 содержатся в работах
[133, 134, 135, 136, 137].
В главе 7 приведена классификация сч¨eтных моделей полных теорий с континуальным числом типов, полученная совместно с Р. А. Попковым [111, 389]. В § 7.1 определяются некоторые основные примеры теорий с континуальным числом типов. В § 7.2 определяются предпорядки Рудин–Кейслера, формулируются некоторые основные свойства и примеры, относящиеся к этим предпорядкам. Понятие предмодельного множества, содержащее основные свойства предпорядков Рудин–
Кейслера для типов представлено в § 7.3. В § 7.4 приводится
критерий того, что последовательность Рудин–Кейслера для
типов образует сч¨eтную модель, и определяются распределения сч¨eтных моделей относительно этих последовательностей.
В § 7.5 определяются три класса: P, L и NPL, простых над
кортежами, предельных и остальных сч¨eтных моделей соответственно. Описываются возможности для числа моделей в
этих классах, предполагая континуум-гипотезу и малость теории. Для класса Tc сч¨eтных теорий с континуальным числом
типов доказывается критерий того, что каждая сч¨eтная модель
проста над некоторым кортежем или предельна. Приводятся
некоторые связи между числом сч¨eтных моделей в классах P, L
и NPL. В § 7.6 определяются операторы, используемые для реализаций возможных распределений сч¨eтных моделей. В §§ 7.7,
7.8 описываются распределения простых и предельных моделей
для конечных и сч¨eтных предпорядков Рудин–Кейслера. В § 7.9
описываются связи между классами P, L и NPL, а также возможные значения для числа сч¨eтных моделей в этих классах,
в предположении континуум-гипотезы. Некоторые реализации
предмодельных множеств приведены в § 7.10.
Основными классификационными теоремами являются следующие: 1.1.4.1, 4.4.0.1, 4.7.0.1, 4.7.0.3, 4.8.0.1, 4.8.0.4, 5.8.0.1,
6.6.0.10, 6.6.0.11, 7.7.0.5, 7.8.0.1, 7.8.0.2, 7.9.0.1, 7.9.0.2.