Отношение включения подмножеств


Тема: Множества и отношения. Читаем, комментируем, решаем ДЗ.

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

Множество -- это совокупность элементов, которые объединены отношением принадлежности. Для любого элемента множества $ A$ можно заключить: $ a \in A$ .

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

$\displaystyle A = \{1, 2, 3, 4\}, B = \{$Иванов$\displaystyle ,$   Петров$\displaystyle ,$   Сидоров$\displaystyle \}$

Бесконечные множества удобно задавать с помощью коллективизирующего условия: $ A = \{ x \vertP(x) \}$ , где $ P(x)$ принимает значение ``истина'' или ``ложь''. Например, $ A = \{ x \vert k\in \mathbb{N}, x = 2 k \}$ .

Множества считаются равными тогда и только тогда, когда они состоят из одних и тех же элементов:

$\displaystyle A = B \Leftrightarrow (\forall x)(x \in A \Leftrightarrow x \in B)$

Отношение включения -- множество $ A$ включается в множество $ B$ , если все элементы $ A$ принадлежат $ B$ : $ A \subseteq B \Leftrightarrow (\forall x)(x \in A \Rightarrowx \in B)$ . Тогда $ A = B \Leftrightarrow (A \subseteq B) \And (B \subseteq A)$ .

Порядок элементов в множестве не играет роли, множество не содержит повторяющихся элементов: $ \{1, 2, 3, 4\} = \{1, 2, 4, 3\} = \{1, 1, 2, 3, 4\}$ . Не следует путать множества элементов и множества множеств: $ \{1, 2, 3, 4\} \neq \{\{1, 2\}, \{3, 4\}\}$ .

Пустое множество не содержит ни одного элемента $ (\forall a) (a \notin A)$ . При этом $ \{ \varnothing \} \neq \varnothing $ .

Существует ли множество, содержащее само себя? Да, рассмотрим пример: $ Z = \{ X \vert$   X -- множество, содержащее не менее трёх элементов$ \}$ :

\begin{displaymath}\left.\begin{array}{c}\{1, 2, 3\} \in Z \{1, 2, 3, 4......2, 3, 4, 5\} \in Z \end{array}\right\} \Rightarrow Z \in Z\end{displaymath}

Существует ли множество, не содержащее само себя? $ Y = \{ X \vert X \notin X\}$. Это парадокс Рассела.

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

Существуют операции над множествами (получение новых множеств на основе существующих):

\begin{displaymath}\begin{array}{ll}\mbox{Объединение:} & A \cup B = \{x \ver...... \bigtriangleup B = (A \cup B) \setminus (A \cap B)\end{array}\end{displaymath}

Если задано универсальное множество $ U$ , то может быть введена операция дополнения: $ \overline{A} = U \setminus A$.

Указанные операции обладают рядом интересных свойств (см. литературу). Свойства оформляются в виде тождеств (всегда истинных равенств). Существует несколько способов доказательства теоретико-множественных тождеств:

  1. метод двух включений;
  2. метод характеристических функций;
  3. метод эквивалентных преобразований.

Операции над множествами могут быть проиллюстрированы на диаграммах Венна. Например, пересечение множеств может быть представлено как тёмная область на рисунке 1.

Рис. 1: Диаграмма Венна для пересечения множеств

\includegraphics[width=4cm]{venn_and.eps}

Метод двух включений основывается на укзанном выше определении равенства множеств ( $ A = B \Leftrightarrow (A \subseteq B) \And (B \subseteq A)$ ). Необходимо доказать две леммы: если $ x \in A \Rightarrow x \in B$ и $ x \in B \Rightarrow x \in A$ . Рассмотрим пример:

Доказать тождество $ (A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B\setminus A)$ . Докажем методом двух включений:

\begin{displaymath}\begin{array}{l}\triangleleft\quad \mbox{Необходимость:}\qu......(A \cup B)\setminus (A \cap B) \quad\triangleright\end{array}\end{displaymath}Задания для самоподготовки. Доказать методом двух включений и проиллюстировать результаты на диаграммах Венна:
  • $ (A \setminus B) \setminus C = A \setminus (B \setminus C)$ ;
  • $ (A \setminus B) \setminus C = (A \setminus C) \setminus (B \setminus C)$ .

Метод характеристичских функций состоит в сопоставлении каждому множеству $ A$ функции $ \chi_A(x) = \left\{ \begin{array}{l} 1, x \in A\ 0, x \notin A \end{array}\right.$ . Тогда функции, соответствующие операциям, будут равны:

\begin{displaymath}\begin{array}{l}\chi_{A \cap B} = \chi_A \chi_B;\chi_......_B;\chi_{A \setminus B} = \chi_A (1 - \chi_B).\end{array}\end{displaymath}

Рассмотрим пример доказательства приведённого выше тождества, $ (A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B\setminus A)$ :

Требуется показать, что $ \chi_{(A \cup B) \setminus (A \cap B)} = \chi_{(A \setminus B)\cup (B \setminus A)}$ .

\begin{displaymath}\begin{array}{l}\triangleleft\quad\chi_{(A \cup B) \setmin......i_A + \chi_B - 2 \chi_A \chi_B}\quad\triangleright\end{array}\end{displaymath}Задания для самоподготовки. Доказать методом характеристических функций и проиллюстировать результаты на диаграммах Венна:
  • $ (A \bigtriangleup B) \bigtriangleup C = A \bigtriangleup (B \bigtriangleup C)$
  • $ A \cup (B \bigtriangleup C) = (A \cup B) \bigtriangleup (A \cup C)$

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

Задания для самоподготовки. Доказать методом эквивалентных преобразований и проиллюстировать результаты на диаграммах Венна: $\displaystyle A \bigtriangleup B = (A \cup B) \cap (\overline{A} \cup \overline{B}).$

Декартово произведение множеств

Определим множество упорядоченных пар следующим образом:

$\displaystyle A \times B = \{ z \vert z = (x, y), (x \in A) \And (y \in B) \}$

В общем случае операция декартова произведения некоммутативна: $ A \timesB \neq B \times A$ . Также эта операция не обладает свойством ассоциативности $ A\times (B \times C) \neq (A \times B) \times C \neq A \times B \times C$ , действительно, если $ a_i \in A, b_i \in B, c_i \in C$ , то $ (a_i, (b_i, c_i)) \neq ((a_i, b_i), c_i) \neq(a_i, b_i, c_i)$ .

Графически декатрово произведение можно изобразить в виде квадрата на плоскости (рисунок 2).

Рис. 2: Декартово произведение множеств

\includegraphics[width=4cm]{set_product.eps}

Умножение множества на себя называют декартовым квадратом (кубом и т.п.): $ A^2 = A \timesA$ , $ A^3 = A \times A \times A$ , .... Декартов квадрат множества всех действительных чисел $ \mathbb{R}^2$ образует декартову плоскость.

Задания для самоподготовки. Доказать методом двух включений и проиллюстировать тождества графиком:
  • $ A \times (B \cup C) = (A \times B) \cup (A \times C)$ ;
  • $ A \times (B \setminus C) = (A \times B) \setminus (A \times C)$ .
Показать, что тождество $ \overline{A \times B} = \overline{A} \times \overline{B}$ в общем случае неверно. Записать верное тождество и доказать его методом двух включений.

Соответствия и операции над ними

Пусть заданы два множества $ A$ и $ B$, соответствием называют некоторое подмножество их декартова произведения: $ \rho \subseteq A \times B$ (рисунок 3). Если для пары $ (x, y) \in A \times B$ имеет место соответствие, то $ (x, y) \in \rho$ . Это также записывают в виде $ x \rho y$ .

Рис. 3: Пример соответствия

\includegraphics[width=4cm]{correspond.eps}

Существует несколько способов задания соответствия: перечислением элементов (возможно для конечных множеств $ A$ и $ B$ ), заданием предиката (например, $ \rho = \{ (x, y) \vert x \in A, y\in B, x < y + 5\}$ ), и в виде графа, часто соответствие иллюстрируют графиком (рисунок 4).

Рис. 4: Пример задания соответствия графически

\includegraphics[width=12cm]{corr_graph.eps}

Для каждого соответствия рассматривают область определения dom$ \, \rho = \{x \vert x \in A \And (x, y) \in \rho\}$ и область значений rng$ \, \rho = \{x \vert y \in B \And (x, y) \in \rho\}$ .

Вводится понятие функциональности соответствия. Соответствие функционально по первой компоненте тогда и только тогда, когда $ \forall (x_1, y_1), (x_2, y_2) \in \rho:y_1 = y_2 \Rightarrow x_1 = x_2$ , другими словами: для каждого $ y$ существует единственный $ x$ . Аналогично, соответствие функционально по второй компоненте тогда и только тогда, когда $ \forall (x_1, y_1), (x_2, y_2) \in \rho:x_1 = x_2 \Rightarrow y_1 = y_2$ , или для каждого $ x$ существует единственный $ y$ .

Рис. 5: Пример соответствия, не функционального по 2-ой компоненте

\includegraphics[width=4cm]{nf2k.eps}

Отображение из $ A$ в $ B$ (функция) -- это соответствие из $ A$ в $ B$ , которое всюду определено и функционально по второй компоненте.

Соответствие -- это множество упорядоченных пар, поэтому все операции над множествами к ним применимы. Для соответствий вводятся две новые операции: композиция и обратное соответствие.

Композиция соответствий $ \rho \subseteq A \times B$ и $ \sigma \subseteq B \times C$  -- новое соответствие $ \tau \subseteq A \times C$ , равное $ \tau = \rho \circ \sigma = \{ (x,y) \vert x \in A, y \in C, \exists z \in B: x \rho z \And z \sigma y \}$ . Для конечных соответствий удобно пользоваться графовым представлений соответствий -- тогда для получения композиции достаточно пройти по ребрам графа.

Пример композиции соответствий представлен на рисунке 6 и иллюстрирует композицию соответствий оценок, полученных студентами, ($ \rho$ ) и соответствия оценки получаемой стипендии. Результат композиции в этом случае -- соответствие студентов и выплаты стипендии.

Рис. 6:Пример композиции соответствий

\includegraphics[width=14cm]{comp_corr.eps}

Под степенью отношения понимают его композицию с самим собой: $ \rho^2 = \rho \circ\rho$ .

Обратное соответствие образуется следующим образом: $ \rho^{-1} \subseteq B \timesA$ , $ \rho^{-1} = \{ (x, y) \vert (y, x) \in \rho \}$ . При этом dom$ \, \rho =$   rng$ \, \rho^{-1}$ и rng$ \, \rho =$   dom$ \, \rho^{-1}$ .

Композиция и обратное соответствие обладают рядом свойств, которые могут быть доказаны методом двух включений. Рассмотрим свойство композиции $ \rho \circ (\sigma \cup \tau) =\rho \circ \sigma \cup \rho \circ \tau$ .

\begin{displaymath}\begin{array}{l}\triangleleft\quad \mbox{Необходимость:}\qu......очность доказывается аналогично}\quad\triangleright\end{array}\end{displaymath}Задания для самоподготовки. Доказать тождества для соответствий. Во втором примере привести контрпример, показывающий, что равенство не может иметь место.
  • $ (\rho \circ \sigma)^{-1} = \sigma^{-1} \circ \rho^{-1}$ ;
  • $ \rho \circ (\sigma \cap \tau) \subseteq \rho \circ \sigma \cap \rho \circ \tau$ .
Задания для самоподготовки. Для соответствия $ \rho \subseteq A \times B$ : 1) построить график и граф; найти область определения и область значений; 2) найти $ \rho^{-1}$ , построить для него график и граф; 3) установить, является ли $ \rho$ отображением из $ A$ в $ B$ :
  • $ A = \{1, 2, 3, 4\}, B = \{p, q, r, s, t\}$ , $ \rho = \{ (1, s), (1, t), (2,r)$ , $ (2, s)$ , $ (3, p),(3, q), (4, q), (4, t)\}$ ;
  • $ A = B = \{a, b, c, d, e\}, \rho = \{(b,b), (d,c), (c,e), (a, e), (e, a)\}$ .

Свойства отображений

Отображение называют инъективным, если оно функционально по первой компоненте.

На рисунке 7 показано неинъективное отображение $ f(x) = x^2$ при $ A =\mathbb{R}$ , $ B = \mathbb{R}^{+}$ . Оно не является инъективным, так как значению $ y = 1$ соответствуют два $ x = 1$ и $ x = -1$ .

Рис. 7: Пример неинъективного отображения

\includegraphics[width=6cm]{func_noninj.eps}

Отображение $ f: A \rightarrow B$ называют сюръективным, если область отображения совпадает с $ B$ .

На рисунке 8 показано несюретивное отображение $ f(x) = e^x$ при $ A =\mathbb{R}$ , $ B = \mathbb{R}^{+}$ . Оно не является сюръективным, так как область значений отображения равна rng$ \, f = (0, +\infty)$ . Однако, оно инъективно, так как функионально по первой компоненте.

Рис. 8: Пример инъективного и несюръективного отображения

\includegraphics[width=6cm]{func_nonsur.eps}

Если отображение инъективно и сюръективно, то оно называется биективным. Такое отображение задаёт взаимо однозначное соответствие между множествами $ A$ и $ B$ .

Пример биекции изображён на рисунке 9: если рассмотреть угол, под которым расположен луч, то он соответствует точке на действительной прямой и наоборот. Таким образом, задано биективное отображение интервала $ (0, \pi)$ на $ \mathbb{R}$ .

Рис. 9: Пример биективного отображения

\includegraphics[width=10cm]{func_biject.eps}Задания для самоподготовки. Для данных функций $ f: A \rightarrow B$ проверить свойства инъективности, сюръективности и биективности.
  • $ A = M_{n \times n}(\mathbb{R}) ($квадратные матрицы$ ), B = \mathbb{R},f(x) = \det x$ ;
  • $ A = \mathbb{C} \setminus \{0\}, B = \mathbb{R}^{+} \times [0, 2 \pi), f(z) =(\vert x\vert, \arg z)$ ;
  • $ A = C[a, b]\, ($функции, непрерывные на отрезке $ [a, b]$$ ), B = \mathbb{R},f(x) = \int\limits_a^b x(t)\, dt$ .

Бинарные отношения и их свойства

Бинарное отношение (отношение) -- соответствие множества самому себе: $ \rho\subseteq A \times A$ . Выделим специальное отношение, которое существут для любого множества $ A$ , называемое диагональю: $ id_A = \{ (x, x) \vert x \in A\}$ .

Задания для самоподготовки. На множестве $ \mathbb{Z}$ задано отношение $ <$ . Найти квадрат этого отношения. Как изменится ответ, если задать это отношение на $ \mathbb{R}$ .

Свойства бинарных отношений:

  1. Отношение называют рефлексивным, если $ (\forall x \in A)((x, x) \in\rho)$ . Отношение рефлексивно тогда и только тогда, когда диагональ полностью включается в него $ id_A \subseteq \rho$ . В качестве примера рефлексивного отношения можно привести $ \rho = \{ (x, y) \vert x = y\}$ .
  2. Отношение называют иррефлексивным, если $ (\forall x \in A)((x, x) \notin\rho$ . Отношение иррефлексивно тогда и только тогда, когда диагональ полностью не принадлежит ему $ id_A \cap \rho = \varnothing$ . Если отношение не рефлексивно и не иррефлексивно, его называют нерефлексивным. Иррефлексивным отношением является $ \rho = \{ (x, y) \vert x \neq y\}$ .
  3. Отношение называют симметричным, если $ (\forall x, y \in A)(x \rho y\Rightarrow y \rho x)$ . При этом график отношения симметричен относительно диагонали, при этом отношение совпадает с обратным к нему $ \rho = \rho^{-1}$ . Примером такого отношения является равенство треугольников.
  4. Отношение называют антисимметричным, если $ (\forall x, y \in A)(x \rho y \Andy \rho x \Rightarrow x = y)$ . Если отношение не симметрично и не антисимметрично, его называют несимметричным. На графике отношения все симметричные относительно диагонали точки будут лежать на самой диагонали $ \rho \cap \rho^{-1} \subseteq id_A$. Пример такого отношения -- $ x \leqslant y$.
  5. Отношение называют транзитивным, если $ (\forall x, y, z \in A)(x \rho y \Andy \rho z \Rightarrow x \rho z)$. При этом квадрат отношения включается в него самого $ \rho^2 \subseteq \rho$ .

На рисунке 10 показаны примеры отношений с перечисленными свойствами.

Рис. 10: Графики, иллюстрирующие свойства отношений

\includegraphics[width=10cm]{rel_graphs.eps}Задания для самоподготовки. Для заданного бинарного отношения $ \rho \subseteqA^2$ 1) построить график; 2) найти $ \rho^{-1}$ и $ \rho^2$ и построить их графики; 3) исследовать свойства Р, И, С, А, Т.
  • $ A = \{1, 2, 3, 4\}, \rho = \{(1,1), (1, 3)$ , $ (2, 1), (2, 4)$ , $ (3, 2), (3,3)$ , $ (3, 4), (4, 1) \}$ ;
  • $ A = [0, 1], x \rho y \Leftrightarrow \vert x - y\vert \leqslant 1 / 3$ ;
  • $ A = [0, 1], x \rho y \Leftrightarrow y \geqslant x + 1/4, x \leqslant 1 /2$ .
Задания для самоподготовки. Для заданного бинарного отношения $ \rho \subseteqA^2$ 1) найти $ \rho^{-1}$ и $ \rho^2$ ; 2) исследовать свойства Р, И, С, А, Т.
  • $ A = M_{n \times n}(\mathbb{R}), P \rho Q \Leftrightarrow p_{i j} \leqslantq_{i j}, i, j \in \{1, \dots n\}$ ;
  • $ A = M_{n \times n}(\mathbb{R}), P \rho Q \Leftrightarrow \det P = \det Q$ ;
  • $ A = M_{n \times n}(\mathbb{R}), P \rho Q \Leftrightarrow \det P \leqslant \detQ$ .

В виде PDF
Исходный вариант


Источник: http://dm-learning.livejournal.com/1264.html



Рекомендуем посмотреть ещё:


Закрыть ... [X]

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


Отношение включения подмножеств Множество. Подмножество, собственное подмножество. Отношение
Отношение включения подмножеств Отношение включения над множествами и его свойства
Отношение включения подмножеств Множества, отношения и функции в логике MathHelpPlanet
Отношение включения подмножеств 16.1. Основные определения теории множеств
Отношение включения подмножеств Подмножество. Отношение включения Life-Prog
Множества Теория Включение множеств Глава 3. Отношения множеств 2. Отношение включения All pix / короткая стрижка одри тоту NailBox - гель-лаки и материалы для наращивания ногтей Tanyant Вред пирсинга чем он опасен Где можно купить пилочку для ногтей со эмблемой спартака? Ну Известные библиотекари разных веков /

Дата: 18.09.2017, 23:27 / Просмотров: 52564