Специальная математика (стр. 4 )

3. Соответствие называется всюдуопределенным, если проекция графика на первую ось совпадает с областью отправления. пр. G1 = X.

4. Соответствие называется сюръективным, если проекция графика на вторую ось совпадает с областью прибытия пр. G2 = Y

5. Соответствие называется биективным (взаимно-однозначным), если оно функционально, инъективно, всюдуопределено и сюръективно.

Пример : Соответствие «студенты сдавали экзамен». (Трифонов не пришел).

И П С Т

X

 

G

 

Y

2 3 4 5

X = {Иванов, Петров, Сидоров, Трифонов} – множество студентов.

Y = {2, 3, 4, 5} – множество возможных оценок.

G = {<И, 5>, <П, 2>, <С, 5>} – результаты сдачи экзамена.

Соответствие функционально, неинъективно, невсюдуопределено, несюръективно, небиективно.

Пример : Соответствие «покупателей и купленных товаров».

 

X

 

G

 

Y

Типовая ситуация для такого соответствия: нефункционально, инъективно, невсюду определено, несюръективно, небиективно.

1.7. Отношения

Отношение, это пара

r = <R, M>

R Í M * M = M2

Первый компонент ( R ) - график отношения.

Второй компонент ( M ) - множество, на котором отношение определено.

Более традиционная запись отношения x r y для x Î M, y Î M.

Свойства отношений

1. Рефлексивность: x r x ( например, x = x)

2. Антирефлексивность: ù x r x (например, x < x)

3. Симметричность: x r y Þ y r x (например, x = y Þ y = x)

4. Антисимметричность: x ¹ y, x r y Þù y r x (например, x ¹y ; y £ x Þù y ³ x)

4¢. Асимметричность: xry Þ ùy r x (например, x < y Þù y < x)

5. Связность ( полнота ): x ¹ y Þ x r y или y r x (например, для любых двух различных натуральных чисел: либо x < y, либо y < x)

6. Транзитивность: x r y, y r z Þ x r z (например, x = y и у = z Þ y = z)

7. Антитранзитивность: x r y, y r z Þùx r z (например, отношение перпендикулярности прямых).

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

Отношение, обладающее одновременно свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности.

~ - символ отношения эквивалентности.

[x] - множество элементов, эквивалентных x (класс эквивалентности х).

Свойства отношения эквивалентности:

1. x ~ х

2. Если x ~ y Þ [x] = [y]

Доказательство 1-го свойства: Следует из свойства рефлексивности.

Доказательство 2-го свойства: 1. z Î [x] Þ z ~ x, x ~ y Þ z ~ y Þ z Î [y], т. е. [x] Í [y]

2. z Î [y] Þ z ~ y, x ~ y Þ z ~ x Þ z Î [x], т. е. [y] Í [x].

Следовательно [x] = [y]

P(M) - множество-степень множества М есть множество всех подмножеств множества М.

Пример:

М={1, 2, 3}

P(M)={Æ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

П(M) - покрытием множества М будем называть любое подмножество множества Р(М), такое, что объединение входящих в него элементов совпадает с М.

П(M) = {{1,2}, {2}, {2,3}}

так как {1,2} È {2} È {2,3} = {1, 2 ,3}

R(M) - разбиением множества М называется такое покрытие множества М, в котором элементы не пересекаются.

Пример разбиения: R = {{1,2}, {3}}

Свойства :

1. Каждый элемент исходного множества М принадлежит какому-либо из множеств, составляющих разбиение.

2. Каждый элемент исходного множества принадлежит строго одному из множеств, составляющих разбиение.

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

Доказательство: 1. Очевидно. х ~ [x]

2. Предположим, что z Î [x] и z Î [y]. Тогда из x ~ y и z ~ y следует x ~ y и по второму свойству отношения эквивалентности [x] = [y].

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

Четыре определения отношений порядка можно свести в таблицу.

	Свойства	Рефлексивность	Антирефлексивность	Антисимметричность	Полнота	Транзитивность
Порядки
нестрогий (частичный)	+		+		+
совершенный нестрогий	+		+	+	+
строгий		+	(+)		+
совершенный строгий		+	(+)	+	+

То есть, например, нестрогий (частичный) порядок - отношение, обладающее свойствами, рефлексивности, антисимметричности и транзитивности.

1.7.3. Морфизмы

Всюду-определенное функциональное соответствие называется отображением.

f : A®B

 

r = <R, A> j = <Ф, В>

B2

A2

 

Отображение f называется отображением гомоморфизма или гомоморфным отображением, или просто морфизмом, если для элементов множества А выполняется А1rА2, а для образов выполняется В1j В2. То есть

f(А1rА2) = f(А1) j f(А2) , где f(А1) = В1, f(А2) = В2.

Содержательный пример морфизма – высота земной поверхности над уровнем моря и более темный коричневый цвет на географической карте.

Эндоморфизм - гомоморфизм "в себя".

Мономорфизм - инъективный гомоморфизм.

Эпиморфизм - сюръективный гомоморфизм.

Изоморфизм - биективный гомоморфизм

Автоморфизм - изоморфизм в себя.

1.8. Решетки

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

чум - частично-упорядоченное множество, т. е. множество с определенным на нем частичным порядком.

1.8.1. Диаграммы Хассе

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

Пример изображения частичного порядка (устанавливаемого отношением включения) для множества

{Æ, {0}, {1}, {0,1}}

Æ {0} {0,1}

 

{0} {1}