2Дискретка / теория множеств

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

так как все лучи пересекаются в этой точке.

Две точки попадают в один класс эквивалентности если они лежат на одном луче, то есть точки представимы в виде (t cos ϕ, t sin ϕ ) . Тогда

(t1 cosϕ, t1 sin ϕ ), (t2 cos ϕ, t2 sin ϕ ) R , где ϕ – любой угол и t1 ≤ t2 .

Пример 3.9

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

y

x

Решение:

Найдём минимальный элемент – такой элемент, меньше которого не существует элементов. Возьмём любую точку на окружности, образованной окружностью, меньше этой точки элементов нет. Поэтому минимальный элемент – любая точка на окружности. Наименьшего элемента не существует, так как нельзя найти точки, которая хотя бы сравнима со всеми остальными. В случае если бы рассматривалась вся область D2 , то минимальными элементами были бы все точки круга.

Пример 3.10

Доказать, что если R – симметрично и антисимметрично, то оно транзитивно, будет ли данной отношение рефлексивно?

Доказательство:

Для доказательства

транзитивности

рассмотрим

две

пары

x, y R

и

y, z R .Так как R

–

симметрично, тогда

y, x R

и z, y R . Так как

R

–

антисимметрично,

тогда

x = y = z .

Следовательно

x, z R ,

то

есть

R

–

транзитивно. Отношение

может

быть

не

рефлексивным,

например

взяв

A ={1, 2} и R ={ 1,1 }.

Пример 3.11

Доказать, что

Ai

– счетное множество,

если

все

Ai

– счётные

i N

множества.

Доказательство:

Представим множества Ai в виде:

A0 ={a00 , a01 , a02 ,...}

A1 ={a10 , a11 , a12 , ...}

A2 ={a20 , a21 , a22 ,...}

…
Объединение	множеств	A = Ai	={aik			i, k N }.	Определим		взаимно
		i N
однозначное	соответствие	f (0) = a00 ,		f (1) = a01 , f (2) = a10 ,				…	(нумерация
«змейкой») между множеством натуральных чисел							N и	множеством A .
Таким образом A = Ai – счётное множество.
	i N
Пример 3.12
Пусть	A ={a, b,..., c}	алфавит	–			конечное	множество		символов,

состоящий из k символов. A* – слова в алфавите. Доказать, что A* –счётное множество.

Доказательство:

Упорядочим слова в алфавите по длине, а слова с одинаковой длиной

упорядочим	лексикографически. Затем	пронумеруем слова	f (0) ="" ,
f (1)= " a " , …,	f (k ) ="c " , f (k +1) = " aa " , …	Следовательно A* –	счётное
множество.

Задачи для самостоятельного решения

1.Доказать, что множество всех корней многочлена α (x ) = β (x ) γ (x ) есть объединение множеств корней многочленов β (x ) и γ (x ).

2. Доказать A B и C D A × C B × D .

3.Доказать (A \ B )× C = (A× C )\ (B × C ).

4.Пусть A, B ≠ и (A × B ) (B × A) = (C × D ). Доказать, что A = B = C = D .

5.Пусть R = { x, y x, y N y + x ≤ 0}. Найти δ R , ρR , R−1 , R R, R R−1 , R−1 R .

6.Доказать, что f (A B ) = f (A) f (B ).

7.Доказать, что множество всех подмножеств данного множества частично упорядоченно отношением включения .

8.Пусть R – это частичный порядок, будет ли R–1 являться частичным порядком?

9.Определим отношение R на множестве натуральных чисел следующим

образом:			a, b R (a − b) 2 . Доказать, что					R является	отношением
эквивалентности. Построить классы эквивалентности.
10.Пусть R1	и R2 отношения эквивалентности на множестве A . Доказать,
что R1 R2 – эквивалентность R1 R2							= R1 R2 .
11.Дано множество				A = {a, b, c, d},		отношение <		определено следующим
образом:			a<c,	b<c,	c<d,	a<d,	b<d.	Будет ли	отношение
≤ = {< x, y >			x < y или x = y}		- частичным		порядком. Найти		наибольший,

наименьший, максимальный, минимальный элементы множества A .