Отношение линейного порядка обладает свойствами. Отношение порядка
Слово «порядок» часто применяют в самых различных вопросах. Офицер дает команду: «По порядку номеров рассчитайся», арифметические действия выполняются в определенном порядке, спортсмены становятся по росту, существует порядок выполнения операций при изготовлении детали, порядок слов в предложении.
Что же общего во всех случаях, когда говорится о порядке? В том, что в слово «порядок» вкладывается такой смысл: оно означает, какой элемент того или иного множества за каким следует (или какой элемент какому предшествует).
Отношение «х следует за у » транзитивно: если «х следует за у » и «у следует за 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°. Линейно упорядоченное множество называется плотным, если для любых двух различных элементов этого множества существует элемент множества, лежащий между ними.
Свойства отношений:
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 и yRz xRz.
Граф транзитивного отношения с каждой парой стрелок, идущих от х к 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 получается в остатке 0 (это числа 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 на множестве .М и некоторых различных элементов выполняется хотя бы одно из отношений
aRb или bRa , то элементы а и Ь называются сравнимыми, в противном случае - несравнимыми.
Полностью (или линейно) упорядоченное множество М -
множество, на котором задано отношение порядка, причем любые два элемента множества М сравнимы; частично упорядоченное множество - то же, но допускаются пары несравнимых элементов.
Линейно упорядоченным является множество точек на прямой с отношением "правее", множества целых, рациональных, действительных чисел по отношению "больше" и т п.
Примером частично упорядоченного множества могут служить трехмерные векторы, если порядок задан так , если
Т е если предшествование выполнено по всем трем координатам, векторы (2, 8, 5) и (6, 9, 10) сравнимы, а векторы (2, 8, 5) и (12, 7, 40) не сравнимы. Этот способ упорядочения можно распространить на векторы любой размерности: вектор
предшествует йектору если
И выполнено
На множестве векторов можно рассмотреть и другие примеры упорядочения.
1) частичный порядок: 
, если
Т.е. по длине векторов; несравнимыми являются векторы одинаковой длины.
2) линейный порядок: 
, если a
Последний пример представляет понятие алфавитного порядка.
Алфавит - это кортеж попарно различных символов, называемых буквами алфавита. Примером служит алфавит любого европейского языка, а также алфавит из 10 арабских цифр В компьютере клавиатура и некоторые вспомогательные средства определяют алфавит допустимых символов.
Слово в алфавите А - кортеж из символов алфавита А. Слово записывается символами алфавита подряд, слева направо, без пробелов Натуральное число является словом в цифровом алфавите Формула не всегда является словом из-за нелинейного расположения символов наличие надстрочных (показатели степени) и подстрочных (индексы переменных, основания логарифмов) символов, дробная черта, знаки радикалов и др.; однако путем некоторых соглашений она может быть приведена к записи в строку, что и применяется, например, в компьютерном программировании (так, знак возведения в степень записывается как 2 знака умножения подряд: 5**3 означает третью степень числа 5.
Лексико-графическое (алфавитное) упорядочение - для различных слов в алфавите с упорядоченными
символами устанавливается упорядочение: , если
возможно представление 
, при котором либо
(подслово может быть пустым), либо - пустое подслово
В этом определении - префикс (начальное подслово), одинаковый у обоих слов - либо первые по счету слева различные
символы, либо - последний символ в слове- хвостовые
подслова.
Таким образом, алфавитное упорядочение слов определяется первым слева различающим их символом (например, слово КОНУС предшествует слову КОСИНУС, поскольку они впервые различаются в третьей букве, и Н предшествует С в русском алфавите). Считается также, что символ пробела предшествует любому символу алфавита - для случая, когда одно из слов является префиксом другого (например, КОН и КОНУС)
Упражнение. Проверьте, что алфавитное упорядочение натуральных чисел, имеющих одинаковое число разрядов в десятичной записи, совпадает с упорядочением их по величине.
Пусть А - частично упорядоченное множество. Элемент называется максимальным в А, если не существует элемента для которого а < b. Элемент а называется наибольшим в А, если для всякого отличного от а элемента выполнено Ь<а-
Симметричным образом определяются минимальный и наименьший элементы. Понятия наибольшего и максимального (соответственно, наименьшего и минимального) элементов различны -см. пример на рис.14. Множество на рис. 14,а имеет наибольший элемент р, он же является максимальным, минимальных элементов два: s и t, наименьшего нет. На рис.14,б, напротив, множество, имеющее два максимальных элемента / и j , наибольшего нет, минимальный, он же наименьший - один: т.
Вообще, если у множества есть наибольший (соответственно, наименьший) элемент, то только один (может не быть ни одного).
Максимальных и минимальных элементов может быть несколько (может не быть совсем - в бесконечном множестве; в конечном случае -обязательно есть).
Разберем еще два примера. - отношение на множестве N :
"Y делит X", или "X является делителем числа Y" (например,
) является рефлексивным и транзитивным. Рассмотрим его на конечном множестве делителей числа 30.
Отношение является отношением частичного порядка (нестрогого)
и изображается следующей матрицей порядка 8, содержащей 31 знак
Соответствующая схема с 8 вершинами должна содержать 31 связку. . Однако она будет более удобна для обозрения, если исключить 8
связок-петель, изображающих рефлексивность отношения (диагональные элементы матрицы) и транзитивные связки, т.е. связки
Если есть промежуточное число Z такое, что
(например, связку , поскольку ). Тогда в схеме
останется 12 связок (рис.15); недостающие звенья подразумеваются "по транзитивности". Число 1 является наименьшим, а число 30
наибольшим элементами в . Если исключить из число 30 и
рассмотреть тот же частичный порядок на множестве , то
наибольшего элемента нет, но имеются 3 максимальных элемента: 6, 10, 15
Теперь построим такую же схему для отношения на булеане
(множестве всех подмножеств) трехэлементного множества
Содержит 8 элементов:
Проверьте, что если сопоставить элементам а,Ь,с, соответственно числа 2, 3, 5, а операции объединения множеств - умножение соответствующих чисел (т.е., например, подмножеству отвечает
произведение 2 5 = 10), то матрица отношения будет точно такой
же, как для отношения ; схемы этих двух отношений с описанными
сокращениями петель и транзитивных связок с точностью до обозначений совпадают (см. рис.16). Наименьшим элементом является
А наибольшим -
Бинарные отношения R на множестве А и S на множестве В называются изоморфными, если между А и В можно установить взаимно однозначное соответствие Г, при котором, если (т.е.
элементы находятся в отношении R), то (образы
этих элементов находятся в отношении S).
Так, частично упорядоченные множества и изоморфны.
Рассмотренный пример допускает обобщение.
Отношение на булеане есть частичный порядок. Если
Т.е. множество Е содержит п элементов , то каждому
подмножеству соответствует п -мерный вектор с
компонентами , где - характеристическая функция
множества Л/ . Совокупность всех таких векторов можно рассматривать как множество точек п -мерного арифметического пространства с координатами 0 или 1, или, по-другому, как вершины п -мерного
единичного куба, обозначаемого , т.е. куба с ребрами единичной длины. Для п = 1, 2, 3 указанные точки представляют собой соответственно концы отрезка, вершины квадрата и куба - отсюда общее название. Для /7=4 графическое изображение этого отношения - на рис.17. Около каждой вершины 4-мерного куба указано соответствующее
подмножество 4-элементного множества и четырехмерный
вектор, представляющий характеристическую функцию этого подмножества. Соединены между собой вершины, отвечающие подмножествам, которые различаются присутствием ровно одного элемента.
На рис.17 четырехмерный куб изображен так, что на одном
уровне расположены попарно не сравнимые элементы, содержащие одинаковое число единиц в записи (от 0 до 4), или, по-другому, одинаковое число элементов в представляемых подмножествах.
На рис.18а,б - другие наглядные представления 4-мерного куба;
на рис.18а ось первой переменной ОХ направлена вверх (намеренное отклонение от вертикали, чтобы не сливались различные ребра куба):
при этом 3-мерный подкуб, соответствующий X = 0 расположен ниже, а для X = 1 - выше. На рис. 186 та же ось ОХ направлена изнутри куба наружу внутренний подкуб соответствует X = О, а внешний - X = 1.
В 
файле материалов приведено изображение 5-мерного единичного куба (стр.134).
Слово «порядок» часто применяют в са-мых различных вопросах. Офицер дает команду: «По порядку номе-ров рассчитайся», арифметические действия выполняются в опре-деленном порядке, спортсмены становятся по росту, все ведущие шахматисты располагаются в определенном порядке по так назы-ваемым коэффициентам Эло (американский профессор, который раз-работал систему коэффициентов, позволяющую учитывать все ус-пехи и неудачи игроков), после первенства все футбольные команды располагаются в определенном порядке и т. д. Существует порядок выполнения операций при изготовлении детали, порядок слов в предложении (попробуйте понять, что значит предложение «на он старика посадил осла не»!).
Располагая элементы некоторого множества друг за другом, мы тем самым упорядочиваем их или устанавливаем между ними некоторое отношение по-рядка. Простейшим примером является естественный порядок натуральных чисел . Его естественность заключается в том, что для любых двух натураль-ных чисел мы знаем, какое из них следует за другим или какое из них больше другого, поэтому мы можем расположить натуральные числа в последова-тельности так, что большее число будет расположено, например, правее меньшего: 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), но не имеет наи-меньшего.
