Отношение упорядоченности

Бинарное отношение, заданное на множестве М и обладающее свойствами рефлексивности, транзитивности и антисимметричности, называется отношением частичной упорядоченности или просто упорядоченностью. Множество М в этом случае называется упорядоченным. Упорядоченность называется строгой, если отношение не рефлексивно. Упорядоченность называется линейной, если для любых элементов а, b Î М => либо (a,b)ÎР, либо (b,a)ÎР. Множество М в этом случае называется линейно–упорядоченным или цепью.

Для обозначения отношения упорядоченности обычно используют знаки £ (или <), ³ (или >). При этом a£b равнозначно b³a, и запись a<b означает, что a£b и a¹b. Если a<b, то говорят, что а предшествует b (находится перед b), а b следует за а (находится после а). Т.о., для любых двух элементов цепи обязательно должно выполняться одно из двух: либо a £ b, либо b £ a.

Утверждение: если множество М упорядочено или линейно–упорядочено, то и каждое его подмножество упорядочено тем же отношением.

Пусть А Ì М и М – упорядоченное множество. Элемент хÎМ называется верхней (нижней) границей множества А, если для " аÎА => а ≤ х ( х ≤ а ). Множество А в этом случае называется ограниченным сверху (снизу). Естественно, что А может иметь не одну верхнюю (нижнюю) границу, а множество верхних (нижних) границ. Тогда наименьшая из верхних границ А называется верхней гранью множества А и обозначается sup(А) – супремум. Аналогично, наибольшая из нижних границ множества А называется нижней гранью Аи обозначается inf(А) – инфимум. (Иначе говоря, верхняя грань А есть нижняя граница множества всех верхних границ А, а нижняя грань А есть верхняя граница множества всех нижних границ А.)

Линейно–упорядоченное множество называется вполне упорядоченным, если у каждого его непустого и ограниченного снизу подмножества есть нижняя грань. Иными словами, упорядоченное множество является вполне упорядоченным, если любое его непустое подмножество имеет первый элемент.

Для графического изображения конечных частично или линейно упорядоченных множеств служит диаграмма Хассе.

Пусть М – упорядоченное множество и элементы x, yÎM, причем x<y. Говорят, что y покрывает x, если не существует элемента zÎM такого, что x £ z £y.

На диаграмме Хассе элементы множества М изображаются в виде точек. Две точки x и y соединяются отрезком прямой в том и только том случае, когда y покрывает x. При этом точку x рисуют ниже точки y.

Примеры.

1) M ={ 1, 2, 3, 4, 5, 6 } упорядочено отношением £. Тогда его диаграмма выглядит так, как показано на рисунке 7. Такая диаграмма характерна для линейно упорядоченных множеств.

2) M = 2^{{ a, b, c }} = { Æ, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c }} упорядочено отношением включения – « Í ». Тогда его диаграмма выглядит как на рисунке 8.

3) M ={ 1, 3, 5, 7, 15, 21, 35, 105 } упорядочено отношением P={ (x, y) : y делится на x }. Его диаграмма Хассе изображена на рисунке 9 и совпадает с предыдущей диаграммой с точностью до обозначения элементов. Между элементами этих множеств можно установить биективное отображение, сохраняющее имеющуюся упорядоченность элементов. Говорят, что такие множества изоморфны (подобны) между собой относительно заданных на них отношений порядка.

Функции

Бинарное отношение Р называется однозначным, если для всякого элемента xÎпр₁Р существует не более одного (а может быть и вовсе ни одного) значения yÎпр₂Р.

Всюду определенное и однозначное бинарное отношение fÍA´B называется функцией или отображением множества А в множество В. Если А и В числовые множества, то функция называется числовой.

Для отображений чаще используются обозначения вида: f : A®B или A B. Пару (х, у) Îf чаще обозначают y = f(x), и поскольку отображение – это частный случай бинарных отношений, то определены все ранее введенные понятия: образа и прообраза для элементов и множеств, области определения и области значений отображения (или функции), а также понятия композиции отображений и обратного отображения.

Отображение (функция) называется постоянным, если " х₁ ¹ х₂Î A следует f(x₁) = f(x₂). Элемент хÎA называется неподвижной точкой отображения, если f(x) = x.

Отображение f : A®B называется инъективным или взаимно-однозначным отображением множества А в В, если для " х₁ ¹ х₂Î A Þ f(x₁) ¹ f(x₂). Т.е. каждый образ имеет только один прообраз. Подчеркнем, что не все элементы множества В обязаны иметь прообраз (должны быть чьими-нибудь образами).

Отображение называется сюрьективным (или сюрьекцией или отображением множества А на множество В), если f(A) = B или " yÎB $xÎA (один или несколько) и y=f(x), т.е. все элементы множества В являются чьими-нибудь образами (имеют по крайней мере один прообраз).

Отображение называется биективным (биекцией или взаимно однозначным отображением A на B), если оно одновременно инъективно и сюрьективно.

Биективное отображение A на А называется тождественным отображением, если все его элементы являются неподвижными точками, т.е. " xÎA следует, что f(x) = x.

Утверждения:

1) Если f : A®В и g : В®С – две функции, то g ∘ f: A→C – тоже является функцией.

2) Пусть f : A®В – функция. Для того, чтобы f ^‑1: В®А было функцией, необходимо и достаточно, чтобы f было биективным отображением. В этом случае f ^–1 называется отображением, обратным к f, или обратной функцией. При этом f ^‑1 – также биективно, f ^‑1∘ f =I_A – тождественное отображение А и f ∘ f ^‑1=I_B – тождественное отображение В.

Отображение f : A®В называется обратимым слева (справа), если существует отображение f_Л^‑1: В®А ( f_П^‑1: В®А ) такое, что f _Л^‑1∘ f =I_A ( f ∘ f _П^‑1=I_B ).

Критерий обратимости слева (справа)

Для того, чтобы отображение f : A®В было обратимым слева (справа), необходимо и достаточно чтобы оно было инъективным (сюрьективным).