Элементы теории множеств

63

Таким образом, R является отношением эквивалентности.

Задание 31. Проверим выполнимость свойств отношения эквивалентности для отношения R-1, если R - отношение эквивалентности на множестве А. Имеем:

1. R - отношение эквивалентности R – рефлексивно a A: (a,a) Ra A: (a,a) R-1 R-1 – рефлексивно;

2. R - отношение эквивалентности R – симметрично

[ a,b A: (a,b) R (b,a) R]

(b,a) R-1		(a,b) R-1
[ a,b A: (b,a) R-1 (a,b) R-1] R-1 – симметрично.
3. R - отношение эквивалентности		R - транзитивно
[ a,b,c A: (a,b) R ˄ (b,c) R (a,c) R ]
(b,a) R-1	(c,b) R -1		(c,a) R-1
[a,b,c A: (b,a) R-1	˄ (c,b) R (c,a) R]
[a,b,c A: (c,b) R ˄ (b,a) R-1			(c,a) R]

R-1 - транзитивно.

Таким образом, R-1 - отношение эквивалентности и все доказано.

Задание 32. Докажем, например, что если R1 и R2 -	отношения
эквивалентности на некотором множестве А, то R1 ∩ R2 -	отношение

эквивалентности на этом множестве, т.е. рефлексивно, симметрично и транзитивно. a,b,c A:

	R	рефл. (a, a) R	def
1.	1	1		(a, a) R1 R2	R1 R2	рефлексивно;
	R2	рефл. (a, a) R2

		(a,b) R		R1	,R2 симм.. (b, a) R
2.	(a,b) R1 R2		1				1	(b, a) R1 R2
		(a,b) R2				(b, a) R2

64

R1 R2 симметрично;

			(a,b),(b,c) R		R1	,R2 транз.	(a,c) R		def
3.	(a,b),(b,c) R1	R2		1				1
			(a,b),(b,c) R2				(a,c) R2
		(a,c) R1 R2		R1	R2 транзитивно.

Таким образом, R1 ∩ R2 – отношение эквивалентности на А.

Задание 33. Решения:

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

Фактор-множество по этому отношению эквивалентности состоит из классов подобных между собой треугольников. Это фактор-множество – бесконечное.

b) Обозначим L(n; ) множество конечномерных линейных пространств над полем , размерности которых не превосходят некоторого заданного натурального числа n. В курсе высшей алгебры при изучении линейных пространств доказывается критерий изоморфизма линейных пространств над одним и тем же полем: «Два конечномерных линейных пространства, заданных над одним и тем же полем, изоморфны тогда и только тогда, когда они имеют одну и ту же размерность». В силу этой теоремы ясно, что отношение изоморфизма на множестве линейных пространств над одним и тем же полем обладает свойствами рефлексивности, симметричности и транзитивности. Таким образом, отношение изоморфизма – отношение

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

65

Класс эквивалентности, состоящий из линейных пространств заданной размерности m, содержит арифметическое пространство m. Обозначим его K( m). Тогда фактор-множество L(n; )∕ множества L(n; ) по этому отношению эквивалентности следующее:

L(n; )∕ = { K( m) m ˄ m ≤ n }.

Задание 34. Рассмотрим произвольный интервал (А; В) точек вещественной прямой . Расположим его над вещественной осью и построим нижнюю полуокружность с центром в середине отрезка АВ диаметром, равным длине АВ (см. рисунок). Затем, каждой точке М отрезка АВ сопоставим точку С полуокружности, проводя перпендикуляр к отрезку АВ из точки М до пересечения с полуокружностью. Теперь, проводя радиус ОС и продлевая его до пересечения с вещественной осью, получим точку D. Сопоставим точку D вещественной прямой исходной точке М интервала АВ.

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

Задания 35,36, 37,38, 39 доказать самостоятельно.

Задание 40. Например, для {2,3,4,5,8,12,18,24,30,32,36,40}; x ≤ y x y

диаграмма Хассе следующая:

66

Задание 41. Диаграммы Хассе для всех попарно неизоморфных ЧУМ на множестве из трех элементов:

1. - все три элемента попарно несравнимы;

2. - два элемента сравнимы, третий – не сравним ни с

одним из них ;

3.	- ЧУМ содержит два максимальных элемента и один

наименьший (он же минимальный);

4. - ЧУМ содержит один максимальный элемент (он же

наибольший) и два минимальных элемента;

5.

- ЧУМ является линейно упорядоченным.

Задания 42, 43 доказать самостоятельно.

Задание 44. Отношение «≤1» рефлексивное (что очевидно следует из определения: (a,a) ≤1 (a,a), т.к. (a = a)).

Поскольку

(a,b) ≤1 (c,d) < > (a < c) ˄ [(a = c) (b ≤ d)])

и

67

(c,d) ≤1 (a,b) < > (c < a) ˄ [(c = a) (d ≤ b)]),

то (a = c) и (b = d), т.е. (a,b) = (c,d) и, тем самым, отношение «≤1» антисимметричное.

Далее: (a,b) ≤1 (c,d) ˄ (c,d) ≤1 (e,f)

(a < c ˄ [a = c b ≤ d]) ˄ (c < e ˄ [c = e d ≤ f]) (a < e ˄ [a = e b ≤ f]) (a,b) ≤1 (e,f)

и, следовательно, отношение «≤1» - транзитивное.

В итоге, «≤1» - отношение частичного порядка на А.

Порядок «≤1» является линейным на А, поскольку любые элементы (любые пары (a,b) и (c,d)) из А сравнимы между собой относительно «≤1». Наименьшим элементом в А относительно порядка «≤1» является пара (1,1) (единственный минимальный элемент). Наибольшим элементом в А относительно порядка «≤1» является пара (4,4) (единственный максимальный элемент).

Диаграмма Хассе для частично упорядоченного множества А представляет собой цепь (расположим ее с учетом доминирования элементов не снизу вверх, а слева направо):

(1,1) →(1,2) →(1,3) → (1,4) →(2,1) →(2,2) →(2,3) →(2,4) →(3,1) →(3,2) →

→(3,3) →(3,4) →(4,1) →(4,2) →(4,3) →(4,4).

Задание 45. Докажем, например, b).

	n :	1 4 7 10 ... (3n 2)		n(3n 1)	;
				2

1.База. Положим n = 1. Получим 1 = 1. База проверена.

2.Предположение. Предположим, что утверждение имеет место при

	n = k, т.е.:
	1 4 7 10 ... (3k 2)		k(3k 1)	.
			2
	3.Шаг. Положим n = k +1. Имеем:

68

1 4 7 10 ... (3k 2) (3(k 1) 2)

1 4 7 10 ... (3k 2) (3k 1)

=	k(3k 1)	3k 1		3k 2 5k 2		(k 1)(3k		2)			(k 1)(3(k 1) 1)		.
	2			2		2					2
Шаг доказан.
4.Вывод. n :			1 4 7 10 ... (3n 2)						n(3n 1)			.
								2

69

Рекомендуемая литература

1. Джеймс А. Андерсон. – Дискретная математика и комбинаторика. – М.:,

Вильямс, 2003. 957с.

2. Белоусов А.И., Ткачев С.Б., Дискретная математика. – М.: МГТУ им. Н.Э. Баумана, 2004. 743с.

3. Галушкина Ю.И., Марьямов А.Н.- Конспект лекций по дискретной математике (с упражнениями и контрольными работами). –

М.: Айрис пресс, 2007. 174 с.

4. Игошин В.И., Математическая логика и теория алгоритмов. - М.:

Академия, 2008. 449 с.

5. Игошин В.И., Задачи и упражнения по математической логике и теории алгоритмов.- М.: Академия, 2007. 305 с.

6. Шапорев С.Д., Математическая логика (курс лекций и практических занятий). - С.- Петербург, 2005. 410 с.

6. Новиков Ф.А., Дискретная математика для программистов.- С.-Петербург.: Питер, 2001. 301 с.

Дополнительная литература

7. Драган Г.С., Федоровский С.В., Элементы алгебры высказываний и логики предикатов (методическое пособие). – Одесса, ОГУ им. И.И. Мечникова, 2014. 98с.

8.Федоровский С.В., Элементы теории графов (методические указания).

-Одесса, ОГУ им. И.И. Мечникова, 2013. 43с.