В.Н. Нефедов - Алгебра множеств, бинарные отношения в примерах и задачах, страница 7

Однако это отношение не является симметричным, поскольку, например, 1  2 , однаконе выполняется 2  1 .Бинарное отношение  на множестве A называется транзитивным, если x, y, z  Ax, y   , y, z    x, z   (или, в дру-гой форме записи, x, y, z  A xy, yz  xz ).Пример 3.3. Бинарное отношение «равенства» на множестве действительных чисел R является транзитивным, так как x, y, z  Rx  y, y  z  x  z .

Бинарное отношение  на множестве действительных чисел R не является транзитивным, поскольку, например,1  2, 2  1 , однако, из этого не следует, что 1  1 . Бинарное отношение «меньше или равно» на R является транзитивным, так какx, y, z  R x  y, y  z  x  z . Бинарное отношение «параллель42ности» на множестве всех прямых на плоскости (или в трехмерном пространстве) является транзитивным.Пример 3.4. Бинарное отношение  на множестве всех подмножеств данного универсального множества U является рефлексивным, антисимметричным и транзитивным (см.

тему №1, стр. 4).Упражнение 3.2. Показать, что бинарное отношение «перпендикулярности» на множестве всех прямых на плоскости (или в пространстве)не является рефлексивным, антисимметричным, транзитивным.Утверждение 3.2. Пусть  – бинарное отношение на A . Тогдадля транзитивности  необходимо и достаточно, чтобы      .Доказательство. Пусть  транзитивно на A . Покажем, что     .

Для любой пары x, z     по определению операциипроизведения бинарных отношений выполняется: y  A : x, y   ,y, z   , откуда в силу транзитивности  на A имеем: x, z   .Пусть теперь      . Покажем транзитивность  на A . Действительно, x, y, z  Ax, y   , y, z    x, z       , т.е.транзитивность  на A доказана.Утверждение 3.3. Пусть  – бинарное отношение, являющеесярефлексивным на A .

Тогда      .Доказательство. Пусть x, y   . Покажем, чтоx, y     . Действительно, из рефлексивности  на A следует, чтоx, x   . Но тогда по определению операции произведения бинарных отношений получаем, чтоx, x   , x, y    x, y     ,что и требовалось доказать.Утверждение 3.4. Пусть  – бинарное отношение, являющеесярефлексивным и транзитивным на A . Тогда      .Утверждение 3.4 является следствием утверждений 3.2, 3.3.43Отношение эквивалентности. Рефлексивное, симметричное итранзитивное бинарное отношение  на множестве A называется эквивалентностью на A.Пример 3.5.

Бинарное отношение «равенства» на множестве действительных чисел R является эквивалентностью на этом множестве.Бинарное отношение «параллельности» на множестве всех прямых наплоскости (или в трехмерном пространстве) является эквивалентностьюна этом множестве. Бинарное отношение «подобия» на множестве всехтреугольников на плоскости является эквивалентностью на этом множестве. Бинарное отношение «равновеликости» (т.е. равенства площади)на множестве всех фигур на плоскости является эквивалентностью наэтом множестве.Утверждение 3.5. Пусть f : A  B – функция. Тогда бинарноеотношение  f на множестве A , определяемое условием: x1 , x2  Ax1  f x2  f ( x1 )  f ( x2 ), является эквивалентностью на A .Доказательство: (а) рефлексивность: x  A f ( x)  f ( x)  x f x ; (б) симметричность: x1 , x2  A x1 f x2  f ( x1 )  f ( x2 )  f ( x2 )  f ( x1 )  x2  f x1 ; ( в) транзитивность:x1 , x2 , x3  A x1  f x2 , x2  f x3  f ( x1 )  f ( x2 ), f ( x2 )  f ( x3 )  f ( x1 )  f ( x3 )  x1 f x3 .Пример 3.6.

Пусть A – множество студентов МАИ и f : A  B –отображение, ставящее в соответствие каждому студенту номер группы,в которой он учится (т.е. B – множество номеров студенческих группМАИ). Тогда x, y  A x f y  x и y учатся в одной студенческойгруппе. Из утверждения 3.5 следует, что  f – эквивалентность на A .Пусть  – эквивалентность на множестве A . Классом эквивалентности (смежным классом) элемента x по эквивалентности  называется множество [ x]  x /   { y  A | xy}  { y  A | yx} .44Совокупность классов эквивалентности элементов множества Aпо эквивалентности  называется фактор-множеством A по  иобозначается A /  . Таким образом, A /   {[ x]  | x  A} .Пример 3.7.

Возвращаясь к примеру 3.6, заключаем, что x  A[ x]  f – студенческая группа, в которой учится студент x , A /  f –множество студенческих групп МАИ.Пример 3.8. График функции y  f ( x), x  X  [0;5], представляет собой ломаную (см. рис.3.1), звенья которой параллельны координатной оси, либо биссектрисам координатных углов; координаты каждой вершины ломаной являются целыми числами. Эта функция порождает отношение эквивалентности  f на множестве X (см.

утверждение 3.5): x1 , x2  X x1  f x2  f ( x1 )  f ( x2 ) . Перечислить всеклассы эквивалентности.Решение. Рассмотрим случаи: (а) Пусть x  [0;1) . Тогда не существует точки x1  X , такой, что x  x1 , f ( x1 )  f ( x) , а следовательно,[ x]  f  {x} . (б) Пусть x {1;4}. Тогда [ x ] f  {1;4}. (в) Пустьx  (1;2) . Тогда [ x] f  {x, x1 , x2 } (см. рис. 3.1). При этом из геометрических соображений получаем: x  1  4  x1  x2  4 , откудаx1  5  x, x2  x  3 , а следовательно, [ x]  f  {x,5  x, x  3} . (г)Пусть x  [2;3]  {5} . Заметим, что f ( x)  2  x  [2;3]  {5} , а следовательно, [ x]  [2;3]  {5} .

(д) Пусть x  (3;4). Тогда, аналогичноf(в), получаем [ x]   {x,5  x,8  x} . (е) Пусть x  (4;5). Тогда, аналоfгично (в), получаем [ x]   {x, x  3,8  x} .f45y32f(x)101x23 x 1 4 x2 5xРис.3.1Нам понадобятся следующие вспомогательные утверждения.Лемма 3.1. Пусть  – эквивалентность на A , x1 , x2  A , и выполняется: x1  [ x2 ]  . Тогда [ x1 ]   [ x2 ]  .Доказательство.

Покажем, что (а) [ x1 ]   [ x2 ]  ; (б) [ x2 ]  [ x1 ]  . (а) Пусть x  [ x1 ]  . Тогда xx1 , откуда, используя то, что изx1  [ x2 ]  следует x1 x2 , в силу транзитивности  получаем xx2 , аследовательно, x  [ x2 ]  . В силу произвольности x  [ x1 ]  заключаемо справедливости утверждения (а). Докажем утверждение (б). Пусть теперь x  [ x2 ]  . Тогда xx2 , откуда, используя то, что из x1  [ x2 ] следует x2 x1 , в силу транзитивности  , получаем xx1 , а следовательно, x  [ x1 ]  .

В силу произвольности x  [ x2 ]  заключаем о справедливости утверждения (б). Из (а),(б) получаем, что [ x1 ]   [ x2 ]  .Лемма 3.2. Пусть  – эквивалентность на A . Тогда любые двакласса эквивалентности либо не пересекаются (т.е. их пересечение является пустым множеством), либо равны между собой.Доказательство.

Пусть [ x1 ]  , [ x 2 ]  – некоторые два класса эквивалентности. Тогда, если [ x1 ]   [ x2 ]    , то x  [ x1 ]   [ x2 ]  . Но46тогда в силу леммы 3.1 выполняются равенства: [ x1 ]   [ x]   [ x2 ]  ,т.е. лемма 3.2 полностью доказана.Разбиение множества. Связь с отношением эквивалентности.Разбиением множества A называется совокупность попарно непересекающихся подмножеств множества A таких, что объединение этихподмножеств дает A .

Таким образом, семейство множеств { Ai | i  I } ,где I – непустое индексное множество, будет являться разбиениеммножества A , если выполняются условия: (а) Ai  A , i  I ; (б) Ai  A ; (в) i, j  I , если Ai  A j , то Ai  A j   (или, что то жеiIсамое, если Ai  A j   , то Ai  A j ).Пример 3.9. Пусть M – множество студентов МАИ, G – множество студенческих групп МАИ. Тогда G – разбиение M .Следующая теорема показывает связь между разбиением множества и отношением эквивалентности на этом множестве.Теорема 3.1. (1) Всякое разбиение { Ai | i  I } множества A определяет на A отношение эквивалентности  : x, y    i  I :x, y  Ai .

(2) Всякое отношение эквивалентности  на множестве Aопределяет разбиение множества A на классы эквивалентности.Доказательство. (1) Докажем рефлексивность  . Пусть x  A .Тогда i  I : x  Ai  x, x  . Докажем теперь симметричность  .Пусть x, y  A , x, y   . Тогда i  I : x, y  Ai , или, что то же самое, y, x  Ai , а следовательно, y, x   . Докажем транзитивность . Пусть x, y, z  A , x, y , y, z   .

Тогда i, j  I : x, y  Ai ,y, z  A j  y  Ai  A j  Ai  A j    Ai  Aj  x, z  Ai  x, z   . (2) Покажем, что совокупность классов эквивалентностиA по  является разбиением A . Требуется доказать, что (а) x  A47[ x]   A ; (б)  [ x]   A ; (в) [ x1 ]   [ x2 ]   [ x1 ]   [ x2 ]    .xAЗаметим, что (а) следует из определения [x]  ; (б) следует из того, чтоx  A x  [x]  ; (в) является следствием леммы 3.2.ЗАДАЧИ:Задача 3.1. Пусть 1 ,  2 – симметричные бинарные отношения намножестве A .

Доказать, что 1   2 симметрично тогда и только тогда,когда 1   2 =  2  1 .Решение. В силу утверждения 2.1 (см. тему №2), имеем( 1   2 ) 1   21  11   2  1 .Симметричность 1   2 означает 1   2  ( 1   2 )(3.1)1или, в си-лу (3.1), имеем 1   2 =  2  1 .Задача 3.2. Доказать, что если  – произвольное бинарное отно-шение на A , то    1 – симметричное бинарное отношение на A .Решение. (    1 ) 1  (  1 ) 1   1     1 .Задача 3.3. Доказать, что объединение 1   2 антисимметричных на A бинарных отношений антисимметрично тогда и только тогда,когда 1   21  e A .Решение.

(а) Пусть 1   2 антисимметричное на A бинарноеотношение. Покажем, что 1   21  e A . Предположим, что  x, y  1   21 :  x, y  eA . Тогда  x, y  1 ,  x, y  21 ,x  y   x, y  1   2 ,  y, x   2  1   2 , x  y, т.е. пришлик противоречию с антисимметричностью 1   2 .(б) Пусть 1   21  e A .