Введение. Частично упорядоченные множества (кратко, у-множества [3] или ч.у.м

Частично упорядоченные множества (кратко, у-множества [3] или ч.у.м. [2]) самым естественным образом возникают во всех математических теориях и их приложениях, начиная с теории множеств: алгебре и анализе, геометрии и топологии, теории вероятностей и комбинаторике, логике и кибернетике и т.д. С учетом наличия такого рода структур, их важности и разнообразия Н. Бурбаки поставлена общематематическая задача исследова-ния систем с заданной структурой [10, 144, 145]. Так, в алгебре широко изучаются упорядоченные системы: у-группоиды, у-полугруппы, у-группы, у-лупы, см. [1-10, 12, 33, 42], особенно проблемы, связанные с у-системами [2-4, 7, 8, 14-20]. Наше исследование s-множеств принадлежит этому направлению.

Различные обобщения решетки рассматривались во многих работах: Гретцера (Gretzer G.), Бенадо (Benado M.), Скала (Skala H.), Фрида (Friede E), Ниминена (Niemenen J.) и Леутовы (Leutova J), Йордана (Iordan P.), Клаучевой (Klaucova O.), Томковой (Tomkova M.), Славика (Slavic V.), Герхардса (Gerhardts M. D.), Фаркаша (Farkas Gh.), Хансена (Hansen D. Z.), Собоцинского (Sobocinski B.), Амосовой Н.В и многих других (см. глава 1 и обзор, помещенный в Приложениях). Названные авторы по-разному назы-вали определяемый ими соответствующий класс обобщенных решеток: мультирешетки или мультиструктуры, c-решетки, квазирешётки, псевдоре-шётки и т.д., по-разному его обозначали или не обозначали никак.

Поскольку в нашей работе требуется систематический подход, то в ней выбраны и зафиксированы следующие обозначения: P обозначает у-множе-ство (договоримся обозначать соответствующий класс у-множеств тем же символом, но жирным шрифтом с наклоном, значит, P -класс у-множеств), P_lf - класс у-множеств конечной длины, L - класс решеток, ML - класс ML-решеток, Mul - класс мультирешеток, SN - класс s-множеств, NP^­ -класс направленных у-множеств (вверх), NP = NP^­¯ - направленных (вверх и вниз) у-множеств (обозначения других классов приведены в главе 1).

Символ # означает окончание утверждения.

В работах упомянутых выше исследователей обсуждаются вопросы соответствующих теорий, не имеющие пересечения по результатам с резуль-татами развиваемой нами теории s-множеств и ML-решёток. Поэтому обзор данных работ, помещенный в Приложения х, по необходимости краток.

Теории ML-решёток и мультирешеток занимают промежуточные положения между теорией у-множеств и теорией решёток:

Теор L Ì Tеор ML Ì Tеор Mul Ì Теор SN Ì Теор NP^­ Ì Tеор P,

т.к. для соответствующих классов имеют место, как показано в гл.1, следующие строгие включения:

L Ì ML Ì Mul Ì SN Ì NP^­ Ì P.

В классе s-множеств SN и ему двойственном IN выделяются такие под-классы, как класс мультирешеток MuL и класс ML-решеток ML. Затем выде-ляются два подкласса ML-решеток: класс ML_f-решеток и класс наиболее простых ML-решеток, а именно Ml-решеток. Вводится основной объект как общей, так и комбинаторной теории - класс полумодулярных ML-решеток. Это позволяет систематически переносить результаты, известные для полумодулярных решеток (см. [2-6, 14, 16]), на полумодулярные ML-решетки и развивать, таким образом, упомянутую теорию; в частности нами показано, что практически все основные понятия и многие факты теории геометри-ческих решеток переносятся на геометрические ML-решетки. Далее, многочисленные классы задач комбинаторной теории сформулированы для (локально) конечных у-множеств с наибольшим и/или наименьшим элемен-тами или же для ограниченных у-множеств конечной длины. Но это как раз и есть, как нами показано, s- или i-полурешетки, или же соответственно ML-решетки, что уточняет формулировки этих задач и фактов и указывает их естественное место.

Необходимость исследования направленных у-множеств общеизвестна. Необходимость изучения такого его подкласса как класс s-множеств SN продиктована как проблемой классификации в классе у-множеств, так и тем обстоятельством, что многие факты теории ML-решеток и решеток находят свое естественное обобщение именно в классе SN. Необходимость теории ML-решеток и одновременно их существования в своей существенной части решается следующими утверждениями:

любое ограниченное у-множество конечной длины является ML-ре-шеткой как и любое локально конечное у-множество;

любое у-множество P конечной длины вкладывается в подходящую ML-решетку, причем среди последних найдется ML-решетка, отличающаяся от P разве что наличием ô или î.

Значит, классыу-множеств конечной длины P_lf и локально конечных у-множеств - одни из основных объектов математики - лежат в проблемной области теории ML-решеток.

Приведем здесь лишь два примера конкретных классов ML-решеток:

1) локальная система подалгерб (определение см. в [142]) при конечной длине этой системы как направленного множества с ô и î;

2) семейство связных подграфов конечного связного графа, а значит и любая гиперблок-схема.

Впрочем, класс ML-решеток существенно богаче в силу следующего утверждения:

класс направленных (вверх-вниз) у-множеств с F-условием принадлежит классу ML-решеток. #

Исследование класса ML-решеток необходимо также потому, что практически все основные понятия и факты теории решеток находят свое естественное развитие именно в классе ML-решеток.

Обоснованию выдвинутых выше тезисов и посвящена наша работа.

Т.к. в теории s-множеств имеет место закон двойственности, то двой-ственные утверждения и определения, как правило, не приводим, но при необходимости используем, помечая двойственное утверждение значком *.

Для указания более точного местоположения исследуемого здесь класса ML-решеток приведем необходимые определения других классов обобщен-ных решеток, наиболее известных и близких классу ML-решеток.

Мультирешётки введены Бенадо [25]. Мультирешёткой называется такое у-множество Р, в котором для любых элементов х, у в у-множестве A общих им мажорант (верхних границ, т.е. А - верхний конус для {x, y}) каждая мажоранта содержит минимальный в A элемент, и двойственно.

c -решетки (Ниминен [85-88]).Пусть ub{a, b} - множество верхних гра-ней {a, b} и lb{a, b} - множество нижних, mub{a, b} - множество минималь-ных верхних граней и двойственно - mlb{a, b}. Множество (Р, £), где mub{a, b} ¹ Æ ¹ mlb{a, b} для каждых двух лементов a, bÎР называется c-множе-ством, где c - функция выбора, выбирающая единственный элемент как из mub{a, b}, так и из mlb{a, b}. Выбранный элемент c(mub{a,b}) обозначается как aÚb, а c(mlb{a,b}) - как aÙb. После выбора c элементы aÚb и a Ùb фикси-руются. Алгебра (Р; Ú, Ù), полученная из c-множества (Р, £) с помощью функции выбора c, называется c-решёткой.

Слабо ассоциативные решетки (с.а.р.) введены в работах Бейкера [4, с. 323], Скала [93] и Фрида [89-91]. В [91] с.а.р. определены следующим образом: с.а.р., или WA-решётка, есть множество A¹Æ c бинарными опера-циями Ú и Ù, удовлетворяющими аксиомам:

1) xÚx = x, x Ùx = x;

2) x Ú y = y Ú x, x Ù y = y Ù x;

3) xÙ(x Úy) = x, x Ú(xÙy) = x;

4) [(x Ù z) Ú (yÙz)] Úz = z, [(xÚz) Ù (yÚz)] Ù z = z.

Косые решётки введены Йорданом [94, 95], см. также [3]. Косой решёткой называется алгебра < A; Ú, Ù> с двумя бинарными операциями, удовлетворяющими тождествам

x Ùx = x = xÚx, x Ù(y Ù z) = (x Ù y) Ù z,

x Ú(yÚ z) = (xÚy) Úz, x Ú(y Ù x) = x = x Ù(yÚ x).

Как видим, WA-решётки и косые решётки образуют многообразия.

Гипорешеткой [36, часть VI-3] называется у-множество, каждый замк-нутый интервал которой является решеткой, причем на пересекающихся интервалах решеточные операции совпадают.

Ясно, что решётка является WA-решёткой, косой решеткой, c-решеткой и гипорешеткой. Обратное неверно: во всех случаях авторами работ [85-95] указаны примеры соответствующих структур, не являющихся решётками.

Обзор по другим классам обобщенных решеток приведен нами в [16, см. Публикации (или см. с. 671-672 Рукописи)] и в Приложениях (см. с. 426-646 Рукописи), в которых как раз и обоснован выбор для задачи классифика-ции приведенных классов.

Общая и комбинаторная теория решеток, как она представлена в моно-графиях и основополагающих работах Горбунова [2], Биркгофа [3], Гретцера [4], Скорнякова [5, 27], Бурбаки [10], Фукса [7], Рота [61], Айгнера [14], Стенли [18], Уолша [59], Маеда Ш. и Маеда Ф. [24], Салия [16, 17], Ковалева [57], Фриза, Ежека и Нейшена [23] и в работах других исследователей [21, 22, 32-44] включает следующие основные проблемные направления:

- многообразия, с углубленным изучением модулярных, дистрибутивных и булевых решеток (с их разноообразными проявлениями в математике и ее прикладных разделах);

- теория полумодулярных решеток, с углубленным исследованием геометри-ческих решеток и ассоциированных с ними (простых) матроидов и их обобщений;

- теория полных решеток;

- приложения, как структурного характера, так и явно выраженного комби-наторного и/или оптимизационного характера.

В нашей работе представлены все эти направления, естественно, прежде всего, в классе ML-решеток и s-множеств. Конечно, буквального следования перечисленным направлениям, особенно в их поднаправлениях нет. Это происходит, как по причине наличия собственной проблематики ML-решеток и s-множеств, так по понятной причине изучения лишь тех проблем, которые не получили свое решение, либо их полное исследование выводит за рамки, в которых они рассматриваются в теории решеток; так, например, при изу-чении структур универсальных алгебр или геометрий и пространств обычно рассматриваются дистрибутивные или модулярные структуры, см. [2, 3, 15, 17, 22, 54-56, 109-113], что далеко не охватывает всего их разнообразия; даже многообразия, близкие модулярному, исследованы пока очень фрагментарно. Изучение же их открывает хорошие перспективы применений к широкому кругу проблем, как теоретического, так и прикладного характера, см. гл. 3 параграфы 3 и 4.

Как уже сказано, многие проблемы теории у-множеств и комбинаторные задачи связаны именно с s-множествами, особенно с ML-решетками. Целью работы как раз и является создание и развитие общей и к омбинаторной теории s- множеств и ML- решеток. При этом необходимо, на наш взгляд, обосновать, что теория достаточно богата и перспективна как в теоретичес-ком, так и прикладном аспекте, чтобы иметь право на существование и развитие. Эта достаточность обосновывается следующими положениями.

Во-первых, выделены основные классы в классе у-множеств и классе ML-решеток (задача классификации), что позволяет ставить как общие вопросы, так и вопросы конкретные, в том числе задачи комбинаторики применительно к этим классам. В частности, выделен основной класс комбинаторной теории ML-решеток, каковым является класс полумодуляр-ных ML-решеток, подобно тому, как класс полумодулярных решеток является центральным объектом в комбинаторной теории решеток, см. [2, 3, 57, 70]. Так, многие комбинаторные задачи сформулированы для конечных ограниченных у-множеств, см. [1, 2, 15, 32, 64, 68, 73], а последние есть в точности конечные ML-решетки. Следовательно, указанные задачи являются задачами комбинаторной теории ML-решеток.

Во-вторых, в рамках теории ML-решеток могут быть изложены, кроме упомянутых, также многие (из числа как намеченных, так и практически не затронутых в данной работе) вопросы алгебры инцидентности, дискретных метрических пространств, суб- и супермодулярных систем и их обобщений [57, 58, 14, 70, 71, 134, 135, 160, 166, 4], некоторые комбинаторные задачи выпуклого анализа, теория матроидов, их обобщений или аналогов [2, 4, 63, 14, 58-61, 71].

В-третьих, приведены применения развиваемой теории как уже имеющиеся, так и перспективные.

Одним из основных объектов комбинаторной теории, так, как она излагается в известных монографиях и работах Айгнера, Рота, Стенли, Стечкина и многих других [35, 36, 39, 40], являются полумодулярные и геометрические решетки. В нашей работе исследовались некоторые из их обобщений. Обобщения шли в следующих направлениях: место полумо-дулярных и геометрических решеток заняли полумодулярные и геометри-ческие ML-решетки, место АС-решеток - MAC-решетки, место точечных ре-шеток - точечные ML-решетки и т.д.

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

Проблема 2 [3]: вычислить для небольших n и найти асимптотику и оценки для степени роста функций G(n) и G^*(n) (G(n) - число неизоморфных у-множеств с n элементами, G^*(n) - число различных упорядочений множества с n элементами).

Проблема 4 [3]: а) подсчитать число g(n,l) связных у-множеств длины l с n элементами; б) сколько среди них решеток?

Проблема 5. Перечислить все конечные решетки, которые однозначно (т. е. с точностью до изоморфизма) определяются своей диаграммой, рассма-триваемой как граф.

Проблема I2 [3]: как можно определить модулярные пары (т.е. отно-шение aMb) в произвольном у-множестве?

Проблема I.30 [4]. Описать многообразия решеток, каждое из которых задается одним тождеством с тремя переменными.

Проблема I.32 [4]: Определить и исследовать слабые частичные решетки и частичные решетки, удовлетворяющие некоторому тождеству.

Проблема II.6 [4]. Для каких классов K конечных решеток можно утвер-ждать, что если L - немодулярная решетка из K, то L содержит "минималь-ный" пентагон?

Проблема 25 [27]: исследовать дедекиндовы структуры, в которых каж-

дый элемент представляется в форме a = S_i=1^n(a) a_i, где La_i - цепи, в частности, конечные.

Обобщение этой проблемы: исследовать (ML-)решетки, конечно порожденные циклами.

Приведем результаты, полученные в нашей работе.

Основной результат общего характера заключается в создании и развитии общей и комбинаторной теории s-множеств и ML-решеток, в том числе:

теории полумодулярных ML-решеток, глава 2,

теории полных ML-решеток, глава 3,

классификации в классе у-множеств, глава 1,

основ теории систем матроидного типа, глава 4.

Приведем теперь

Основные результаты конкретного характера.

Проблема классификации. Данная проблема рассмотрена нами в двух аспектах:

как взаимоотношение классов различных обобщений решетки как алгебры (или как y-множества) из числа известных, которые выводят, вообще говоря, за класс Р y-множеств, и

как классификация в рамках собственно класса Р.

Решение первой приведено в гл. 1 § 1, а второй - в основном в гл. 1, § 2 и § 3.

Задача обобщения понятия многообразия на языке теоретико-множественных тождеств решена в § 3 п.3.3 гл. 1.

Проблема модулярной пары (м. п.). Исследованию этой проблемы по-cвящена гл. 2. Оказалось, что ранг-модулярная пара находит свое естествен-ное место в теории полумодулярных ML-решеток, развитой нами независимо от проблемы м.п. В § 5 этой же главы исследованы возможности распростра-нения понятия м. п. на существенно более широкий класс y-множеств. Это распространение представляется нам предельным в том смысле, что оно с одной стороны все еще сохраняет некоторые свойства м. п., известные в случае решеток, а с другой явно обосновывает вывод, что дальнейшее расширение не дает никакого эффективного результата.

Проблема неподвижной точки (н.т.) (обзор по данной проблеме см. в Приложении).

Проблема н.т. рассматривалась нами, прежде всего, в классах ML- и мультирешеток. Оказалось при этом, что некоторые результаты верны также для определенных классов s-множеств.

Проблема существования супермодулярных многообразий решена нами в § 3, п. 3.2.3 этой же главы.

Проблема распространения понятия матроида. Показано, что такую основную комбинаторную структуру, как матроид, можно распространить на существенно более широкий класс решеток и даже ML-решеток, глава 4, § 1.

Проблемы перечисления конечных y-множеств и ассоциированных с ними конфигураций. В рамках вычислительной упорядоченности в гл. 4 получен ряд результатов по порождению и перечислению конечных y-мно-жеств специальных видов; получен каталог всех y-множеств соответственно с n = 4, 5, 6, 7 элементами каждая, а также каталог всех решеток соответ-ственно с n = 4, 5, 6, 7, 8 элементами каждая.

Применения. Примеры применений s-множеств и ML-решеток как в самой математике, так и в ее прикладных разделах приведены в основном в главах 5 и 6.

Заключение содержит ряд нерешенных задач.

Приложение содержат обзоры, справки, рефераты и другие материалы (подтверждающие развиваемую в данной работе нами концепцию о роли и значении в математике теории у-множеств, мультирешеток и решеток).

Понятия, обозначения и некоторые факты, используемые в работе, приведены в п. Обозначения и определения.

---

Дата добавления: 2015-07-11