Какими свойствами обладает отношение порядка

Свойства отношений:

1) рефлексивность;

2)симметричность;

3)транзитивность.

4)связанность.

Отношение R на множестве Х называется рефлексивным, если о каждом элементе множества Х можно сказать, что он находится в отношении R с самим собой: хRх. Если отношение рефлексивно, то в каждой вершине графа имеется петля. И обратно, граф, каждая вершина которого содержит петлю, представляет собой граф рефлексивного отношения.

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

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

Не обладает свойством рефлексивности и отношение «длиннее» для отрезков, «больше на 2» для натуральных чисел и др.

Отношение R на множестве Х называется антирефлексивным, если для любого элемента из множества Х всегда ложно хRх: .

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

Отношение R на множестве Х называется симметричным, если выполняется условие: из того, что элемент х находится в отношении с элементом y, следует, что и элемент y находится в отношении R с элементом х: xRyyRx .

Граф симметричного отношения обладает следующей особенностью: вместе с каждой стрелкой, идущей от х к y, граф содержит стрелку, идущую от y к х (рис. 35).

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

Существуют отношения, которые не обладают свойством симметричности.

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

Отношение R называют антисимметричным, если для любых элементов х и y из истинности xRy следует ложностьyRx: : xRyyRx.

Кроме отношения «длиннее» на множестве отрезков существуют и другие антисимметричные отношения. Например, отношение «больше» для чисел (если х больше у, то у не может быть больше х), отношение «больше на» и др.

Существуют отношения, которые не обладают ни свойством симметричности, ни свойством антисимметричности.

Отношение R на множестве Х называют транзитивным, если из того, что элемент х находится в отношении R с элементом y, а элемент y находится в отношении R с элементом z, следует, что элемент х находится в отношении R с элементом z: xRy и yRzxRz.

Граф транзитивного отношения с каждой парой стрелок, идущих от х к y и от y к z, содержит стрелку, идущую от х к z.

Свойством транзитивности обладает и отношение «длиннее» на множестве отрезков: если отрезок а длиннее отрезка b, отрезок b длиннее отрезка с, то отрезок а длиннее отрезка с. Отношение «равенства» на множестве отрезков также обладает свойством транзитивности: (а=b, b=с)(а=с).

Существуют отношения, которые не обладают свойством транзитивности. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку b, а отрезок b перпендикулярен отрезку с, то отрезки а и с не перпендикулярны!

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

Отношение R на множестве Х называется связанным, если для любых элементов х и y из данного множества выполняется условие: если х и y различны, то либо х находится в отношении R с элементом y, либо элемент y находится в отношении R с элементом х. С помощью символов это определение можно записать так: xy xRy или yRx.

Например, свойством связанности обладает отношение «больше» для натуральных чисел: для любых различных чисел х и y можно утверждать, либо x>y, либо y>x.

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

Существуют отношения, которые не обладают свойством связанности. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа х и y, что ни число х не является делителем числа y, ни число y не является делителем числа х (числа 17 и 11, 3 и 10 и т.д.).

Рассмотрим несколько примеров. На множестве Х={1, 2, 4, 8, 12} задано отношение «число х кратно числу y». Построим граф данного отношения и сформулируем его свойства.

Про отношение равенства дробей говорят, оно является отношением эквивалентности.

Отношение R на множестве Х называется отношением эквивалентности, если оно одновременно обладает свойством рефлексивности, симметричности и транзитивности.

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

В рассмотренном выше отношении «равенства дробей», множество Х разбилось на три подмножества: {; ; }, {;}, {}. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х, т.е. имеем разбиение множества на классы.

Итак, если на множестве Х задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества – классы эквивалентности.

Так, мы установили, что отношению равенства на множестве
Х={ ;; ; ; ; } соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей.

Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему?

Во-первых, эквивалентный – это значит равносильный, взаимозаменяемый. Поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности {; ; }, неразличимы с точки зрения отношения равенства, и дробь может быть заменена другой, например . И эта замена не изменит результата вычислений.

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

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

Другим важным видом отношений являются отношения порядка. Рассмотрим задачу.На множестве Х={3, 4, 5, 6, 7, 8, 9, 10} задано отношение «иметь один и тот же остаток при делении на 3». Это отношение порождает разбиение множества Х на классы: в один попадут все числа, при делении которых на 3 получается в остатке (это числа 3, 6, 9). Во второй – числа, при делении которых на 3 в остатке получается 1 (это числа 4, 7, 10). В третий попадут все числа, при делении которых на 3 в остатке получается 2 (это числа 5, 8). Действительно, полученные множества не пересекаются и их объединение совпадает с множеством Х. Следовательно, отношение «иметь один и тот же остаток при делении на 3», заданное на множестве Х, является отношением эквивалентности.

Возьмем еще пример: множество учащихся класса можно упорядочить по росту или возрасту. Заметим, что это отношение обладает свойствами антисимметричности и транзитивности. Или всем известен порядок следования букв в алфавите. Его обеспечивает отношение «следует».

Отношение R на множестве Х называется отношением строгого порядка, если оно одновременно обладает свойствами антисимметричности и транзитивности. Например, отношение «х<y».

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

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

Множество Х называется упорядоченным, если на нем задано отношение порядка.

Например, множество Х={2, 8, 12, 32} можно упорядочить при помощи отношения «меньше» (рис. 41), а можно это сделать при помощи отношения «кратно» (рис. 42). Но, являясь отношением порядка, отношения «меньше» и «кратно» упорядочивают множество натуральных чисел по-разному. Отношение «меньше» позволяет сравнивать два любых числа из множества Х, а отношение «кратно» таким свойством не обладает. Так, пара чисел 8 и 12 отношением «кратно» не связана: нельзя сказать, что 8 кратно 12 либо 12 кратно 8.

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

Источник

Бинарное отношение R на множестве X называется отношением порядка, если имеют место

Транзитивность: ;
Антисимметричность: .

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

Рефлексивно: .

Напротив, отношение строгого порядка

Антирефлексивно (или иррефлексивно): .

Отношение порядка называется полным (линейным), если любые два элемента множества так или иначе связаны этим отношением, т.е.:

Полнота: .

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

Рефлексивное, транзитивное, антисимметричное отношение называется частичным порядком. А рефлексивное, транзитивное (но не обязательно антисимметричное!) отношение называется квазипорядком (или предпорядком).

Обычно отношение строгого порядка (полного или частичного) обозначается знаком <, а отношение нестрогого порядка — знаком .

Знаки < и > изобретены Томасом Гарриотом (1560-1621).

БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ПОРЯДКА

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

1. Что такое порядок?

Порядок играет огромную роль в нашей жизни. Люди на протяжении всей истории пытались упорядочить отношения между собой, окружающие явления. Без порядка невозможно представить жизнь человека. Попробуйте представить общество, в котором царит анархия или словарь, в котором слова расположены хаотично. Но что такое порядок? С некоторыми упорядочениями мы настолько свыклись, что часто их просто не осознаем, как, например, грамматический порядок слов в предложении. В данной статье дано формальное определение порядка, которое используется в математике.

Определение 1.1. Бинарное отношение a на множестве X называется отношением порядка, если оно транзитивно:

и антисимметрично:

Пример 1.1. Рассмотрим отношение “старше” на множестве людей. Очевидно, что оно транзитивно и антисимметрично, и, следовательно, является отношением порядка.

Пример 1.2. Иерархия животных, построенная по этапам эволюции, является отношением порядка (рис.1).

Рис. 1. Основные этапы эволюции эукариотических организмов

Определение 1.2. Множество X с определенным на нем отношением порядка называется упорядоченным множеством и обозначается .

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

Так, например, на рисунке 2 приведен ориентированный граф, представляющий отношение = {(a, a), (a, b), (a, c), (b, c)} на множестве M = {a, b, c, d}.

Рис. 2. Граф упорядоченного множества

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

Площадь	Россия	США	Франция	Англия
Население	США	Россия	Франция	Англия
Плотность населения	Англия	Франция	США	Россия

Рис. 3. Три способа упорядочения

На рисунке 4 приведены ориентированные графы, представляющие отношения “делится” и “меньше” на множестве M = {1, 2, 3, 4} натуральных чисел.

Рис. 4. Графы отношений “делится” (а) и “меньше” (б) на множестве {1,2,3,4}

2. Разновидности отношений порядка

Определение 2.1. Отношение порядка a называется отношением нестрогого порядка на множестве X, если a рефлексивно:

Отношение нестрогого порядка обычно обозначается символом . Если , то говорят, что “элемент x предшествует элементу y” или “y следует за x“.

Пример 2.1. Отношение на множестве действительных чисел является отношением нестрогого порядка.

Пример 2.2. На совокупности подмножеств некоторого универсального множества U отношение является отношением нестрогого порядка.

Пример 2.3. Отношение подчиненности в учреждении является нестрогим порядкомна множестве сотрудников учреждения.

Пример 2.4. Отношение (m делит n) на произвольном подмножестве натуральных чисел является нестрогим порядком. На рисунке 5 приведен граф, соответствующий упорядоченному множеству

Рис. 5. Граф нестрого упорядоченного множества

Пример 2.5. Тождественное отношение является как отношением эквивалентности, так и отношением нестрогого порядка.

Определение 2.2. Два элемента называются сравнимыми элементами упорядоченного множества X, если либо , либо .

Несравнимыми элементами в упорядоченном множестве из примера 4 являются, например, элементы 7 и 2, 2 и 3, 3 и 7.

Определение 2.3. Отношение порядка a называется отношением строгого порядка на множестве X, если a антирефлексивно:

Отношение строгого порядка обозначается символом <.

Пример 2.6. Пусть f и g – функции с одинаковыми областями определения. Определим отношение > следующим образом: f > g, если для любого x из области определения функции f(x) > g(x). Очевидно, что данное отношение является отношением строгого порядка.

Для функций f и g, изображенных на рисунке 6, имеет место соотношение f > g. Пары функций f и h, а также g и h несравнимы.

Рис. 6. Три функции

Пример 2.7. Алфавитный порядок является отношением строгого порядка на множестве букв.

Пример 2.8. Пусть на множестве X задано отношение строго порядка . Как можно задать отношение строгого порядка на множестве , то есть, как сравнивать пары элементов из множества X? Один из возможных вариантов состоит в следующем. На множестве X определим отношение условием:

Отношение является строгим порядком.

Пример 2.9. Другой способ задания строгого порядка на множестве состоит в следующем. Будем считать, что выполнено соотношение (a, b) (c, d), если

Это отношение порядка называется лексикографическим. В общем случае оно определяется следующим образом. Для слов v и w одинаковой длины полагается v < w, если существует такой номер k, что , , …, , , где – i-ые буквы слов v и w соответственно. Для слов и (k > ) разной длины считается v < w, если или , и w < v, если . Такой способ упорядочения используется в словарях. В этом порядке, например:

детство < отрочество < юность,

институт < школа < ясли,

12 < 123 < 4.

Как уже отмечалось, упорядоченные множества удобно изображать в виде графов. При этом если – отношение строго порядка, то граф отношения a не содержит циклов. Верно и обратное: для любого графа G без циклов существует отношение a строгого порядка такое, что граф, ассоциированный с данным отношением, совпадает с транзитивным замыканием графа G. (Транзитивным замыканием графа G называется граф, полученный из графа G добавлением дуг, связывающих каждую вершину a с вершинами, достижимыми из a.) Действительно, пусть G – граф без контуров. Определим на множестве M вершин этого графа отношение , если существует путь по направлению дуг, ведущий из x в y. Легко видеть, что ввиду отсутствия циклов отношение является строгим порядком.

Определение 2.4. Множество X с бинарным отношением называется связным, если для любых двух различных элементов x и y из X либо , либо .

Определение 2.5. Связное отношение порядка на множестве X называется отношением линейного порядка.

Пример 2.10. Лексикографический порядок слов в словаре является линейным порядком.

Пример 2.11. Отношение включения на множестве фигур линейным порядком не является (рис. 7).

Рис. 7. Две несравнимые фигуры

Пример 2.12. Отношение “старше” на множестве людей является линейным порядком.

Пример 2.13. Рассмотрим множество людей. Их можно упорядочить различным образом, например, по росту (рис. 8).

Рис. 8. Шеренга

Упорядочение элементов множества X с помощью отображения его элементов на какое-нибудь упорядоченное множество Y – довольно типичный пример определения порядка.

Соответствующий общий прием упорядочения некоторого множества состоит в следующем. Пусть на множестве X определена инъективная функция

f: X ® R,

принимающая вещественные числовые значения. Зададим отношение < на X условием: x < y, если f(x) < f(y). Так определенное отношение < антирефлексивно, так как не может быть f(x) < f(x). Транзитивность и антисимметричность отношения < столь же очевидна. Наконец, для любой пары различных элементов x, y из X верно либо f(x) < f(y), либо f(y) < f(x), так как f – инъекция. Значит порядок < является линейным. Функция f взаимно однозначно отображает наше множество X на некоторое подмножество множества R вещественных чисел, так что соотношение x < y для любых элементов множества X равносильно неравенству f(x) < f(y).

Определение 2.6. Пусть на множестве X задано отношение строгого порядка <. Элемент x О X такой, что для всякого y из X, не совпадающего с x, выполнено соотношение x < y (x > y) называется наименьшим (наибольшим).

Определение 2.7. Пусть на множестве X задано отношение строго порядка <. Тогда элемент называется минимальным (максимальным) в упорядоченном множестве <X, < >, если не существует никакого элемента y, для которого y < x (соответственно y > x).

Если, как обычно, в случае x < y проводить стрелку от x к y, то в графе отношения минимальный элемент – это тот, в который не входят стрелки, а максимальный – из которого не выходят стрелки.

В случае линейного строго порядка минимальный элемент x обладает тем дополнительным свойством, что для всякого выполнено x < y. Тем самым для случая линейных порядков понятие минимального элемента совпадает с понятием наименьшего элемента. В общем случае может оказаться так, что элемент x минимален, но не находится в соотношении x < y с какими-то иными элементами. Например, на рисунке 5 элемент 2 является минимальным, но не сравним с элементами 3 и 7.

Чтобы понять различие между минимальным и наименьшим элементами, рассмотрим пример.

Пример 2.14. На рисунке 9 изображена диаграмма упорядоченного множества, в котором нет ни наименьшего, ни наибольшего элементов, но в то же время есть ровно 1 минимальный и ровно 1 максимальный элемент.

Рис.9. Упорядоченное множество

Рассмотрим подробнее конечные строго упорядоченные множества.

Лемма 2.1. Если на конечном (непустом) множестве X задан линейный строгий порядок, то существует наименьший элемент, и он единственен.

Доказательство. Возьмем произвольный элемент . Если – наименьший элемент, то существование искомого элемента доказано. Если нет, то поскольку < – линейный строгий порядок, существует такой элемент , что . Опять же либо – наименьший, либо существует , такой, что . Будем продолжать это процесс. Предположим, что уже выбрано n + 1 элементов, для которых

В силу транзитивности ясно, что при i > j. Значит, в силу антирефлексивности, все выбранные элементы попарно не равны. Стало быть, ввиду конечности множества X процесс выбора должен прерваться за конечное число шагов. Элемент , выбранный на последнем шаге, будет, очевидно, искомым. Итак, для любого выполнено . Покажем, что этот элемент единственен. В самом деле, пусть существует другой элемент такой, что, для всякого . Тогда одновременно выполняется и , что невозможно в силу антисимметричности. Лемма доказана.

Теорема 2.1. Пусть дано отношение линейного строгого порядка < на конечном множестве X. Тогда на X можно выбрать такую нумерацию , что соотношение будет выполняться в том и только в том случае, когда i < j.

Доказательство. Пусть – наименьший элемент во множестве X, выбранный согласно лемме 1. Обозначим через множество . Обозначим через наименьший элемент множества . Ясно, что . Удалим из элемент и оставшееся множество обозначим через . Его наименьший элемент удовлетворяет условию: . Процедура нумерации уже ясна: перебирая по указанному методу последовательно все элементы из X, мы их выстроим в цепочку:

где p – количество элементов в X. В силу транзитивности и антисимметричности ясно, что в том и только в том случае, когда i < j. Теорема доказана.

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

С отношением порядка непосредственно связано отношение доминирования.

Определение 2.8. Пусть – упорядоченное множество, x и y – его элементы. Будем говорить, что x доминирует над y, если , но не существует такого элемента z О X, что .

С помощью отношения доминирования можно ввести другой наглядный способ изображения упорядоченных множеств – диаграммы Хассе. На диаграммах каждый элемент изображается точкой на плоскости, и если y доминирует над x, то точки x и y соединяют отрезком, причем точку, соответствующую x, располагают ниже y.

Рассмотрим три отношения частичного порядка и построим для них диаграммы Хассе.

Пример 2.15. Пусть A = {1, 2, 3}. На множестве всех подмножеств множества A рассмотрим отношение “быть подмножеством”. Диаграмма этого упорядоченного множества приведена на рисунке 10(а).

Пример 2.16. Пусть X = {1, 2, 3, 5, 6, 10, 15, 30}. Введем на этом множестве отношение “делится”. Диаграмма этого упорядоченного множества приведена на рисунке 10(б).

Пример 2.17. На множестве X = {1, 2, 3, 4, 5, 6, 7, 8} рассмотрим отношение линейного порядка <. Его диаграмма изображена на рисунке 10(в).

Рис. 10. Диаграммы Хассе

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

Определение 2.9. Два упорядоченных множества и называются изоморфными, если существует биекция , сохраняющая отношение порядка. Иными словами, тогда и только тогда, когда , где и – отношения порядка, заданные на множествах X и Y соответственно.

Упорядоченные множества, рассмотренные в примерах 1 и 2 изоморфны.

Теорема 2.2. Всякое нестрого упорядоченное множество изоморфно некоторой системе подмножеств множества X, нестрого упорядоченной отношением включения.

Доказательство. Для каждого элемента рассмотрим множество . Тогда и – совокупность всех таких подмножеств. Докажем, что эта система подмножеств, нестрого упорядоченная отношением включения, изоморфна . Рассмотрим отображение такое, что . Тогда – биекция. Действительно, если , то, поскольку , в силу рефлексивности , имеем и . Аналогично получаем и в силу антисимметричности имеем a = b, т. е. отображение инъективно. Кроме того, сюръективно, так как у любого подмножества есть прообраз a. Докажем теперь, что отображение сохраняет отношение частичного порядка. Пусть . Тогда для любого из в силу транзитивности отношения следует , а значит, и . Если , то, поскольку , имеем , поетому .

Операции над отношениями порядка

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

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

Возьмем два отношения и . Каждому из них соответствует некоторое множество пар (подмножества и ).

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

Пример 3.1. Пусть X – множество вещественных чисел, a – отношение “быть не меньше”, b – отношение “быть строго больше”. Тогда есть отношение “быть строго больше”.

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

Пример 3.2. Если – отношение “больше” на множестве чисел, а – отношение “равно”, то – это отношение .

Можно ввести операции непосредственно не сводящиеся к теоретико-множественным.

Определение 3.3. Обратным отношением называется отношение, определяемое условием: .

Пример 3.3. Пусть – отношение “делит”, тогда – отношение “делится”.

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

Пример 3.4. Пусть – отношение “быть женой”, а – отношение “быть отцом”. Что означает в этом случае соотношение ? По определению существует такой z, что “x – жена z” и “z – отец y“. Другими словами, “x есть жена отца y“, т.е. “x – мать или мачеха y“.

Пример 3.5. Пусть – отношение “быть братом”, а – отношение “быть родителем”. Тогда произведение есть отношение “быть братом одного из родителей”, т.е. “быть дядей”.

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

Лемма 3.1. Если отношения и рефлексивны, то рефлексивны и следующие отношения:

, , , .

Лемма 3.2. Если отношения и симметричны, то симметричны и следующие отношения:

, , .

Лемма 3.3. Чтобы произведение симметричных отношений и было симметрично, необходимо и достаточно, чтобы отношения и коммутировали.

Лемма 3.4. Если отношения a и b – антисимметричны, то антисимметричны также и следующие отношения: , .

Антисимметричность может не сохраняться при объединении и произведении.

Лемма 3.4. Если отношения и транзитивны, то транзитивны также следующие отношения: , .

Из лемм 3.1, 3.2, 3.3, 3.4 вытекают следующие две теоремы.

Теорема 3.1. Если и – строгие порядки (нестрогие порядки), то пересечение также является строгим порядком (нестрогим порядком).

Замечание. Пересечение строгого и нестрогого порядка есть строгий порядок.

Свойство “быть линейным порядком” не обязано сохраняться при пересечении. Это проще всего увидеть из следующих соображений. Пусть a – линейный порядок (строгий или нестрогий), тогда (или = E). Значит, на множестве более чем из одного элемента не является линейным порядком.

Теорема 3.2. Если отношение является строгим (нестрогим, линейным) порядком, то и отношение является строгим (нестрогим, линейным) порядком.

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

Теорема 3.3. Если и – строгие порядки, то объединение является строгим порядком в том и только том случае, когда

Теорема 3.4. Для того чтобы объединение нестрогих порядков и было нестрогим порядком, необходимо и достаточно выполнение условий

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

есть полное отношение. Достаточным условием является, например, такое.

Теорема 3.5. Если и – строгие порядки и выполнены соотношения

то – строгий порядок.

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

Источник