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

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

Частичным порядком на множестве A назовем отно­шение, которое рефлексивно, антисимметрично и транзи­тивно. Порядок (называемый также отношением поряд­ка)— это обобщение отношения ≤ на N. Поэтому мож­но легко проверить требуемые три свойства. Заметим, что мы могли бы в качестве определения взять отноше­ние <. Тогда отношение порядка было бы только тран­зитивно. Поэтому свойство транзитивности является наи­более важным для отношения порядка.

Определив отношение можно определить отноше­ние < следующим образом:

a < b a < b и a ≠ b.

Аналогично, если задано <, то

a ≤ b a = b или a < b.

Пример 5.1. Пусть задано произвольное множест­во А. Тогда отношение на (А) есть тривиальное отношение порядка. (X X для всех X; если X Y и Y Х, то Х =Y;

Х Y и Y Z X Z.) //

Отношение порядка на A называется полным, если для любых x, у A или x у, или y х (или же выпол­няются оба).

Пример 5.2. Очевидно, что порядок на подмноже­ствах данного множества не является полным. Естест­венный порядок чисел на действительной оси R являет­ся полным.

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

Пример 5.3. На основе порядка, определенного на N, мы можем формально получить обычные отношения порядка на множествах чисел Z, Q и R. (Как уже упо­миналось, исследование N будет проведено в § 3 гл. 3.)

Вначале рассмотрим Z. Чтобы облегчить рассужде­ния, разобьем Z следующим образом:

Z = N {0} А.

Поэтому A = {-х: x N}. Определим отношение (кото­рое будем называть полным отношением порядка) на Z рассмотрением всевозможных элементов х и у из разбие­ния

{N {0} A}.

Если х = у, то х ≤ y и у ≤ х. Пусть х ≠ у. Тогда:

а) если х, y N, то порядок в Z тот же самый, что и в N;

б) если х, y A, то х ≤ у тогда и только тогда, когда

–у ≤ –х в N (т. е. -5≤-4, так как 4 ≤5);

в) если х = 0 и у N, то х ≤ у,

г) если х Aи у = 0, то х ≤ у;

д) если x A и y N, то x ≤ у или в противном случае у ≤ х.

На основе порядка на Z и обычных арифметических операций с целыми числами мы можем определить поря­док на Q:

a/b ≤ c/d тогда и только тогда, когда а d ≤ b с.

Проверку этого утверждения оставляем в качестве упражнения. Наконец, определим отношение порядка на множестве действительных чисел R. Рассмотрим десятичные представления двух действительных положитель­ных чисел:

D = …0d_n­…d₂ d₁ d_{0 1 2}…,

C = …0c_m­…c₂ c₁ c_{0 1 2}…

Если d₁ = c₁ и ₁ = ₁ для всех i, от D = C и, следова­тельно,

D ≤ C и C ≤ D . В противном случае:

а) если d_n ≠ 0, c_m ≠ 0 и п ≠ т, то D ≤ С, если n < m, и С ≤ D если m < n;

б) если m = n и d₁ ≠ c₁ но d₁ = c₁ для всех j таких, что i < j ≤ n, то из d₁ < c₁ следует, что D ≤ С, и, обратно, если

c₁ < d₁, то С ≤ D;

в) если т = п и d₁ = c₁ для всех i, но _k ≠ _k для некоторых k и _j = _j для всех j таких, что 0<j<k, тогда C ≤ D, если _k < _k, и D ≤ C, если _k < _k.

Читатель может проверить это самостоятельно. Отри­цательные числа могут быть исследованы так же, как в Z. //

Множество X вместе с отношением порядка ≤ называется частично упорядоченным множеством (обозначается (X, ≤)). Тогда любой элемент u (Х, ≤) такой, что х ≤ u и у ≤ u, называется верхней границей xиy.Аналогично, если 1 (X,≤), 1≤ х и 1 ≤ у, то 1 является нижней границей х и у. Множество всех верхних границ х и у является подмножеством X и упорядочено отноше­нием ≤. Если существует единственный наименьший элемент этого множества, т. е. если существует (X, ≤) такое, что x ≤ , y ≤ и ≤ u для любой верхней границы u, то называют верхней гранью (sup) х и у. Аналогично, если существует единственная наибольшая нижняя граница х и у, ее называют нижней гранью (inf) х и у. Мы отложим изучение верхней и нижней граней до § 5 гл. 5, где будут изучаться решетки.

Наконец, заметим, что использование естественного порядка на R определяет новые множества. Их называ­ют интервалами:

[a, b] = {x: x R, а ≤ х ≤ b}

есть замкнутый интервал (отрезок) от a до b;

]а, b[ = {х: x R, a<х<b}

есть открытый интервал от a до b. В каждом случае числа a и b называются концевыми точками.

Замкнутый интервал включает в себя концевые точ­ки, а открытый нет. Удобно также определить полуот­крытые интервалы:

[a, b[ = {x: x R, а ≤ х <b},

]a, b] = {x: x R, а <х ≤ b}.

Для удобства будем использовать следующие обозна­чения:

]-∞, a] = {х: х ≤ a},

]-∞, a[ = {х: х < a},

[a, ∞[ = {х: a ≤ x},

]a, ∞[ = {х: a < x},

]-∞, ∞[ = R.

Хотя интервалы и множества чисел в общем-то не яв­ляются центральной частью нашего рассмотрения, мы увидим, что их удобно использовать время от времени.

Упражнение 2.5.

1. Пусть A — произвольное множество и — отноше­ние на множестве (A) x (A), определенное следую­щим образом:

(P, Q) (X, Y) тогда и только тогда, когда

(PΔQ) (XΔY).

Является ли отношением порядка?

2. Пусть A — произвольное множество и — отно­шение на S^>(A)XSP(A), определенное следующим об­разом:

(P, Q)o(X, Y) тогда и только тогда, когда

P XиQ Y.

Является ли отношением порядка? Если да, то явля­ется ли этот порядок полным?

3. Пусть и — отношения на N², определяемые соотношениями:

(a, b) (c, d) тогда и только тогда, когда a≤c и b≤d;

(a, b) (c, d) тогда и только тогда, когда a≤c и b≥d.

Являются ли и отношениями порядка?

4. Пусть определено на положительных элементах Q следующим образом:

(a/b) (c, d) тогда и только тогда, когда a d≤ b с.

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