График отношения порядка

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

График отношения делимости

Для множества действительных чисел R декартов квадрат представляется не геометрическим квадратом, а всей плоскостью с декартовыми координатами. Диагональ / на этом представлении — это биссектриса угла первой и третьей четвертей, а графиком линейного порядка < на множестве R является верхняя полуплоскость, определяемая диагональю /, вместе с этой диагональю.

График частичного нестрогого порядка выглядит иначе. Диагональ в него попадает тоже, но треугольник график уже не образует.

Рассмотрим, например, отношение делимости на множестве N. Так как из a I b следует а < Ь, можно заранее предугадать, что график отношения | делимости на N составит часть графика отношения <, т. е. новый график будет находиться внутри черного треугольника.

Множество из двух элементов М = {а, Ь} можно упорядочить тремя способами:

  • 1) оба элемента несравнимы;

  • 2) а < Ь;

  • 3) b < а.

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

Сначала посмотрим, сколько различных графов можно нарисовать, используя три точки. На схеме изображены эти графы без обозначения вершин. Граф а) — это отношение, при котором все элементы несравнимы. На графе Ь) два элемента сравнимы между собой, а третий — нет. На графе с) два максимальных элемента и наименьший, а на графе d) — два минимальных и наибольший. Граф е) является изображением линейного порядка. Любой другой порядок на множестве из трех элементов будет совпадать с одним из пяти описанных типов.

Упорядочения трехэлементного множества

На а) как бы не были занумерованы вершины — порядок останется тем же самым. На графах Ь) и е) вершины можно расставить шестью различными способами, а на графах с) и d) — тремя. Суммируя все эти варианты, получаем, что на множестве из трех элементов можно задать отношение порядка 19 способами.

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

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

Рассмотрим, например, сначала обычное упорядочение множества натуральных чисел:

1 < 2 < 3 < 4 < 5 < 6 < ..., (1)

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

1 < 3 < 5 < ... < 2 < 4 < 6 < ... (2)

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

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

Пусть М — множество произвольных символов, которые назовем буквами, а М — соответственно алфавитом. Среди символов поместим и символ пробела, например и. Любую конечную цепочку букв назовем словом.

Упорядочение алфавита

Упорядочение слов в словаре называютсловарным (или лексикографическим) упорядочением. Текст в словаре идет сверху вниз, одно слово расположено выше или ниже другого, поэтому словарное упорядочение является упорядочением по высоте.

Словарное упорядочение является продолжением упорядочения алфавита. Пусть алфавит М = {uj, а, Ь, с,..., d} упорядочен по высоте, причем символ пробела расположен выше всех остальных символов. Возьмем два слова в этом алфавите:

U - Хц Х2, х3,..., х,„

W = yi,y2, Уз, -,Ут,

где х,-, y'j є М. Если п * т, то, добавив необходимое число пробелов справа к слову меньшей длины, можно выровнять слова по длине. После этого можно сравнить эти слова по высоте. Слово U в словаре будет расположено выше слова W, если хі=уі, Х2=У2, х*_і=Уг-і, но х* выше у*.

Словарное упорядочение определяется по первым различным символам.

Упорядочение слов по высоте («не выше» или «не ниже») является рефлексивным, транзитивным, антисимметричным и связным. Короче говоря, словарное упорядочение является линейным порядком.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >