Самопознание

человеческий потенциал безграничен


  • Второй семинар

  • Четвертый семинар

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

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

    Множество -- это совокупность элементов, которые объединены отношением
    принадлежности
    . Для любого элемента множества $ 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
    Исходный вариант



























































































































































































































































  • Второй семинар

  • Четвертый семинар






  • Последние новости


    Дружба

    Все жизненные проблемы приносят с собой золотые самородки мудрости, обнаружить которые помогает истинная дружба. Вы замечали, что есть люди, которые дают вам силы, поднимают настроение и вызывают желание находиться рядом? И те, кто стремится вытянуть из вас энергию, надоедает вам и делает все так, что хочется сбежать. Нас подде...
    Читать далее »

    Советы, способствующие успеху

    ВЫЯВЛЕНИЕ ЦЕННОСТЕЙ Правильный выбор – Это результат жизни в соответствии со своими высшими ценностями, то есть путь к лучшей жизни. ЖИЗНЕННАЯ ЦЕЛЬ Лучшие люди выбирают цель, которая затрагивает лучшие струны в других. МИССИЯ Жизнь нельзя прожить дважды. Теперь или никогда, поэто...
    Читать далее »

    Утренние вопросы

    Если бы мне осталось жить всего месяц, что бы я делал из того, что делаю сегодня? Что я сделаю сегодня, чтобы почувствовать себя счастливым? Какие прекрасные воспоминания останутся у меня в памяти сегодня? Какие убеждения сделали мою жизнь такой, какая она есть? Во что нужно поверить, чтобы прожить удивительную жизнь? ...
    Читать далее »

    И еще несколько вопросов

    Знать мысли Бога – все равно что знать, как преуспеть в жизни. Глубоко поразмыслив над вопросами этой книги и записав свои ответы в дневник, вы развили в себе привычку анализировать. Поздравляю! Это важнейший навык успешной жизни. Способность к самоанализу и постановке правильных вопросов наряду с пониманием того, как использовать интуицию и природную мудрость, изменит нап...
    Читать далее »

    Путешествия

    Поставьте перед собой цель жить полноценно. Самый печальный итог – оглянуться назад и вопрошать, что можно было бы иметь, если бы… Дорожите своими заветными мечтами, воплощая их в жизнь. Ах, путешествия… Большинство из нас любят путешествовать и страстно стремятся к этому. Мы тоскуем по приключениям в реальной жизни. Хотим посетить удаленные места, узнать культуры, не...
    Читать далее »

    Счастье

    Там, где жизнь бьет ключом, где оживленно и весело, там и ищите свое счастье. Моя шестилетняя внучка Элла однажды зашла в мой офис и уселась в кресло. Она давно слышала, что я занимаюсь коучингом, поэтому я спросил ее: «Не хочешь побыть сегодня тренером и немного поучить других?» Малышка посмотрела на меня, выпрямилась в кресле, и я понял: она готова. Элла спросила: – О ч...
    Читать далее »

    Взаимоотношения

    Любовь Магия Бога выражается через любовь; наивысшая форма любви – бескорыстная помощь другим. Вы когда нибудь смотрели в глаза новорожденного и ощущали восторг, который ребенок приносит в этот мир? Большинство из нас чувствуют исходящую от детей любовь. Мы являемся в мир с любовью и открытым сердцем. С самого детства мы отдаем свою любовь этому миру. Из л...
    Читать далее »

    Ваш комментарий:


    Вы должны войти в систему, чтобы оставить комментарий.