Содержание к диссертации
Введение
1 Определения и вспомогательные утверждения 7
1.1 Основные определения и обозначения 7
1.2 Свойства частично упорядоченных множеств 11
1.3 Доопределение частичных функций и монотонных отображений 13
2 Достаточные условия конечной порожденности классов всех функций, монотонных относительно множеств ширины два 17
2.1 Вспомогательные утверждения 17
2.2 Операторы ф и ф и их свойства 25
2.3 Теорема о существовании монотонного доопределения не всюду определенного отображения 73
2.4 Существование монотонной мажоритарной функции и достаточное условие конечной порожденности класса М-р 96
3 Критерий конечной порожденности класса всех функций, монотонных относительно множества ширины два 98
3.1 Семейство иредполиых классов монотонных функций, не имеющих конечного базиса 98
3.2 Необходимые и достаточные условия конечной порожденности класса М-р 102
Литература 104
- Свойства частично упорядоченных множеств
- Доопределение частичных функций и монотонных отображений
- Теорема о существовании монотонного доопределения не всюду определенного отображения
- Необходимые и достаточные условия конечной порожденности класса М-р
Введение к работе
Данная работа относится к теории функциональных систем. В ней изучаются свойства преднолных классов функций многозначной логики. Рассматривается задача о конечной порожденное™ преднолных классов монотонных функций.
В теории функций многозначной логики важное место занимают задачи классификационного характера. Одной из наиболее естественных и хороню изученных классификаций является разбиение множества Pk всех функций &-значной логики на классы, замкнутые относительно операции суперпозиции (см. [20, 10, 8]). Все замкнутые классы функций двузначной логики были описаны Э. Постом [38, 39], который показал, что число таких классов счетно. В книге [21] дано более простое изложение этих результатов. Описание классов Поста содержится также в работах [30, 16, 13, 15, 41, 33]. Некоторые важные свойства замкнутых классов булевых функций изучены в [5, 6, 12, 7].
Несмотря на то, что многозначные логики во многом похожи на двузначную, имеют место и принципиальные различия. К их числу относится пример континуального семейства замкнутых классов в Pk при к 3, приведенный в работе 10. И. Янова и А. А. Мучника [24]. Континуальность семейства всех замкнутых классов Р при к 3 приводит к значительным трудностям при их изучении. К настоящему времени изучены только некоторые семейства замкнутых классов в Д. К числу таких семейств относятся иредполные классы функций. Из теоремы А. В. Кузнецова [9] (см. также [19, 20]) следует, что при любом к 2 в Рд. существует конечное число предполных классов. При к = 3 описание всех предполных классов было получено С. В. Яблонским ([17, 18[). Отдельные семейства предполных в Pk классов при к А были найдены в работах [18, 11, 34, 35, 36, 37]. Полное описание преднолных классов в Pk было получено И. Розенбергом [42, 43] (см. также [22, 23, 8, 14, 4]), который выделил шесть семейств предполных классов: классы самодвойственных функций — классы типа Р, классы линейных функций — классы типа L, классы функций, сохраняющих разбиения множества Ek = {0,1,..., к — 1} — классы типа Е, классы функций, сохраняющих центральные отношения — классы типа С, классы функций, сохраняющих сильно голоморфные прообразы /і-адических элементарных отношений — классы типа В, и классы функций, монотонных относительно частично упорядоченных множеств с наименьшим и наибольшим элементами — классы типа О (мы пользуемся обозначениями из [23]).
К настоящему времени получен ряд достаточных условий конечной порожденности предполных классов монотонных функций. Из интерполяционной теремы К. Бейкера и А. Пиксли [25] (см. также [26, 27, 28]) следует, что если в замкнутом классе содержится мажоритарная функция, то класс является конечно-порожденным. В работе [27] приводится следующее условие: предполный класс всех функций, монотонных на частично упорядоченном множестве V, имеет конечный базис, если множество V представляется в виде С \ /С, где С — решетка, а /С — выпуклое подмножество С, не содержащее наименьшего и наибольшего элементов (определения см. в [3]). Отсюда, в частности, следует конечная порожденность классов функций, монотонных относительно решеток и линейно упорядоченных множеств. В [28] показано, что это условие эквивалентно отсутствию в множестве V четверки элементов а, Ь, с, d, таких, что а,Ь с, элементы а и b не имеют точной верхней грани и элементы cud не имеют точной верхней грани. Доказательство конечной порожденности класса монотонных функций, приведенное в работе [27[, опирается на существование в классе мажоритарных функций. Отметим, что условие существования мажоритарных функций в классе не является необходимым для конечной порожденности этого класса даже для замкнутых классов булевых функций (см. [39]). Примеры частично упорядоченных множеств, таких что классы всех функций, монотонных относительно этих множеств, являются конечно-порожденными, но не содержат мажоритарных функций, приведены в работе [29], однако эти классы не являются предполпыми.
В диссертации исследуются предполные классы функций, монотонных относительно частично упорядоченных множеств ширины два. Для всех множеств ширины два в терминах свойств этих множеств получены необходимые и достаточные условия конечной порожденности соответствующих предполных классов монотонных функций.
Дадим некоторые определения. Обозначим через А семейство всех конечных частично упорядоченных множеств с наименьшим и наибольшим элементами. Число элементов множества V обозначается через \Р\. Шириной частично упорядоченного множества V называется максимальное число попарно несравнимых элементов V; ширина множества V обозначается через w-p. Обозначим через А2 подсемейство семейства А, состоящее из всех множеств V, для которых выполняются неравенства \Р\ 2 и wp 2; множества из А2 будем называть множествами ширины два.
Пусть V Є А2, a,b Є V, элементы а и b несравнимы. Точная верхняя грань элементов а и Ъ обозначается через sup(a, b). Пусть несравнимые элементы а и b не имеют точной верхней грани, пусть с и d — две минимальные верхние грани элементов а и Ь, и существует е — точная верхняя грань элементов cud. Тогда е называется точной верхней гранью второго порядка элементов а и b и обозначается через snp2(a, b).
Теорема 1 (теорема 2.4.2). Пусть V — частично упорядоченное множество из семейства Аг, такое, что для любых двух несравнимых элементов а и b в V существует либо snp(a, b), либо sup2(a, b). Тогда класс Мр всех функций, монотонных относительно множества V, является конечно-порожденным.
Теорема 2. (теорема 3.1.1). Пусть V — частично упорядоченное множество из семейства А2, такое, что найдутся два несравнимых элемента а и Ь, для которых в V не существует ни sup(a,b), ни sup2 (а, Ь). Тогда класс Мр всех функций, монотонных относительно множества V, не имеет конечного базиса.
Из теорем 1 и 2 следует критерий конечной порожденности класса Мр.
Теорема 3 (теорема 3.2.1). Пусть V — частично упорядоченное множество из семейства А2. Класс Мр всех функций, монотонных относительно множества V, является конечно-порожденным тогда и только тогда, когда для любых двух несравнимых элементов а пЬвТ существует либо sup(a, b), либо sup2(a, b).
Этот результат можно переформулировать следующим образом.
Теорема 4 (теорема 3.2.2). Пусть V Є А2. Класс Мр является конечно-порожденным тогда и только тогда, когда он содержит некоторую мажоритарную функцию.
Из теоремы 3 следует алгоритмическая разрешимость задачи распознавания конечной порожденности предполных классов функций, монотонных относительно частично упорядоченных множеств ширины два.
Теорема 5 (теорема 3.2.3). Для любого частично упорядоченного множества V ширины два с наименьшим и наибольшим элементами существует алгоритм распознавания конечной порожденности класса Мр.
Нетрудно показать, что этот алгоритм имеет полиномиальную сложность (см. [1, 2]).
Следует отметить, что семейству А2 принадлежит множество, приведенное в работе [44]. Отметим также, что начиная с к — 10 в А2 существуют множества из к элементов, которым соответствуют конечно-порожденные предполные классы монотонных функций, но для которых пс выполняются условия из работ [27] и [28].
Опишем кратко содержание работы.
Работа состоит из введения, трех глав и списка литературы. В главе 1 приводятся основные определения и доказывается ряд свойств частично упорядоченных множеств из семейств А и Аг, а также некоторые свойства монотонных функций и отображений.
В главе 2 устанавливается достаточное условие существования конечного базиса в классе Мр всех функций, монотонных относительно некоторого частично упорядоченного множества V ширины два с наименьшим и наибольшим элементами (теорема 2.4.2).
В этой главе рассматривается семейство А2 частично упорядоченных множеств ширины два с наименьшим и наибольшим элементами, состоящее из всех таких множеств V, что для любой пары несравнимых элементов а и Ь в V существует либо sup(a, b), либо snp2(a, b). В параграфе 2.1 устанавливается ряд соотношений для элементов произвольного множества V Є А,2 . В параграфе 2.2 определяются операторы фиф специального вида, и доказывается ряд свойств этих операторов. В параграфе 2.3 рассматриваются отображения / : Q —» V, где Q! — некоторое подмножество произвольного частично упорядоченного множества Q, а V — произвольное множество из семейства А2 , и с помощью операторов ф и ф, определенных в предыдущем параграфе, задается доопределение отображения / на множество Q . Основным результатом параграфа 2.3 является теорема о необходимых и достаточных условиях существования монотонного доопределения отображения f : Q! — V на множество Q (теорема 2.3.1). В параграфе 2.4 на основе полученного критерия существования монотонного доопределения не всюду определенного отображения доказана теорема (теорема 2.4.1) о существовании в классе Мр, где V Є А2 , некоторой мажоритарной функции, число переменных которой зависит только от мощности множества V. Из этого результата с помощью теоремы Бейкера и Пиксли (см. [25]) получено утверждение о конечной порожденное™ класса М-р для любого множества V из семейства А2 .
В главе 3 доказывается критерий конечной порожденное™ класса всех функций, монотонных относительно множеств ширины два с наименьшим и наибольшим элементами. В параграфе 3.1 приводится семейство А2 частично упорядоченных множеств ширины два, которым соответствуют предполные классы монотонных функций, не имеющие конечного базиса. Основной результат сформулирован в теореме 3.1.1. Для доказательства используется метод Тардоша из работы [44], а именно, рассматривается произвольное множество V Є А2 , для каждого значения п 4 строится множество Ир п наборов элементов множества V, устанавливается ряд свойств наборов из этого множества, с помощью этих свойств показывается, что при всех значениях к множество 7l-ptn сохраняется всеми функциями из класса Мр, зависящими от к переменных, и, далее, что существует функция f{%\,... ,х 2п) Є Мр, которая не сохраняет множество TZptU. В диссертации при доказательстве лемм 3.1.2 и 3.1.3 метод Тардоша обобщается для семейства множеств А2 произвольной мощности. В параграфе 3.2 на основе результатов предыдущего параграфа и главы 2 приводится критерий конечной порожденное™ класса Мр, где V — произвольное множество из семейства А.
В диссертации принята следующая нумерация утверждений, теорем и лемм. Утверждения нумеруются тройками чисел, где первое число — номер главы, второе — номер параграфа, третье — номер утверждения внутри параграфа. Леммы и теоремы (кроме основных теорем, приведенных во введении) нумеруются аналогичным образом. Следствия не нумеруются.
Основные результаты диссертации опубликованы в работах [45, 46, 47, 48].
Свойства частично упорядоченных множеств
Пусть А — некоторое конечное множество. Через Ап будем обозначать n-ую декарто-ву степень множества А, то есть множество всех упорядоченных наборов (аь ..., ап), где все а, Є А. Через \А\ будем обозначать число элементов множества А. Пусть \Л\ = к, к 2. Обозначим через Р множество всех функций вида /(хі, Xi,..., хп), п = 0,1,2,..., аргументы которых определены на множестве А и такие, что f(ai,...,an) Є А при «!,...,«„ Є А. Функции из множества Р будем называть функциями k-значной логики (см. [20], [23]). Обозначим через Рд множество всех функций вида f(x\,... ,хп) : Ап — Ап, где п = 0,1,2,..., Ап — некоторое подмножество множества Ап. Функции из множества Р будем называть частичными функциями k-значиой логики. Пусть А — произвольная система функций из Р . Через [А] обозначим замыкание системы А относительно операции суперпозиции (см. [20]). Множество А С РЛ называется замкнутым классом, если [А] = А. Замкнутый класс функций А называется предполным классолі в РА, если А ф Р , и для любой функции / Є Рл \А выполняется равенство [Аи{/}] = РА- Система функций А порождает класс С С Рл, если [А] = С. Система функций А называется базисом в классе С, если [А] = С и [А0] ф С для любого подмножества Ао С А, такого, что Ао ф А. Замкнутый класс С С РЛ называется конечно-пороэ/сденнъш, если существует конечная система функций, порождающая С. Пусть А — некоторое множество, а о — бинарное отношение на этом множестве, удовлетворяющее условиям рефлексивности (а о а), транзитивности (из соотношений aob и Ьос следует соотношение аос) и антисимметричности (из соотношений сюЬ и boa следует равенство а = Ь). Множество А = (А, о) называется частично упорядоченным множеством, а отношение о — отношением частичного порядка на А. (см. [3]). Пусть V = (Р, ) и Q = (Q, -с) — некоторые конечные частично упорядоченные множества. Отображение / :V —» О, называется монотонным, если для любых элементов a, b Є V, таких, что а Ь, выполняется неравенство /(а) С f{b). В частности, функция f(x-[,... ,хп) б Pv называется монотонной относительно множества V, если для любых наборов (х\,...,хп) и {уи ..., уп), таких, что х\ yi,..., хп уп, выполняется неравенство f{x\,... ,хп) /(: /ь.. ,уп). Через Мр будем обозначать замкнутый класс всех функций, монотонных относительно V. Пусть V — некоторое частично упорядоченное множество с отношением порядка . Если для элементов a, b множества V выполнено одно из соотношений а b или b а, то эти элементы называются сравнимыми, в противном случае — несравнимыми; если выполняются неравенства а b и а ф Ь, будем говорить, что а меньше b (обозначение а Ь).
Пусть а\,аі Є V, элементы а\ и а несравнимы, элемент Ъ Є V называется верхней гранью элементов а\,а 2, если выполняются неравенства b а\ и b (i2- Верхняя грань b элементов ai,«2 называется минимальной верхней гранью этих элементов, если ни для какой другой верхней грани х этих элементов не выполняется неравенство b х; b называется точной верхней гранью а\,й2 (обозначение sup(ai, 02)), если для любой верхней грани х этих элементов выполняется неравенство b х. Так, например, и множестве V, приведенном на рис. 1.1, элементы c,d,e,f,g,h,l являются верхними гранями элементов а, Ь, элементы end — минимальными верхними гранями элементов а и Ь; элемент / является одновременно и минимальной, и точной верхней гранью элементов cud; элементы а я b по, имеют точной верхней грани. Далее, пусть Л С V, b Є А. Элемент b называется максимальным элементом миооїсества А, если не существует таких элементов х Є А, что выполняется неравенство х Ь; если в множестве А содержится ровно один максимальный элемент, то он называется наибольшим элементом множества А- Аналогичным образом определяются нижняя, максимальная нижняя и точная нижняя грани элементов, а так же минимальный и наименьший элементы множества А; точная нижняя грань элементов аі,аг обозначается inf(ai,a2). Далее, пусть а и b — несравнимые элементы множества V. Будем говорить, что элементы а и b 1-несравнимы, если они несравнимы и не имеют точной верхней грани. Будем говорить, что элементы а и b 2-несравнимы, если они 1-несравнимы, и найдутся две их минимальные верхние грани, которые являются 1-несравнимыми. Так, в множестве V на рис. 1.1 элементы а и /; 1-несрашшмы, элементы е и d 1-несравнимы, и элементы е и / 1-несравнимы; 2-несравнимых элементов в этом множестве нет. А в множестве Тц (см. рис. 1) 2-несравнимыми являются элементы а и а . Пусть V — некоторое частично упорядоченное множество. Определим ряд отно- шений между элементами и подмножествами V. Пусть Х\,... ,хк,ух,... ,ут Є V, будем говорить, что выполняется неравенство !,...,xjt Уі,...,ут (соответственно, хъ...,хк yi,...,ym), если для любых х Є {хх,...,хк} и у Є {уі,...,ут} выполняется неравенство х у (соответственно х у). Пусть А, В С V. Будем говорить, что выполняется неравенство А В (соответственно, А В), если для любых элементов х Є А, у Є В выполняется неравенство х у (соотиетстг.енпо х у); будем говорить, что выполняется отношение А В, если для любого элемента х Є Р, такого, что х А, выполняется х В. Пусть х Є V, А С Т, будем говорить, что выполняется неравенство х А (соответственно, х А), если для любого у Є А выполняется неравенство х у (соответственно, х у). Пусть хі,...,хп,уі,...,уп Є Р, будем говорить, что выполняется неравенство (х],..., хп) (уі,..., уп), если для каждого г = 1,...,п выполняется неравенство .т Уи будем говорить, что выполняется неравенство (хх,..., хп) (уд,..., уп), если (хи ..., хп) (т/ь ..., уп), и найдется такой ііомеї) і Є {1,..., п}, что выполняется неравенство ХІ Уі. Обозначим через Р2 множество всех неупорядоченных пар несравнимых элементов частично упорядоченного множества V = (Р, ). Элементы V2 будем обозначать че-])СЗ {хьХг}- Определим па Vі отношение порядка -С следующим образом: {хі,х2} С {у\,У2} тогда и только тогда, когда выполняется хотя бы одно из неравенств (xi,x2) (г/1,2/2) или (х2,а;і) (2/1,2/2)- ПуСТЬ V — ЧаСТИЧНО уПОІ ЯДОЧЄПНОЄ МНОЖеСТВО, Хі,Х2 Є Р, Элементы Х\ И Х2 1- несравнимы. Обозначим через у\ и т/2 две минимальные верхние грани элементов х\,х2. Тогда {7/1,7/2} е 27 будем обозначать элемент {7/1,7/2} через sup(хi,x2). Пусть элементы х\ и х2 1-несравнимы, {?/i,2/2} = sup(xi,2;2), и существует z = sup(j/i,2/2)- Тогда будем говорить, что элемент z — точная верхняя грань второго порядка элементов Х\ и х2, и обозначать этот элемент через sup2(xi,x2). Пусть элементы х\ и х2 2-несравнимы, {2/1,2/2} = sUp(zi,x2), {z\,z2} = іїїїр(г/і,2/2). Тогда будем обозначать элемент {zuz2} через sup2(xi,х2). Так, например, в множестве V (см. рис. 1.1) выполняются соотношения {c,d} = sup(a, 6) и / = sup2(a, 6), а в множестве 7 (см. рис. 1) выполняется соотношение {7)7 } = sup2(a,a ). Будем говорить, что элементы 01,02,61, Є Р образуют неполный квадрат, если элементы (її и а2 несравнимы, Ь\ и Ь2 несравнимы, и найдется такая перестановка 7г на множестве {1,2}, что выполняются следующие соотношения: ai 6,,-(1), а2 6 2), элементы ai и Ъф) несравнимы и элементы а2 и 6ж(і) несравнимы. Будем говорить, что элементы ai,a2,6i,62 Є V образуют квадрат, если элементы ai и а2 несравнимы, 6] и 62 несравнимы, выполняется неравенство ai,a2 61,62, и не существует такого элемента с Є V, что выполняются неравенства ai,a2 с 6i,62. Будем говорить, что элементы o,i,a2,bi,b2,C\,c2 образуют двойной квадрат, если элементы а і и а2 2-нссравиимы, {6i,62} = sup(ai,a2), {ci,c2} = sup2(ai,a2). Так, например, элементы a,b,c,d множества V, при веденного на рис. 1.1 образуют квадрат, элементы a,b,c,d также образуют квадрат; элементы a, a , (i, ft , 7,7 множества Ps (см. рис. 1) образуют двойной квадрат.
Доопределение частичных функций и монотонных отображений
Леммы, приведенные в этом параграфе, обобщают некоторые утверждения из работы [44]. Леммы 1.3.1 и 1.3.2 являются обобщениями леммы 2, а лемма 1.3.3 — обобщением леммы 5 из [44]. Будем рассматривать некоторое множество V Є А, содержащее шестерку элементов а,а ,Р,Р , 7,У, образующих двойной квадрат. Положим V = {0, а, а ,/?,/? ,7,7 , 1}- Лемма 1.3.1. Пусть Q - некоторое частично упорядоченное множество, Q! С Q, / — некоторое монотонное отображение Q! —» Vі, и в Q не существует зигзага для / . Тогда существует монотонное доопределение отображения / на множество Q. Доказательство. Построим монотонное отображение /, определив для каждого є Є V множество Далее, определим граф G следующим образом: элементы множества Н являются вершинами графа, и для любой пары элементов y,z ЄН ребро (у, z) существует тогда и только тогда, когда элементы у и z сравнимы. Обозначим через Tip объединение связных компонент графа, содержащих хотя бы один элемент из множества {//-1(/ )}) положим Tip = Ті \ Tip. Таким образом, построено разбиение множества Q на непересекающиеся подмножества Тіе. Определим отображение / : Q— V: для каждого элемента q Є Q положим f(q) = є тогда и только тогда, когда q Є Тіє (заметим, что так как подмножества Н не пересекаются, то определение корректно).
Из определения / следует, что если для элемента z Є Q выпоняется равенство f(z) = а, то а Є f (z), так как в этом случае z Є На, а значит выполняются соотношения / (z) С {0,о;} и / (г) {0}. Аналогично, если f(z) — а , то а Є f {z), если f(z) = 7, то 7 Є / (2)» ссли f(z) 7 » т0 і Є f {z)- Пользуясь этими соотношениями, а также в силу того, что для любых элементов 1, Є Q, таких, что Z\ z i выполняются соотношения ft(z{) С / (г 2) и f (z 2) С f (zi), нетрудно показать, что отображение / монотонно. Кроме того, легко видеть, что для каждого z Є Q , такого, что f(z) ф /? , ВЬШОЛЕІЯЄТСЯ равенство f(z) = f (z). Покажем, что f(z) = f (z) для тех z Є Q!, для которых f(z) = Р . Для этого достаточно показать, что в графе G пет компоненты, одновременно содержащей элементы из множеств {f x{(3)} и {f l(P )}. Из определения Н следует, что для каждого элемента z Є Н выполняются соотношения f (z) . {0, а}, {0, а } и f (z) . {1,7} {1 7 }- В силу монотонности / это эквивалентно тому, что выполняются следующие два условия: (1) Р Є / (z) или /? Є /,( ) или {а, а } С /„(г), (2) (З Є f (z) или $ Є f (z) или {7, У} С f (z). Предположим, что в графе G найдется компонента, содержащая и элемент Хт из {//_1(/?)}, и элемент Xmi из {/ _1(/ )}- Это значит, что в графе существует путь (цепочка ребер) между этими элементами. Рассмотрим кратчайший из таких путей (то есть проходящий через наименьшее число вершин). Если x,y,z - последовательные вершины этого пути, то не выполняется ни одно из соотношений х у z и х у Z, так как в противном случае существовал бы более короткий путь, не проходящий через вершину у. Следовательно, если обозначить последовательность вершин этого пути через Хт,...,Хт , то для этих элементов будут выполнены условия а), с), d), е) из определения зигзага. Так как Хт,...,Хт — кратчайший путь между элементами Хт и Хт , то в последовательности Хт,... ,Хт нет элементов множества Q , отличных от Хт и Хт . Отсюда следует, что выполняется условие Ь).
Далее, в силу того, что мы рассматриваем кратчайший путь, для всех Х%и т 21 т , из трех возможных соотношений в (2) выполняется только {7)7 } С f (z), следовательно, выполняется условие f). Аналогично, для всех X2;+i, т 2г + 1 гп , из трех возможных соотношений в (1) выполняется только {а, а } С f (z), значит выполняется условие g). Таким образом, последовательность Хт,... ,Хт является зигзагом для / , что противоречит исходному предположению. Доказательство. Пусть Хт... ,Хт — зигзаг для / в Q. Предположим, что существует / — монотонное доопределение отображения / на множество Q. Обозначим через к наименьшее число из т,т + 1,... ,т , такое что значение f(Xk) несравнимо с /?. В силу равенств f(Xm) = (3, f(Xm ) = /3 , выполняется неравенство т к т . Положим Д. = f(Xk), fk-i = f(Xk-i)- Так как элементы Д. и j3 несравнимы, то в силу свойства (а) множеств ширины два элемент Д сравним с /? . В силу монотонности отображения / выполняются неравенства а, а /І 7,7 ) гДе і = к—1,к. Рассмотрим два случая: Д (З1 и Д /3 . 1- Д р"- Так как р" — минимальная верхняя грань элементов а, а , то из неравенства Д а, а следует Д = /? . Предположим, что к четно. Тогда Д_і Д, значение Д_1 согласно выбору к сравнимо с /?, и если Д_і /3, получим, что Д Д-1 р\ что цротивоі)Єчит выбору номера А;. Поэтому Д._! /3. Но тогда, в силу неравенства Д_і а, а , получаем противоречие с тем, что (3 — минимальная верхняя грань элементов а,а . Пусть теперь к нечетно. Тогда Д_і Д, и если выполняется Д_і (3, то Д Д_! /3, что противоречит выбору номера к. Поэтому Д_1 (3. Получили, что выполняются неравенства 13,(3 Д_і 7)7 ) которые противоречат тому, что 7,7 — минимальные верхние грани элементов (3,(3 - 2. Д (3 . Предположим, что к четно. Тогда Д_і Д. В силу выбора номера к соотношение Д_і (3 невозможно, поэтому выполняется неравенство Д_! (3, которое в силу неравенства а, а Д противоречит тому, что (3 — минимальная верхняя грань элементов а, а . Пусть теперь к нечетно. Тогда из неравенства Д-1 Л следует неравенство Д_і (3 . В силу выбора к значение Д_! сравнимо с (3. Так как элементы (3 и (3 несравнимы, неравенство Д_і (3 выполняться не может, поэтому Д_і (3. Получаем, что выполняются соотношения 7,7 Д-1 (3,(3 , которые противоречат тому, что 7,7 минимальные верхние грани элементов (3, /? . Лемма доказана. Пусть п 3. Обозначим через V2n подмножество множества V2n, состоящее из следующих Лемма 1.3.3. Пусть V Є А2. Тогда в классе М-р существует функция, являющаяся доопределением частичной функции ip2. Доказательство. Очевидно, что частичная функция (р2 1 монотонна на множестве V2n. Предположим, что ее невозможно доопределить до монотонной функции на множество V2n. В этом случае в силу леммы 1.3.1 в Т2п существует зигзаг для ip2 1
Теорема о существовании монотонного доопределения не всюду определенного отображения
Покажем, что для каждого а Є Q\Q! значение /(a) определено. Действительно, если значение /(a) определяется по правилам (fl) или (f2), то это очевидно. Если по правилу (f3), то в силу монотонности отображения / и свойства (с) окрестностей выполняется неравенство а А. Так как, по условию, T(Q, Q , / ) = 0, то равенства \А\ = 1, А = {а} не выполняются, значит выполняется строгое неравенство а А. Тогда (а, А) Є ф, а значит значение ф((а,А)) определено. Заметим, что в этом случае (а, А) не является элементом типа (фЗ), так как иначе элемент а был бы особым для отображения / , что противоречит условию. Наконец, если значение /(a) выполняется по правилу (f4), то в силу свойства (а) окрестностей элементы (7,1,( несравнимы, в силу монотонности отображения / и свойства (с) окрестностей выполняется неравенство ai,a2 А, и тогда (аі,а,2,А) Є Тф. Далее, по свойству 2 оператора ф, значение ф((аі,а,2,А)) не определено только тогда, когда Л = 2, и (01,02,7 1,7 2), "ДО {74,7} = А, — квадрат . Но это значит, что а является зигзагом длины 1 для / , что противоречит условию леммы. Следовательно, значение ф((аі,а,2,А)) определено. Покажем, что для каждого а Є Q \ Q! отображение / монотонно на множестве Q U{a}. Действительно, если значение /(a) определяется по правилам (fl) или (f2), то это очевидно, если по правилам (f3) или (f4), то это следует из свойства 2 оператора ф и свойства 3 оператора ф соответственно. Покажем теперь, что так построенное отображение / монотонно на всем множестве Q, то есть для любых двух элементов а, (З Є Q, таких, что a /3, выполняется неравенство /(a) /(/?). Ест и а,Р Є Q , то неравенство /(a) /(/?) выполняется в силу монотонности отображения / . Если ровно один элемент є Є {а,/?} не принадлежит множеству Q , то требуемое неравенство верно в силу показанной выше монотонности / на множестве Q! U {є}. Пусть теперь а,р Є Q \ Q!. Рассмотрим несколько случаев. 1. Если найдется такой элемент є Є Q , что a є (3, то будут выполнены неравенства /(a) f(e) f((3) (первое неравенство выполняется в силу монотонности отображения / на множестве Q U{a}, втрое - в силу монотонности / на множестве # U {/?}). 2. Пусть теперь такого элемента є не существует. (a) Пусть хотя бы одно из значений /(a) или /(/і) определяется по правилам (fl) или (f2).
Если значение /(a) определяется по правилу (fl), то /(a) = 0 /(/?). Если значение /(a) определяется по правилу (f2), то есть у(а) ф 0, Ну/(а) = 0, то, так как в силу свойства (d) окрестностей выполняются соотношения / Н С ,,(/?) и Ег(р) С Е//(а), то &(0) ф 0, Е}Щ = 0. Это значит, что значение /(/?) определяется по правилу (f 2), и тогда /(/?) = 1 = /(a). Случаи, когда значение /(/?) определяется по правилам (fl) или (f2), рассматриваются аналогично. (b) Пусть теперь значения /(a) и /(/?) определяются по правилам (f3) или (f4). Тогда множества //(a),E//(a),//(/?),Ну/(/?) непусты. Положим A = Ау/(а), В = Ау/(/?). Из свойства (d) окрестностей следуют соотношения (а) для каждого .х Є oy/(a) найдется / Є Sf(f3), такой, что х у, W) А±в- Далее рассмотрим четыре случая. і. \5г{а)\ = 15,,(/3)1 = 2. Пусть 8r(a) = {aha2}, 5f,(p) = {bub2}. Тогда, по определению, f(a) = ф((аиа2,А)), /(/?) = ф((ЬиЬ2,В)). В силу соотношения (а) и i$ силу свойства (Ь) множеств ширини дна выполняется неравенство {«1,02} С {b\.,b2}. II тогда, так как в силу соотношения (fj) А В, то неравенство ф((аі,а2,А)) ф((Ь\,Ь2,В)) выполнено по следствию из леммы 2.2.1. и. \5г(а)\ = 2, \5f,(p)\ = 1. Пусть 5г(а) = {аиа2}, 5Г(/3) = {Ьі}. По определению, /(а) = ф(((іі, а2, А)), /(/?) = ф((Ь\, В)), причем но условию (Ьи В) не является элементом типа ( 3). В силу соотношения (а) выполняется неравенство а,\, а2 by. II тогда, так как в силу (/3) А - В, то неравенство ф((аиа2,А)) ф((Ьу, В)) выполнено по следствию из леммы 2.2.3. ІІІ. \fif,(a)\ = 1, \5r(f3)\ = 2. Пусть 5r(a) = {oi}, 5r(0) = {h,b2}. По определению, f(a) = ф((а ,Л)), /(/?) = ф((Ь\,Ь2,В)), при этом по условию (ci\,A) не является элементом типа (фЗ). Из соотношения (а) следует, что выполняется по крайней мере одно из неравенств ci\ by или а і b2, пусть выполняется неравенство ai Ь\. Если выполняется неравенство а\ Ь2, то в силу соотношения А X В неравенство ф((аі,А)) Ф{(Ьі, b2, В)) выполняется в силу леммы 2.2.9. Если же неравенство ау Ь2 не выполняется, то, так как элементы Ь\ и Ь2 несравнимы, неравенство а\ Ь2 выполняться не может, а значит элементы а\ и Ь2 несравнимы. И тогда в силу соотношения А - В неравенство ф((а\,А)) ф{(Ь\,Ь2,В)) выполняется в силу следствия из леммы 2.2.14. iv. 5y(tt) = 5р(/3) = 1- Пусть $г(а) = (ai} fif iP) — (M- В этом случае /(a) = ф((аиА)), /(/?) = ф((ЬиВ)), причем (auA) и (buB) по условию не являются элементами типа (фЗ). Из соотношения (а) следует, что выполняется неравенство «і by. И тогда в силу соотношения А В неравенство ф((а\,А)) ф((Ь\.,В)) следует из леммы 2.2.8. Лемма доказана. Следствие. Пусть Q - некоторое частично упорядоченное множество, Q С Q, / : Q — V — монотонное отображение, и пусть в Q не существует особых элементов и зигзагов длины 1 для / . Тогда существует монотонное доопределение f отображения / иа множество Q. Доказательство. Если T(Q, Q ,/ ) = 0, то утверждение следует из леммы 2.3.2. Пусть теперь T(Q, Q ,f) ф 0. Рассмотрим отображение /т, которое является доопределением отображения / на множество Q" = Q U T(Q, Q , / ). Согласно лемме 2.3.1 отображение /т монотонно. Легко видеть, что в q не существует ни особых элементов, ни зигзагов длины 1 для /V, а также, что множество Т( 2, Q", /г) пусто. Поэтому в силу леммы 2.3.2 существует монотонное доопределение / отображения Д на множество Q, которое является также доопределением отображения / . Таким образом, утверждение доказано. Утверждение доказано.
Лемма 2.3.3. Пусть / — монотонное отображение Q! — V, а Є Q\Q! — особый элемент для отображения / . Пусть /" — отображение Q! U {а} — Р, такое, что /"Is = / ; /"(а) = Vf (a)- Пусть (З Є Q \ Q , элемент /3 не является ни зигзагом длины 1, ни особым элементом для отображения f, и является либо зигзагом длины 1, либо особым элементом для отображения /". Тогда выполняются следующие утверждения: (1) а Р, (2) 5Г(Р) = 5Г(Р), (3) а В„ гдеВ = 5г(р), (4) Д/"(/?) = {а, г} где г — элемент из множества Д//(/?), несравнимым с элементом а, (5) г w, где w = sup2(ui,«2), {щ,щ} = х{о ,А), (6) выполняется соотношение Д/ (/?) = {г}. Доказательство. Разобьем доказательство леммы на несколько этапов. 1. Так как а — особый элемент для отображения / , то по определению особого элемента #р(а) = 1, Д/ (а) = 2, пара (а, А), где {a} = 5f(a), А = Д/ (а), — это элемент типа (грЗ), и выполняется равенство r]f (a) = ф((а,А)). Из определений элемента типа ( 3) и оператора ф следует, что значение ф((а,А)) определяется по правилу ( 3). Поэтому выполняется равенство f"(a) = ф{{а,А)) = а. Предположим, что утверждение (1) леммы неверно, то есть либо элементы а и (3 несравнимы, либо выполняется неравенство р а. Тогда по свойству (g) окрестностей выполняются равенства 5/ (/?) = #/"(/?), Д/ (/?) = Afn(P). Если р — особый элемент для отображения /", то по свойству 3 особых элементов Р является особым элементом для отображения / , что противоречит условию леммы. Если Р — зигзаг длины 1 для /", то по свойству зигзагов длины 1 Р является зигзагом длины 1 для отображения / , что также противоречит условию. Следовательно, выполняется неравенство Р а. Доказано утверждение (1). 2. Легко видеть, что в силу определения отображения /", в силу неравенства р а и в силу свойства (g) окрестностей выполняются следующие соотношения: 5f(P) = $f"(P), а 0 Af(P), (і Є Af(p). Таким образом, доказано утверждение (2). 3. В силу свойства 2 оператора ф и свойства (є) окрестностей отображение /" монотонно. Так как /? является либо особым элементом, либо зигзагом длины 1 для отображения /", то выполняется равенство Ду»(/?) = 2. Обозначим 5/ (р) через В„. В силу свойства (с) окрестностей выполняется неравенство /"(/?) Е/«(/3), следовательно, выполняется неравенство 5/»(Р) Д/»(/?). Из последнего неравенства в силу соотношений В = Sf(P) = Sf»{P) и а Є Afi(P) (см. н. 2) следует неравенство а Bt. Доказано утверждение (3). 4. Так как выполняются соотношения Д/»(/3) = 2 (см. п. 3) и а Є Д/»(/?) (см. п. 2), то Д/"(/?) = {а,г}, где г — элемент из множества Д/ (/?), несравнимый с элементом а. Доказано утверждение (4).
Необходимые и достаточные условия конечной порожденности класса М-р
В этом параграфе описываются все частично упорядоченные множества ширины два с наименьшим и наибольшим элементами, такие, что соответствующие предполные классы монотонных функций не имеют конечного базиса. Основной результат, сформулированный в теореме 3.1.1, опирается на леммы 3.1.2 и 3.1.3, в которых метод из работы Тардоша [44] обобщается для семейства А2 множеств ширины два специального вида. Обозначим через А2 семейство всех множеств из А2 (частично упорядоченных множеств ширины два с наименьшим и наибольшим элементами), содержащих пару 2-несравнимых элементов. Всюду в этом разделе будем рассматривать некоторое множество Р Є А2 . Доказательство. Необходимость. Предположим, что не существует монотонного доопределения отображения д на множество 71. Из монотонности отображения д следует, что выполняются неравенства а,а Ь, Ъ ,с и для всех j = 1,..., п неравенства а, а Cj. Покажем, что элементы а и а несравнимы. Действительно, предположим, что эти элементы сравнимы, пусть, например, выполняется неравенство а а . Тогда определим отображение д : 71 —» V следующим образом: положим д\-л = д , /(А) = а для всех к = 1,... ,2п + 1. Очевидно, что отображение д является монотонным доопределением отображения д на множество 71, что противоречит исходному предположению. Далее, покажем, что в V не существует sup(a,a ).
Действительно, в противном случае можно было бы построить монотонное доопределение отображения д на множество 71 положив д \ті = / , g(Dk) = sup(a, а ) для всех к = 1,..., In + 1, что противоречит исходному предположению. Отсюда следует, что элементы а и а имеют две минимальные верхние грани (обозначим их через v и /), и, кроме того, выполняются неравенства а, а Ъ, У, с , а также а, а Cj для всех j = 1,..., п. Легко видеть, что для каждого і — 1,..., п элементы СІ и с1 несравнимы, и пи для какого і = 1,..., п не существует inf(c;, с ). Поэтому для каждого г — 1,..., п элементы СІ,с несравнимы, значит, в силу свойства (а) множеств ширины два, все элементы С\,...,сп сравнимы между собой и в множестве {с\,...,сп} существует единственный минимальный элемент, который обозначим через с. Покажем, что выполняются неравенства с v,v и d v,v . Действительно, так как с Є {ci,...,cn}, найдется такой нечетный номер г Є {1,... ,2n + 1}, что выполняются неравенства а, а gi(Dr),g2(Dr) c,d. Так как v,v — минимальные верхние грани элементов а, а , то из соотношений а, а gi(Dr),g2(Dr) следует, что для каждого г = 1,2 выполняется по крайней мере одно из неравенств gt{Dk0) v и g D ) г/. Предположим, что найдется такой элемент V\ Є {v, v }, что выполняются неравенства #i(A-)) (А-) vi- Тогда обозначим В через D0, В через Дг«+2 далее, положим Я к = д , Для к = 0, ...,г — 1 положим g{Dk) = 7i(A:)
Для = г + I,... ,2п + 2 положим g(Dk) = #2(At) и положим g{Dr) = v\. Так определенное отображение д является монотонным доопределением д па множество 71, что противоі)ечит исходному предположению. Поэтому такого элемента V\ не найдется, это значит, что найдется такая перестановка 7Г на множестве {1,2}, что выполняются неравенства #тг(і)(А) v, fh(2)(Dr) v . Отсюда CKV CT, что выполняется неравенство с,с v,v . Покажем, что элементы v,v ,b,b образуют неполный квадрат. Действительно, из неравенства Ь, У а, а следует, что выполняется по крайней мере одно из соотношений b v п b v И ПО крайней мере одно из соотношений b v и У v1. Будем считать, что b v, случай b d рассматривается аналогично. Неравенство У v противоречит тому, что v — минимальная верхняя грань элементов а, а . Предположим, что выполняется неравенство У v. Тогда можно построить монотонное доопределение д отображения д , положив //(A) = v для всех к = l,...,2n + 1, что противоречит исходному предположению. Поэтому элементы У и v несравнимы. Тогда элементы У и v сравнимы, а значит выполняется нерагюнство b і/. Рассуждая так же, как для элементов U и v, можно показать, что что элементы b и v несравнимы. Легко видеть, что не существует элемента z, для которого выполняются неравенства v, Vі z с, d. Действительно, в противном случае можно было бы построить монотонное доопределение д отображения д , положив #(Д) = v, #(Дп+і) = /, g{Dk) = z для к = 2,..., 2n. Отсюда следует, что элементы v, v имеют две минимальные верхние грани (обозначим их через w,w ), а также, что элементы w,w ,c,d образуют неполный квадрат. Далее без ограничения общности будем считать, что выполняются неравенства С W И d XVі. Покажем, что пи для какого і = 1,...,п не существует элемента z, для которого выполняются неравенства v,v z Ci,d. Действительно, пусть для некоторого номера г существует такой элемент z. Тогда можно построить монотонное доопределение д отображения д , положив для к = 1,..., 2г — 1 7(Д) = v, для к = 2г + 1,..., 2n + 1 g(Di) = v И g(D2i) = z. Отсюда следует, что для каждого номера г = 1,..., п элементы w,w ,Ci,d образуют квадрат. Таким образом, необходимость доказана. Достаточность. Предположим, что условия 1-3 выполнены, и существует д — монотонное доопределение отображения (j. Будем считать (см. условие 2), что выполняются неравенства b vnb /. Обозначим #( Д) через di, і = 1,..., 2а + 1. Так как отображение д монотонно, то для каждого номера г = 1,... ,2п + 1 выполняются неравенства di а,а , и следовательно, выполняется по крайней мере одно из неравенств di v и di v . Кроме того, так как v, v — минимальные верхние грани элементов а, а , то ни для какого di не может выполняться ни одно из неравенств di v, di v . Покажем индукцией по г, что для всех і = 1,..., 2п + 1 выполняется неравенство di v, а элементы di и v несравнимы. Из неравенства dx v следует, что выполняются соотношения b d\ v1 , что противоречит условию 2. Поэтому элементы d\ и v несравнимы, и выполняется неравенство d\ v. Из неравенства d-2 t/ следует, что выполняются соотношения v,v d-i C\,d. Согласно условию 3, w,w ,cd — неполный квадрат, но тогда последние соотношения невозможны в силу свойства (с) квадратов. Поэтому элементы d2 и v несравнимы и выполняется неравенство d2 v. Аналогичным образом для каждого к = 1,...,п можно показать, что если выполняется неравенство d2k v, а элементы d2k и / несравнимы, то выполняются неравенства соотношения d2k+i,d2k+2 v, элементы СІ2А.-+1 и г/ несравнимы и элементы d2k+2 и v несравнимы. Но тогда из неравенства c n+i v следуют соотношения // d2n+i v, что противоречит условию 2. Лемма доказана. Пусть п 3, Qo = {А, А , В, В , Сі,..., Сп-2, С", Д,..., Д«-з} — Г-множество раи-гап-2, Q 0 = {A,A ,B,B ,Cu...,Cn-2,C }, Qi = 2\{2? }, Q 2 = Q 0\{B}. Обозначим через Т набор элементов (а, а , Ь, Ь , С\, ..., сп, d) Є Тп+Ь. По этому набору определим п отображений Q 0 — V следующим образом: для каждого і — {,... ,п положим f[(A) = а, f (A ) = а , / (#) = b, f (B ) = U, для каждого j = 1,...,п — 2 определим величину кц = г + j — 1 (modn) и положим f-(Cj) = с , и наконец, Д(С) = d. Обозначим через /?о множество таких наборов Т Є Рп+", что для каждого і = 1,..., п отображения // \Q , f! \Q МОЖНО монотонно доопределить на Q0. Далее, для каждого j = 1,...,77. обозначим через Rj множество таких наборов из Но, что отображение / можно монотонно доопред(!лить на QQ.
