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

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

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

Легко видеть, что это обобщение отношения «» на множестве N, для которого все три свойства выполняются.

Пример 2.19.

Назовем P(B) множество всех подмножеств множества B. Тогда отношение « » на P(B) есть отношение нестрогого порядка (X  X для всех X; если X  Y и Y  X, то X = Y; X  Y и Y  Z  X  Z). 

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

Пример 2.20.

Отношение «>» на множестве N, Z или R есть отношение строгого порядка (неверно, что X > X для всех X; если X > Y, то неверно, что Y > X; X > Y и Y > Z  X > Z).

Таким же образом можно показать, что отношение «быть старше» на множестве людей является отношением строгого порядка. 

Отношение нестрогого порядка или отношение строгого порядка на том же множестве обобщается термином «отношение порядка».

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

Таким образом, отношение линейного порядка – это отношение порядка, обладающее свойством сравнимости.

Пример 2.21.

Порядок на множестве подмножеств данного множества (отношение « ») не является линейным, так как не для каждых подмножеств X и Y имеет место отношение X  Y или Y  X.

Естественный порядок (отношение « ») чисел на действительной оси R является линейным, так как для любых x, y  R имеем: x  y или y  x. 

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

Следующий пример иллюстрирует эту идею.

Пример 2.22.

На основе отношения порядка, определенного на множестве N, можно формально получить обычные отношения порядка на множествах Z и Q.

Сначала рассмотрим Z, причем следующим образом:

Z = N  {0}  A, где A = {-x: x  N}.

Определим на таком Z отношение порядка « » следующим образом:

1. Если x = y, то x  y и y  x.

2. Пусть x  y, тогда

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

б) если x, y  A, то x  y  - y  - x в N (т.е. -5  - 4, так как 4  5);

в) если x=0 и y  N, то x  y;

г) если x  A и y=0, то x  y;

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

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

a/b  c/d  a*d  b*c.

Проверку этого утверждения оставляем в качестве упражнения.

2.12. Отображения и их свойства. Виды отображений

Если отношение определялось парой <A, R>, где R  A  A, то отображением множества X в множество Y называется тройка множеств  = <X, Y, F>, где F  X  Y (обозначение ).

Если пара <x, y> F (из этого следует, что x X, y Y), то y называется образом элемента x, а x – прообразом элемента y при отображении  (обозначение: или y =  (x)).

Таким образом, в F находятся те и только те пары, первая компонента которых, принадлежащая X, отображается во вторую, принадлежащую Y, при отображении . X называется областью определения отображения , а Y – областью прибытия. Множество первых компонент множества F (то есть множество всех прообразов, обозначается F_x) называется областью определения отображения , а множество вторых компонент (то есть множество образов, обозначается F_y) называется областью значений . Конечно, F_x  X, F_y  Y, но не обязательно F_x = X, F_y = Y.

Если, тем не менее, F_x = X, то отображение  называется всюду определенным; если F_y = Y, то  называется отображением X на Y.

Если любой x  F_x (а в конечном итоге любой x  X ) имеет не более одного образа в Y (то есть на F_y), то отображение  называется функциональным (однозначным) отображением или просто функцией.

Отображение -1 = <Y, X, F-1>, где F-1 Y X и пара <y, x>  F-1 тогда и только тогда, когда пара <x, y>  F, называется обратным отображением по отношению к  (запись: ).

Отображение  называется взаимно однозначным, если

1)  является всюду определенным функциональным отображением X на Y;

2) ^-1 является всюду определенным функциональным отображением Y на X.

Если существует хотя бы одно взаимно однозначное отображение , то говорят, что между множествами X и Y имеется (установлено) взаимно однозначное соответствие. В этом случае каждому элементу множества X соответствует один (и только один) элемент множества Y и наоборот.

Пример 2.23.

Пусть X = Y= R – множество действительных чисел, <a, b>  F тогда и только тогда, когда b = sin a. Тогда отображение  является: 1) всюду определенным и 2) функциональным.

Отображение  не является 1) отображением X на Y, так как не существует x, при котором  (x) = 2, например (хотя 2  Y); 2) взаимно однозначным, так как не является отображением «на». 

Часто приходится связывать отображения друг с другом (в математическом анализе это эквивалентно функции от функции). Определим эту связь формально.

Пусть заданы множества A, B и C и

 = A; B; S отображение A в B

 = B; C; T – отображение B в C.

Возьмем элемент aA_S; он имеет образ b = (a)B_S. Если b принадлежит не только области прибытия B_S отображения , но и области определения B_Т отображения  (bB_T), то b имеет образ с = (b)С_T.

Но тогда с = (b) = ((a)) = ( _ )(a) = (a).

Тем самым, для некоторых элементов из А мы задали сложное отображение в С, являющееся суперпозицией отображений  и . Эта суперпозиция (последовательное выполнение) отображений обозначается как  _ , причем порядок применения отображений записывается справа налево.

Сложное отображение  = A, C, V для элементов пересечения множеств A_S   ^-1(B_TB_S), где B_TB_S – множество элементов в В, имеющих как прообразы (по ) в А, так и образы (по ) в В.

Области отправления и прибытия, связанные с  и , заштрихованы в разных направлениях.

П римеры использования сложных отображений в линейной алгебре приведены в разделе 5.