Пусть у нас имеется два элемента 
и 
. Пара (, ) называется упорядоченной. 1-ый элемент ее - , 2-ой- .
Пары (, ) и (
, 
) считаются равными, если = , а = ;
Пара (, )=(, ), если только = .
Пусть заданы два множества
А={ 
, 
,…, 
} и В={ , ,… 
}.
Декартовым или прямым произведением множества А на множество В называется множество упорядоченных пар, 1-ый элемент которых принадлежит множеству А, а 2-ой множеству В.
Обозначается декартово произведение знаком Х.
Для данных множеств получим
АхВ={(, ),(, ),…,(, ),…,(, ),…,(, )}
Мощность декартового произведения равна nm.
Обозначение: |A X B|=nm.
Пример:
A= {1, 4} и В {2, 3, 4}. A X B={(1,2),(1,3),(1,4),(4,2),(4,3),(4,4)}
Геометрически каждой паре чисел соответствует точка координатной плоскости.
Пример1
Рис.8. Декартово произведение А Х В для конечных А и В.
Пример2
A={x 
R, \ x [-1; 2]};
B={y Z, \ y [-3; 3]};
Рис.9. А х В, где А - непрерывное множество.
Пример 3.
A={x R, \ x 
[-1; 2]};
B={y R, \ y [-3; +∞)};
Рис.10.Декатрово произведение А Х В. Оба множества непрерывны.
Декартова степень.
Если в качестве множества В в декартовом произведении выбрать множество А, мы будем говорить о декартовом квадрате.
А Х А=А 
А Х А =А 
…
А Х А 
=А 
Набор n-элементов будем зазывать кортежем.
Декартовым произведением n-множеств
А 
х А 
х А 
х…х А 
будем называть множество упорядоченных кортежей, 1-ый элемент которых принадлежит множеству А 
, 2-ой множеству А и т.д.
Свойства Декартового произведения.
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 и которые отличаются друг от друга или элементами, или их порядком.
Предполагается, что элементы водном размещении не повторяются.