Теория множеств #
Основные понятия #
Множество - совокупность элементов, объединенных по какому-либо признаку.
Множества:
- конечные
- бесконечные
Обозначения:
\(x \in X - x \text{ является элементом множества } Х \\ x \forall - \text{ для всех } x \\ x \exists - \text{ существует } x \\ \alpha \implies \beta - \text{ следовательно(импликация) } \\ \alpha \iff \beta - \text{ эквивалентно } \\ U - \text{ универсум } \\\)Универсум (универсальное множество) - разумное множество элементов, за пределы которого не выходят при рассмотрении больших множеств.
Подмножества #
Обозначается: \(A \subset B - \text{ (теоретико-множественное) включение }\)
Определение: \(x \in A \implies x \in B\) Т.е. A есть часть B.
\(A = B \text{ if } A \subset B \text{ and } B \subset A\) Т.e. множества A и B состоят из одних и тех же элементов.
Операции над множествами #
- Объединение(“ИЛИ”) \(A \cup B\)
- Пересечение(“И”) \(A \cap B\)
- Дополнение (“НЕ”; множество всех элементов U, не входящих в А) \(\overline{A}\)
Пустое множество #
\(\varnothing\)Не имеет ни одного элемента. Таким образом, пересечение непересекающихся множеств даёт:
\(A \cap B = \varnothing\)Основные свойства: \(A \cup \varnothing = A \\ A \cap \varnothing = \varnothing \\ A \cap \overline{A} = \varnothing\\ \overline{\varnothing} = U \\ \varnothing = \overline{U} \\\)
Производные свойства множеств #
\(A \cup B = B \cup A \\ A \cup A = A \\ A \cap B = B \cap A \\ A \cap A = A \\ A \cup \overline{A} = U \\ \overline{\overline{A}} = A \\ A \cup ( B \cup C ) = ( A \cup B ) \cup C \\ A \cap ( B \cap C ) = ( A \cap B ) \cap C \\ A \cap ( B \cup C ) = ( A \cap B ) \cup ( A \cap C ) \\ A \cup ( B \cap C ) = ( A \cup B ) \cap ( A \cup C ) \\\)Объединение и пересечение произвольного числа множеств \(A_1, A_2, ..., A_m\) обозначается:
\(\bigcup_{i=m}^m A_i \Big( \bigcap_{i=m}^m A_i\Big)\)Формулы Де Моргана #
\(\overline{A \cup B} = \overline{A} \cap \overline{B} \\ \overline{A \cap B} = \overline{A} \cup \overline{B}\)Теория бесконечных множеств #
Пусть \(f : X \to Y\) т.е. f - отображение (“функция”), у которой множеством задания является Х, на множество значений лежит в Y. Тогда каждому:
\(x \in X\)сопоставляется элемент \(y = f(x) \in Y\)
Отображение такого вида называется взаимно однозначным соответствием, если для каждого \(y \in Y\) существует единственный элемент \(x \in X\) такой, что \(f(x) = y\)
Если для множеств X и Y существует взаимно однозначное соответствие, то эти множества называются эквивалентными или равномощными. Обозначается \(X \sim Y\)
Свойства эквивалентности: \(X \sim X \\ X \sim Y \implies Y \sim X \\ X \sim Y, Y \sim Z \implies X \sim Z\)
Мощность множества А - класс всех эквивалентных ему множеств. Соответственно, мощности множеств равны тогда и только тогда, когда они эквивалентны.
Изначально мощность множества выражалась через количество его элементов.
Множество, эквивалентное натуральному ряду называется счетным, не эквивалентное - несчетным.
Мощности четных(и нечетных), натуральных, целых и рациональных чисел равны. Кроме того, они равны и мощностям плоскости и трёхмерного пространства.
Мощность числовой прямой также носит название континуум.
Теория конечных множеств #
Является частью дискретной математики.
Комбинаторика - раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.
Если мы имеем дело с непустым конечным множеством M, состоящим из m элементов, это обозначается как:
\(|M| = m\)Отличие от обозначения модуля числа определяется только по контексту.
Размещение из m элементов по n - упорядоченный набор, составленный из n различных элементов множества M. \(1 \le n \le m\) Обозначается: \(A^n_m = \frac{m!}{(m-n)!}\)
Перестановкой называют размещение из m элементов по m.
\(P_m = m!\)Сочетанием из m элементов по n называется набор, состоящий из n различных элементов множества M.
\(C^n_m = \frac{A^n_m}{P_m} = \frac{m!}{(m-n)n!}\)Сочетание может быть использовано, например, для определения коэффициентов многочлена \((1 + x)^m\) при некотором фиксированном m:
\((1+x)^m = C_m^0 + C_m^1x + C_m^2x^2+...+C_m^mx^m = \sum_{n=0}^m C_m^nx^n\) Эта формула называется биномом Ньютона, а сочетания в ней - биноминальными коэффициентами. Их сумма: \(\sum_{n=0}^m C^n_m = 2^m\)