О сводимостях размеченных частично упорядоченных множеств и лесов тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат наук Жуков, Антон Владимирович

• Жуков, Антон Владимирович
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Жуков, Антон Владимирович

Оглавление

Введение

1 Предварительные сведения

1.1 Размеченные чумы и их разновидности

1.1.1 Предпорядки и частичные порядки

1.1.2 Фундированность и хорошие предпорядки

1.1.3 Высота чумов и их элементов

1.1.4 Классы размеченных чумов

1.1.5 Основные операции над /с-чумами

1.2 Морфизмы и сводимости размеченных чумов

1.2.1 Определение г-морфизма для г € {0,1, 2}

1.2.2 Сводимости и эквивалентности

1.2.3 Технические свойства сводимостей

1.3 Факторструктуры /с-чумов

1.3.1 Определения факторструктур

1.3.2 Полурешетки с дискретными замыканиями

1.3.3 Простейшие 2-чумы

2 Размеченные частично-упорядоченные множества

2.1 Контрпримеры к wqo

2.2 Универсальность

2.3 Вложение 2-сводимости в 0- и 1-сводимость на конечных к-чумах и к-лесах

2.4 Решеточность и дистрибутивность

2.5 Верхние и нижние границы 1-сводимости

3 Размеченные леса

3.1 Общее описание 1- и 2-сводимости на к-лесах

3.2 Алгебраические свойства 0-сводимости

3.2.1 О семействах 0-обобгценных /с-деревьев

3.2.2 Штрих-функция ' (в структуре к-лесов)

3.2.3 Штрих-функция Л (в структуре /с-деревьев)

3.3 Определимость в структурах 0-сводимости

3.3.1 Определимость элементов

3.3.2 Атомность и автоморфизмы

3.3.3 Определимость операций замыкания

3.4 Неразрешимость в структурах 1-й 2-сводимости

3.4.1 Схема интерпретации

3.4.2 Доказательство неразрешимости

4 Дополнительные вопросы

4.1 Расщепление произвольных fc-чумов

4.2 Сводимости Вайрауха и топологическая интерпретация

4.3 Ретракты и минимальные fc-чумы

4.3.1 Эндоморфизмы и автоморфизмы fc-чумов

4.3.2 Операция стягивания

4.3.3 г-ретракты в широком и узком смысле

4.3.4 Минимальные fc-чумы

4.4 Спектр fc-цепей

Заключение

Приложение. Программная реализация размеченных лесов

Список литературы

Обозначения

Предметный указатель

Список иллюстраций

Введение диссертации (часть автореферата) на тему «О сводимостях размеченных частично упорядоченных множеств и лесов»

Введение

Актуальность темы исследования

Частичные порядки - бинарные рефлексивные транзитивные антисимметричные отношения, элементы которых в общем случае могут быть несравнимы, - являются широко распространенными математическими объектами и встречаются (часто в виде диаграмм Хассе) как в естественных, так и в гуманитарных науках. К примерам частичных порядков можно отнести представления о социальных структурах в обществознании и отношение причинности в физике. Мировоззренческое и дидактическое значение понятия частичного порядка вытекает из возможной несравнимости как естественного состояния различных сущностей, а также первичности операции сравнения по отношению к равенству. Отсюда следует целесообразность изучения частичного порядка в школьной математике, в том числе на интуитивном уровне в начальной школе [6]. Можно предположить, что понятие частичного порядка способно играть не меньшую мировоззренческую и научную роль, чем понятие линейного порядка (например, в психологии, где распространены линейные шкалы типа К^).

Термин «частично упорядоченное множество» в тексте диссертации сокращается до «чум» и для удобства склоняется по падежам. В самой общей формулировке, под лесом понимается (фундированный) чум, в котором любой верхний конус является линейно упорядоченным множеством с наибольшим элементом. Дерево - это лес с наибольшим элементом (называемым корнем дерева). Разновидности чумов - леса и деревья - широко применяются в информатике для представления структур данных (например, многоуровневых списков и файловых систем).

Чум называется размеченным, если каждому его элементу поставлена в соответствие метка, в данной работе - натуральное число из фиксированного множества к = {0,... , к}, и в этом случае чум называется (размеченным) /с-чумом. Естественным образом определяются подклассы размеченных чумов: размеченные решетки, леса и деревья. В теоретической информатике размеченные чумы использовались как модели параллельных процессов [40]. Как известно, деревья (размеченные или с размеченными листьями) представляют разнообразные структуры данных (списки, файловые системы и т.д.). Размеченные чумы являются взвешенными ориентированными графами (без циклов, кроме петель), и в этом смысле тематика диссертации включается в теорию графов, однако результаты и методы диссертации относятся преимущественно к алгебре (теории порядков) и математической логике. Кроме конечных /с-чумов [26], к-лесов и /с-деревьев [8], представляют интерес так называемые счетные к-леса и к-деревья, все цепи которых конечны [9; 43]. В статье [33] рассматривались также счетные /с-чумы (без ограничения на длину цепей).

В диссертации рассматриваются следующие три сводимости на к-чумах. Для г е {0,1,2} г-сводимость (г-предпорядок) означает существование монотонного отображения между к-

чумами, называемого г-морфизмом, со следующими свойствами: 0-морфизм сохраняет метки элементов, 1-морфизм отображает элементы с неравными метками в элементы с неравными метками, а 2-морфизм отображает сравнимые элементы с неравными метками в элементы с неравными метками. Отношения <о, и ® рекурсивно определенных размеченных деревьях были предложены П. Гертлингом [17; 18]. Эти отношения можно считать разновидностями графовых гомоморфизмов, а они составляют актуальное направление в теории графов и ее приложениях [16]. Сводимости <о, <1 и <2 на к-лесах вычислимы за полиномиальное время [19], но сводимость <о на к-чумах является КР-полной [33], а КР-полнота сводимостей <1 и <2 на к-чумах следует из доказательства их универсальности в [59].

Для каждой г-сводимости, где г Е {0,1,2}, стандартным образом определяются %-эквивалентность и факторструктуры с индуцированной г-сводимостью <г размеченных конечных чумов, конечных и счетных лесов, конечных и счетных деревьев - соответственно VI, Тгк, Тгк} Тк и Тк. Диссертация посвящена в основном изучению алгебраических и логических свойств этих структур. Представление о сложности структуры (}~гк) при г = 0, к = 3 дает рис. 1. На нем треугольники изображают классы О-эквивалентности 3-деревьев, а круги - классы эквивалентности собственных (т.е. не О-эквивалентных никаким 3-деревьям) 3-лесов. На рис. 2 и 3 компактно показаны уровни с 1-го по 8-й структур (Т^, <о), (^з, <1) и (^з2, <2) (под п-м уровнем понимается множество элементов высоты п). Этот рисунок создан автоматически на основе программы, вычисляющей уровни структуры Программ-

ная реализация размеченных лесов относительно 0-сводимости обсуждается в приложении (с. 117).

В таблице 1 показаны предположительные мощности первых 17 уровней в структуре (^3°, <0), также вычисленные программно.

п 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

П{п) 1 3 3 7 9 21 32 60 99 175 306 543 984 1782 3294 6089 11403

П(п) 1 1 1 2 2 5 7 12 18 33 54 96 170 307 559 1034 1920

П(п) 1 1 1 1 2 3 4 6 11 17 28 45 73 118 193 313 510

Таблица 1. Мощности первых уровней структур (Т®, <о), (^3, <1) и <2)

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

Первоначальная мотивация для изучения сводимостей на к-лесах происходит из вычислимого анализа и топологии. К. Вайраух [46; 47] ввел в рассмотрение 2-сводимость <2 на функциях между канторовскими топологическими пространствами или между канторов-ским и дискретным пространством (над одним алфавитом). М. Д. Хирш [21] независимо предложил близкое по смыслу определение сводимости алгоритмических проблем (в смысле С. Смейла), при котором решения сводимых проблем являются 2-сводимыми функциями (на произвольных топологических пространствах). В контексте исследования степеней разрывности функций П. Гертлинг предложил еще две сводимости <о и <1 функций на произвольных топологических пространствах [18]. Частным случаем сводимости <о (для функций с двухэлементной областью определения) по сути является сводимость Вэджа, один из

Рис. 1. Начальный сегмент структуры , уровни с 0-го по 5-й

8 ййяии»лплплял?л1лпл11л?л1лплклалй«лзл1лалйлпл1

шп

7 шшлшлшлшлзлхлшлшййнянп

^шт^шш^зшап^шга^ш!^!!;!!^!]!]0!!

6 л^ллдшшшш^шшшшшшшшшшшшшш^шш0!0] з шш'йгшпммп'йгшпп0!:

оо*

4 ншттт

3 ШШ'

сю о-* о»

1

2

о о

Рис. 2. Уровни структуры (.7Г7. <о) с 1-го по 8-й, вычисленные и нарисованные программно. Числа означают номера уровней (количество элементов на уровнях указано в таблице 1). Цвета (белый, серый и черный) показывают метки (0, 1 и 2). Детали вычислений см. в Приложении на с. 117

основных объектов исследования современной дескриптивной теории множеств, поскольку сводимость множеств по Вэджу означает сводимость <о их характеристических функций.

Как известно, /с-разбиением множества (или топологического пространства) X называется функция /: X —у к, которая отождествляется с кортежем (А0,... , Ак_-у), где А^ = /-1(г). Отсюда определения сводимостей <0, <1 и <2 функций естественным образом распространяются на разбиения топологических пространств. П. Гертлинг исследовал начальный сегмент структуры /с-разбиений бэровского пространства (В) = шш относительно всех трех сводимостей [18]. Оказалось, что для каждого г Е {0,1,2} структура <г-степеней этого начального сегмента изоморфна факторструктуре {}7%к \ {{0}},<г) размеченных лесов относительно г-сводимости (без пустого леса). А именно, П. Гертлинг определил сюръективную функцию, которая любое /с-разбиение / из данного начального сегмента отображает в конечный к-лес £>(/) так, что / <г д тогда и только тогда, когда £>(/) <г В(д). В. Л. Селиванов распространил этот результат для О-сводимости на более широкий начальный сегмент [44].

Другая область применения О-сводимости размеченных чумов и лесов (а также других подклассов чумов) относится к булевой иерархии разбиений. Пусть М - множество, Р(М) - класс всех подмножеств множества М. Базой С, С Р(М) называется класс подмножеств, замкнутый относительно операций и,П и содержащий множества 0, М [8]. Булева иерархия (над С) ВН(С) - известная классификация элементов булевой алгебры, порожденной классом С в классе Р(М). К. Вагнер и С. Косуб предложили естественное обобщение булевой иерархии для разбиений [25; 26]. По любому к-чуму (Р, с) определяется некоторый класс С(Р, с) /с-разбиений множества М, далее иерархии разбиений над С определяются по классам чумов:

• по классу /с-решеток - «обычная» булева иерархия /с-разбиений

ВНк(С) = {С(Р,с)\(Р,с)еСк}-

• по классу /с-чумов - так называемая расширенная булева иерархия /с-разбиений

11ВНк(£) = {£(Р,с)\(Р,с) еГк}-,

• по классу к-лесов - РВНк(С) = {С(Р, с)\(Р, с) Е Тк}\

• по классу /с-деревьев - ТВНк(С) = {С(Р, с)\(Р, с) Е 71}■

Булевы иерархии разбиений обобщают классическую разностную иерархию Хаусдорфа и ее варианты в теории вычислений, включая иерархию Ершова. В. Л. Селивановым установлено, что в случае так называемых редуцируемых баз эти иерархии разбиений обладают некоторыми хорошими свойствами. Многие из известных множеств в теории вычислимости являются такими базами [8]. Вычислимые варианты сводимостей играют заметную роль в вычислимом анализе, где используются для классификации алгоритмических задач по степеням невычислимости (аналогично классической теории степеней неразрешимости).

Э. Летонен и Л. Квуида в статье [33] построили изоморфное вложение структуры гомоморфизма ориентированных графов (без петель) в структуру О-сводимости размеченных чумов (причем оказалось достаточно только чумов высоты 2, т.е. чумов с максимальными цепями длины 2). Этот результат также показывает тесную связь между тематикой диссертации и теорией графов. Известно, что структура ориентированных графов относительно

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

Следующую связь 0-сводимости с алгеброй клонов заметил Э. Летонен в статье [36]. Рассмотрим клон М< всех монотонных функций произвольной местности на фиксированном чуме (Д <) и сводимость функций на А: / 9, если и только если / = д(Ъ, 1,... , Нт) для некоторых ,1гт £ М<. Тогда структура функций на А относительно вкла-

дывается в структуру А-размеченных чумов относительно 0-сводимости посредством отображения / I—Р(А, /) = Р((Ап, <'), /), где п - местность функции /, а частичный порядок <' на декартовой степени Ап определяется из < покомпонентно. Иными словами, / 9 тогда и только тогда, когда Р(А, /) <о Р(А,д).

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

Степень разработанности темы

Тематика диссертации является относительно новым направлением на стыке теоретической информатики, математической логики и алгебры. Первые работы по данной тематике были опубликованы в начале 90-х годов прошлого века. Три сводимости на размеченных деревьях и лесах были введены П. Гертлингом [17; 18], а 2-сводимость в топологическом контексте была впервые рассмотрена К. Вайраухом [46; 47] и независимо М. Д. Хиршем [21]. Среди данных трех сводимостей наиболее известна 0-сводимость (в литературе называемая также гомоморфным или /¿-предпорядком). В различных контекстах она изучалась рядом специалистов в России и зарубежом: П. Гертлингом, К. Вагнером, С. Косубом, В. Л. Селивановым, О. В. Кудиновым, Э. Летоненом и Л. Квуидой.

Цели и задачи исследования

Цель исследования: установить новые свойства структур 0—, 1-й 2-сводимости размеченных частично упорядоченных множеств, лесов и их подклассов, а также выявить сходства и различия между данными структурами.

Задачи исследования:

• Построить функцию, вычисляющую предшественников неразложимых элементов в структурах 0-сводимости размеченных счетных лесов.

• Исследовать определимость элементов и операций замыкания (добавления корня) в структурах 0-сводимости размеченных счетных лесов.

• Исследовать вопросы разрешимости элементарных теорий изучаемых структур.

• Проверить универсальность (вложимость любого счетного частичного порядка) для структур 1- и 2-сводимости размеченных частично упорядоченных множеств.

• Исследовать структурные свойства и взаимосвязи 0-, 1-й 2-сводимости на размеченных частично упорядоченных множествах и лесах, по возможности распространить результаты, полученные для размеченных лесов, на размеченные деревья и деревья с фиксированной корневой меткой.

Научная новизна

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

Теоретическая и практическая значимость работы

Работа носит теоретический характер. Результаты могут найти применение в дальнейших исследованиях по тематике диссертации и в приложениях данной тематики. Материал диссертации также может быть использован при проведении спецкурсов для студентов и аспирантов.

Методология и методы исследования

В работе применяются как алгебраические и комбинаторные, так и логические методы. Широкое применение для построения алгебраических объектов, операций и логических формул нашли различные виды индукции.

В первой главе ключевую роль в определениях изучаемых объектов играет введение алгебраических структур на классах эквивалентности (операции факторизации и индуцирования). Материал второй главы изложен преимущественно в алгебраическом и теоретико-графовом контексте. В третьей главе широко применяются методы математической логики. Структуры к-лесов и /с-деревьев относительно 1- и 2-сводимости описаны на основе понятия хорошего предпорядка ('«^о) и теоремы Крускала [9]. В доказательстве наследственной неразрешимости в структурах лесов и деревьев относительно 1- и 2-сводимости ключевую роль играет известный результат Ю. Л. Ершова, И. А. Лаврова, А. Д. Тайманова и М. А. Тайцлина [2], метод применения которого к структурам 0-сводимости разработан В. Л. Селивановым и О. В. Кудиновым [31]. В четвертой главе к размеченным чумам применяются некоторые алгебраические и топологические методы. Для иллюстративных целей и для проверки некоторых фактов разработан программный код, который для 0-сводимости обсуждается в приложении.

Положения, выносимые на защиту

1. Построена функция, вычисляющая предшественников неразложимых элементов в структурах О-сводимости размеченных счетных лесов и деревьев с фиксированной корневой меткой [49; 52; 54].

2. Посредством этой функции доказана определимость в языке ЬШ1Ш каждого элемента факторструктур О-сводимости размеченных счетных лесов, деревьев и деревьев с фиксированной корневой меткой, во всех трех случаях с минимальными ненаименьшими элементами в качестве параметров; как следствие, описаны группы автоморфизмов этих факторструктур [49; 54].

3. Доказана определимость в языке первого порядка операций замыкания (добавления корня) в факторструктурах О-сводимости размеченных счетных и конечных лесов [51].

4. Доказана наследственная неразрешимость факторструктур 1- и 2-сводимости размеченных счетных лесов [50; 55; 56].

Степень достоверности и апробация результатов

Результаты работы докладывались на нескольких российских и иностранных конференциях:

• Международная научная студенческая конференция, Новосибирск, Россия, 2008 г.;

• Topological and Game-Theoretic Aspects of Infinite Computations, Дагштуль, Германия, 2008 г.;

• Мальцевские чтения, Новосибирск, Россия, 2009 г.;

• Workshop on Logical Approaches to Barriers in Computing and Complexity, Грайфсвальд, Германия, 2010 г.;

• Computability in Europe 2010: Programs, Proofs, Processes, Понта-Делгада, Португалия, 2010 г.;

• Всероссийская научная школа-конференция с международным участием «Информатика и информационные технологии в образовании: теория, приложения, дидактика», Новосибирск, 2012 г.

Кроме того, по результатам работы автором были сделаны доклады на семинарах «Автоматы и сложность вычислений» (Институт систем информатики СО РАН) и «Конструктивные модели» (Институт математики СО РАН) в Новосибирске.

Публикации автора

В диссертацию вошли результаты 11 публикаций [49]- [59], из них 3 публикации в изданиях, относящихся к перечню ВАК, и 5 совместных публикаций.

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения, приложения, списка литературы, списка обозначений, предметного указателя и списка иллюстраций. Объем диссертации составляет 138 страниц. Диссертация содержит 19 иллюстраций. Список литературы включает 59 наименований.

Благодарности

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

Глава 1 Предварительные сведения

В данной диссертационной работе употребляется обычная алгебраическая терминология, которая широко распространена в литературе (см. напр. [1; 13]), применяются также некоторые понятия из теории графов и теории категорий. Большинство специфичных для предметной области диссертации русскоязычных терминов определяется в статьях [8] и [9]. Повсюду в диссертации, если не оговорено противное, термин «счетный» означает «конечный или равномогцный множеству натуральных чисел», иногда добавляется пояснение «(не более чем) счетный». Запись /: С А —> В обозначает частичную функцию / с областью определения сЬт(/) С А и областью значений гаг^е(/) С В. Для области определения и области значений применяются также компактные альтернативные обозначения Ф(/) = с1от(/) и £(/) = гаг^е(/). Как обычно, всюду определенная функция с с1от(/) = А обозначается как ¡'.А —В. (Частичная) функция / отождествляется с ее графиком {(ж,у) € с1от(/) х га^е(д) | /(ж) = у}. В частности, включение функций / С д означает, что с1от(/) С сЬэт^) и /(ж) = д(х) для любого ж & с1от(/). Остальные общематематические обозначения в тексте диссертации традиционны. Символ -<=>• или означает равносильность в метаязыке, т.е. сокращение фразы «тогда и только тогда, когда». Знак □ указывает на конец доказательства.

1.1 Размеченные чумы и их разновидности

1.1.1 Предпорядки и частичные порядки

Предпорядком (или квазипорядком) называется бинарное рефлексивное транзитивное отношение. Антисимметричный предпорядок является частичным порядком. Символ <, в том числе с индексами, используется в тексте диссертации для обозначения предпорядков и частичных порядков на различных классах и множествах (определяемых по контексту). Числовой нижний индекс у символа < в диссертации может обозначать только номер сводимости и принимать значения только 0, 1 или 2, т.е. в обозначении г-сводимости будет предполагаться, что г € {0,1,2} (см. определение 1.6).

Как обычно, для произвольного предпорядка < символом > обозначается обратное отношение: х > у у < х, а символом < - строгое отношение: х < у х < у Л у ^ х. Элементы хну называются сравнимыми (относительно <), если х < у V у < :г; в противном случае они называются несравнимыми, обозначение х || у. Через С1 или < будем обозначать

отношение непосредственного следования или покрытия, определяемое предпорядком <:

х <1 у ^ х <у ^ х < у /\ < г < у).

Если у покрывает х, т.е. х С1 у, то элемент х называется непосредственным предшественником элемента у, а у - непосредственным последователем элемента х. Множество всех непосредственных предшественников элемента х обозначим через х\.. Элементы х и у называются соседними (относительно предпорядка <), если х С1 у V у С1 х.

Множество Р вместе с заданным на нем частичным порядком (предпорядком) < называется частично упорядоченным (соответственно, предупорядоченным) и обозначается (Р; <). Термин «частично упорядоченное множество» будем сокращать до «чум» (как это общепринято в литературе) и для удобства склонять по падежам (как и производные термины, например «подчум» и «факторчум»). Чумы часто отождествляются в литературе со своими частичными порядками, поскольку, в силу рефлексивности частичного порядка и определения отношения как подмножества декартова квадрата, соответствующее множество однозначно восстанавливается по своему частичному порядку (то же самое верно и для предпо-рядков). Для сокращения обозначений предпорядок или частичный порядок на множествах часто не будет указываться в явном виде, а именно обозначение вида (Р; <) будем сокращать до Р, если отношение < ясно из контекста. Чум (0; 0) называется пустым и обозначается символом 0 (символ 0 будет обозначать пустое множество без «структуры» на нем, в частности пустое отношение и отображение). Чум называется цепью (или линейно упорядоченным множеством), если все его элементы попарно сравнимы, и антицепью, если его неравные элементы попарно несравнимы. Цепь и антицепь являются крайними случаями частичного порядка на данном множестве, в которых он соответственно максимальный и наименьший по включению.

Любое подмножество <5 чума (Р; <) можно рассматривать как чум относительно индуцированного частичного порядка, обозначаемого как <, при этом (<5; <) называется подчу-мом чума (Р; <). Распространенные примеры подчумов: верхний конус х = {у е\ х < у}, нижний конус х = {уеР\у< ж}, замкнут ый интервал (отрезок) [х,у] = {г е Р \ х < г < у}, от,крыт,ый и,нт,ервал, (ж, у) = {г е Р \ х < г < у}, а также цепи и антицепи в Р.

Максимальная цепь не включается ни в какую отличную от нее цепь. По принципу максимума Хаусдорфа, эквивалентному аксиоме выбора и лемме Цорна, всякая цепь в чуме содержится в некоторой максимальной цепи. В частности, в любом чуме существует максимальная цепь. Если в цепи есть наименьший элемент х и наибольший элемент у, то назовем ее [ж, у]-цепью или цепью от ж до у. В конечной максимальной [ж, у]-цепи длины п из элементов {ж = Жо,... , жга_1 = у каждый следующий элемент покрывает предыдущий: Жо С1 • • • С1 хп-\. Длиной, конечной цепи назовем количество ее элементов (иногда в литературе длина цепи полагается на 1 меньшей количества элементов, например в [1, с. 17]).

Любой чум (Р; <) (в особенности, конечный) можно рассматривать как граф или, точнее, орграф (ориентированный граф) С(У,А) с множеством вершин (или узлов) V = Р и множеством дуг (или ориентированных ребер) А =<= {(х,у) Е Р2 \ х < у}. Орграф С(Р, <) чума (Р; <) далее будет обозначаться так же, как сам чум Р. В силу транзитивности и ан-

тисимметричности отношения <, такой орграф не содержит циклов, кроме петель, т.е. дуг вида (ж, ж). Тем самым терминология теории графов естественным образом распространяется на чумы. К примеру, элементы чумов можно называть вершинами или узлами. Если в чуме (Р; <) нет бесконечных цепей, то отношение < является транзитивным замыканием отношения покрытия <. Поэтому на рисунках чумов в виде графов (диаграммах Хассе) линиями обычно соединяются только соседние вершины. Граф (Р; <) для чума (Р; <) без бесконечных цепей назовем графом Хассе этого чума. Именно графы Хассе конечных (или фрагментов бесконечных) чумов обычно изображаются на диаграммах Хассе.

Как известно, в теории графов основополагающую роль играет понятие пути. (Простым) пут,ем длины п (из вершины у в вершину ио) в орграфе С(У, А) называют последовательность чередующихся вершин и дуг у = Уо,ао,У\,а\,У2, ■ ■ ■, уп-1, 1,уп = га, в которой = (щ, ^¿+1) € V, т.е. а,г - дуга между вершинами у г и у^ \ для каждого г от 0 до п — 1, и все вершины у г попарно различны. Это традиционное определение, по-видимому, сложилось из визуального представления графов, и на самом деле путь задается последовательностью своих вершин, т.е. путь можно определить как последовательность попарно различных вершин Уо, У\,... , уп, в которой (Уг,Уг-\-1) Е V [16, с. 4]. Поэтому путь в чуме будем считать синонимом цепи. Но длина конечного пути на единицу меньше длины соответствующей цепи. В отличие от пути, в полупути не важно направление дуг, т.е. полупуть (из у в ги) в чуме - это последовательность вершин V = Уо, У\,... , уп = уз такая, что Уг и сравнимы в этом чуме для каждого г от 0 до п — 1.

Вершины х,у е Р слабо связаны, если в Р существует полупуть из ж в у. Отношение сильной связанности хну, которое означает существование путей из х в у и из у в х, в любом чуме тривиально, а именно совпадает с отношением равенства. В дальнейшем под связанностью элементов в чуме или орграфе понимается именно слабая связанность. Чум называется связным, если любая пара его вершин связана. Связанность является отношением эквивалентности и делит Р на классы эквивалентности - компоненты (слабой) связности. Подчум ССР является компонентой связности тогда и только тогда, когда С связный, но подчум С и ж не связный для любого ж е Р \ С. Через Сопр(х) (или Соп(х)) будет обозначаться компонента связности, содержащая элемент ж.

Счетным лесом [9] называется не более чем счетный (то есть конечный или равно-мощный множеству натуральных чисел) чум, в котором все цепи конечны и любой верхний конус является цепью. Счетное дерево - это счетный лес, содержащий наибольший элемент, называемый корнем. В частности, конечный лес (конечное дерево) - это счетный лес (соответственно, счетное дерево) с конечным числом элементов. Под лесами и деревьями далее понимаются соответственно счетные леса и деревья, если не оговорено противное. В данной работе леса и деревья «растут сверху вниз», что согласуется с распространенным способом изображения лесов и деревьев в информатике: по оценке Д. Кнута, более 80% рисунков деревьев в компьютерной литературе и в неформальных дискуссиях специалистов изображают корни сверху [24, с. 311]. По техническим причинам мы рассматриваем также пустой чум, который является лесом, но не деревом. Лес называется собственным, если он не является деревом. Например, пустой лес собственный. Корнями леса называются его максимальные, а листьями - его минимальные элементы. Любой счетный лес является объединением не более

Список литературы диссертационного исследования кандидат наук Жуков, Антон Владимирович, 2018 год

Список литературы

1. Биркгоф, Г. Теория решеток / Г. Биркгоф. - 3-е изд. - М. : Наука, 1984. - 568 с.

2. Ершов, Ю. Л. Элементарные теории / Ю. Л. Ершов, Т. А. Лавров, А. Д. Тайманов, М. А. Тайцлин // Успехи мат. наук. - 1965. - т. 20, № 4. - С. 37-108.

3. Ершов, Ю. Л. Неразрешимость некоторых полей / Ю. Л. Ершов // ДАН СССР. - 1965. - т. 161, № 1. - С. 27-29.

4. Кейслер, Г. Теория моделей / Г. Кейслер, Ч. Чен. - М. : Мир, 1977. - 614 с.

5. Келли, Дж. Л. Общая топология / Дж. Л. Келли. - 2-е изд. - М. : Наука, 1968. - 432 с.

6. Мальцев, А. А. Общее математическое образование: традиции и современность / А.А. Мальцев. - Новосибирск : Изд-во НИИ МИОО НГУ, 1997. - 251 с.

7. Селиванов, В. Л. О структуре степеней обобщенных индексных множеств / В. Л. Селиванов // Алгебра и логика. - 1982. - т. 21, № 4. - С. 472-491.

8. Селиванов, В. Л. Булевы иерархии разбиений над редуцируемой базой / В. Л. Селиванов // Алгебра и логика. - 2004. - т. 43, № 1. - С. 77-109.

9. Селиванов, В. Л. Фактор-алгебра размеченных лесов по отношению /¿-эквивалентности / В. Л. Селиванов // Алгебра и логика. - 2007. - т. 46, № 2. - С. 217-243.

10. Brattka, V. Weihrauch degrees omniscience principles and weak computability / V. Brattka, G. Gherardi // Journal of Symbolic Logic. - 2011. - Vol. 76, Issue 1. - S. 143-176.

11. Brattka, V. Effective choice and boundedness principles in computable analysis / V. Brattka, G. Gherardi // The Bulletin of Symbolic Logic. - 2011. - Vol. 17, Issue 1. - P. 73-117.

12. Cormen, Th. H. Introduction to Algorithms / Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein. - Third edition. - The MIT Press, 2009. - 1292 p.

13. Davey, B. A. Introduction to Lattices and Order / B. A. Davey, H. A. Pristley. - Second edition. - Cambridge : Cambridge University Press, 1994. - 298 p.

14. Fiala, J. An universality argument for graph homomorphisms / J. Fiala, J. Hubicka, Y. Long // The Eight European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015). - Electronic Notes in Discrete Mathematics. - Elsevier, 2015. - Vol. 49. -P. 643-649.

15. Grätzer, G. On the Jordan-Dedekind chain condition / G. Grätzer, E. T. Schmidt // Acta Sei. Math. 18. - Szeged, 1957. - P. 52-56.

16. Hell, P. Graphs and Homomorphisms / P. Hell, J. Nesetril. - Oxford University Press, 2004.

- 256 p.

17. Hertling, P. Topologische Komplexitätsgrade von Funktionen mit endlichem Bild / P. Hertling // Informatikberichte. - Hagen : Fernuniversität Hagen, 1993. - Bericht Nr. 152. - 34 S.

18. Hertling, P. Unstetigkeitsgrade von Funktionen in der effektiven Analysis: PhD thesis. / P. Hertling // Informatikberichte. - Hagen : Fernuniversität Hagen, 1996. - Bericht Nr. 208.

- 157 S.

19. Hertling, P. Complexity issues for preorders on finite labeled forests / P. Hertling, V.L. Selivanov // Logic, Computation, Hierarchies (Eds. V. Brattka, H. Diener, D. Spreen).

- Boston/Berlin : Walter de Gruyter Inc./Ontos, 2014. - Vol. 4. - P. 165-189.

20. Hertling, P. Levels of degeneracy and exact lower complexity bounds for geometric algorithms / P. Hertling, K. Weihrauch // Proceedings of the 6th Canadian Conference on Computational Geometry. - Saskatoon : University of Saskatchewan, 1994. - P. 237-242.

21. Hirsch, M. D. Applications of topology to lower bound estimates in computer science / M. D. Hirsch // From Topology to Computation: Proceedings of the Smalefest. - New York : Springer, 1993. - P. 395-418.

22. Hubicka, J. Universal partial order represented by means of oriented trees and other simple graphs / J. Hubicka, J. Nesetril // European Journal of Combinatorics. - 2005. - Vol. 26. -P. 765-778.

23. Hubicka, J. Finite paths are universal / J. Hubicka, J. Nesetril // Order. - 2005. - Vol. 22. -P. 21-40.

24. Knuth, D. E. The Art of Computer Programming. Volume 1: Fundamental Algorithms / D. E. Knuth. - Third edition. - Reading, Massachusetts: Addison-Wesley, 1997. - 670 p.

25. Kosub, S. Complexity and partitions: PhD thesis / S. Kosub. - Würzburg, 2000. -

26. Kosub, S. The boolean hierarchy of NP-partitions / S. Kosub, K. Wagner // Lecture Notes of Computer Science : Proceedings of 17th Symposium on Theoretical Aspects of Computer Science. - Berlin : Springer, 2000. - Vol. 1770. - P. 157-168.

27. Kosub, S. The boolean hierarchy of NP-partitions / S. Kosub, K. Wagner // Journal of Information and Computation. - 2008. - Vol. 206, Issue 5. - P. 538-568.

28. Kruskal, J. B. Well-quasi-ordering, the tree theorem, and Vaszonyi's conjecture / J. B. Kruskal // Transactions of the American Mathematical Society. - 1960. - Vol. 95. - P. 210-225.

29. Kruskal, J. B. The theory of well-quasi-ordering: a frequently discovered concept / J. B. Kruskal // Journal of Combinatorial Theory, Series A. - 1972. - Vol. 13, Issue 3. -P. 297-305.

30. Kudinov, O. V. Definability in the homomorphic quasiorder of finite labeled forests / O. V. Kudinov, V. L. Selivanov // Lecture Notes in Computer Science : Computability in Europe-2007 (Eds. S. B. Cooper, B. Löwe and A. Sorbi). - Berlin : Springer, 2007. - Vol. 4497. - P. 436-445.

31. Kudinov, O. V. Undecidability in the homomorphic quasiorder of finite labeled forests / O. V. Kudinov, V. L. Selivanov // Journal of Logic and Computation. - 2007. - Vol. 17.

- P. 1135-1151.

32. Kunen, K. Set Theory: an Introduction to Independence Proofs / K. Kunen. - Amsterdam : North-Holland (Elsevier), 1980. - 329 p.

33. Kwuida, L. On the homomorphism order of labeled posets / L. Kwuida, E. Lehtonen // Order.

- 2011. - Vol. 28, Issue 2. - P. 251-265.

34. Laver, R. On Fra'isse's order type conjecture / R. Laver // Annals of Mathematics. - 1971. -Vol. 28, no. 1. - P. 89-111.

35. Lehtonen, E. Descending chains and antichains of the unary, linear, and monotone subfunction relations / E. Lehtonen // Order. - 2006. - Vol. 23. - P. 129-142.

36. Lehtonen, E. Labeled posets are universal / E. Lehtonen // European Journal of Combinatorics. - 2008. - Vol. 29. - P. 493-506.

37. Nash-Williams, C. St. J. A. On well-quasi-ordering finite trees / C. St. J. A. Nash-Williams // Mathematical Proceedings of the Cambridge Philosophical Society. - 1963. - Vol. 59, no. 04. - P. 833-835.

38. Pouzet, M. Applications of well quasi-ordering and better quasi-ordering / M. Pouzet // Graphs and Order. NATO Science Series C: Mathematical and Physical Sciences. - 1985. -Vol. 147. - P. 503-519.

39. Pouzet, M. From well-quasi-ordered sets to better-quasi-ordered sets / M. Pouzet, N. Sauer // The Electronic Journal of Combinatorics. - 2006. - Vol. 13, Research Paper 101. - 27 p.

40. Pratt, V. R. Modelling concurrency with partial orders / V. R. Pratt // Internatinal Journal of Parallel Programming. - 1987. - Vol. 15. - P. 33-71.

41. Pultr, A. Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories / A. Pultr, V. Trnkovä. - Amsterdam : North-Holland, 1980. - 372 p.

42. Selivanov, V. L. Boolean hierarchy of partitions over reducible bases / V. L. Selivanov // Technical Reports. - Würzburg : Institut für Informatik, Universität Würzburg, 2001. - Vol. 276. - 15 p.

43. Selivanov, V. L. The algebra of labeled forests modulo homomorphic equivalence / V. L. Selivanov // Schriften zur Theoretischen Informatik. - Siegen : Universität Siegen, 2006. - Technical Report 06-01. - 18 p.

44. Selivanov, V. L. Hierarchies of Aíj-measurable fc-partitions / V. L. Selivanov // Mathematical Logic Quarterly. - 2007. - Vol. 53, Issue 4-5. - R 446-461.

45. Selivanov, V. L. Undecidability in some structures related to computation theory / V. L. Selivanov // Journal of Logic and Computation. - 2009. - Vol. 19, Issue 1. - P. 177-197.

46. Weihrauch, К. The degrees of discontinuity of some translators between representations of the real numbers / K. Weihrauch // Informatikberichte. - Hagen : Fernuniversität Hagen, 1992.

- Bericht Nr. 129. - 32 S.

47. K. Weihrauch. The TTE-interpretation of three hierarchies of omniscience principles / K. Weihrauch // Informatikberichte. - Hagen : Fernuniversität Hagen, 1992. - Bericht Nr. 130. - 27 S.

48. Weihrauch, K. Computable Analysis / К. Weihrauch. - Berlin : Springer Verlag, 2000. - 285 p.

Публикации автора по теме диссертации

Публикации в журналах из перечня ВАК

49. Zhukov, А. V. Definability in the /i-quasiorder of labeled forests / О. V. Kudinov, V.L. Selivanov, A.V. Zhukov // Annals of Pure and Applied Logic. - 2009. - Vol. 159, Issue 3. - P. 318-332.

50. Kudinov, О. V. Undecidability in Weihrauch degrees / О. V. Kudinov, V. L. Selivanov, A. V. Zhukov // Lecture Notes in Computer Science : Programs, Proofs, Processes (Proceedings of CiE-2010, eds. F. Ferreira, В. Löwe, E. Mayordomo, L. M. Gomes). - Berlin Heidelberg : Springer, 2010. - Vol. 6158. - P. 256-265.

51. Жуков, A.B. Определимость операций замыкания в /¿-предпорядке размеченных лесов / А. В. Жуков, О. В. Кудинов, В. Л. Селиванов // Алгебра и логика. - 2010. - т. 49, № 2.

- С. 181-194.

В англоязычной версии:

Zhukov, А. V. Definability of closure operations in the h-quasiorder of labeled forests / A.V. Zhukov, О. V. Kudinov, V. L. Selivanov// Algebra and Logic. - 2010. - Vol. 49, Issue 2.

- P. 120-129.

Другие публикации

52. Жуков, А. В. Предшественники деревьев в решетке счетных размеченных лесов / А. В. Жуков // XLVI Международная научная студенческая конференция, тезисы докладов. — Новосибирск : Изд-во НГУ, 2008.

53. Жуков, А. В. Пример бесконечной антицепи в структуре 2-размеченных частично-упорядоченных множеств / А. В. Жуков // XLVI Международная научная студенческая конференция, тезисы докладов. — Новосибирск : Изд-во НГУ, 2008.

54. Zhukov, А. V. Definability in the /¿-quasiorder of labeled forests / О. V. Kudinov, V. L. Selivanov, A. V. Zhukov // Schriften zur Theoretischen Informatik. - Siegen : Universität Siegen, 2008. - Bericht Nr. 08-02. - 22 S.

55. Zhukov, A. V. Undecidability in the 2-quasiorder of labeled forests / A. V. Zhukov // Маль-цевские чтения 2009: тезисы докладов. - Новосибирск, 2009. - Р. 217.

56. Zhukov, A.V. Undecidability in Weihrauch degrees / O.V. Kudinov, V.L. Selivanov, A. V. Zhukov // Workshop on Logical Approaches to Barriers in Computing and Complexity: Proceedings. - Greifswald, 2010. - P. 124-127.

57. Zhukov, A. V. An Algorithm for Embedding 2-Order into O-Order of Finite Labeled Posets and Forests / A. V. Zhukov // Материалы Всероссийской научной школы-конференции с международным участием «Информатика и информационные технологии в образовании: теория, приложения, дидактика». - Новосибирск : Изд-во НГПУ, 2012. - Том 1. - С. 149155.

58. Zhukov, А. V. A Note on Universality of 1- and 2-Orders of Finite Labeled Posets / A. V. Zhukov // Материалы Всероссийской научной школы-конференции с международным участием «Информатика и информационные технологии в образовании: теория, приложения, дидактика». - Новосибирск : Изд-во НГПУ, 2012. - Том 1. - С. 156-158.

59. Zhukov, А. V. Some Notes on the Universality of Three Orders on Finite Labeled Posets / A.V. Zhukov // Logic, Computation, Hierarchies (Eds. V. Brattka, H. Diener, D. Spreen). -Boston/Berlin : Walter de Gruyter Inc./Ontos, 2014. - Vol. 4. - P. 393-409.

Обозначения

Натуральное число к > 2 отождествляется с множеством меток {0,1,... ,к — 1}, номер сводимости г Е {0,1,2}, метка (корневая) г Е к.

Классы и фактормножества /с-чумов

Тк\Т})\3~к класс конечных к-лесов | фактормножество Тк/=г или структура (Тк/=г,<г) | то же, что Т^, с. 22

Тк | I к класс счетных к-лесов | фактормножество Тк/=г или структура (Рк/=г, | то же, что с. 22

класс конечных /с-решеток | фактормножество Ск/=г или структура (Ск/=г, <») | то же, что с- 22

класс конечных /с-чумов | фактормножество Тк/=г или структура (Рк/=г, <г) | то же, что VI, с. 22

Тк\Тк \ Тк класс конечных /с-деревьев | фактормножество Тк!=г или структура (7"к/=г, <г) I то же, что 7^°, с. 22

%,г№г\Тк,г класс конечных /с-деревьев с корневой меткой г | фактормножество Тк,г!=г или

структура (Тк,г/=г, <г) I то же, что с. 22 Тк\Тк\Тк класс счетных к-деревьев | фактормножество 7"к/=г или структура (7&/=г,<г) | то же, что Тк, с. 22

%,г№г\Тк,г класс счетных /с-деревьев с корневой меткой г | фактормножество Тк,г!=г или структура (Тк,г/=и <г) | то же, что с. 22

Множества

Ы(Р) высота фундированного предпорядка Р, с. 19

]г(8)\а]г(8) множество ненулевых неразложимых элементов полурешетки Б | множество

ненулевых с-неразложимых элементов с-полурешетки Б, с. 66 Р(а) уровень а - множество элементов высоты а в фундированном чуме Р, с. 20

VI [п] | Ск [п] множество элементов (индуцированной) внутренней высоты п в факторструк-

турах VI и Ск, соответственно, с. 41 [Р] класс О-эквивалентности к-чума Р в одном из классов /с-чумов (который опре-

деляется по контексту), с. 32 \Р\г класс ¿-эквивалентности к-чума Р в одном из классов /с-чумов (который опре-

деляется по контексту), с. 31 х\х верхний конус {у Е Р \ х <р у} элемента х Е Р | нижний конус {у Е Р \ у <р х}

элемента х Е Р, с. 15 х\. множество всех непосредственных предшественников элемента х, с. 15

Отношения

С1 отношение покрытия (непосредственного следования) для частичного порядка

<, с. 14

=г ¿-эквивалентность /¿-чумов, с. 30

<г ¿-сводимость /¿-чумов или классов ¿-эквивалентности /¿-чумов, с. 30

< то же, что <1, с. 14

¿-вложение /¿-чумов, с. 30 ¿-изоморфизм /¿-чумов, с. 30

Операции

2-произведение семейства к-чумов или 2-обобгценных /¿-чумов, инфимум в решетке с. 56

произведение семейства к-чумов или 0-обобгценных /¿-чумов, инфимум в решетке с. 26

У Б джойн (непересекающееся объединение) семейства /¿-чумов или их классов

О-эквивалентности (обобщенных /¿-чумов), с. 24 |_|Л5 джойн непересекающихся деревьев с общим корнем и корневой меткой, или

соответствующая индуцированная операция в структуре 7^гг, с. 26 расщепленное произведение /¿-лесов, инфимум в структуре с. 56 аН(Р) альтернирующая высота фундированного /¿-чума Р, с. 23

аНр(х) альтернирующая высота элемента х в фундированном /¿-чуме Р, с. 23

Ыр(х) высота элемента х в фундированном предпорядке Р, с. 19

1(х) множество меток /¿-чума или 0-обобщенного /¿-чума х, с. 22

|/(ж)| количество меток /¿-чума, 0- или 1-обобщенного /¿-чума х, с. 36

рг(х) замыкание /¿-чума х - добавление наибольшего элемента с меткой г, или инду-

цированная операция в факторструктурах 0-сводимости, с. 27 дг(£) замыкание /¿-дерева £ с корневой меткой, отличной от г, или индуцированная

операция в факторструктурах 0-сводимости, с. 27 гк(Р) ранг (то же самое, что высота) хорошего предпорядка Р, с. 20

¿' штрих-функция в структуре где £ € Тк, с. 70

¿А штрих-функция в структуре 7~к,г, где £ вида РгР1{х) при ] ф г, с. 77

Предметный указатель

г-изоморфизм 30 г-морфизм 28 г-ретракт

— в узком смысле 106

— в широком смысле 105

— собственный 107 г-сводимость 30

— Вайрауха 5, 100

к- лес

— главный 53

— счетный 22 /¿-разбиение 9 к-чум 22

— г-минимальный 107

— г-обобщенный 32

— бесповторный 23, 33

— главный 51

— жесткий (в смысле разметки) 58

— связный 58

Антицепь 15, 41 Высота

— альтернирующая 23 --/¿-цепи 109

— в информатике 19

— фундированного чума 19

— элемента в фундированном чуме 19

Джойн 24

Клон 10 Корень 16

Корневая метка 22, 23 Неразрешимость 91, 95

Полупуть 16

Предпорядок (квазипорядок) 14

— bqo 64

— специализации 100

— хороший (-«^о) 41, 42 Произведение /¿-чумов 26

Ранг (хорошего предпорядка) 20 Расщепление

— /¿-чума с ограниченными сверху цепями 97

— счетного /¿-чума с конечными цепями 35

Сводимость Вэджа 9, 100

Теорема

— Краскала 64 Топология Александрова 101

Уровень 20

Условие Жор дана-Д еде кинда 21 Цепь 15

— Косуба (контрпример для свойства wqo) 42

Частичный порядок 4

— универсальный 46

— фундированный 17 --ранжированный 21

Штрих-функция

— ' (в структуре /¿-лесов) 70

— А (в структуре /¿-деревьев) 77

Элемент

— с-неразложимый 66, 70

— неразложимый 33, 50, 66, 80, 93, 95

— определимый см. Определимость

Определимость 79 Орбита 86

Список иллюстраций

1 Начальный сегмент структуры уровни с 0-го по 5-й............. 6

2 Уровни структуры с 1_го по 8-й, вычисленные и нарисованные программно. Числа означают номера уровней (количество элементов на уровнях указано в таблице 1). Цвета (белый, серый и черный) показывают метки (0, 1

и 2). Детали вычислений см. в Приложении на с. 117............... 7

3 Уровни структур (^з1, <1) и (^1, <2) с 1-го по 8-й, вычисленные и нарисованные программно (обозначения те же, что и на рис. 2)................. 8

1.1 Счетное бесповторное О-замкнутое 2-дерево высоты ш + 2........................23

1.2 Любая цепь в Р 2-сводится к <5, но Р ^2 Я ........................................31

1.3 3-чум, 2-сводящийся к 2-цепи, но не 2-эквивалентный никакому 2-чуму .... 32

1.4 Структуры Т\ и Т2\ сплошной линией (овалами) изображены классы 0-эквивалентности (0-обобгценные 2-леса), штриховой и штрихпунктирной линией - классы 1- и 2-эквивалентности, соответственно................................40

2.1 Бесконечно убывающая цепь 2-чумов в (Т>2,<{), ¿ €= {0,1} (цепь Косуба) .... 42

2.2 Бесконечно убывающая цепь 2-чумов в (7*2, <г), ¿€{0,1,2}........... 42

2.3 Последовательность 2-чумов, содержащая бесконечную антицепь в (Р2> ъ € {0,1}........................................... 44

2.4 Последовательность 2-чумов, содержащая бесконечную антицепь в ("Рг, <г), ^ ^ {0,1,2} ......................................... 44

2.5 Другое представление последовательности {Сга}га> 1................ 45

2.6 а) Бесконечно убывающая цепь в (£3, <г), г Е {0,1}; Ь) бесконечная антицепь

в (£3, <г), г € {0,1} (примеры В. Л. Селиванова) ..................................46

2.7 а) Бесконечно убывающая цепь в (£3, г £ {0,1, 2}; Ь) последовательность, содержащая бесконечную антицепь в (£3, ¿€{0,1,2}........................46

2.8 Представления <5(С) и Ь(С) графа С, состоящего из двух узлов и дуги между ними......................................................................................48

2.9 Представление д(а) кортежа а = (а\,..., ап) Е М..................................50

2.10 2-чумы Р и <5, для которых |тиЬр1([Р]1, [<5)1) | = 2................................60

3.1 Пункты (11) и (ш) предложения 3.12 (пт(Ы) = 0).................. 71

3.2 Пункт (1у) предложения 3.12 (пт(Ы) = 0)...................... 71