7. Отношение порядка. Диаграммы Хассе. Примеры.

Def: бинарное отношение Р с= А², где А – не пусто, обладающие свойствами рефлексивности и транзитивности называются предпорядком.

Def:Р с= А²называется частичным порядком, если Р – рефлексивно, транзитивно и антисимметрично, т.е частичный порядок – антисимметричный предпорядок.

Def: отношение меньше называется строгим порядком, если определяется след образом: x<yx≤y и x≠у. Строгий порядок не является частичным порядком, т.к не рефлексивен.

Def:Если во множестве А есть элементы х и у, о которых нельзя сказать, что х≤у или у≤х, то такие элем называются несравнимыми. Def:частичный порядок называется линейным порядком, если любые 2 элемента х,уєА сравнимы.

Def: Если на непустом множестве А зафиксирован некоторый частичный (линейный) порядок называется частично(линейно)-упорядоченным множеством.

Def:аєА, где А-ЧУМ называется max(min), если х єА из того, что а≤х(х≤а) =>а=х. Def:аєА, где А-ЧУМ называется наибольшим(наименьшим), если х≤а (а≤х) для всех х є А.

Замечание: Всякий наибольший (наименьший) элемент является max(min). Всякое ЧУМ имеет maxи min.

Def:Верхней (нижней) гранью под В, ЧУМ А наз всякий элема єА: b≤а (а≤b)для всех b є B, т.е В с А, А-ЧУМ, а є А=>а – верх грань В.

Def: Точная верхняя (нижняя) грань В с А называется наименьшая верхняя (наибольшая нижняя) грань для В.

Def: Линейный порядок (≤) на множестве А называется полным, если каждое непустое подмножество множества А имеет наименьший элемент. В этом случае множества А – называется вполне упорядоченным (ВУМ)

Диаграммы Хассе.

Рассмотрим непустое множество А, конечное, ЧУМ <A,≤>.

Def: Говорят, что у покрывает эл х, если х≤у и не существует такого элем z: x<z<y. Если х<y, то существует х₁,х₂,…,x_n, что х=x₁<x₂<…<x_n=y, где x_i+1 покрывает x_i.

Def:Любое конечное ЧУМ можно представить в виде схемы, в кот каждый элемент изображается точкой на плоскости и если у покрывает х, то точки х и у соединяются отрезком, причем х располагают ниже у. Такие схемы наз диаграммами Хассе.

Замечание: диаграмма Хассе для конечного ЧУМ ясно показывает наибольший (наименьший) элемент, а также все max и min элементы.

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

Утверждение: конечное, непустое ЧУМ А содержит по крайней мере один max(min) элемент и если он единственный, то он наибольший (наименьший).

Из диаграммы Хассе для ЛУМ легко выделить цепи, т.е части, которые состоят из одной линии без разветвлений.

8. Отображения и их виды. Свойства функций. Примеры.

Опр: Бинарное отношение f называют функцией или отображением из множества А в множество B.

Dom f= A – область определения (ООФ)

Im f ⊆ B – область значения (ОЗФ)

∀ x ∈ Dom f=A ∃ y ∈ Im f ⊆ B : (x,y) ∈ f

Обозначение: f:A→B

Единственный y называют значением функции для аргумента х.

y=f(x) : f:x→y

Области определения и значения функции определяются как и для бинарных отношений.

Опр: ООФ– область определения бинарного отношения f. Dom f = {x|∃y: (x,y) ∈f}

Опр: ОЗФ – область значения бинарного отношения f. Im f = {y|∃x: (x,y)∈f}

Опр: Функции f и g называются равными  они равны как множества. Т.е. f=g ((x,y) ∈ f  (x,y) ∈ g)

Примеры:

1)Тождественные отношения являются функциями.

2) f={(x,y) | y - площадь x} это отображение является функцией.

3) f={(x,y) |y – фигура с площадью х} Не выполняется единственность y => f не является функцией.

Виды отображений.

Любая функция является отображением, но не любое отображение является функцией.

Опр: Бинарное отношение f называется отображением из A в B если Dom f⊆A и Im f⊆B

Опр: Бинарное отношение f называется отображением A в B если Dom f=A и Im f⊆B

Опр: Бинарное отношение f называется отображением A на B если Dom f=A и Im f=B

Опр: Образом множества А при отображении f из А в B называют f(A)={f(x) | x∈A}, A⊆B

Опр: Прообразом образа А при отображении f:A→B называют f ^-1 (B)={x | x∈Dom A f(x)∈B}

Опр: Отображение называется инъективным если:

1) ∀ x₁,x₂ ∈ Dom f из x₁≠x₂ => f(x₁)≠f(x₂)

2) ∀ x₁,x₂ ∈ Dom f из f(x₁)=f(x₂) =>x₁₌x₂

3) ∀y∈Im f ∃!x ∈ Dom f, (x,y) ∈ f (f(x)=y)

Любой элемент из области значения имеет единственный прообраз.

Опр: f:A→B называется сюрьективным если:

1) Im f=B

2) Для любого элемента из B имеется хотя бы один прообраз из А.

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

Опр: f:A→A называется подстановкой множества А в А

Простейшим примером подстановки являетcя тождественное отношение id_A

Свойства функций:

1. Композиция двух функций является функцией. f:A→B ; g:B→C; f○g:A→C

2. Композиция двух биективных функций – биекция. f:A↔B; g:B↔C; f○g:A↔C

3. f:A→B имеет обратное отображение f ^-1 :B→A  f – биекция.