WWW.DISSERS.RU

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

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


Pages:     | 1 | 2 || 4 | 5 |   ...   | 11 |

Таким образом, показано, что для указанных выше отношений ( ) ( ) ( ) ( ) (1.1) (обратное, вообще говоря, не верно).

1.2.3 Однородные отношения Отношение A2 называется бинарным на A или однородным. Понятно, что если отношение на A и B A, то B2 отношение на B.

Множество P(A2) всех бинарных на A отношений обозначим R(A). Для элементов R(A) произведение всегда определено, поэтому в силу ассоциативности произведения соответствий алгебра R(A), есть полугруппа. Мы будем всегда предполагать, что A =.

Для натурального k вводят естественное обозначение... = k.

k раз Проиллюстрируем действие введённых выше операций из R(A) на простом примере.

Пример 6 (Мальцев). Рассмотрим отношение =< на множестве N.6 Тогда справедливо следующее.

1. # : (a <#b = b < a) (<# = >). Таким образом, псевдообращением отношения меньше будет отношение больше.

2. 2 : a <2 b = x ( a < x x < b ) = a + 1 < b. Отсюда следует, что N a

3. # : a(< >)b = x ( a < x x > b ) = N x ( x > max {a, b} ) =.

N N 4. # : a(> <)b = x ( a > x x < b ) = N = x ( x < min {a, b} ) = 1 (0), если min {a, b} > 1 (иначе).

N Мы видели, что, вообще говоря, =. Отношения, R(A) называются перестановочными, если =.

Выделим некоторые типы однородных отношений на A. Отношения и назыA вают несобственными. Очевидно, что для любого отношения R(A) имеет место.

A Мы используем стандартные обозначения N, Z, Q и R для множеств натуральных, целых, рациональных и действительных чисел соответственно. N0 = N {0} пополненный натуральный ряд.

Единичное 1A (иначе диагональное ) отношение есть { (a, a) A2 }. Это отA ношение тождества. Ясно, что 1A единица в полугруппе однородных отношений на множестве A, и АС R(A),, 1A и есть моноид. С другой стороны, например, # может быть не равно 1A. Это объясняет выбор термина “псевдообратное” для отношения #. В обозначениях 1A,, когда это не приводит к недоразумениям, обычно опускают A подстрочный символ.

Определение 1.8. Пусть отношение R(A) называется R: рефлексивным, если, что означает справедливость aa;

AR: антирефлексивным, если =, означает, что aa;

S: симметричным, если #. Из свойства (#)# = сразу следует, что симметричность отношения эквивалентна свойству # =, или что ab = ba;

AS: антисимметричным, если # =, что означает ab ba a = b;

T: транзитивным, если 2, что означает ab bc ac.

Здесь a, b и c произвольные элементы множества A.

Утверждение 1.1. Пусть, R(A). Тогда 1. Если рефлексивно, то. Если рефлексивно, то.

2. Если транзитивно, то.

Доказательство. 1. Для произвольных a и b из A, если рефлексивно, справедливо ab ab bb ab.

Первое включение доказано, второе доказывается аналогично.

2. Для произвольных a и b из A, если транзитивно, справедливо a()b = x (ax xb) x (a( )x x( )b) = a( )2b a( )b, что эквивалентно требуемому.

1.3 Отношение эквивалентности и его свойства Исключительную роль в математике играют отношения эквивалентности.

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

1.3.1 Классы эквивалентности Множество всех эквивалентностей на непустом множестве A будем обозначать E(A).

Очевидно, любая эквивалентность на A содержит и содержится в. Последнее A A отношение называют иногда аморфной эквивалентностью.

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

Отношения эквивалентности часто обозначают знаком. По определению, эквивалентность описывается соотношением = # 2. Ниже будет показано, что 2 =, и, таким образом, справедливо соотношение = # = 2. (1.2) При данной эквивалентности на множестве A каждому a A можно сопоставить множество [a] эквивалентных ему элементов классов эквивалентности или смежных классов: [a] def { x A | x a }. Если эквивалентность фиксирована, то смежный класс = элемента a обозначают [a].

Формирование смежных классов происходит в ходе выполнения т.н. операции абстракции отождествления по данной эквивалентности. Понятно, что при этом каждый x A попадает в один и только один класс эквивалентности, и классы эквивалентности или совпадают, или не пересекаются, накрывая в совокупности всё множество A.

Отсюда, в частности следует, что 2 = и справедливо (1.2).

Говорят, что совокупность непустых множеств {Ai}iI образует разбиение множества A, если Ai = A и Ai Aj = при i = j; i, j I.

iI Пусть задано разбиение множества A. Тогда можно определить отношение эквивалентности так, что элементы A эквивалентны, если входят в один класс. Ясно, что такая эквивалентность единственна. Таким образом, между отношением эквивалентности и разбиениями A существует взаимнооднозначное соответствие.

Приведённые рассуждения можно оформить в виде очень простой, но очень важной теоремы.

Теорема 1.10 (О классах эквивалентности). Пусть A непустое множество. Если на A задана эквивалентность, то множество классов эквивалентности образует разбиение A. Если задано разбиение A на классы, то можно единственным образом определить эквивалентность на A так, что для любой пары a, b элементов A a b a и b находятся в одном классе разбиения.

Теорема о классах эквивалентности находит в математике широчайшее применение, и её по праву можно считать одной из главных (а то и самой главной) теоремой.Множество, элементами которого являются классы эквивалентности множества A по отношению эквивалентности называется фактор-множеством и обозначается A/.

Пример 7. 1. Если A множество зёрен, насыпанных в мешки, и для зёрен a и b положить a b, если они лежат в одном мешке, то классами эквивалентности являются множества зёрен, лежащих в одном мешке, а фактор-множеством A/ множество мешков.

2. Если W множество слов русского языка и для слов u и v положить u v, если они начинаются с одной и той же буквы (в русском языке 33 буквы), то классами эквивалентности являются множества слов, начинающихся на данную букву, а фактор-множеством W/ множество соответствующих букв ( |W/ | = 31 ).

Успенский В.А. Что такое аксиоматический метод Ижевск: Издательский дом Удмуртский университет, 2000.

1.3.2 Устойчивость эквивалентности Будем говорить, что отношение эквивалентности устойчиво относительно некоторой операции над множествами, если результат применения этой операции к эквивалентностям есть эквивалентность. Ясно, например, эквивалентность не устойчива относительно взятия дополнения.

Теорема 1.11. Отношение эквивалентности устойчиво относительно пересечения множеств.

Доказательство. Покажем рефлексивность, симметричность и транзитивность пересечения эквивалентностей. Поскольку и эквивалентности, то для них справедливо соотношение (1.2). Тогда R: ;

S: ( )# = # # = ;

T: ( )2 2 2 =.

При доказательстве транзитивности мы воспользовались соотношением (1.1).

Замечание. Из доказанной теоремы следует, что пересечение эквивалентностей из произвольной непустой (возможно бесконечной) совокупности есть эквивалентность.

Теорема 1.12. Пусть и эквивалентности. Тогда если для любой пары смежных классов по и, соответственно, по справедливо утверждение: либо один из классов лежит в другом, либо они не пересекаются, то есть эквивалентность. Если эквивалентность, то =.

Доказательство. Пусть приведённое утверждение неверно, т.е. имеются смежные классы [a] и [b] не лежат один в другом и имеют общий элемент c. Можно считать, что a [a] [b] и b [b] [a].

[a] [b] a c b A Пары (a, c) и (c, b) содержатся в. Если бы это отношение было эквивалентностью, то оно, в силу транзитивности, содержало бы и пару (a, b). Последнее означает справедливость либо ab, либо ab. Это, однако, не имеет места, и, следовательно, не эквивалентность. C другой стороны, (a, b).

Если же приведённое утверждение верно, то любой класс [a] есть элемент разбиения некоторого класса [b], либо наоборот, и классы эквивалентности суть “объемлющие классы”.

Пример 8. Пусть и эквивалентности на множестве A = {a, b, c, d} со смежными классами A/ = {{a}, {b}, {c, d}} и A/ = {{a, b}, {c}, {d}}.

Тогда есть эквивалентность и A/( ) = {{a, b}, {c, d}}.

Мы уже отмечали, что отношения могут быть, а могут и не быть перестановочными.

Покажем, что то же справедливо и для эквивалентностей. Пусть и эквивалентности на множестве A = {a, b, c, d} со смежными классами {a, b}, {c, d} и {a, c}, {b, d} соответственно. Тогда и аморфные эквивалентности на A и, значит, и перестановочны. Если же A = { a, b, c }, а смежные классы по эквивалентностям, суть соответственно {a, b}, {c} и {a}, {b, c}, то a()c, но неверно, что a()c, и данные эквивалентности не перестановочны. При этом, ни, ни не являются эквивалентностями.

Теорема 1.13. Произведение эквивалентностей будет эквивалентностью, если и только если они перестановочны.

Доказательство. Пусть и эквивалентности.

() Если эквивалентность, то = ()# = ## =.

() Если =, то иммем R: для произвольного a A имеем aa aa, откуда a()a, т.е. ;

S: ()# = ## = = ;

T: ()2 = = = 22 =.

Теорема 1.14. Пусть, и эквивалентности. Тогда 1), ;

2).

Доказательство. 1) Данные включения следуют из п. 1) утверждения 1.1.

2) Включение следуют из п. 2) утверждения 1.1, если заметить, что.

Таким образом, произведение эквивалентностей содержит каждую их них и содержится в любой эквивалентности, которая их порознь содержит. Заметим, что здесь может и не быть эквивалентностью.

Если S некоторое свойство элементов множества A, то наименьшим подмножеством множества A, обладающим свойством S называется пересечение всех подмножеств A, элементы которых обладают этим свойством.

В случае, когда можно взять =, теорема 1.14 имеет важное Следствие. Для перестановочных эквивалентностей произведение является наименьшей эквивалентностью, их содержащей.

Ниже мы укажем процедуру построения наименьшей эквивалентности, содержащую данное отношение.

e Определение 1.10. Наименьшая эквивалентность, содержащая отношение, называется эквивалентным замыканием.

t Наименьшее транзитивное отношение, содержащее отношение, называется транзитивным замыканием.

Заметим, что t, есть моногенная полугруппа, порождённая отношением.

Транзитивное замыкание данного отношения легко строится. Введём обозначение + = n. По определению произведения отношений, справедливость a+b означаn=ет существование таких элементов x0 = a, x1,..., xn = b соответствующего множества, что x0x1... xn-1xn. Ясно, что + транзитивно, и если уже транзитивно, то + =.

t Утверждение 1.2. Для произвольного однородного отношения справедливо = +.

t Доказательство. С одной стороны, + и + транзитивно. С другой, из t t следует + (t)+ = и, по определению транзитивного замыкания, + =.

Следствия. 1. Для произвольного однородного отношения справедливо e = { # }t.

e Действительно, обозначим = { # }. Отношение должно, кроме, e e t e содержать и #, поэтому. В силу транзитивности имеем, t e откуда = по определению эквивалентного замыкания.

2. Эквивалентное замыкание совокупности эквивалентностей совпадает с объединением всевозможных произведений этих эквивалентностей.

Действительно, с одной стороны, данное объединение содержит все эквивалентности из рассматриваемой совокупности, а с другой содержится во всех из них (см.

теорему 1.14.) В частности, для двух эквивалентностей и их эквивалентное замыкание совпадает с объединением всевозможных произведений вида,,,.... Отсюда следует, что если и перестановочны, то {, }e = = (см.

следствие из теоремы 1.14).

Рефлексивным замыканием однородного на множестве A отношения называют отношение +. Обычно по определению полагают 0 = и тогда =. Ясно, A A n=что e =.

Пример 9. 1. Если отношение на множестве натуральных чисел, определяемое def правилом mn = m + 1 = n, то t = <.

2. Пусть на множестве A = { 1, 2, 3, 4, 5, 6, 7, 8 } заданы эквивалентности и со смежными классами соответственно {1, 2}, {3, 4}, {5, 6, 7}, {8} и {1, 4}, {2, 3}, {5, 6}, {7}, {8}.

Тогда эквивалентность ( )e порождает смежные классы {1, 2, 3, 4}, {5, 6, 7} и {8}.

3. Если на множестве A = { a, b, c, d, e, f } заданы эквивалентности и со смежными классами соответственно {a, b}, {c}, {d}, {e, f} и {a}, {b, c}, {d, e}, {f}, тогда ни, ни не есть эквивалентность, а эквивалентное замыкание {, }e, совпадающее с { }, порождает смежные классы {a, b, c} и {d, e, f}.

Пусть и две эквивалентности на множестве A. Отношение включения для них означает, что любой смежный класс по лежит в некотором смежном классе по. Иными словами, разбиение множества A на смежные классы по есть подразбиение его разбиения на смежные классы по. Говорят также, что разбиение по есть измельчение разбиения по. Для таких эквивалентностей определим на фактор-множестве A/ дробную эквивалентность / по правилу [x] (/) [y] def xy (x, y A).

= Таким образом, два смежных класса по эквивалентны по /, если они находятся в одном смежном классе по.

1.4 Соответствия и отображения 1.4.1 Основные типы соответствий Рассмотрим соответствие A B между непустыми множествами A и B. Ясно, что = =. Кроме того, всегда справедливо включение #. Действительно, A B ab = ab b#a ab a(#)b.

Для соответствия первая проекция называется областью определения, а вторая областью значений отношения, которые обозначаются Dom и Im соответственно.

Для a A множество (a) = { b B | ab } называется образом элемента a при соответствии. Если X A, то множество (X) = (x) называется образом xX множества X при соответствии. Если b B то множество #(b) = { a A | ab } называется прообразом элемента b при соответствии.

В связи с введёнными понятиями рассмотрим ещё одно свойство произведения соответствий.

Теорема 1.15. Пусть A B и B C. Тогда P r1() = #(P r1), P r2() = (P r2).

Доказательство. Заметим, что через проекции соответствия могут быть записаны образ и прообраз соответствующих множеств:

P r1 = #(C) и P r2 = (A).

Пользуясь свойствами соответствий и их псевдообращений получим P r1() = ()#(C) = (##)(C) = #(#(C)) = #(P r1) ;

P r2() = ()(A) = ((A)) = (P r2).

Если соответствие между множествами A и B и A A, то соответствие |A = (A B) = { (a, b) | a A } называется ограничением или сужением соответствия на подмножество A. Понятие сужения очевидным образом распространяется на произвольные отношения.

Выделим основные типы соответствий между A и B, обладающие особыми свойствами.

Определение 1.11. Соответствие между A и B называется • многозначным отображением или всюду определённым соответствиями, если # (что эквивалентно Dom = A );

A • частичным отображением A в B, если # (что эквивалентно B ab1 ab2 b1 = b2 для a A );

• функциональным или отображением A в B, если # # (что A B эквивалентно существованию для всех a A единственного b B такого, что ab );

• дифункциональным или квазиоднозначным, если # или, с учётом доказанного выше, # = (что эквивалентно (a1) (a2) = (a1) = (a2) для всех a1, a2 A или #(b1) #(b2) = #(b1) = #(b2) для всех b1, b2 B ).

Данные соотношения указывают, что как образы, так и прообразы дифункциональных отношений либо совпадают, либо не пересекаются. Это означает, что дифункциональные отношения задают разбиения множеств Dom и Im на одинаковое число классов, причём эти разбиения обладают тем свойством, что образы элементов из одного класса разбиения Dom лежат в одном и том же классе разбиения Im.

1.4.2 Отображения Наибольшее применение на практике находят функциональные соответствия. Рассмотрим их подробнее.

Отображение из A в B называют также функцией из A в B.8 При этом исполь зуют обозначения : A B или A B. Тот факт, что ab записывают как (a) = b или a b ; при теоретических выкладках удобна запись a = b или даже a = b.

Множество всех отображений A B будем обозначать F un (A, B). При A = B будем пользоваться обозначением F un (A).

Рассмотрим специальные классы отображений множества A в множество B. Если окажется, что (x) = b B для всех x A, то отображение называют постоянным или константой. Единичное отношение, рассматриваемое как отображение A на A себя, называют тождественным. Для тождественного отображения будем употреблять обозначение idA.

Легко показать, что для отображений A B и B C произведение также является отображением. Действительно, для и справедливо # # и # #.

A B B C Но тогда # = # (#) = ()()#. Включение ()#() C A B показывается аналогично. Таким образом, отображение.

Pages:     | 1 | 2 || 4 | 5 |   ...   | 11 |






















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

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