Свойства Декартового произведения.

1) А Х В≠В Х А.

2) (А Х В) Х С≠А Х (В Х С).

3) А Х (В∩С)=(А Х В)∩(А Х С).

4) А Х (В С)=(А Х В) (А Х С).

5) (А∩В) Х С=(А Х С) ∩(В Х С).

6) (А В) Х С=(А Х С) (В Х С).

7) А Х (В\С)=(А Х В)\(А Х С).

8) (А\B) X C= (A X C)\ (B X C).

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

Обозначим А Х (В∩С)=D1 и (А Х В)∩(А Х С)= D2.

a) Пусть z D1, z- элемент декартового произведения, z=(x,y), где х А, а у (В∩С), то есть у В и у С по определению пересечения. Тогда (x,y) (АХВ) и (x,y)  (АХС). По определению пересечения (x,y) D2. Мы доказали, что D1-подмножество D2.

b) Пусть (x,y) D2. Это означает, что (x,y) (АХВ) и (x,y) (АХС) по определению пересечения. Следовательно, х А, а у В и у С. Так как у В и у С, то у (В∩С). Следовательно, (x,y)  D1. Значит, D2 является подмножеством D1.

По теореме о равенстве множеств D1= D2.

Что и требовалось доказать.

Остальные свойства доказывается аналогично предыдущему

Отношения.

Пусть заданы два множества А и В. Найдем А Х В.

Подмножество k А Х В называется отношением из множества А во множество В.

Отношения задаются знаками  =, <, >,      и  т.д.

Пример:

А={2,3,4}, B={1,4,3}

A X B={(2,1),(2,4),(2,3),(3,1),(3,4),(3,3),(4,1),(4,4),(4,3)}

Выделим отношения  больше > ={(2,1),(3,1),(4,1),(4,3)}

и меньше < ={(2,4),(2,3),(3,4)}

 

                                  Рис.11. Отношение >.

Композиция отношений.

Пусть отношение А Х С и отношение С Х В.

Композицией этих отношений является отношение k = , где   k A X B.

Композицией отношений из А в В называется множество пар (а,b) таких, что, а А, b B и существует такое с С, что (а, с)  и (с,b) .

Пример:

А={2,3,4}, B={1,4,3}, С={2,5}

A X В={(2,1),(2,4),(2,3),(3,1),(3,4),(3,3),(4,1),(4,4),(4,3)}

A X C={(2,2),(2,5),(3,2),(3,5),(4,2),(4,5)}

C X B={(2,1),(5,1),(2,4),(5,4),(2,3),(5,3)}

Определим отношение

>: A X C={(3,2),(4,2)} и отношение < C X B= {(2, 4), (2, 3)}  

Возьмем пару (3,2) . В  есть пары, начинающиеся с 2. Это пары (2,4) и (2,3). Значит пары (3, 4) и (3, 3) войдут в композицию k.

Берем пару (4,2) . В  есть пары, начинающиеся с 2. Это те же пары (2,4) и (2,3). Значит пары (4, 4) и (4, 3) войдут в k.

Получим k= =(k AXB)= {(3, 4), (3, 3), (4, 4), (4, 3)}

Таким образом, для элемента (2,4)  А Х В, в k войдут {(2,х), (у,4)}, где (2,х) , а (у,4)  для всех х и y.

Отношения на множестве.

Если в декартовом произведении в качестве множества В выбрать множество А (то есть  А Х А= А ), то отношение k из А  называется отношением на множестве.

Для отношений на множестве вводятся понятия:

Обратное отношение -это множество пар (а,b) таких, что (b,a)  А . Обозначение

Дополнение -это множество пар (а,b) k. Обозначение

Тождественное отношение -множество пар (а, а) таких, что, а А,

I= {(a, a), a  A}

Универсальное отношение U ={(a,b),a A, b А}

Виды отношений:

Инъекция.

Если каждый элемент множества А соответствует элементу из множества В, то отношение  f  называется инъективным.

 

 

                                                Рис.12.Инъекция.

 

 

Сюръекция.

Если для каждого элемента y множества В существует элемент х А, соответствующий элементу y, то такое отношение  f  называется сюръекцией.

 

 

                                                Рис.13.Сюръекция.

 

Биекция.

Если для каждого элемента y B существует ровно один элемент х А, которому соответствует y, то такое отношение называется биективным.

Биективное отношение инъективно и сюръективно.

Биективное отношение имеет обратное отношение.

 

 

                       

 

                                    Рис.14. Биекция.

 

Функции.

 

Пусть заданы множества А и В. Найдем А Х В.

Выберем отношение f  АХВ={(, ),(, ),…}, состоящее из пар таких, что ≠ , i=1,2,3,…., то есть отношение, в которой все первые элементы пар различны. Такие отношения называются функциями.

Способы задания:

А В;    f: A B;    b=f (a);  a f b.

Пример: А={2,3,4}, B={1,4,3}

A X В={(2,1),(2,4),(2,3),(3,1),(3,4),(3,3),(4,1),(4,4),(4,3)}

Выделим: функции ={(2,1),(3,1),(4,1)} и ={(2,4),(3,1),(4,1)}

 

Рис.15.Функция .                             Рис.16.Функция .

Комбинаторика.

 

Задачи, в которых требуется определить количество возможных операций, называется комбинаторными. Пусть имеется группа некоторых объектов , , которые мы будем называть элементами.

Из этой группы элементов будем образовывать подгруппы. Такие подгруппы будем называть соединениями.

Из этих соединений выделим классы, которые будем называть размещениями.

Размещения.

 

Размещениями из m -элементов по n называются соединения, каждое из которых содержит n элементов, взятых из данных m и которые отличаются друг от друга или элементами, или их порядком.

Предполагается, что элементы водном размещении не повторяются.