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

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

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

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

Элементы a и b сравнимы по отношению порядка R, если выполняется одно из условий aRb или b R^-1а.

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

Примеры.

1. Отношения “£“ и “³“ для чисел являются отношениями нестрогого порядка, а отношения “<“ и “>“ - отношениями строгого порядка. Оба отношения полностью упорядочивают множества N и R.

2. Определим отношения “£“ и “<“ для векторов на Rⁿ следуюшим образом:

(a₁,a₂,...,a_n)£(b₁,b₂,...,b_n), если a₁£ b₁, a₂£ b₂, a_n£ b_n;

(a₁,a₂,...,a_n)<(b₁,b₂,...,b_n), если (a₁,a₂,...,a_n)£(b₁,b₂,...,b_n) и хотя бы в одной координате i выполнено условие a_i<b_i.

Эти отношения определяют частичный порядок на Rⁿ.

Например, при n=3 (7,4,-3)<(7,6,-3), а (7,4,-3) и (7,0,0) не сравнимы.

3. На системе подмножеств множества М отношение включения “Í“ задаёт нестрогий частичный порядок, а отношение “Ì“ задаёт строгий частичный порядок. Например, {1,2}Ì{1,2,3}, а {1,2} и {1,3,4} не сравнимы.

4. Отношение подчинённости на предприятии задаёт строгий частичный порядок. Несравнимыми в нём являются сотрудники разных отделов.

5. Пусть в списке букв конечного алфавита А порядок букв зафиксирован, как, например, в русском или латинском алфавите. Тогда этот список определяет полное упорядочение букв, которое называют отношением предшествования и обозначают “ ” (a_i a_j, если a_i предшествуетa_j в списке букв. На основе отношения предшествования букв строится отношение предшествования слов, определяемое следующим образом. Пусть даны слова

a₁=a₁₁ a₁₂... a_1n и a₂=a₂₁ a₂₂... a_2m. Тогда a₁ a₂, когда

- либо a₁=ba_ig, a₂=ba_jd и a_i a_j (b, g, d - некоторые слова, возможно, пустые; a_i и a_j - буквы),

- либо a₂=a₁b, где b - непустое слово.

Это отношение задаёт полное упорядочение множества всех конечных слов в алфавите А, которое называется лексико-графическим упорядочением слов.

а) Наиболее известным примером лексико-графического упорядочения является упорядочение слов в словарях. Например,

математика материал (здесь b=мате, м р, g=атика, d=иал);

ком команда (здесь b=анда).

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

В общем случае эти два вида упорядочения могут не совпадать: например, 70<705 и 80<705, но 70 705, а 80 705. Чтобы они совпали, нужно выровнять число разрядов у сравниваемых чисел, приписывая слева нули, например 080 705. Такое выравнивание автоматически происходит при записи целых чисел в ЭВМ.

в) Лексико-графическое упорядочение цифровых представлений дат вида 31.01.98 не совпадает с естественным упорядочением дат от ранних к поздним: например, 31.01.98 лексико-графически “старше” 27 числа любого года. Чтобы возрастание дат совпало с лексико-графическим упорядочением, на первое место в дате надо поставить год, затем месяц и, наконец, число: 98.01.31. Так обычно хранят даты в памяти ЭВМ.