D-M-1-Mnozh-Funkts-05r

30

§ 8. Отношение эквивалентности. Фактор-множество

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

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

Отношение нестрогого неравенства (≤ ) на множестве действительных чисел не будет отношением эквивалентности, ибо не является симметричным: из 3≤ 5 не следует, что 5≤ 3.

Классом эквивалентности (классом смежности), порожденным элементом а при данном отношении эквивалентности R, называется подмножество тех х А, которые находятся в отношении R с а. Указанный класс эквивалентности обозначается через [а]R, следовательно, имеем:

[а]R={х A: а,х R}.

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

Теорема 1.6. Пусть R - отношение эквивалентности на множестве А и [а]R смежный класс, т.е. [а]R={х A: а,х R}, тогда:

1)для любого а А: [а]R ≠ , в частности, а [а]R;

2)различные смежные классы не пересекаются;

3)объединение всех смежных классов совпадает со всем множеством А;

4)совокупность различных смежных классов образуют разбиение множества А.

31

Доказательство. 1) В силу рефлексивности R получим, что для любого

а, а А, имеем a,a R, следовательно а [а]R и [а]R≠;

2) допустим, что [а]R ∩ [b]R ≠ , т.е. существует элемент с из А и с [а]R ∩ [b]R. Тогда из (cRa)&(cRb) в силу симметричности R получаем, что (аRс)&(cRb), а из транзитивности R имеем аRb.

Для любого х [а]R имеем: (хRa)&(аRb), тогда в силу транзитивности R

получим хRb, т.е. х [b]R, поэтому [а]R [b]R. Аналогично для любого у,

у [b]R, имеем: (уRb)&(аRb), а в силу симметричности R получим, что

(уRb)&(bRа), затем, в силу транзитивности R, получим, что уRа, т.е. у [а]R и поэтому [b]R [а]R. Из [а]R [b]R и [b]R [а]R получаем [а]R = [b]R, т. е. если смежные классы пересекаются, то они совпадают;

3) для любого а, а А, как доказано, имеем а [а]R, тогда, очевидно, что объединение всех смежных классов совпадет с множеством А.

Утверждение 4) теоремы 1.6 следует из 1)-3). Теорема доказана. Можно доказать следующую теорему.

Теорема 1.7. Различные отношения эквивалентности на множестве А порождают различные разбиения А.

Теорема 1.8. Каждое разбиение множества А порождает отношение эквивалентности на множестве A, причем различные разбиения порождают различные отношения эквивалентности.

Доказательство. Пусть дано разбиение В={Bi} множества A.

Определим отношение R: а,b R тогда и только тогда, когда существует Bi

такое, что а и b оба принадлежат этому Bi. Очевидно, что введенное отношение является рефлексивным, симметричным и транзитивным, следовательно, R – отношение эквивалентности. Можно показать, что если

32

разбиения различны, то и отношения эквивалентности, ими порождаемые, тоже различны.

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

Рассмотрим пример отношения эквивалентности на множестве целых чисел Z = {…, -3, -2, -1, 0, 1, 2, 3, …}.

Два целых числа а и b называют сравнимыми (конгруэнтными) по модулю m, если m делитель числа a-b, т. е. если имеем:

a=b+km, k=…, -3, -2, -1, 0, 1, 2, 3, ….

В этом случае записывают a≡ b(mod m).

Теорема 1.9. Для любых чисел a, b, c и m>0 имеем:

1)a ≡ a(mod m);

2)если a ≡ b(mod m), то b ≡ a(mod m);

3)если a ≡ b(mod m) и b ≡ c(mod m), то a ≡ c(mod m).

Доказательство. Утверждения 1) и 2) очевидны. Докажем 3). Пусть a=b+k1m, b=c+k2m, тогда a=c+(k1+k2)m, т.е. a ≡ c(mod m). Теорема доказана.

Таким образом, отношение сравнимости по модулю m является отношением эквивалентности и делит множество целых чисел на непересекающиеся классы чисел.

Построим бесконечно раскручивающуюся спираль, которая на рис. 1.13 изображена сплошной линией, и бесконечно скручивающуюся спираль, изображенную штриховой линией. Пусть задано целое неотрицательное число m. Построим m лучей, как сделано на рис 1.13 для случая m = 8. Все целые числа (элементы из множества Z) расположим в точках пересечения этих спиралей с m лучами, см. рис. 1.13.

			33
Для отношения сравнимости по модулю m (в частности и для m=8)
класс эквивалентности – это числа, лежащие на луче. Очевидно, что каждое
число попадает в один и только один класс. Можно получить, что для m=8
имеем:
[0]={…, -8, 0, 8, 16, …};
[1]={…, -7, 1, 9, 17, …};
[2]={…, -6, 2, 10, 18, …};
…
[7]={…, -9, -1, 7, 15, …}.
Фактор-множество множества Z по отношению сравнения по модулю m
обозначается как Z/m или как Zm. Для рассматриваемого случая m=8
получим, что Z/8 = Z8 = {[0], [1], [2], …, [7]}.
		18
19		10
	11	2		17
	3
			9
	-5	-6	1
			-7
12 4	-4 -12		-8 0	8	16
	-11		-9
	-3	-10	-1
	5	-2	7
13				15
		6
		14
		Рис. 1.13
Теорема 1.10. Для любых целых a, b,				a*, b*, k и m:

34

1)если a ≡ b(mod m), то ka ≡ kb(mod m);

2)если a ≡ b(mod m) и a* ≡ b*(mod m), то:

а) a+а* ≡ b+b*(mod m);

б) аа*≡ bb*(mod m).

Доказательство теоремы 1.10 приведем для случая 2б). Пусть a ≡ b(mod m) и a* ≡ b*(mod m), тогда a=b+sm и a*=b*+tm для некоторых целых s и

t. Перемножив, получим: aa*=bb*+ btm+ b*sm+ stm2=bb*+(bt+ b*s+ stm)m.

Следовательно, aa*≡ bb*(mod m).

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

очевидно, имеем: 11 ≡ 3(mod 8) и 10 ≡ 2(mod 8), тогда 21 ≡ 5(mod 8) и 110 ≡ 6(mod 8). Только сокращать, вообще говоря, нельзя: имеем, что 10 ≡ 2(mod 8),

но сравнение 5 ≡ 1(mod 8), неверно, хотя 2 ≠ 0.

§ 9. Отношения порядка

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

Отношение частичного порядка обозначается через , т.е. вместо xRy

пишется х у и читается, что х предшествует у.

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

Отношение строгого порядка обозначается через , т.е. вместо xRy пишется

х у и читается, что х строго предшествует у.

35

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

Отношение x<y на (-∞,∞) является отношением строгого порядка, но не является отношением частичного порядка, так как это отношение не рефлексивно.

На множестве подмножеств данного множества М отношение является отношением частичного порядка.

Если для х,у А имеем х у или у х, то считаем элементы х и у

сравнимыми, в противном случае несравнимыми.

Множество А с заданным на нем отношением частичного порядка называется частично упорядоченным множеством.

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

Элемент а частично упорядоченного множества А называется

наименьшим элементом, если не существует элементов х, х ≠ а,

предшествующих ему, т.е. не существует х, х ≠ а, такого, что х а. Элемент b частично упорядоченного множества А называется минимальным элементом, если для любого х из А элементы b и х несравнимы или b х.

Отметим, что если наименьший элемент существует, то он единственный, а минимальных элементов может быть сколько угодно. Если же у множества существует наименьший элемент, то он является единственным минимальным элементом.

Пример. Рассмотрим множество точек плоскости с заданной прямоугольной декартовой системой координат. Каждая точка задается

упорядоченной парой (х,у) действительных чисел. Отношение порядка на

множестве точек определим следующим образом (a,b) (c,d), если и только

36

если a ≤ b и c ≤ d. Рассмотрим множество точек треугольника ОАВ, см. Рис. 1.14 а). Точка с координатами (0,0) является в этом треугольнике наименьшим элементом. Теперь рассмотрим множество точек треугольника АВС, см. Рис. 1.14 б). Для этого треугольника каждая точка стороны АС будет минимальной точкой.

у		у
А	А	В

		х	х
0	В	0	С
	а)		б)
		Рис. 1.14

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

Множество М = {0, 1, 2, …} является вполне упорядоченным.

Множество (-∞,∞) не является вполне упорядоченным, ибо, например,

каждое из подмножеств (-∞,0] и (0,1] не имеют наименьшего элемента.

§ 10. Равномощные множества

Множества А и В считаются равномощными, если существует биективное отображение f множества А на множество В. Как известно, биективное отображение (биекция) осуществляет взаимно однозначное соответствие между элементами множеств А и В.

Очевидно, что тождественное отображение множества А на А является биективным.

37

Из существования биекции f множества А на В следует, что f -1 является биекцией В на А (см. § 6).

Если существует биекция множества А на В и биекция множества В на С, то из теоремы 1.5 следует, что существует биекция множества А на множество С.

Таким образом, отношение равномощности множеств обладает свойствами рефлексивности, симметричности и транзитивности, поэтому является отношением эквивалентности, следовательно, порождает разбиение множеств на классы равномощных множеств. Если множества А и В равномощны, то считается, что множества А и В имеют одинаковую мощность и записывается: А В.

Множество А содержащее конечное число элементов, положим n

элементов, считается конечным. Тогда А {1,2,…, n }. Множество не являющееся конечным, считается бесконечным. Любое множество, равномощное множеству всех натуральных чисел называется счетным.

Имеют место следующие интересные и важные результаты.

Теорема 1.11. Любое бесконечное множество содержит счетное множество.

Теорема 1.12. любое подмножество счетного множества конечно или счетное.

Теорема 1.13. Объединение любого не более чем счетного семейства счетных множеств счетное.

Пусть множества А и В таковы, что В содержит некоторое множество С равномощное с А, но в А нет подмножества равномощного В, тогда считается, что мощность множества В больше мощности множества А.

38

Теорема 1.14. Пусть А – бесконечное множество, а В – его не более чем счетное подмножество. Если A\B бесконечное множество, то оно равномощно множеству А.

Теорема 1.14. Пусть А некоторое множество и пусть 2А – множество элементами которого являются всевозможные подмножества множества А. Тогда 2А имеет мощность большую, чем мощность исходного множества.

Пусть, как обычно, N – множество все натуральных чисел. Мощность множества 2А называют мощностью континуума, а любое множество, равномощное множеству 2А, называют множеством мощности континуума или континуальным множеством.

Теорема 1.15. Множество всех рациональных чисел счетное, а множество все действительных чисел является континуальным множеством.

39

§9. Вопросы и темы для самопроверки

1.Понятие множества, способы задания множества.

2.Аксиоматическое задание множества.

3.Операции над множествами: дополнение, объединение, пересечение, разность, симметрическая разность.

4.Какими свойствами обладают операции над множествами?

5.Основные равенства для алгебры подмножеств.

6.Разбиение множества. Декартово произведение множеств. Коммутативно ли декартово произведение множеств?

7.Отношения на множествах. Области определения и значения бинарных отношений. Образы и прообразы элементов при заданном отношении.

8.Способы задания отношений (5 способов).

9.Операции над отношениями.

10.Свойство операций над отношениями.

11.Функция. Инъективная, сюръективная и биективная функция.

12.Отношения эквивалентности. Связь с разбиением множества.

13.Пример отношения эквивалентности на множестве целых чисел - отношение сравнимости по модулю m.

14.Отношение частичного и строгого порядка. Линейно упорядоченные и вполне упорядоченные множества.

Небеса не помогают людям, которые бездействуют.

Софокл

§10. Упражнения

1.Поставить знаки и так, чтобы получилось истинное высказывание:

а) {1,2} {1,2,{1},{2}};

г) {1,2}

{1,{1,2}};