13. Операции над отображениями. Суперпозиция отображений, ее свойства. Примеры. Обратное отображение. Примеры. Критерий обратимости отображения. Свойства операции.

Суперпозиция отображений, ее свойства.

Суперпозицией отображения f и g назовем отображением fog : А С, которое определяется по следующему правилу:

Для всех а, принадлежащих множеству А fog (a)^det=g(f(a))

Свойства:

1. fog не = gof

2. fo(goh)=(fog)oh

3. Если f: A B id_Aof =f, foid_B=f

Утверждение:

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

f: A B – биекция, g: B C – биекция fog: A C – биекция

Пример:

f: R R f(x)=x²

g:R R g(x)= sinx

fog(x)=sinx²

gof(x)=sin²x

Обратное отображение

Если в отображении f: A B каждому элементу множества B соответствует только 1 прообраз A, то в этом случае говорят, что определено отображение из В А, которое является обратным отображению f.

Пример:

y=x+1

y=2x

Критерий обратимости отображения

Отображение   обратимо тогда и только тогда, когда оно биективно.

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

14. Мощность множества. Равномощные множества. Мощность конечного множества. Первая теорема Кантора. Счетное множество. Свойства счетных множеств. Доказательство того, что множество рациональных чисел счетно. Вторая теорема Кантора. Множество мощности континуум. Примеры.

Мощность множества — это обобщение понятия количества элементов множества, которое имеет смысл для всех множеств, включая бесконечные.

Множество А называется равномощным множеству В, если существует взаимно однозначное соответствие f: A B.

Два конечных множества равномощны тогда и только тогда, когда они состоят из одинакового числа элементов. То есть для конечного множества понятие мощности совпадает с привычным понятием количества.

Первая теорема Кантора

|N|<|[0,1]|. Где N – множество натуральных чисел, а [0,1] – множество вещественных чисел из отрезка [0,1].

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

1. Докажем, что |N|<=|[0,1]|. Для этого выберем из отрезка [0,1] подмножество {0,100…;0,1100…;0,11100…;…} и сопоставим натуральному числу n тот элемент этого подмножества, в котором n единиц. Очевидно, что построено взаимно однозначное соответствие между множеством N и подмножеством отрезка [0,1], ч.т.д.

2. Докажем что |N| не =|[0,1]| методом от противного. Пусть |N| = |[0,1]|. Это означает, что существует взаимно однозначное соответствие f: N [0,1].

Т.О. f(1)=0,a11,a12,…a1n..

f(2)= 0,a21,a22,…a2n..

f(3)= 0,a31,a32,…a3n..

Здесь a_ij – цифры. По предположению, в правых частях этих равенств перечислены все числа из отрезка [0,1]. Приведем это предположение к противоречию, а именно, найдем на отрезке [0,1] такое число, которого нет в правых частях.

Пусть b_n={1, если a_nn не =1 ; 2, если a_nn =1. И b=0,b1,b2,…bn…

Числа b в правых частях нет. Число b не имеет хваста из 0 или 9 и значит, записывается единственным образом.

f(1) не = b, поскольку у этих чисел разные первые цифры; f(2) не =b, поскольку у этих чисел разные вторые цифры; f(n) не =b, поскольку у этих чисел разные n -е цифры. Ч.т.д.

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

Множество, равномощное множеству N, называется счетным. Иными словами счетными являются такие множества, которые можно занумеровать натуральными числами.

Свойства:

1.Любое подмножество счётного множества не более чем счётно (т.е. конечно или счётно).

2.Объединение конечного или счётного числа счётных множеств счётно.

3.Прямое произведение конечного числа счётных множеств счётно.

4.Множество всех конечных подмножеств счётного множества счётно.

5.Множество всех подмножеств счётного множества континуально и, в частности, не является счётным.

Множество рациональных чисел Q счетно.

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

Рациональные числа это числа, которые представимы в виде p/q, где числа p и q целые, q не =0. Достаточно проверить утверждение для положительных рациональных чисел Q= Q_q, где Q_q={1/q, 2/q, 3/q,…}. Т.о., множество рациональных чисел является объединением счетного семейства счетных множеств, т.е. счетное.

Вторая теорема Кантора

|A|<|β(А)| для всякого множества А.

Множество мощности континуум.

Континуум — мощность множества всех вещественных чисел. Обозначается строчной латинской буквой . Множество, имеющее мощность континуум, называется континуа́льным множеством.

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

Примеры: Все точки отрезка [0,1] . Все точки плоскости  (или  ). Множество всех иррациональных чисел.

15. Граф. Неориентированный граф. Ориентированный граф. Мультиграф. Псевдограф. Примеры. Смежность. Инцидентность. Примеры. Степень вершины неориентированного графа. Полустепени входа и выхода вершины ориентированного графа. Примеры.

Графом Г называется пара (V,E), где V- конечное множество, E- антирефлексивное бинарное отношение на V. Элементы множества V называются вершинами графа, множества E – дугами или ребрами графа. Число вершин обычно обозначается через p, число дуг - через q.

Если отношение E симметричное, то граф называется неориентированным, в противном случае – ориентированным.

Если бинарное отношение на V не является антирефлексивным, то соответствующий объект называется псевдографом.

Иногда полезно считать, что некоторые вершины соединяются несколькими дугами, такой объект называется мультиграфом

.

Вершины a, b принадлежащие V, называются смежными, если (а, b) принадлежит Е или (b, а) принадлежит Е. т.е. если эти вершины на картинке соединяются дугой.

Дуги графа называются смежными, если у них есть общая вершина.

( тут и дуги и вершины смежные. Дуги одновременно являются инцидентными.)

Вершина а принадлежащая V и дуга (a, b) принадлежащая Е или дуга (b, а) принадлежащая Е. (т.е. вершина является одним из концов дуги) называются инцидентными. Т.е. если 2 вершины смежны, то дуга между ними инцидентна.

Степенью вершины неориентированного графа называется число дуг графа, ей инцидентных. Обозначение: deg(a).

Для вершины ориентированного графа определены полустепени выхода и входа deg^-(a), deg⁺(a) – числа дуг соответственно начинающихся и заканчивающихся вершиной a.