Мощность объединения конечного числа конечных множеств A₁, A₂, …, A_n равна

Доказательство производится методом математической индукции по числу множеств n, участвующих в объединении.

Отношения и функции

Отношение является фундаментальным понятием дискретной математики, которое используют для обозначения связи между объектами или понятиями. Например, отношение включения элемента во множество, отношение включения подмножества во множество, отношение параллельности и перпендикулярности прямых, отношение равенства чисел и множеств. Общим для всех отношений является то, что они ставят в соответствие друг другу объекты из разных множеств или из одного и того же множества. В общем случае отношение можно определить как некоторое утверждение, относительно которого можно сказать, что оно является истинным или ложным. В дискретной математике такое утверждение называется предикатом. Например, предикат x>y может быть истинным или ложным в зависимости от того, какие значения примут входящие в него переменные x и y. Понятие предиката непосредственно вытекает из понятия отношения. Если предикат устанавливает какое- либо соответствие между двумя объектами, то эту пару объектов можно рассматривать как элемент декартова произведения двух множеств, элементами которых и являются эти объекты. В силу последнего обстоятельства объекты, входящие в пары, могут принимать различные сочетания значений. При некоторых из них предикат будет истинным, при других ложным. Подмножество декартова произведения двух множеств, для каждого из элементов которого данный предикат будет истинным, называется двуместным (бинарным) отношением между элементами двух множеств.

В общем случае n - местным отношением между элементами множеств А₁, A₂, ..., A_n называется любое подмножество декартова произведения этих множеств. Соответственно  бинарное отношение - это любое подмножество декартова произведения двух множеств (возможно, одного и того же множества). При n =1 отношение называется одноместным или унарным и обозначает просто свойство на множестве. Например, r={x | х положительное целое число} задает множество положительных целых чисел.

Для обозначения отношений принято использовать строчные буквы латинского или греческого алфавита. Будем обозначать n - местное отношение между элементами множеств А₁ , А₂, ..., А _n как r⁽ⁿ⁾ Í А₁´А₂´...´А_n. Верхний индекс определяет местность отношения. Таким образом, n-местное отношение – это множество упорядоченных n-ок, элементы которых принадлежат соответствующим множествам, участвующим в декартовом произведении и порождающим универсум для этого отношения. Поэтому, например, если требуется определить все бинарные отношения на множестве {0,1}, то надо вначале найти декартов квадрат этого множества, который и будет универсумом для всех возможных отношений. Мощность множества {0,1}² равна 4. Следовательно, искомая мощность множества всех возможных отношений равна мощности булеана множества {00, 01, 10, 11}, т.е. 16.

Наиболее часто встречаются бинарные отношения вида r Í А´В или r Í А². В последнем случае множество А называется несущим множеством, на котором задано отношение r. В приведенном выше примере несущим множеством для всех бинарных отношений на множестве {0,1} является множество {00, 01, 10, 11}. С каждым бинарным отношением связывают два множества: область определения dom r и область значений rng r, которые определяются как проекции отношения r на первую и вторую координаты соответственно, т.е. dom r ={x| $y: (x,y) Î r},

rng r={x | $у: )(у,х) Î r}. Очевидно, каждое бинарное отношение задано на множестве (dom r È rng r).

Для обозначения бинарных отношений r Í А²  часто используют следующие записи:

· хrу , читается "х находится в отношении r с у";

· (х,у) Î r, читается "элемент (х,у) принадлежит отношению r";

· у Î r(х).

Множество элементов отношения r называется графиком отношения r.

Отношение является множеством, следовательно, к нему применимы любые операции, определенные для множеств. Кроме того, для отношений определены также следующие операции:

· обратное отношение r^-1 , которое определяется как r^-1={(x,y) | (y,x) Îr}. Например, для отношения хrу Û х ³ у, заданного на множестве А={1,2,3}, r = {(1,1), (2,1), (2,2), (3,1), (3,2), (3,3)}, обратное отношение r^-1={(x,y)|y³x}; график обратного отношения получается простой перестановкой первого и второго элементов в каждой паре, участвующей в r: r^-1 = {(1,1), (1,2), (2,2), (1,3), (2,3), (3,3)};

· дополнение отношения ` r, которое определяется как дополнение r до универсального отношения: `r = {(x,y) | (x,y) Î А²\ r};    

· композиция отношений · , таких что  и . Композиция отношений – это бинарное отношение, которое определяется следующим образом

На рис.2 приведен композиции двух бинарных отношений.

Рисунок 2 Композиция бинарных отношений

Отношение не обладает свойством коммутативности. Легко показать, что композиция отношений ассоциативна, а также, что

Для визуализации отношений можно использовать различные способы:

1. Задание отношения перечислением элементов.

2. Графиком отношения в декартовой системе координат.

3. Изображением связей в виде стрелок, связывающих элементы множеств, участвующих в отношении, стрелками, направление которых задает отношение.

4. Графом отношения.

5. Фактор - множеством, в котором перечисляются окрестности каждого из элементов несущего множества.

Рассмотрим различные способы на примере отношения хrу Û x > y, x,y Î {1, 2, 3, 4, 5}.

1. Перечислением элементов: r = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3), (5,4)}. Это множество называется также графиком отношения.

2. Графиком отношения, т.е. указанием всех точек плоскости, в которых указанное отношение истинно. Для изображения графика отношения введем декартовы координаты, примем, что ось абсцисс - это ось х, а ось ординат - это ось у. Точки, находящиеся в пересечениях всех горизонталей и вертикалей, проведенных через точки координатных осей, изображающие элементы несущего множества, дадут "универсум", т.е. множество, мощность которого равна в данном случае 25. В этом множестве выделим точки, принадлежащие отношению, Рис.2.

3. Изображение отношения с использованием координатных осей и стрелок очевидно из

Рис. 3, a, b.

4. Изображение отношения с помощью графа. Множество элементов несущего множества используется в качестве имен вершин графа отношения. Ребрами ориентированного графа являются элементы отношения, Рис. 4.

5. При изображении отношения с помощью фактор -множества каждому элементу несущего множества сопоставляется его окрестность, определенная следующим образом:

О_r(v_i)={v_j | (v_i,v_j) Î r, v_i, v_j ÎA}, где А - несущее множество. Фактор - множество записывается в виде заключенной в фигурные скобки последовательности элементов несущего множества, под каждым из которых указывается его окрестность, т.е. множество вершин, смежных с данной вершиной. В рассматриваемом случае

.

Для любого множества А определим тождественное отношение I_A, которое называется также диагональю А, и универсальное отношение 1 следующим образом:

I_A  = {(xx)| x ÎА}. 1 = А². Так как Æ Í А², то Æ является отношением на А и называется пустым отношением.