Предварительные сведения

Множества

Множество - это одно из основных понятий математики, как дискретной, так и непрерывной. Оно не определяется через другие понятия. Содержательно, под множеством понимается некоторая совокупность элементов. Основное отношение между элементами и множеством - это отношение принадлежности элемента множеству. Оно обозначается знаком $$\in:$$ $$x\in A$$ означает, что элемент x принадлежит множеству A. $$x\notin A$$ означает, что элемент x не входит в множество A. $$A\subseteq B$$ означает, что каждый элемент множества A является также элементом множества B. В этом случае множество A называется подмножеством множества B. Если $$A \subseteq B$$ и $$B \subseteq A,$$ то A=B, т.е. множества A и B равны. Если $$A \subseteq B$$ и $$A\ne B,$$ то A называется собственным подмножеством множества B, и в этом случае пишем $$A\subset B.$$ Множество, не содержащее элементов, называется пустым и обозначается $$\varnothing$$ .

Обычно множества обозначаются с помощью пары фигурных скобок, в которые заключены их элементы. Небольшие множества задаются прямым перечислением всех элементов. Например, множество простых чисел, не превосходящих 10, это {2, 3, 5, 7} ; множество (имен) летних месяцев: {июнь, июль, август}. В описаниях "больших" конечных множеств используют многоточие. В них часто указывается несколько первых элементов и последний элемент множества. Например, множество целых неотрицательных чисел, не превосходящих 100, записывают как {0, 1, 2, ... , 100}, множество всех месяцев года - как { январь, февраль, ..., декабрь}. Такое задание требует определенной аккуратности. Например, если некоторое множество A задано как {3, 5, 7, ... , 19}, то не ясно, является ли A множеством нечетных чисел, лежащих в интервале от 3 до 19, или это множество простых чисел из того же интервала (возможны и другие его расшифровки). Перечисления элементов бесконечных множеств начинаются несколькими начальными элементами, а завершаются многоточием. При этом часто указывают общий вид элемента задаваемого множества. Основное бесконечное множество, рассматриваемое в дискретной математике, это множество всех натуральных чисел N={1, 2, 3, ... } . Множество всех квадратов этих чисел можно задать, например, так: {1, 4, 9, ..., n2, ... } .

Как мы уже отметили, большие множества не всегда можно точно определить, используя перечисление с многоточием. Основной способ их описания имеет вид: { Elem | условие на Elem}, где Elem - это общий вид элемента определяемого множества, а после вертикальной черты описано условие, которому этот элемент должен удовлетворять. Например, $$\{ n | (n \in N) и (10 \le n \le 1000)\}$$ - это множество целых чисел в интервале от 10 до 1000, $$\{ n^{2} | n \in N\}$$ - множество квадратов натуральных чисел, $$\{ x \in N | x - простое \ число\}$$ - множество всех простых чисел.

Множества, элементами которых являются другие множества, часто называют семействами или классами. Семейство ( множество ) всех подмножеств множества A обозначается через 2A, т.е. $$2^{A} = \{ B | B \subseteq A\}.$$ Например, если A={ 0, 1, {2,3}}, то $$2^{A} = \{ \varnothing , \{ 0\} , \{ 1\} ,\{ \{ 2,3\} \} ,\{ 0,1\} , \{ 0, \{ 2,3\} \} ,\{ 1, \{ 2,3\} \} , \{ 0,1, \{ 2,3\} \} \},$$ а для пустого множества $$\varnothing$$ семейство его подмножеств $$2^{\varnothing } =\{ \varnothing \}.$$

Операции над множествами

Имеется целый ряд операций, позволяющих получать одни множества из других. Рассмотрим основные из них.

Объединением множеств A и B называется множество

$$A \cup B =\{ x | x\in A \ или\ x \in B \}.$$

Объединением семейства множеств $$A_{i}(i\in I)$$ называется множество

$$\bigcup_{i\in I}A_i = \{ x | \textit{ существует такое }\ i_0 \in I, \ \textit{ что } x \in A_{i_0}\}.$$

Пересечением множеств A и B называется множество

$$A \cap B = \{ x| x\in A \textit{ и } x \in B\}.$$

Пересечением семейства множеств $$A_{i}(i \in I)$$ называется множество

$$\bigcap_{i\in I}A_i = \{ x| \textit{ для всякого }\ i \in I \quad x \in A_{i}\}.$$

Из определения операций объединения и пересечения непосредственно следует, что они обладают свойствами ассоциативности: $$A \cup (B \cup C) = (A \cup B) \cup C,$$ $$A \cap (B \cap C) = (A \cap B) \cap C$$ и коммутативности $$A \cup B = B \cup A,$$ $$A \cap B = B \cap A.$$

Разностью множеств A и B называется множество

$$A \setminus B = \{ x| x\in A \textit{ и } x \not\in B\}.$$

Обычно все рассматриваемые множества являются подмножествами некоторого "универсального" множества U. Разность U \ A называется дополнением множества A (в U ) и обозначается через $$\bar{A}.$$ Ясно, что $$A \cup \overline{A} = U$$ и $$A \cap \overline{A} = \varnothing.$$

Симметрической разностью множеств A и B называется множество

$$A \dot{-} B = (A \setminus B) \cup (B \setminus A) .$$

Иногда симметрическую разность множеств называют дизъюнктивной суммой и обозначают $$A \oplus B$$ или $$A \nabla B.$$

Декартовым (прямым) произведением множеств A1, ... , An называется множество n -ок

$$A_1 \times \ldots \times A_n =\{ (a_1,\ldots, a_n)| a_1 \in A_1, \dots, a_n \in A_n \}.$$

Если A1= ... =An=A, то A1 x ... An называется декартовой (прямой) степенью множества A и обозначается через An .

Пример1.1. Пусть заданы множества A= {0,1,... ,n} и B={0,1,... m}, где $$n \in N$$ и $$m \in N$$ - числа и n < m.

Тогда $$A \cup B = B, A \cap B = A, A \setminus B =\varnothing , B \setminus A = \{ n+1,\dots , m\},$$ A x B = {(i,j)| 0 <= i <= n, 0 <= j <= m}.

Как доказывать равенство множеств?

Многие математические утверждения, в том числе и многие теоремы в этой книге, имеют следующую форму. Даны разные определения двух множеств A и B. Требуется доказать, что A = B.

Стандартный способ доказательства такого утверждения состоит в доказательстве двух утверждений о включениях:

$$A \subseteq B$$ и

$$B \subseteq A.$$

Доказательства этих включений проводятся по такой схеме: рассматривается произвольный элемент, удовлетворяющий определению меньшего множества (слева от знака $$\subseteq$$ ), и устанавливается, что он удовлетворяет также определению большего множества (справа от знака $$\subseteq$$ ).

В качестве примера докажем одно из свойств (законов) дистрибутивности для операций объединения и пересечения:

$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C).$$

Пусть a - произвольный элемент из $$A \cup (B \cap C).$$ Тогда по определению операции $$\cup$$ имеем $$a \in A$$ или $$a \in (B \cap C).$$ В первом случае из того же определения выводим, что $$a \in (A \cup B)$$ и $$a \in (A \cup C).$$ Но тогда по определению операции $$\cap$$ получаем, что $$a \in (A \cup B) \cap (A \cup C).$$ Во втором случае из определения $$\cap$$ следует, что $$a \in B$$ и $$a \in C.$$ Из этого и из определения $$\cup$$ снова следует, что $$a \in (A \cup B)$$ и $$a \in (A \cup C)$$ и $$a \in (A \cup B) \cap (A \cup C).$$ Таким образом, мы установили, что $$A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C).$$

Пусть теперь $$a \in (A \cup B) \cap (A \cup C).$$ Тогда по определению операции $$\cap$$ имеем $$a \in (A \cup B)$$ и $$a \in (A \cup C).$$ Если $$a \in A,$$ то оба эти включения выполнены. Но тогда $$a \in A \cup (B \cap C).$$ Если же $$a\notin A,$$ то из первого включения следует, что $$a \in B,$$ а из второго - $$a \in C.$$ Следовательно, $$a \in (B \cap C)$$ и $$a \in A \cup (B \cap C).$$ Таким образом, $$(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$$ и наше утверждение доказано.

Используя эту же схему, можно установить много других свойств введенных выше операций над множествами и связей между ними (см. задачи 1.2 и 1.5).

Отношения и функции. Мощность множества

Бинарным или двуместным отношением между элементами множеств A и B называется любое подмножество R их декартова произведения A x B . Говорят также, что R является отношением из A в B. При A = B отношение R называется бинарным отношением на A. Вместо $$(x,y) \in R$$ часто пишут xRy. Например, для отношений порядка на множестве натуральных чисел N используют записи вида 3 <= 7, x >= 23, z > y и т.п.

Тождественным отношением на множестве A называется отношение

$$I\_ A= \{ (x,x)| x\in A\}.$$ Его обозначают знаком равенства " = ".

С бинарным отношением R связана его область определения:

$$\delta_R=\{ x\ | \textrm{ существует } y \textrm{ такое, что } (x,y) \in R\}$$

и его область значений:

$$\rho_R=\{ y\ | \textrm{ существует } x \textrm{ такое, что } \ (x,y) \in R\}.$$

Обратным отношением для бинарного отношения R называется множество пар $$R^{-1} = \{ (x,y)| (y,x) \in R\}.$$

Образом множества X относительно R называется множество $$R(X) = \{ y| \ существует \ x \in X \ такое, \ что (x,y) \in R\},$$ прообразом X относительно R называется R-1(X).

Произведением отношений $$R_{1} \subseteq A \times B$$ и $$R_{2} \subseteq B \times C$$ называется следующее отношение $$R_{1} \hat{} R_{2} \subseteq A \times C$$:

$$R_1 \circ R_2 = \{(x,z)| \textrm{ существует } y\in B \textrm{ такое, что } (x,y) \in R_1 \textrm{ и } (y,z) \in R_2\}.$$

Важную роль среди бинарных отношений играют отношения эквивалентности. Бинарное отношение R на множестве A называется отношением эквивалентности, если для него выполнены следующие условия:

Рефлексивность: для любого $$a \in A$$ $$(a,a) \in R$$ ;

Симметричность: для любых a, b из $$A (a,b) \in R \Leftrightarrow (b,a) \in R$$ ;

Транзитивность: для любых трех элементов a, b,c из A, если $$(a,b) \in R$$ и $$(b,c) \in R,$$ то и $$(a,c) \in R.$$

Примером отношения эквивалентности на множестве натуральных чисел N является равенство остатков при делении на некоторое фиксированное число n: a = b (mod n).

С каждым отношением эквивалентности $$\equiv$$ на множестве A связано разбиение A на непересекающиеся подмножества - классы эквивалентности. Для каждого $$a \in A$$ его класс эквивалентности $$[a]_{\equiv }$$ включает все эквивалентные a элементы: $$[a] \equiv = { b \isin; A | a \equiv b}.$$ Из определения эквивалентности непосредственно следует, что, если $$a \equiv b,$$ то $$[a]_\equiv = [b]_\equiv,$$ а если $$a \not\equiv b,$$ то $$[a]_\equiv \cap [b]_\equiv= \emptyset.$$ Таким образом, разбиение A на классы эквивалентности не зависит от выбора конкретных представителей этих классов в качестве их имен.

Если в приведенном выше примере в качестве n взять, например, 5, то все числа из N разобьются на 5 классов эквивалентности: N0, N1, N2, N3, N4, где в класс Ni (i=0,1,2,3,4) войдут числа, дающие при делении на 5 остаток i.

Еще один важный класс отношений - отношения (частичного) порядка. Бинарное отношение R на множестве A называется отношением частичного порядка, если для него выполнены следующие условия:

Антирефлексивность: для любого $$a \in A$$ \ $$(a,a) \notin R$$ ;

Антисимметричность: для любых a, b из A, если $$(a,b) \in R$$ и $$(b,a) \in R,$$ то a = b ;

Транзитивность: для любых трех элементов a, b,c из A, если $$(a,b) \in R$$ и $$(b,c) \in R,$$ то и $$(a,c) \in R.$$

Примером такого отношения является отношение строгого включения на множестве 2A всех подмножеств некоторого множества A. Обычное отношение строгого порядка < на N также удовлетворяет условиям 1 - 3. Но для него выполнено еще одно существенное условие:

Линейность: для любых a, b из A либо $$(a,b) \in R,$$ либо $$(b,a) \in R.$$

Отношения, для которых выполнены условия 1 - 4 называются отношениями линейного порядка.

Отношение f называется функцией из A в B ( из A на B ) , если $$\delta _{f}=A,$$ $$\rho _{f} \subseteq B$$ (соответственно, $$\rho _{f} = B$$ ) и для всех x, y1, y2 из того, что $$(x,y_{1}) \in f$$ и $$(x,y_{2}) \in f,$$ следует, что y1 = y2. Запись: f : A -> B. В качестве синонимов термина "функция" часто используются слова отображение и преобразование. Если f функция, то вместо $$(x,y) \in f$$ пишем f(x) = y и называем y значением f на аргументе x. f называется 1-1-функцией (или обратимой функцией), если для любых x1, x2, y из того, что f(x1) = y и f(x2) = y следует, что x1 = x2 . Функция f : A -> B называется взаимно однозначной функцией, если она является 1-1-функцией и $$\rho _{f}=B.$$ Взаимно однозначная функция f : A -> A называется перестановкой множества A .

Определения бинарных отношений и функций с одним аргументом естественным образом обобщаются на многоместные отношения и функции.

n -арным (или n - местным) отношением на множествах A1,..., An называется любое подмножество A1 x ... x An. Функцию f : A1 x ... x An -> B называем n -арной (или n - местной) функцией и пишем f(x1, ..., xn) = y при $$x_{1} \in A_{1}, \dots , x_{n} \in A_{n}.$$ Чаще всего мы будем рассматривать n -арные функции для A1 = ... = An =A. В этом случае f : An -> B будем называть n -арной функцией из A в B.

Множество A называется эквивалентным (по мощности ) множеству B, если между A и B можно установить взаимно однозначное соответствие. Мощностью множества A называется класс всех множеств, эквивалентных множеству A, и эта мощность обозначается через |A| .

Для каждого $$n \in N$$ мощность множества Nn={0,1,...,n-1} обозначим через n. Множество называется конечным, если оно для некоторого $$n \in N$$ эквивалентно множеству Nn. Для конечных множеств их мощность - это количество элементов. В частности, для пустого множества $$|\varnothing | = 0.$$

Каждое множество, эквивалентное N, называется счетным и его мощность обозначается $$\aleph_0.$$

В нашем курсе мы будем рассматривать только конечные и счетные множества, а также - отношения и функции на таких множествах. Отметим, что многие объекты, изучаемые в дискретной математике, являются частными случаями отношений и функций на конечных множествах. К ним относятся, в частности, слова. Пусть алфавит A={a1, ..., am} - это конечное множество элементов, называемых символами (буквами). Слово в алфавите A - это конечная последовательность символов этого алфавита: $$w =w_{1} \dots w_{n}, w_{i} \in A$$ при i = 1, ..., n . Число букв в этой последовательности называется длиной слова и обозначается |w|. Имеется одно специальное "пустое" слово длины 0. Будем обозначать его через $$\varepsilon.$$ Нетрудно понять, что слова длины n взаимно однозначно соответствуют функциям вида f: {1,..., n} -> A. А именно, слову w = w1... wn, соответствует функция fw(i) = wi, i = 1, ..., n. Языком в алфавите A называется произвольное множество слов этого алфавита . На языках, как и на множествах, определены операции объединения, пересечения и разности. Язык, включающий все слова в алфавите A ( в том числе и пустое), обычно обозначается через A*. Дополнение языка $$L \subseteq A^{*}$$ это язык L = A* \ L.