отношение порядка обладающее свойством антирефлексивности называется

Отношения. Часть II

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

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

Понятие отношения

Думаю, что термин отношение знаком каждому читателю, но просьба дать определение поставит большинство в тупик. Причин для этого много. Они чаще всего в преподавателях, которые, если и использовали отношения в процессе преподавания, внимания на этом термине не заостряли, запоминающихся примеров не приводили. Некоторые комментаторы статьи отнесли замечания на свой счет и насыпали минусов. Но шила в мешке не утаишь. Серьезных публикаций как не было, так и нет. Задайте себе вопрос, работали ли Вы с каким-либо пространством отношений? И честно себе ответьте. Что об этом пространстве можете миру поведать, для начала хотя-бы перечислить его элементы и указать свойства. Даже на СУБД Вы смотрите глазами их создателей, а они ведь тоже не все видят, или не все показывают, как, например, в микросхемах.

Здесь сделаю небольшой повтор. Начинать следует с абстрактного множества А =. О нем почитать можно здесь. Для лучшего понимания сократим множество до 3 элементов, т.е. А =. Теперь выполним декартово умножение А×А =А 2 и явно перечислим все элементы декартова квадрата
А×А=<(a1, a1),(a1, а2),(a1, a3),(a2, а1),(a2, a2),(a2, a3),(a3, a1),(a3, a2),(a3, a3)>.
Получили 9 упорядоченных пар элементов из А×А, в паре первый элемент из первого сомножителя, второй — из второго. Теперь попробуем получить все подмножества из декартова квадрата А×А. Подмножества будут содержать разное количество пар: одну, две, три и так до всех 9 пар, включаем в этот список и пустое множество ∅. Сколько же получилось подмножеств? Много, а именно 2 9 = 512 элементов.

Отношения можно задавать в разном представлении:

Пространства бинарных отношений

Пространством бинарных отношений с множеством-носителем называется произвольное подмножество множества бинарных отношений заданных на. Рассмотрим основные пространства для отношений предпочтений (рис. 2.15).

Рисунок 2.15 Схема пространств бинарных отношений

Выявленные связи между пространствами используются для переноса задач принятия решений (ЗПР) из одних пространств в другие, где они могут быть решены более простым путем, а затем полученное решение возвращают в исходное пространство, где была сформулирована ЗПР.
Эти отношения представлены диаграммой на рис. 2.14. Пространства бинарных отношений (типы отношений) представлены рис. 2.15.

Отношения эквивалентности

Определение. Бинарное отношение σ ⊆ А×А, обладающее тремя свойствами рефлексивности, симметричности, транзитивности, называется, бинарным отношением эквивалентности (БОЭ). Обозначается отношение эквивалентности σ(х, у), (х, у)∊σ, хσу, х≈у. Удобно использовать матричное (табличное) представление отношения. Ниже на рис 2.24 приведено как раз матричное представление. Над множеством из 4-х элементов существует 15 БОЭ, которые все изображены.

Представление и анализ структуры отношений эквивалентности (n = 4)
Эквивалентность из бинарных отношений, пожалуй, самое распространенное БО. Редкая наука обходится без этого понятия, но даже тогда, когда эквивалентности используются в изложении каких-либо вопросов, бывает трудно понять, что в виду имел автор. Даже при корректном определении и перечислении свойств, присущих этому бинарному отношению – трудности восприятия остаются.

Начнем с примера об эквивалентностях, который иллюстрирует ограниченность их количества.

Пример 1. Пусть имеется три кубика. Составим список свойств, которыми наделены кубики и практическое использование которых (свойств кубиков) делает их как бы взаимозаменяемыми. Кубикам присвоим номера, а их свойства представим таблицей 1.

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

Рассмотрим множество из трех элементов А = <1,2,3>и получим для него все возможные разбиения на все части. ①1|2|3; ②12|3; ③13|2; ④ 1|23; ⑤123. Последнее разбиения на одну часть. Номера разбиений и БО в кружках.

Определение. Разбиением множества А называют семейство Аi, i = 1(1)I, непустых попарно непересекающихся подмножеств из А, объединение которых образует все исходное множество А=UАi, Аi∩Аj =∅, ∀ i ≠ j. Под-множества Аi называют классами эквивалентности разбиения исходного множества.

Это все разбиения множества (5 штук). Анализ БО показывает, что различных отношений эквивалентности тоже только 5 штук. Случайно ли это совпадение? Мы можем каждому разбиению сопоставить матрицу из девяти ячеек (3×3 = 9), в каждой из которых либо размещается упорядоченная пара элементов из множества А, либо ячейка остается пустой, если для соответствующей пары нет объекта. Строки и столбцы матрицы размечаются элементами множества А, а пересечению строка – столбец соответствует упорядоченная пара (i, j). В ячейку матрицы вписывается не пара, а просто единица или нуль, впрочем, нуль часто не пишут совсем.

Нет, совпадение не случайное. Оказывается, каждому разбиению множества взаимно однозначно соответствует БОЭ, при этом мощность множества может быть любой |A| = n.

Это отношение едва ли не самое частое по использованию в научном обороте, но совокупность свойств, реализуемых в этом отношении, сильно ограничивает его распространенность.
Так среди всех абстрактных бинарных отношений над множеством из трех элементов (всего их 2 9 = 512 отношений) только пять являются эквивалентностями — носителями требуемых свойств, менее одного процента.

Для |A| = 4 отношений существует 2 16 = 65536, но эквивалентностей лишь 15 штук. Это весьма редкий тип отношений. С другой стороны, отношения эквивалентности широко распространены в прикладных задачах. Везде, где имеются и рассматриваются множества самых различных объектов и различные разбиения таких множеств (не чисел) на части возникают отношения эквивалентности. Их можно назвать математическими (алгебраическими) моделями таких разбиений, классифицирующими множества объектов по различным признакам.

Решетка Р(4): все разбиения множества А = =

Минимальному разбиению соответствует отношение эквивалентности П15, которое называется равенством или единичным отношением. В каждом классе эквивалентности — единственный элемент. Разбиению множества А, включающему лишь само множество А, соответствует отношение эквивалентности, содержащее все элементы декартова квадрата А×А.

Ближайший тип к отношениям эквивалентности – отношения толерантности. Множество отношений толерантности содержит в себе все отношения эквивалентности. Для носителя А из трех элементов толерантностей 8. Все они обладают свойствами рефлексивности и симметричности.

При выполнении свойства транзитивности пять из восьми толерантностей преобразует в эквивалентности (рис. 2.24 и 2.25).

Определение. Совокупность классов [a]σ эквивалентности элементов множества А называется фактор-множеством (обозначается А/σ) множества А по эквивалентности σ.

Определение. Естественным (каноническим) отображением f: A→ А/σ называется такое отображение f, при котором f(а) = [a]σ.

Отношения толерантности и их анализ

Об этих БО ранее уже упоминалось, а здесь рассмотрим их подробнее. Всем известны понятия сходство, похожесть, одинаковость, неразличимость, взаимозаменяемость объектов. Они кажутся близкими по содержанию, но при этом не одно и то же. Когда для объектов указано только сходство, то невозможно разбить их на четкие классы так, что внутри класса объекты похожи, а между объектами разных классов сходства нет. В случае сходства возникает размытая ситуация без четких границ. С другой стороны, накапливание несущественных различий у сходных объектов может привести к совершенно непохожим объектам.

В предыдущей части мы обсудили содержательный смысл отношения одинаковости (эквивалентности) объектов. Не менее важной является ситуация, когда приходится устанавливать сходство объектов.

Пусть изучается форма геометрических тел. Если одинаковость формы объектов, например, кубиков, означает их полную взаимозаменяемость в определенной ситуации обучения, то сходство – это частичная взаимозаменяемость, (когда среди кубиков встречаются очень похожие на них параллелепипеды) т. е. возможность взаимной замены с некоторыми (допустимыми в данной ситуации) потерями.

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

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

В самом деле, будем рассматривать множество точек (х, у) на плоскости. Пусть величина d имеет значение меньшее порога разрешимости глаза, т. е. d – такое расстояние, при котором две точки, находящиеся на этом расстоянии, сливаются в одну, т.е. визуально неразличимы (при выбранном удалении плоскости от наблюдателя). Рассмотрим теперь n точек, лежащих на одной прямой и отстоящих (каждая от соседних) на расстоянии d. Каждая пара
соседних точек неразличима, но, если n достаточно велико, первая и последняя точки будут отстоять друг от друга на большое расстояние и заведомо будут различимы.

Традиционный подход к изучению сходства или неразличимости состоит в том, чтобы сначала определить меру сходства, а затем исследовать взаимное расположение сходных объектов. Английский математик Зиман, изучая модели зрительного аппарата, предложил аксиоматическое определение сходства. Тем самым свойства сходства стало возможным изучать независимо от того, как конкретно оно задано в той или иной ситуации: расстоянием между объектами, совпадением каких-то признаков или субъективным мнением наблюдателя.
Введем экспликацию понятия сходства или неразличимости.

Определение. Отношение Т на множестве M называется отношением толерантности или толерантностью, если оно рефлексивно и симметрично.

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

Ясно также, что поскольку одинаковость есть частный случай сходства, то эквивалентность должна быть частным случаем толерантности. Сравнивая определения эквивалентности и толерантности, убеждаемся, что так оно и есть. Философский принцип: «частное богаче общего» наглядно подтверждается. Дополнительное свойство – транзитивности делает часть отношений толерантности эквивалентностями. Двое близнецов бывают настолько одинаковыми, что без риска могут сдавать экзамены друг за друга. Однако если два студента только похожи, то такая проделка, хотя и осуществима, но рискованна.

Каждый элемент множества несет определенную информацию о похожих на него элементах. Но не всю информацию, как в случае одинаковых элементов. Здесь возможны разные степени информации, которую один элемент содержит относительно другого.

Рассмотрим примеры, где толерантность задается разными способами.

Пример 2. Множество M состоит из четырехбуквенных русских слов — нарицательных существительных в именительном падеже. Будем называть такие слова сходными, если они отличаются не более чем на одну букву. Известная задача «Превращение мухи в слона» в точных терминах формулируется так. Найти последовательность слов, начинающуюся словом «муха» и кончающуюся словом «слон», любые два соседних слова в которой сходны в смысле только что данного определения. Решение этой задачи:

муха — мура — тура — тара — кара — каре — кафе — кафр — каюр — каюк — крюк — крок — срок — сток — стон — слон.

Толерантность подмножеств (граней) означает наличие у них общих вершин.

Определение. Множество M с заданным на нем отношением толерантности τ называется пространством толерантности. Таким образом, пространство толерантности есть пара (M, τ).

Пример 4. Пространство толерантности Sp допускает обобщение на бесконечный случай. Пусть H — произвольное множество. Если SH – совокупность всех непустых подмножеств множества H, то отношение толерантности Т на SH задается условием: X Т Y, если X∩Y ≠ ∅. Симметричность и рефлексивность этого отношения очевидны. Пространство SH обозначается и называется «универсальным» пространством толерантности.

Пример 6. Рассмотрим пространство толерантности, компоненты которого принимают любые действительные значения.

В частности, это множество всех точек x = (a1, a2) декартовой плоскости. Толерантность двух точек означает совпадение у них хотя бы одной координаты. Значит, две толерантные точки находятся либо на общей вертикали, либо на общей горизонтали.

Отношения частичного порядка и их анализ

Упорядоченные множества – это множества с введенным на нем отношением порядка. Определение. Множество А и бинарное отношение порядка R на нем (≤) называется частично упорядоченным, если для отношения выполнены (как и в БОЭ) три условия (одно условие другое):

Элемент х∊А ЧУМ А покрывает элемент у∊А, если х > y и не существует z∊А такого, что х > z > y. Пара элементов х, у∊А называется сравнимой, если х ≥ у или х ≤ у.

Если в ЧУМ А всякая пара его элементов является сравнимой, то А называют линейно упорядоченным множеством или цепью.

Если же некоторое ЧУМ В состоит лишь из несравнимых друг с другом элементов, то множество В называют антицепью. Цепь в ЧУМ А называется насыщенной, если она не может быть вложена ни в какую другую цепь, отличную от себя.

Аналогично определяется насыщенная антицепь. Максимальной цепью (антицепью) называется цепь (антицепь), содержащая максимальное количество элементов.

Элемент m ЧУМ А называется минимальным, если в А нет элемента х∊А, отличного от m и такого, что х≤m. Элемент M ЧУМ А называется максимальным, если в А нет элемента х «большего», чем M, отличного от M и такого, что х ≥ M.

Элемент у∊А ЧУМ А называется наибольшим, если ∀ х∊ А х ≤ у. Элемент у∊ А ЧУМ А называется наименьшим, если ∀ х∊А х ≥ у. Для наибольшего и наименьшего элементов принято использовать обозначения 1 и 0 соответственно. Их называют универсальными границами. Всякое ЧУМ А имеет не более одного наименьшего и не более одного наибольшего элементов. В ЧУМ А допустимо несколько минимальных и несколько максимальных элементов
Изображать конечное ЧУМ А удобно диаграммой Хассе, которая представляет собой ориентированный граф, его вершины распределены по уровням диаграммы и соответствуют элементам из А, а каждая дуга направляется вниз и рисуется тогда и только тогда, когда элемент х∊А покрывает элемент у∊А.

Транзитивные дуги не изображаются. Уровни диаграммы Хассе содержат элементы одинакового ранга, т.е. связанные с минимальными элементами ЧУМ путями равной длины (по числу дуг).
Пусть В непустое подмножество ЧУМ А, тогда элемент х∊А называется точной верхней гранью (обозначается sup_AB) множества В, если х ≥ у для всех у∊В и, если из истинности соотношения z ≥ у для всех у∊В вытекает, что z ≥ х.

Точной нижней гранью (обозначается inf_AB) множества В называется элемент х∊А, если х ≤ у для всех у∊В и, если из условия z ≤ у для всех у∊ В вытекает, что z ≤ х.

Пример 7. Заданы два конечных числовых множества
А = <0,1,2,…,21>и B = <6,7,10,11>.

ЧУМ (А, ≤) представлено рис. 2.26.

Совокупность В Δ всех верхних граней для В называется верхним конусом для множества В. Совокупность В ∇ всех нижних граней для В называется нижним конусом для В.

Всякое подмножество ЧУМ также является ЧУМ относительно наследованного порядка. Если в множестве существуют наибольший и/или наименьший элементы, то они являются максимальным (минимальным соответственно). Обратное неверно. Булеан обладает единственным наименьшим (Ø) и единственным наибольшим элементами.

В приведенном множестве наименьший элемент нуль (0) и он совпадает с единственным минимальным элементом, а наибольшего элемента не существует. Максимальными элементами являются <19, 20, 21>. Точная верхняя грань для B = <6,7,10,11>есть элемент 21 (это наименьший элемент в верхнем конусе).

Общая ситуация. Пусть задано множество, мощность которого*******. Из всех бинарных отношений, возможных на этом множестве, выделим бинарные отношения предпочтения и связанные с ними отношения строгих частичных порядков.

Частичные порядки отличаются от строгих частичных порядков только тем, что содержат в своем составе дополнительные элементы (в матричном представлении – диагональные) (аi, ai ) = 1, i = 1(1)n, а число тех и других порядков в полном множестве отношений одинаково. До настоящего времени не найдены зависимости (формула, алгоритм), которые позволяли бы подсчитывать и перечислять при любом n число частичных порядков.

Разными авторами непосредственным подсчетом определены и опубликованы следующие результаты (табл. 2.12).

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

В таблице 2.12 показаны: n = |A| – мощность множества-носителя; вторая строка – количество всех бинарных отношений на множестве А; и далее

|Ин(n)| – количество классов неизоморфных отношений;
|Г(n)| – количество отношений частичного порядка;
|Гн(n)| – количество классов неизоморфны отношений частичного порядка;
|Гл(n)| = n! – количество отношений линейного порядка.

Как видим, в таблице для небольших n, например, Г(n=4) имеется всего 219, приводятся данные, значения которых с увеличением n очень быстро растут, что существенно усложняет их количественный (и качественный) непосредственный анализ даже с помощью ЭВМ.

Таблица ниже иллюстрирует возможность порождения Г(n=4) всех частичных порядков из пересечения каждого с каждым линейных частичных порядков. Но в этой ситуации возникают избыточные (повторяющиеся), которые при малых n можно отсечь вручную (пересчитать). Получаются 300 матриц, но ЧУМ среди них лишь 219. Общие формулы так и не были получены. На мировом уровне ситуация аналогичная, хотя мне не довелось видеть публикаций о перечислениях ЧУМ западных авторов. Наши алгоритмы вполне оригинальны и пионерские.

Приведу возможную схему решения задачи перечисления элементов пространства частичных порядков (n=4).

Множество строгих частичных порядков при лексикографическом упорядочении линейных порядков (n=4) порождается при их взаимном пересечении.

Несколько важных определений математики, для встречающихся часто в текстах понятий.

Определение. Замкнутый интервал – это множество вида ; открытый интервал не замкнут, и полуоткрытый интервал, т. е. множество вида

Источник

Количественные характеристики отношений

Теория частично упорядоченных множеств содержит ещё немало нерешенных проблем. Даже на вопрос о числе таких множеств, которые могут быть построены из заданного числа n элементов, не существует еще ответа, если n≥6. Прямыми подсчетами удалось лишь установить, что если S(n) — число частично упорядоченных множеств, то S(2) = 3, S(3)= 19, S(4) = 219, S(5) = 4231, а числа Sн(n) для неизоморфных множеств найдены только для n=4 и n=5 элементов: Sн(4) = 16 и Sн(5) = 63.

Мы научились вычислять количества отношений над большими множествами-носителями и перечислять отношения, но строгих формул даже для количества S(n) получить не удалось. Я вспоминаю это время как период интенсивного творческого роста своего и сотрудников, когда почти после каждой выдачи ЭВМ результатов и их анализа возникали идеи по модификации, совершенствованию модели, алгоритмов, вносились исправления для проверки очередных гипотез, но чего-то существенного (возможно мозгов) не хватало.

То, что удалось открыть (получить) привожу ниже по тексту. Кстати, результаты других зарубежных исследователей совпадали с нашими, но они сообщали только о количестве S(n) и не упоминали о перечислении частичных порядков.

Начинали мы с малого. Полный список бинарных отношений для любого n-множества-носителя известен и легко может быть получен. Отыскивался ответ на вопросы: сколько при заданном n существует отношений с фиксированным одним свойством, с парой свойств, с тройкой и т. д. Дело в том, что располагая этими данными, можно было строить не переборные, а прямые алгоритмы перечисления таких отношений, которые, следуя правилу «бритвы Оккама», не производят лишних сущностей.

Здесь дальше пойдет речь о получении таких результатов для бинарных отношений (БО).
Итак, имеется n-множество-носитель БО и полный список всех БО, а также список свойств БО:

— рефлексивность; антирефлексивность; частичная рефлексивность;
— симметричность; антисимметричность; асимметричность; несимметричность;
— транзитивность; антитранзитивность;
— слабый порядок; строгий порядок; частичный порядок; совершенный (линейный);
— толерантность;
— эквивалентность;
— цикличность;
— полнота.

Количественные характеристики типов бинарных отношений

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

Другой тип отношений возникает из отношений толерантности, если потребовать от таких отношений выполнимость расширенного списка свойств: симметричность, рефлексивность и транзитивность. Понятно, что возможно не все отношения толерантности окажутся транзитивными, но те, которые будут обладать набором трех названных свойств, образуют новый тип отношений, называемых эквивалентностями.

Множество отношений эквивалентности оказывается вложенным в множество отношений толерантности. Для примера в каталоге эти типы отношений выделены заливкой (8 толерантностей и только 5 из них эквивалентности). Возникает вопрос о количестве БО, обладающих набором свойств или одним из них.

Рефлексивность

Отношение α = на множестве A = <> является рефлексивным (обладает свойством рефлексивности), если каждая пара () удовлетворяет данному отношению. Здесь Å — график (не граф) отношения .

Другими словами, главная диагональ матрицы графика Å отношения заполнена единицами. На графе рефлексивного отношения все вершины имеют петли. Отношение является антирефлексивным, если ни для какого не выполняется . В этом случае матрица антирефлексивного отношения α на главной диагонали не имеет ни одной единицы, т.е. там размещаются нули, а соответствующий граф не имеет петель ни в одной вершине.

Наконец, отношение α является нерефлексивным, если для некоторого выполняется, а для других не выполняется. Такие отношения будем считать частично рефлексивными. Матрица нерефлексивного отношения на главной диагонали содержит частично единицы, частично – нули. Граф такого нерефлексивного отношения имеет петли не во всех вершинах.

Классическим примером рефлексивного отношения является главная диагональ матричного представления, единичное (E = Δ) отношение, т.е. отношение равенства (в каталоге № 68). График этого отношения образован точками (парами), лежащими на главной диагонали матрицы и соответствующими парами , никаких других точек график этого отношения не содержит.

Матричное представление этого отношения соответствует единичной матрице (E). Граф диагонального отношения образован вершинами, соответствующими элементам из множества А, которым приписаны петли. Часто диагональное отношение обозначают символом .

В случае рефлексивного отношения, соответствующий ему граф также является рефлексивным, в случае антирефлексивного отношения его граф антирефлексивный. Если для некоторого отношения α известно, что оно рефлексивное, то дополнение ᾱ всегда антирефлексивное, и .

Для антирефлексивного отношения β справедливо .

Пример 1. Отношение ≤ (не больше) на множестве N является рефлексивным, а отношение на множестве A является симметричным (обладает свойством симметрии относительно прямой, совпадающей с главной диагональю графика Å), если для некоторой пары из следует . Другими словами, для любой пары выполняется либо в обе стороны, либо совсем не выполняется.

На графе симметричного отношения, если пара вершин i и j связана дугой (i, j), то она обязательно связана и дугой (j, i). Граф симметричного отношения является симметричным ориентированным или просто неориентированным, обыкновенным графом.

Отношение α является антисимметричным, если из и следует что i=j.

Матрица антисимметричного отношения содержит не обязательно все единицы на главной диагонали и содержит единицы в одной из двух симметричных относительно главной диагонали позиций: над диагональю либо под диагональю. Граф этого отношения образован вершинами с петлями для всех или некоторых из них и, если пара вершин (i, j) в графе связана, то всегда дугой только одного направления. Заметим, что для симметричного и антисимметричного отношения некоторые диагональные точки могут либо включаться в него, либо нет.

Если антисимметричное отношение не содержит ни одной диагональной точки, то говорят, то такое отношение является асимметричным, т.е. оно всегда антирефлексивно.

Пример 2. Отношение (≤) на множестве N – является антисимметричным, а отношение ( содержит и любые последовательности $» data-tex=»inline»/>, образованные перестановкой членов множества Х.

Заметим также, что асимметричное отношение всегда антирефлексивно; нерефлексивное и транзитивное бинарное отношение всегда асимметрично. Для практики и выполнения вычислений интерес представляет количество отношений, обладающих определенным свойством, связанным с симметрией графика. Выполним подсчет таких отношений для произвольного множества А мощностью |A| = n.

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

Множества отношений во всех классах имеют одинаковое устройство, отличаются только числом и составом диагональных точек, все разнообразие которых определяется числом . Определим состояние диагонали отношения при фиксированном n количеством и составом точек на ней и принадлежащих конкретному отношению. Ясно, что при фиксированном множество состояний заполненности ячеек диагонали определяется булеаном , где ∆ – полное множество точек диагонали графика декартова квадрата мощностью |∆| = n.

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

Будем называть все промежуточные состояния с одной диагональной точкой, с двумя и так далее частичной рефлексивностью k-го порядка k=0(1)n, а отношения такого вида частично рефлексивными. Так частично рефлексивное отношение порядка ноль – это антирефлексивное отношение, а частично рефлексивное отношение порядка n- это просто рефлексивное отношение.

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

Пусть рассматриваются отношения рефлексивные и симметричные. Симметричность отношения определяется наличием пар точек в нем, которые расположены в матрице отношения симметрично относительной диагонали. При произвольном n таких пар существует . Обозначим множество этих пар символом S.

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

Ниже в табл. 1 приведены значения числа толерантных отношений для начальных значений n из отрезка натурального ряда чисел.

Таблица 1. Количества толерантных БО

где n число диагональных точек отношения. В табл. 2 приводятся значения |SM| для некоторых n.

Таблица 2. Количества симметричных БО

Теперь перейдем к подсчету асимметричных отношений, множество которых будем обозначать через AS. Эти отношения характеризуются тем, что в них отсутствуют все точки диагонали и ни одна из клеток матрицы отношения, лежащих вне диагонали, не имеет симметричной. Другими словами, это множество антирефлексивных и антисимметричных отношений.

Мощность этого множества может быть определена из выражений

где К =.

Получим приведенную формулу для подсчета мощности множества AS — асимметричных отношений при заданной мощности носителя |А| = n. По определению все отношения множества AS антирефлексивны, следовательно, главная диагональ в матрицах отношений пуста, а единичные элементы могут размещаться лишь в половине оставшихся позиций матрицы, т.е. в клетках.

Итак, предположим, что асимметричное отношение содержит k-элементов (точек, упорядоченных пар) 0 ≤ k ≤ . Количество отношений с таким числом элементов, очевидно, будет равно числу сочетаний из по k.

При этом с каждым из k элементов свяжем пару симметричных позиций: одна над главной диагональю матрицы, другая – под диагональю.Поскольку в каждой паре элемент может быть в одной из двух позиций, то для размещения k элементов возникает булеан возможностей.

Таким образом, – это число выборов k пар позиций из имеющихся пар в матричном представлении отношений, а – количество возможностей расставить k элементов по позициям в каждой паре. Количество отношений, содержащих k элементов определяется как произведение числа выборов пар позиций на количество вариантов расстановки этих k элементов, т.е. .

Полное же число отношений в множестве AS получается при суммировании полученных произведений по всем значениям k от нуля до максимально допустимого K =, т.е.

где К =.

Пример 3. Пусть мощность множества носителя |А| = 5. Подсчитаем по найденной формуле число асимметричных отношений. Определим значение верхнего предела К в сумме, К ==10. Данные подсчета слагаемых суммы приведены в табл. 3.

Существует другой способ подсчета мощности множества AS. Он основан на подсчете числа отображений множества пар симметричных позиций во множество состояний, в котором может быть каждая такая пара. В асимметричном отношении имеется пар позиций.

Каждая позиция в паре клеток может быть занята 0 или 1, но для пары позиций имеются S = 3 состояния, которые обозначим следующим образом:

— 1, если элемент (1) помещен над диагональю;
— 2, если элемент (1) помещен под диагональю;
— 3, если обе позиции пусты (заняты нулями).

Таким образом, пара симметричных позиций (в матрице отношения) может быть в каждом
отношении в одном из трех состояний. Формула для подсчета всех возможных отображений множества пар позиций (обозначим его символом K ) в множество S состояний имеем:
|AS| =|S|^<|K|>$» data-tex=»inline»/>

Пример 4. Для условий предыдущего примера имеет вид |A| = 5, K=|K| = |S| = 3, тогда, .

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

где К =

Приведем в табл. 4 числа асимметричных отношений |AS| для небольших значений n.

Таблица 4. Количества асимметричных БО

Имея формулу для определения числа асимметричных отношений, можно получить другую – для подсчета числа антисимметричных отношений, так как наличие или отсутствие диагональных точек не меняет свойства антисимметричности отношения.

Итак, обозначим множество антисимметричных отношений символом ANS, тогда мощность этого множества определится по формуле

где К =

Ниже приводится табл. 5, содержащая значения (ANS) при n = 3(1)5.

Таблица 5. Количества антисимметричных БО

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

Транзитивность (лат. Transitivus – переходный, от transitus – переход)

Другими словами, для транзитивного отношения из наличия в его составе элементов () и () следует, что оно содержит, обязательно и элемент ( ). Для графа отношения это свойство означает, что если пара вершин ( ) связана ориентированным путем, проходящим через вершину k и образованным 2-мя последовательными дугами ( ), ( ), то эти же вершины непосредственно связаны и единственной дугой (). Для элементов матрицы [] транзитивного отношения α из следует .

Определение свойства транзитивности для бинарных отношений предполагает, что отношение содержит не менее трех элементов (упорядоченных пар). А как это свойство проявляется в отношениях одноэлементных, пустых или содержащих только два элемента?

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

Например, пусть ( )є α и ( )є α. Сформулированное определение требует: чтобы отношение α было транзитивным, обязательно наличие в нем третьей пары (дуги), а именно, ( ), но так как ее нет, то свойство транзитивности для α не выполнено.

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

Транзитивным отношение будет и в случае, когда две пары не имеют общих элементов. Примерами транзитивных отношений являются:« равенство » (=), так как из i = k, k = j вытекает i = j; « i больше j»; в геометрии – «параллельность прямых». Примеры не транзитивных отношений: «перпендикулярность прямых» в геометрии; « i не равно j».

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

Для транзитивного отношения α отношение также всегда является транзитивным. Пересечение произвольного числа транзитивных отношений является транзитивным отношением. Если рассматривать отношение ᾰ, которое является пересечением всех транзитивных отношений, содержащих отношение α, то ᾰ называется транзитивным замыканием отношения α.

Транзитивное замыкание ᾰ может быть построено для любого отношения α в соответствии с правилом из следует:

.

Отношение ᾰ является наименьшим транзитивным отношением, содержащим α. Если α транзитивно, то оно совпадает со своим транзитивным замыканием α=ᾰ и наоборот.

При изображении транзитивного бинарного отношения ориентированным графом можно изображать не весь орграф, а лишь его транзитивный остов, т.е. не изображаются дуги, соединяющие начало и конец каждого маршрута длиной более единицы. В этом случае говорят, что для отношения α взят транзитивный остов графа. Эта операция по существу является обратной к операции транзитивного замыкания, при которой начало и конец каждой цепи соединяются дугой.

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

Так является транзитивным относительно при выполнении условий:

1) из следует ;
2) из следует .

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

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

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

Композиция транзитивного отношения α с собой удовлетворяет соотношению α·α ⊆ α. Отношение α является отрицательно транзитивным (нетранзитивным) в том случае, если транзитивным является дополнение к нему, т.е. ᾱ. В матрице такого отношения [ ] из и следует . Отрицательная транзитивность α не исключает того, что само α может быть также транзитивным.

В этом случае говорят, что α является сильно транзитивным отношением. Элементы матрицы [ ] такого отношения характеризуются тем, что из следует , a из следует .

Наряду с сильно транзитивными отношениями рассматриваются слабо транзитивные (псевдотранзитивные), к которым относятся те из отношений, где выполняются условия из и следует . Из асимметрии и отрицательной транзитивности следует его транзитивность.

Отношение α является транзитивно полным, если для любых δ из ,
следует сравнимость и , т.е. выполняются либо либо .

Цикличность

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

Отношение = является циклическим, если из элементов множества А может быть образована хотя бы одна цепочка вида произвольной длины δ. График Å транзитивного замыкания для циклического отношения содержит, по крайней мере, одну пару (), а для ациклического отношения α не содержит ни одной такой пары.

Отношение = является ациклическим, если для любого δ≥1 выполняется условие из следует . В матрице[] ациклического отношения из следует i≠j. Ациклическое отношение всегда асимметрично, но обратное не верно. Другими словами, если некоторые вершины и графа α ациклического отношения соединены путем; то в графе нет дуги ().

Классическими примерами графов с таким свойством являются транзитивные турниры. Вершины таких графов допускают перенумерацию, при которой для любой дуги () номер вершины j больше, чем вершины i.

Если α – антирефлексивное транзитивное бинарное отношение, то оно ациклично. Из ацикличности и транзитивной полноты отношения следует его транзитивность.

Полнота

Свойство полноты (совершенства, линейности). Все множество отношений разделяет на неполные и полные, среди которых в свою очередь выделяются сильно полные. Будем иллюстрировать свойство полноты отношений, рассматривая графы отношения.

Граф полного отношения – полный, т.е. любые две его вершины непосредственно связаны хотя бы одной дугой, т.е. являются смежными. Поскольку каждой дуге в графе соответствует точка (элемент, пара) графика отношения, то на основании изложенного можно сформулировать определение.

Отношение = является полным (совершенным, линейным) тогда и только тогда, когда все элементы множества А являются сравнимыми или равны между собой. Таким образом, полное отношение рефлексивно. Другими словами, для любых двух элементов и справедливо .

Если в отношении α найдется хотя бы одна пара , несравнимых и неравных между собой элементов, то такое отношение является неполным. Для любого полного отношения α справедливо или из следует . Бинарное отношение α полно тогда и только тогда, когда , т.е. когда его асимметричная часть совпадает с двойственным (п.9) отношением.

Бинарное отношение α является сильно полным, когда его график совпадает с A×A. Граф такого отношения является полным графом, в котором каждая пара вершин связана ребром, а каждая вершина имеет петлю. Такой граф называют сильно полным графом. Для полного отношения α всегда выполняются соотношения и . Отношение всегда полно.

Если и полные отношения, то полно. В матрице [] полного отношения или для любых i, j, либо верны оба равенства. Отношение α является слабо полным (слабосвязным), если для любых таких, что , либо , либо .

В матрице [] слабо полного отношения для любых i ≠ j, либо , либо , либо верны оба равенства. Отношение α является транзитивно полным, если для произвольного n из следует сравнимость т.е. или .

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

Если на одну линию (прямую) в матрице отношения попадают две и более пар симметричных позиций, то число линий, тем не менее, остается равным числу таких пар позиций. Полное число пар позиций при произвольном n определяется как .

Итак, в матрице для произвольного отношения над множеством А имеется множество L параллельных отрезков (линий). Обозначим концевые позиции отрезков (линий) символами Л – левая и П – правая. Имеется также |L| фишек, которые можно помещать в позиции на концах линий. Задача заключается в том, чтобы определить число способов, которыми можно было бы расставить |L| фишек так, чтобы на каждой линии было не менее одной фишки.

Понятно, что задача может быть сведена к определению числа F отображений f: L → π множества L линий в множество π позиций (п = <Л, П>). Известно, что число таких отображений определяется формулой . Конкретное отображение (образ) может иметь вид последовательности индексов для | L | позиций. Символу Л соответствует позиция под главной диагональю, а символу П, симметричная ей над диагональю.

Из определения полного отношения следует, что его график содержит не менее К точек, К = , расположенных: так, что все линии оказываются занятыми, хотя бы одной фишкой. Число k точек графика, дополнительных к минимально необходимому числу, может пробегать значение k = 0(1)К =.

При каждом фиксированном числе k точек множество выборов позиций, в которых они могут размешаться определяется значением , где К – множество незанятых позиций. Так как k дополнительных точек заполняют полностью k линий, то для обеспечения свойства полноты отношения остается заполнить К — k позиций фишками (точками из множества минимально необходимого), и число таких заполнений равно .

Выборы позиций для k дополнительных точек и способы заполнения фишками К-k линий являются независимыми. Следовательно, общее число возможностей размещения К + k точек в 2∙К позициях так, чтобы все линии были заняты хотя бы одной точкой, определится выражением

Если просуммировать это выражение по, то получим число полных отношений, которое не зависит от ситуации с размещением диагональных точек. Другими словами, это число частично рефлексивных полных отношений, например, антирефлексивных и полных рефлексивных и полных и т.п.

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

.

Для отношений с тремя обязательными свойствами

Для отношений эквивалентности с тремя обязательными свойствами. Имеется замечательный результат: каждому отношению эквивалентности над множеством из n элементов взаимно однозначно соответствует разбиение этого множества. Число таких отношений определяется формулой

, где S(n, m) — число Стирлинга 2-го рода, Bn — число
Белла или в рекуррентной форме

Для упорядоченных множеств (частичных порядков) подобные формулы не открыты и их число определяется непосредственными вычислениями, т.е. моделированием. Для малых значений n данные приведены в таблице

Таблица 6. Количественные характеристики бинарных отношений

В таблице 6. показаны: n = |A| – мощность множества-носителя;
– количество всех бинарных отношений на множестве А;
|Ин(n) | – количество классов неизоморфных отношений;
|Г(n)| – количество отношений частичного порядка;
|Гн(n)| – количество классов неизоморфны отношений частичного по-рядка;
|Гл(n)| = n! – количество отношений линейного порядка.

Заключение

В работе выполнен детальный анализ основных свойств и устройства бинарного отношения, на основе которого удалось получить количественные характеристики для БО с одним и более свойствами. Найдены и приведены оригинальные соотношения для количества некоторых типов отношений с двумя и тремя обязательными свойствами. Эти результаты открывают возможность моделирования и изучения БО и отношений более высокой арности.

Источник