WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 11 |

Также понятно, что произведение функций как отображений совпадает с их композицией () и, в силу ассоциативности произведения соответствий, имеет место def ( )(x) = ((x)) = ( )(x)9.

Определение 1.12. Отображение : A B называется Таким образом, мы не различаем понятия функционального отображения и функции, хотя они не тождественны друг другу. Пример для знакомых с теорией алгоритмов: невычислимые функции, строго говоря, являются лишь функциональными отображениями, а не функциями.

Здесь становится очевидным удобство записи ((x)) = x.

• вложением или инъективным отображением A в B, если idA = #. Легко видеть, что при вложении различные элементы A переходят в различные элементы B и прообраз #(y) элемента y Y не более, чем одноэлементное множество.

Тот факт, что вложение A в B записывают A B.

Если A B, то вложение (x) = x называется естественным вложением A в B ;

• наложением или сюръективным отображением A в B, если # = idB. Легко видеть, что при наложении каждый элемент множества B имеет свой прообраз.

i Ясно, что для A = A1... An отображения A Ai, определяемые как i (a1,..., ai,..., ak) ai, i = 1, n сюръективны. Они называются отображениями проектирования;

• биекцией, биективным, взаимнооднозначным отображением, если idA = # # = idB, т.е. оно является одновременно и вложением, и наложением. Множество всех биективных отображений из A в B будем обозначать Bij (A, B). В случае A = B будем пользоваться обозначением Bij (A).

Отображение : B A называется обратным отображению : A B, если idA = = idB.

Ясно, что обратное отображение существует только для биекций, и при этом оно единственно. Если отображение, обратное к, то используется обозначение = -1, и -1 = #.

Моноид F un (A),, idA называют моноидом эндоморфизмов множества A и обо-значают End A. Группу Bij (A),,, idA называют группой автоморфизмов множества A и обозначают Aut A.

Поскольку отображения являются отношениями, к ним можно применять все теоретико-множественные операции. Однако ясно, что если, F un (A, B), то и будет от отображениями лишь при =. Поэтому интересной здесь будет лишь операция произведения (композиции) отображений.

Нетрудно показать, что произведение двух вложений, наложений или биекций также является, соответственно, вложением, наложением или биекцией. Отметим, что для конечного множества A инъективность, сюръективность и биективность функций из F un (A) равносильные условия.

Следующие две теоремы характеризуют вложение и наложение через свойства их произведений (композиций).

Теорема 1.16. Отображение f : X Y инъекция если и только если для любых двух отображений g1, g2 из некоторого множества Z в X g1 f = g2 f g1 = g2.

Доказательство. () Пусть f инъекция из множества X в Y и для любых двух отображений g1, g2 из Z в X справедливо g1 f = g2 f. Но тогда же справедливо g1 f f# = g2 f f# или g1 idX = g2 idX, откуда g1 = g2.

() Пусть для любых двух отображений g1, g2 из Z в X справедлива равносильность g1 f = g2 f g1 = g2, но f не является вложением. Тогда найдутся x1 и xиз X, что x1 = x2, но f(x1) = f(x2). Возьмём в качестве Z одноэлементное множество z0 и построим два отображения g1, g2 из Z в X такие, что g1(z0) = x1, g2(z0) = x2.

Поскольку f(g1(z0)) = f(g2(z0)), а других значений аргумента нет, то g1 f = g2 f, g1 = g2 и x1 = x2. Противоречие.

Теорема 1.17. Отображение f : X Y сюръекция если и только если для любых двух отображений g1, g2 из Y в некоторое множество Z f g1 = f g2 g1 = g2.

Доказательство. () Пусть f сюръекция из множества X в Y и для любых двух отображений g1, g2 из Y в Z справедливо f g1 = f g2. Из того, что f наложение следует непустота f#(y) для любого y Y. Пусть x f#(y).10 Тогда g1(y) = g1(f(x)) = g2(f(x)) = g2(y), что в виду произвольности элемента y влечёт g1 = g2.

() Пусть для любых двух отображений g1, g2 из Y в Z справедлива равносильность f g1 = f g2 g1 = g2, но f не является наложением. Тогда найдётся элемент y из области Y Im(f). Зафиксируем в Y элемент y0 = Y и рассмотрим отображение g2 : Y Y, определяемое условием t, если t = y, g1(t) = y0, если t = y.

Ясно, что g1 = idY, в силу чего f g1 = f idY. Однако для всех x X имеем g1(f(x)) = f(x) = idY (f(x)).

Противоречие.

Свойства биекции позволяют описывать фундаментальные свойства множеств.

Теорема 1.18 (Кантора-Шрёдера-Бернштейна11). Если для двух множеств A и B существуют биекции 1 между A и подмножеством B и 2 между B и подмножеством A, то существует биекция между A и B.

Доказательство. Обозначим A0 = A и Im(2) = A1. Ясно, что можно считать A0 Aи Im(1) B, иначе теорема тривиально справедлива. Также ясно, что в этом случае A и B бесконечные множества.

Последовательное применение отображений, указанных в формулировке теоремы, даёт взаимно однозначное отображение = 1 2 множества A0 на своё подмножество A2 и A1 A2. Обозначим (Ai) = Ai+2, i = 0, 1, 2.... Получим цепочку строго содержащихся друг в друге подмножеств A: A = A0 A1 A2....

Обозначим Ci = Ai Ai+1, i = 0, 1, 2... и C = Ai. По построению между i>множествами C0, C2,... существует взаимно однозначное соответствие ; то же и для множеств C1, C3,....

Построим теперь взаимно однозначное отображение между A0 и A1. Положим (x), если x C2i, i = 0, 1,..., (x) = (см. рис. 2).

x, иначе - -Таким образом, имеем взаимно однозначные соответствия A A1 B и искомая биекция.

Заметим, что возможность указания такого x эквивалентна принятию аксиомы выбора (см. п. 2.1.4).

Теорема была приведена без доказательства в работе Кантора 1883 г. и доказана позднее Шрёдером и Бернштейном.

...

= A0 C0 + C1 + C2 + C3 + C4 + + C...

= A1 C1 + C2 + C3 + C4 + + C Рис. 2: Схема соответствия между A0 и A1 (символ + подчёркивает дизъюнктивность разбиения множеств) 1.4.3 Основные свойства отображений Пусть эквивалентность на A. Тогда существует функция : A A/, ставящая в соответствие каждому элементу a A его класс эквивалентности, т.е. (a) = [a]. Такое отображение называется естественным (каноническим, натуральным). Каноническое отображение мы будем обозначать nat(A, ) или просто nat(), если множество A фиксировано при данном рассмотрении. Понятно, что nat() наложение.

Пример 10. Для примера 7 имеем:

1. (a) мешок, в котором лежит зерно a;

2. (u) все слова, имеющие общую первую букву со словом u.

Пусть дано отображение, определённое на множестве A. Его ядром называется отношение Ker R(A), заданное как a1(Ker )a2 def (a1) = (a2).

= Очевидно, что ядро эквивалентность на своей области определения и подчеркивая это, Ker называют ядерной эквивалентностью. С ядерной эквивалентностью отображения из A связано фактор-множество A/Ker и натуральное отображение nat(A, Ker ). Заметим, что отображения : A B и nat(A, Ker ) имеют общую ядерную эквивалентность, но отображают A в разные множества: соответственно в B и в A/Ker. Также нетрудно видеть, что Ker = #.

Ясно, что если ядро отображения из A в B есть единичное отношение на A, то вложение A в B : действительно, Ker = 1A означает, что a1 = a2, то (a1) = (a2).

Далее мы будем пользоваться следующим удобным изображением соответствий. Если A, B, C, D некоторые множества и : A B, : B C, : A C, : B D, : C D, то указанные отображения на них наглядно задают в виде диаграмм, приведённых на рис. 3.

Говорят, что эти диаграммы коммутативны, если = и = соответственно.

Аналогично определяется коммутативность и для более сложных диаграмм. Биективные отображения будем обозначать на диаграммах двунаправленными стрелками.

Сформулируем теперь основную теорему о разложении отображений.

A B A B C C D Рис. 3: Диаграммы отображений на множествах Теорема 1.19 (О разложении отображений). Пусть даны непустые множества A, B и отображение : A B. Тогда для отображения справедливо разложение = µ, (1.3) где = nat(Ker ), взаимнооднозначное соответствие между A/Ker и Im и µ вложение Im в B.

Доказательство. Теорема утверждает, что диаграмма A B µ A/Ker Im коммутативна.

Ясно, что Im есть подмножество B и в качестве µ возьмём естественное вложение. Из определения Ker следует, что отображение : A/Ker Im биективно.

Отсюда следует справедливость разложения (1.3 ), если в качестве взять nat(Ker ).

При этом все элементы разложения (1.3) определены однозначно.

Следующая теорема является следствием только что доказанной.

Теорема 1.20 (Основное свойство отображений). Пусть даны непустые множества A, B и отображение : A B. Тогда имеется единственное отображение : A/Ker B являющееся вложением, и такое, что диаграмма A B nat (Ker) A/Ker коммутативна.

Доказательство. Положим в (1.3 = µ ). Тогда ([a]Ker) = (a) однозначно определённое вложение Ker в B.

Из данной теоремы следует, что для любого отображения : A B справедливо каноническое разложение =, где = nat(A, Ker) наложение, а вложение. Такое разложение, очевидно, единственно. Это свойство и называют основным свойством отображений.

Основное свойство отображений можно обобщить, если заметить, что для произвольной эквивалентности, содержащийся в Ker существует единственное отображение : A/ B.

Теорема 1.21 (О фактормножествах). Пусть даны непустые множества A, B с отображением : A B и эквивалентность на A такая, что Ker. Тогда имеется единственное отображение : A/ B такое, что диаграмма A B nat () A/ коммутативна.

Доказательство. Коммутативность диаграммы обеспечивается при задании правилом ([a]) = (a), a A. Такое задание корректно, поскольку, в силу Ker, всем элементам x из [a] соответствует единственное значение (x) = (a). Ядерная эквивалентность отображения единичное отношение на A/ лишь при = Ker, и поэтому, вообще говоря, не есть вложение. Единственность следует из теоремы о классах эквивалентности.

Из данной теоремы следует, что для любого отображения : A B и эквивалентности на A такой, что Ker, справедливо обобщённое разложение =, где = nat(A, ) наложение. Такое разложение, очевидно, не единственно, поскольку возможны, вообще говоря, различные измельчения классов эквивалентностей по Ker.

Иногда данную теорему коротко формулируют как утверждение о возможности факторизации любого отображения по эквивалентности, содержащийся в его ядре.

Из основного свойства отображений вытекает Теорема 1.22 (О дробных эквивалентностях). Пусть дано множество A и эквивалентности, на нём такие, что. Тогда существуют отображение : A/ A/ и биекция : (A/)/(/) A/ такие, что диаграмма A nat nat A/ A/ nat (/) (A/)/(/) коммутативна.

Доказательство. Зададим функцию правилом ([a]) = [a]. Нетрудно видеть, что такое задание корректно. Далее применим теорему 1.20 к нижней части диаграммы.

Поскольку, как легко видеть, накрытие, то ([[a]]/) = ([a]) = [a] биекция.

2 Порядки и решётки 2.1 Отношение порядка 2.1.1 Предпорядки и порядки Определение 2.1. Предпорядками называют рефлексивные и транзитивные бинарные отношения.

Пример 11. 1. Отношение делимости ( | ) на множестве целых чисел Z есть предпорядок.

2. Отношение на множестве действительных функций, задаваемое условием fh множество нулей функции f содержится во множестве нулей функции h.

является предпорядком.

Из определения следует, что если предпорядок то одновременная справедливость xy и yx может быть как при x = y, так и при x = y.

Определение 2.2. Рефлексивные, антисимметричные и транзитивные бинарные отношения называют отношениями частичного порядка.

Отношения частичного порядка будем обозначать. Антисимметричность определяет равенство x = y, при x y и y x. Когда x y и x = y, то будем писать x y.

Пример 12. 1. Оба предпорядка из примера 11 не являются частичными порядками ввиду отсутствия антисимметричности: (1) из m | n и n | m следует не m = n, а лишь |m| = |n|; (2) совпадение множеств нулей функций не означает равенства последних.

2. Важнейшим примером частичного порядка является отношение включения на совокупности подмножеств некоторого множества. При этом говорят, что такая совокупность упорядочена по включению.

3. Диагональное отношение на произвольном множестве является частичным порядком. Множество с таким порядком называют тривиально упорядоченным.

Из предпорядка rho всегда можно построить порядок, если отождествить элементы, x и y, для которых одновременно xy и yx.

Теорема 2.1.

1. Если предпорядок на множестве P, то отношение, определяемое условием def ab = a b b a является эквивалентностью.

2. Отношение на фактор-множестве P/, определяемое условием [a] [b] def a b = является частичным порядком.

Доказательство. 1. Вследствие определения, отношение приобретает свойство симметричности в дополнение к свойствам рефлексивности и транзитивности, наследуемых от.

2. Если [a] = [a ], [b] = [b ] и [a] [b], то a a b b, т.е. [a ] [b ] и отношение на P/ определено корректно.

Свойства рефлексивности и транзитивности наследуются от отношения. Если [a] [b] и [b] [a], то [a] [b] [a], т.е. [a] = [b], так что отношение оказывается и антисимметричным.

Пример 13. Для примера 11 имеем:

1. [n] = { n, -n } и есть отношение делимости на фактор-множестве Z/ = { 0, 1,... }.

2. (a) fh множество нулей функций f и h совпадают.

(b) [f] [h] множество нулей любой функции из [f] содержится во множестве нулей любой функции из [h].

Элементы a и b сравнимы, если либо a b, либо b a, и несравнимы в противном случае. Нетрудно видеть, что отношение сравнимости есть эквивалентность.

Если a b, то говорят, что a предшествует b или b следует за a, содержит a.

Множество { x | a x x b } называют интервалом и обозначают [a, b]. Интервал [a, b] непуст, если a b. Если [a, b] = {a, b}, то говорят, что a непосредственно предшествует b, и что b непосредственно следует за a.

2.1.2 Частично упорядоченные множества Пару P = P,, где P множество, а частичный порядок на нём, называют частично упорядоченным множеством (сокращённо ч.у. множеством ). P представляет собой пример нового типа алгебраической системы, а именно модели. АС является моделью, если в ней отсутствуют операции на носителе, но имеются отношения на нём.

Пример 14. 1. Модели R,, N, |, Bn, и P(M), суть ч.у. множества.

2. Пусть A =. Модель E(A), есть ч.у. множество, состоящее из разбиений множества A, упорядоченных по измельчению.

Ясно, что если P, ч.у. множество и Q P, то и Q, ч.у. множество, где сужение отношения на Q.

Для наглядного представления конечных ч.у. множеств, имеющих небольшое число элементов, используют диаграммы Хассе. На этих диаграммах изображают элементы ч.у. множеств, причём если элемент a предшествует элементу b, то a рисуют ниже b, и соединяют их отрезком, если a непосредственно предшествует b.

На рис. 4 для примера приведены диаграммы Хассе для ч.у. множеств { 0, 1, 2, 3 }, и P({ 1, 2, 3 }),.

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

Всякому выражению x y в дуальном ч.у. множестве соответствует выражение x y.

Ясно, что к ч.у. множествам применим следующий принцип двойственности.

{1, 2, 3} {1, 2} {1, 3} {2, 3} {1} {2} {3} a) b) Рис. 4: Диаграммы Хассе двух ч.у. множеств Принцип двойственности (для частично упорядоченных множеств). Любое утверждение, истинное в ч.у. множестве остаётся истинным в ч.у. множестве, дуальном к нему.

Определение 2.3. Элемент u P ч.у. множества P, называют:

1) максимальным, если u x u = x, 2) минимальным, если u x u = x, 3) наибольшим, если x u, 4) наименьшим, если x u для любых x P.

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

Понятно, что наибольший [наименьший] элемент есть одновременно и единственный максимальный [минимальный]. С другой стороны, максимальных или минимальных элементов может быть несколько, а может и не быть совсем.

1 Пример 15. 1. Рассмотрим ч.у. множество Nf,, где Nf множество единичных наборов монотонной булевой функции f(x1, x2, x3, x4, x5) = x1 x2x3 x3x4x5.

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 11 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.