Материал: Дискретная математика теория и практика

Следовательно, отношение P2 антисимметрично, так как матрица || P2 ∩ P2−1 || вне главной диагонали содержит только нули.

3.7. Отношение эквивалентности

Определение 3.13. Бинарное отношение на множестве А называется от- ношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Отношение эквивалентности обычно обозначают символами ~ или ≡. Примерами отношения эквивалентности являются отношение равенства

на множестве действительных чисел, отношение параллельности на множестве прямых евклидовой плоскости.

Определение 3.14. Пусть R – отношение эквивалентности на множестве

А и a A . Классом эквивалентности, порожденным элементом a, называется множество {x A xRa}.

Класс эквивалентности, порожденный элементом a, будем обозначать через a/R. Совокупность всех классов эквивалентности отношения R на множестве А обозначается через А/R.

Определение 3.15. Представителем класса эквивалентности называется любой элемент этого класса.

Определение 3.16. Пусть А – непустое множество. Фактор- множест- вом множества А по отношению эквивалентности R называется множество A/R всех классов эквивалентности.

Теорема 3.1 (прямая). Пусть R – отношение эквивалентности на непустом множестве А. Тогда фактор-множество A/R является разбиением множества А.

Доказательство. Так как отношение R рефлексивно, то для любого a A имеем aRa. Это значит, что каждый элемент a множества А принадлежит классу эквивалентности a/R. Итак, имеем семейство непустых классов a/R (a/R содержит по крайней мере один элемент a) и U a / R = A. Осталось доказать, что пе-

a A

ресечение любых двух различных классов пусто. Для этого достаточно показать, что классы эквивалентности, имеющие хотя бы один общий элемент, совпадают. Пусть a/R и b/R – классы эквивалентности, имеющие общий элемент c. Тогда cRa и cRb. В силу симметричности отношения R из cRa следует aRc. Пусть х – любой элемент из a/R , тогда хRa. Имеем, хRa и aRc. Следовательно, в силу транзитивности отношения R xRc. Имеем, xRc и cRb. Тогда xRb, так как отношение R транзитивно. Следовательно, x b/R. Таким образом, a/R b/R. Аналогично доказывается, что b/R a/R. Следовательно, a/R = b/R.

42

Из теоремы 3.1 непосредственно вытекает следующее следствие. Следствие. Пусть R – отношение эквивалентности на множестве А. То-

гда

1)( a А) a a /R;

2)U a / R = A;

a A

3)( a ,b А) a /R = b/R a R b;

4)a /R ≠ b/R a /R ∩ b/R = .

Пусть S – разбиение непустого множества А и RS – бинарное отно- шение, определяемое следующим образом: (x,y) RS тогда и только, когда x

и y принадлежат одному и тому же подмножеству семейства S.

Теорема 3.2 (обратная). Отношение RS, соответствующее разбиению S непустого множества А, является отношением эквивалентности на А, причем фактор-множество А/RS совпадает с разбиением S.

Доказательство. 1. Так как S есть разбиение, то ( a А) M i S : a M i .

Следовательно, по определению отношения RS, aRs a , а значит RS – рефлексивно.

2.Пусть a, b – произвольные элементы из А такие, что aRSb. Тогда, по оп-

ределению отношения RS, Mj S: a, b Mj . Следовательно, bRSa. Получили, что RS – симметрично.

3.Пусть a, b, c – произвольные элементы из А такие, что aRS b bRS c. Следовательно, по определению отношения RS, Mi , Mj S: a, b Mi

b, c Mj. Отсюда b Mi ∩ Mj. Но тогда, по определению разбиения, Mi = Mj , а

значит, a, c Mi , и, по определению отношения RS, aRSc. Получили, что RS – транзитивно.

Из п. 1 – 3 следует, что RS – отношение эквивалентности. Фактор-

множество A/RS совпадает с разбиением S по определению отношения RS. Пример 3.10. На множестве A = {a, b, c, d, e} задано отношение

R = {(a, a), (b, b), (b, c), (b, d), (c, b), (c, c), (c, d), (d, b), (d, c), (d, d), (e, e)}. Дока-

зать, что R является отношением эквивалентности на множестве A. Найти классы эквивалентности, на которые разбивается множество A отношением R.

Решение. Построим граф отношения R (рис. 3.4), на основании которого

Замечание 3.3. Частным случаем отношения эквивалентности является отношение равенства элементов некоторого множества А, которое определяет разбиение множества на одноэлементные классы эквивалентности:

43

( x A) x / = {x}. В этом случае классов эквивалентности оказывается

столько же, сколько элементов содержится в множестве А, так как каждый элемент из А эквивалентен только самому себе.

Вдругом частном случае все элементы множества А эквивалентны друг другу. При этом фактор-множество А / состоит всего из одного класса – самого множества А.

Влюбом другом случае среди классов эквивалентности имеется хотя бы один класс, который содержит больше одного элемента и в то же время не сов-

падает с самим множеством А. Замечание 3.4. Понятие отношения эквивалентности имеет большое зна-

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

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

3.8. Счетные и несчетные множества

Определение 3.17. Множества X и Y называются изоморфными (пишут X Y), если между ними можно установить взаимно однозначное соответствие.

Утверждение 3.3. Бинарное отношение «быть изоморфными» на совокупности множеств является отношением эквивалентности.

По теореме 3.1 все множества относительно отношения «быть изоморфными» разбиваются на классы эквивалентности, каждый из которых состоит из попарно изоморфных между собой множеств.

Определение 3.18. То общее, что есть у всех множеств одного и того же класса эквивалентности по отношению «быть изоморфными» (количество элементов), называется кардинальным числом (т.е. количественным) или мощно- стью множеств данного класса.

Таким образом, мощность множества представляет собой обобщение понятия «число элементов» на случай произвольного (конечного или бесконечного) множества. Как и для конечного множества, мощность бесконечного множества X обозначается через |X|.

Определение 3.19. Множества X и Y называются равномощными, если они изоморфны, то есть между ними можно установить взаимно однозначное соответствие. При этом пишут |X| = |Y|.

Пример 3.11. Пусть Х – множество действительных чисел, а У – множество точек координатной прямой. Установим между ними следующее соответствие: каждому действительному числу x сопоставим точку M(x) координатной

44

прямой. Это соответствие является взаимно однозначным, так как каждому действительному числу сопоставляется единственная точка координатной прямой и, наоборот, каждая точка на координатной прямой соответствует только одному числу. Следовательно, |X| = |Y|.

Пример 3.12. Пусть Х – множество точек отрезка АВ, У – множество точек отрезка СD, причем длины отрезков АВ и СD различны. Между множествами Х и У можно установить взаимно однозначное соответствие так, как показано на рис. 3.5. Следовательно, |X| = |Y|.

N

Рис. 3.5

В теории конечных множеств имеет место утверждение: «часть меньше целого».

Пример 3.13. А ={a, b, c, d, e}, В = {b, c, e} B A B ≠ A.

Между конечным множеством и его собственным подмножеством нельзя установить взаимно-однозначное соответствие.

Определение 3.20. Множество X называется конечным, если X не равномощно никакому его собственному подмножеству.

В противном случае множество называется бесконечным.

Определение 3.21. Множество X называется бесконечным, если из множества X можно выделить равномощное ему собственное подмножество.

Пример 3.14. Рассмотрим N и A = {x N | x – четное число}. Имеем:

АN, A ≠ N. Собственное подмножество A равномощно N, так как между N и

Аможно следующим образом установить взаимно однозначное соответствие:

N: 1 2 3 ... n ...

A: 2 4 6 ... 2n ...

Таким образом, в теории бесконечных множеств теряет силу утверждение, что «часть меньше целого».

Определение 3.22. Кардинальное число называется конечным, если оно является мощностью конечного множества.

Определение 3.23. Кардинальное число называется бесконечным, если оно является мощностью бесконечного множества.

Определение 3.24. Конечные ненулевые кардинальные числа называются

натуральными числами.

Другими словами, натуральное число – это общее свойство класса конечных непустых равномощных множеств.

45

Наименьшей бесконечной мощностью является 0 (áлеф-нуль) – мощность множества натуральных чисел. Итак, |N| = 0.

Определение 3.25. Множества, равномощные множеству натуральных чисел, называют счетными.

Другими словами, множество является счетным, если его элементы можно перенумеровать. Мощность любого счетного множества равна 0.

Пример 3.15. Множество Z счетно. Покажем, как можно перенумеровать элементы множества Z.

Запишем множество Z в виде двух строк и будем нумеровать по столб-

цам:

0 – № 1; −1 – № 2; 1 – № 3; −2 – № 4 и т.д.: 0 1 2 3 4 5 6 ...

−1 −2 −3 −4 −5 −6 −7 ...

Таким образом, все положительные числа и нуль нумеруются нечетными числами, а все отрицательные целые числа – четными.

Пример 3.16. Множество Q счетно. Покажем, как можно перенумеровать элементы множества Q.

После того как занумерованы все положительные рациональные числа, все рациональные числа нумеруются аналогично целым числам. Для этого надо перенумерованные положительные и отрицательные рациональные числа записать отдельно в виде двух строк, и числа одной строки нумеровать четными номерами, а второй – нечетными, оставив еще один номер для нуля.

Теорема 3.3 (Кантора). Множество всех действительных чисел несчетно. Доказательство. Предположим противное. Пусть все действительные числа занумерованы: x1, x2, ..., xn, ... . Известно [5], что между множеством всех действительных чисел и множеством допустимых десятичных дробей (то есть бесконечных десятичных дробей, не имеющих периода 9) существует взаимно однозначное соответствие. Запишем числа x1, x2, ..., xn, ... с помощью допусти-

мых десятичных дробей:

46