Упорядоченные отношения. Отношение порядка

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

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

Отношение «х следует за у » транзитивно: если «х следует за у » и «у следует за z », то «x следует за z ». Кроме того, это отношение должно быть антисимметричным: для двух различных х и у , если х следует за у , то у не следует за х .

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

Выясним особенности графа и графика отношений строгого порядка.

Рассмотрим пример. На множестве X = {5, 7, 10, 15, 12} задано отношение R : «х < у ». Зададим это отношение перечислением пар
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Построим его граф. Мы видим, что граф данного отношения не имеет петель. На графе нет двойных стрелок. Если из х идет стрелка в у , а из у – в z , то из х идет стрелка в z (рис. 8).

Построенный граф позволяет расположить элементы множества X в таком порядке:

{5, 7, 10, 12, 15}.

На рис.6 (§ 6 этой главы) графы VII, VIII – это графы отношений строгого порядка.

Отношение нестрогого порядка

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

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

Такие отношения являются объединениями отношения строгого порядка с отношением тождества.

Рассмотрим отношение «не больше» (£) для множества

X = {5, 7, 10, 15, 12}. Построим его граф (рис. 9).

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

На рис. 6 (§ 6 этой главы) графы V, VI – это графы отношений нестрогого порядка.

Упорядоченные множества

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

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

(х , у ) Î R или (у, х ) Î R .

Если R – отношение строгого порядка, то множество Х упорядочено этим отношением при условии: если х , у любые два неравных элемента множества Х , то (х , у ) Î R или (у, х ) Î R , или любые два элемента х, у множества Х равны.

Из школьного курса математики известно, что числовые множества N , Z , Q , R упорядочены отношением «меньше» (<).

Множество подмножеств некоторого множества не упорядочено введением отношения включения (Í), или строгого включения (Ì) в указанном выше смысле, т.к. существуют подмножества ни одно из которых не включается в другое. В этом случае говорят, что данное множество частично упорядочено отношением Í (или Ì).

Рассмотрим множество X = {1, 2, 3, 4, 5, 6} и в нем два отношения «меньше» и «делится на». Легко проверить, что оба эти отношения являются отношениями порядка. Граф отношения «меньше» можно изобразить в виде луча.

Граф отношения «делится на» можно изобразить лишь на плоскости.

Кроме того, на графе второго отношения есть вершины, не соединенные стрелкой. Например, нет стрелки, соединяющей числа 4 и 5 (рис. 10).

Первое отношение «х < у » называется линейным. Вообще, если отношение порядка R (строгого и нестрогого) на множестве X обладает свойством: для любых х , у Î Х либо хRy , либо yRx , то его называют отношением линейного порядка, а множество X – линейно упорядоченным множеством.

Если множество X конечно, и состоит из n элементов, то линейное упорядочивание Х сводится к нумерации его элементов числами 1,2,3, ..., n .

Линейно упорядоченные множества обладают рядом свойств:

1°. Пусть а, в, с – элементы множества X , упорядоченного отношением R . Если известно, что aRв и вRс , то говорят, что элемент в лежит между элементами а и с .

2°. Множество X , линейно упорядоченное отношением R , называется дискретным, если между любыми двумя его элементами лежит лишь конечное множество элементов этого множества.

3°. Линейно упорядоченное множество называется плотным, если для любых двух различных элементов этого множества существует элемент множества, лежащий между ними.

Отношение эквивалентности. Связь отношения эквивалентности с разбиением множества на классы

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

Пример. Рассмотрим отношение «х однокурсник у » на множестве студентов педфака. Оно обладает свойствами:

1) рефлексивности, т.к. каждый студент является однокурсником самому себе;

2) симметричности, т.к. если студент х у , то и студент у является однокурсником студента х ;

3) транзитивности, т.к. если студент х - однокурсник у , а студент у – однокурсник z , то студент х будет однокурсником студента z .

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

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

Теорема. Если на множестве Х задано отношение эквивалентности, то оно разбивает это множество на попарно непересекающиеся подмножества (классы эквивалентности).

Верно и обратное утверждение: если какое-либо отношение, заданное на множестве Х , порождает разбиение этого множества на классы, то оно является отношением эквивалентности.

Пример. На множестве Х = {1; 2; 3; 4; 5; 6; 7; 8} задано отношение «иметь один и тот же остаток при делении на 3». Является ли оно отношением эквивалентности?

Построим граф данного отношения: (самостоятельно)

Данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, является отношение эквивалентности и разбивает множество Х на классыэквивалентности. В каждом классе эквивалентности будут числа, которые при делении на 3 дают один и тот же остаток: Х 1 = {3; 6}, Х 2 = {1; 4; 7}, Х 3 = {2; 5; 8}.

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

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

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

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

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

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

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

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

Пример . На множестве Х = {1; 2; 3; 4; 5} заданы два отношения: «х £ у » и «х – делитель у ».

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

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

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

Контрольные вопросы

1. Дайте определение бинарного отношения на множестве Х .

2. Как записать утверждение о том, что элементы х и у находятся в отношении R ?

3. Перечислите способы задания отношений.

4. Сформулируйте свойства, которыми могут обладать отношения. Как данные свойства отражаются на графе?

5. Какими свойствами должно обладать отношение, чтобы оно являлось отношением эквивалентности?

6. Как отношение эквивалентности связано с разбиением множества на классы?

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

X {\displaystyle X} называется отношением нестрогого частичного порядка (отношением порядка , отношением рефлексивного порядка ), если имеют место

Множество X {\displaystyle X} , на котором введено отношение частичного порядка, называется частично упорядоченным . Отношение нестрогого частичного порядка часто обозначают знаком ≼ {\displaystyle \preccurlyeq } .

Варианты

Отношение частичного порядка R {\displaystyle R} называется линейным порядком , если выполнено условие

∀ x ∀ y (x R y ∨ y R x) {\displaystyle \forall x\forall y(xRy\lor yRx)} .

Множество X {\displaystyle X} , на котором введено отношение линейного порядка, называется линейно упорядоченным , или цепью .

Отношение R {\displaystyle R} , удовлетворяющее только условиям рефлексивности и транзитивности, называется предпорядком , или квазипорядком .

Строгий порядок

Если условие рефлексивности заменить на условие антирефлексивности:

∀ x ¬ (x R x) {\displaystyle \forall x\neg (xRx)} ,

то получим определение строгого , или антирефлексивного частичного порядка (обозначается обычно символом ≺ {\displaystyle \prec } ).

Замечание. Одновременная антирефлексивность и транзитивность отношения влечёт антисимметричность. Поэтому отношение является отношением строгого порядка тогда и только тогда, когда оно антирефлексивно и транзитивно.

В общем случае, если R {\displaystyle R} - транзитивное, антисимметричное отношение, то

R ≼ = R ∪ { (x , x) | x ∈ X } {\displaystyle R_{\preccurlyeq }=R\cup \{(x,x)|x\in X\}} - рефлексивный порядок R ≺ = R ∖ { (x , x) | x ∈ X } {\displaystyle R_{\prec }=R\setminus \{(x,x)|x\in X\}} - строгий порядок.

Примеры

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

Размерность Душника - Миллера

История

Знаки < {\displaystyle <} и > {\displaystyle >} изобретены

Пусть R - бинарное отношение на множестве А.

ОПРЕДЕЛЕНИЕ. Бинарное отношение R на множестве А называется отношением порядка на А или порядком на А, если оно транзитивно и антисимметрично.

ОПРЕДЕЛЕНИЕ. Отношение порядка R на множестве А называется нестрогим, если оно рефлексивно на А, т. е. для всякого из А.

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

ОПРЕДЕЛЕНИЕ. Бинарное отношение R на множестве А называется строгим порядком на А, если оно транзитивно и антирефлексивно на А.

Примеры. 1. Пусть - множество всех подмножеств множества М. Отношение включения на множестве есть отношение нестрогого порядка.

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

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

ОПРЕДЕЛЕНИЕ. Бинарное отношение R на множестве А называется отношением предпорядка или предпорядком на А, если оно рефлексивно на и транзитивно.

Примеры. 1. Отношение делимости во множестве целых чисел не является порядком. Однако оно рефлексивно и транзитивно, значит является предпорядком.

2. Отношение логического следования является предпорядком на множестве формул логики высказываний.

Линейный порядок. Важным частным случаем порядка является линейный порядок.

ОПРЕДЕЛЕНИЕ. Отношение порядка на множестве называется отношением линейного порядка или линейным порядком на , если оно связанно на , т. е. для любых х, у из А

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

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

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

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

Располагая элементы некоторого множества друг за другом, мы тем самым упорядочиваем их или устанавливаем между ними некоторое отношение по-рядка. Простейшим примером является естественный порядок натуральных чисел . Его естественность заключается в том, что для любых двух натураль-ных чисел мы знаем, какое из них следует за другим или какое из них больше другого, поэтому мы можем расположить натуральные числа в последова-тельности так, что большее число будет расположено, например, правее меньшего: 1, 2, 3, ... . Разумеется, последовательность элементов можно вы-писывать в любом направлении, а не только слева направо. Само понятие натуральных чисел уже содержит в себе идею упорядоченности. Устанавливая некоторое относительное расположение элементов какого-либо множества, мы тем самым задаем на нем некоторое бинарное отноше-ние порядка, которое в каждом конкретном случае может иметь свое назва-ние, например, "быть меньше", "быть старше", "содержаться в", "следовать за" и т. д. Символические обозначения порядка также могут быть разнооб-разными, например, Í, и т. д.

Главным отличительным признаком отношения порядка является наличие у него свойства транзитивности. Так, если мы имеем дело с последовательно-стью каких-то объектов x 1 , х 2 , ..., х n , ... , упорядоченных, например, по отно-шению , то из того, что выполняется х 1 х 2 ... х п ..., должно следо-вать, что для любой пары х i , х j элементов этой последовательности также выполняется x i x j :

Для пары элементов x i j в графе отношения мы проводим стрелку от вершины x i к вершине x j , т. е. от меньшего элемента к большему.

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

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

Отноше-ние R в множестве X называется отношением строгого поряд-ка, если оно транзитивно и асимметрично.

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

Граф отношения «меньше» в множестве натуральных чисел можно изобразить в виде луча:

Отношение R в X называется отношением нестро-гого (частичного)порядка , если оно транзитивно и антисимметрично. Всякое отношение нестрогого порядка рефлексивно.

Эпитет "частичный" выражает тот факт, что, возможно, не все элементы множества сравнимы в данном отношении.

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

Отношение включения Í между подмножествами некоторого множества также является частичным порядком. Очевидно, что не любые два подмно-жества сравнимы по этому отношению. Ниже на рисунке показан частичный по-рядок по включению на множестве всех подмножеств множества {1,2,3}. Стрелки на графе, которые должны быть направлены вверх, не показаны.

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

Элементы х и у частично упорядоченного множества называются сравни-мыми, если х у или у х. В противном случае они не сравнимы.

Упорядоченное множество, в котором любые два элемента сравнимы, называется линейно упорядоченным , а порядок - линейным порядком. Линейный порядок еще называют совершенным порядком.

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

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

Пример 1. Части книги упорядочены так, что книга содержит главы, главы содержат разделы, а разделы состоят из подразделов.

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

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

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

Элемент х называется наибольшим (наименьшим), если для любого у Î А выполняется у < х (х< у).

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

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

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

Бесконечные множества могут не иметь максимальных, или минимальных, или тех и других элементов. Например, множество натуральных чисел (1,2, 3, ...) имеет наименьший элемент 1, но не имеет максимальных. Множество всех действительных чисел с естественным порядком не имеет ни наимень-шего, ни наибольшего элемента. Однако его подмножество, состоящее из всех чисел х < 5, имеет наибольший элемент (число 5), но не имеет наи-меньшего.