Дискретная математика. Множества. Отображения. Отношения

64 Примерами отношений порядка являются : • Отношение включения ( ) ⊂ множеств , определенное на 2 Ω . Здесь Ω – произвольное множество . Это отношение является час - тичным порядком . • Отношение делимости : , ( делит ) m n m n m n ∀ ∈ ≤ ↔ N . Это отношение также является частичным порядком на множестве N . • Отношение неравенства кортежей ( ) ≤ (5.4) ( см . пример (5.3)) является частичным порядком . Упорядоченное множество ( , ) n ≤ R является частично упорядоченным . В нем существуют несравнимые кортежи . Таковыми являются , в частности , кортежи (1, 2, 1/ 2) x = и (1, 1, 2). y = Это отношение является конечномерным аналогом отношения (5.6) из примера 5.5, которое также является отношени - ем частичного порядка на множестве [ , ] a b С . • Лексикографическое неравенство кортежей (5.5) ( см . при - мер 5.4). Данное отношение является линейным порядком , т . е . об - ладает свойством полноты . Докажем это . Действительно , если ( , ( , ) ) n x y x y ≠ ∈ −∞ ∞ , то 1, ( ) l l i n x y ∃ ∈ ≠ . Пусть min{ : } l l k i x y = ≠ . То - гда ( ) & ( 1, 1 ( )) k k i i x y i k x y ≠ ∀ ∈ − = . Так как k k x y ≠ , то либо k k x y < , либо k k y x < . В первом случае , по определению (5.5), x y p , а во втором y x p . Что и требовалось доказать . Следовательно , лексикографический порядок является ли - нейным порядком , и множество ( , ) n −∞ ∞ линейно упорядочено этим порядком . Лексикографический порядок называют также алфавитным порядком . Именно в лексикографическом порядке упорядочены библиотечные алфавитные каталоги : буквы алфавита упорядочены естественным образом ; отношение предшествования двух различ - ных авторов определяется по первой букве их фамилий ; если пер - вые буквы фамилий совпадают , то по второй и т . д .