Метка: множества

Бинарные отношения

Пусть $A$ и $B$ два конечных множества. Декартовым произведением множеств $A$ и $B$ называют множество $A\times B,$состоящее из всех упорядоченных пар, где $ a\in A, b\in B. $

Бинарным отношением между элементами множества $A$ и $B$ называется любое подмножество $R$ множества $A\times B$, то есть $ R\subset A\times B.$

По определению, бинарным отношением называется множество пар. Если R — бинарное отношение (т.е. множество пар), то говорят, что параметры $x$ и $y$ связаны бинарным отношением $R$, если пара $\langle x,y \rangle $ является элементом R, т.е. $\langle x,y \rangle\in R. $

Высказывание: «предметы $x$ и $y$ связаны бинарным отношением $R$» записывают в виде $xRy.$Таким образом, $ xRy\leftrightarrow\langle x,y\rangle\in R.$

Если $R\subset A\times A $, то говорят, что бинарное отношение определено на множестве $A$.

Примеры бинарных отношений:

  • на множестве целых чисел $Z$ отношения «делится», «делит», «равно», «больше», «меньше», «взаимно просты»;
  • на множестве прямых пространства отношения «параллельны», «взаимно перпендикулярны», «скрещиваются», «пересекаются», «совпадают»;
  • на множестве окружностей плоскости «пересекаются», «касаются», «концентричны».

    • Областью определения бинарного отношения $R$ называется множество, состоящее из таких $x$, для которых $\langle x,y \rangle\in R $ хотя бы для одного $y$.
    Область определения бинарного отношения будем обозначать $ \Re R$.
    $\Re R=\{ x|\exists y(\langle x,y\rangle\in R)\}$
    Областью значений бинарного отношения $R$ называется множество, состоящее из таких $y$, для которых $\langle x,y \rangle\in R $ хотя бы для одного $x$.
    Область значений бинарного отношения будем обозначать $\Im R$
    $\Im R=\{ y|\exists x(\langle x,y\rangle\in R)\}$

    Инверсия (обратное отношение) $R$ — это множество $\{\langle x,y\rangle |\langle y,x\rangle\in R\}$ и обозначается, как ${R}^{-1}.$

    Композиция (суперпозиция) бинарных отношений $R$ и $S$ — это множество $\{\langle x,y\rangle |\exists z\langle xSz\wedge zRy\rangle\}$ и обозначается, как $R\circ S$.

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

    Бинарное отношение $R$ на некотором множестве $M$ может обладать различными свойствами, например:

    • Рефлексивность: $\forall x\in M(xRx)$
    • Антирефлексивность (иррефлексивность): $\forall x\in M\neg (xRx)$
    • Корефлексивность: $\forall x,y\in M(xRy\Rightarrow x=y)$
    • Симметричность: $\forall x,y\in M(xRy\Rightarrow yRx)$
    • Антисимметричность: $\forall x,y\in M(xRy\wedge yRx\Rightarrow x=y)$
    • Асимметричность: $\forall x,y\in M(xRy\Rightarrow\neg (yRx))$. Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.
    • Транзитивность: $\forall x,y,z\in M(xRy\wedge yRz\Rightarrow xRz)$
    • Связность: $\forall x,y\in M(x\neq y\Rightarrow xRy\lor yRx)$

    Виды отношений

    • Рефлексивное транзитивное отношение называется отношением квазипорядка
    • Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности
    • Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка
    • Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка
    • Полное антисимметричное (для любых $x, y$ выполняется $xRy$ или $yRx$) транзитивное отношение называется отношением линейного порядка

      • Операции над отношениями

      Над бинарными отношениями можно производить некоторые операции, точно так же, как и над множествами. Не ограничивая общности, будем считать, что следующие операции выполняются на множестве $M$.

      • Пересечение. Пересечением двух бинарных отношений ($A$и $B$) является отношение, которое определяется пересечением соответствующих подмножеств. Очевидно, что отношение $A\cap B$ выполнимо только в том случае, когда некоторые $x$ и $y$ связаны как первым, так и вторым отношением ($xAy$ и $xBy$).

        Например, пересечением отношения «не меньше» и «не равно» является отношение «больше».
        $ xAy\Leftrightarrow x\geq y, xBy\Leftrightarrow x\neq y$, тогда $A\cap B\Leftrightarrow x>y $

      • Объединение. Объединением двух бинарных отношений ($A$ и $B$) является отношение, которое определяется объединением соответствующих подмножеств. Отношение $A\cup B$ выполнимо только в том случае, когда некоторые $x$ и $y$ связаны хотя бы одним из двух отношений хотя бы одно из отношений ($xAy$ или $xBy$).

        Например, объединением отношения «больше» и отношения «равно» является отношение «больше, либо равно».

      • Включение. Обозначается $A\subseteq B$. Первое отношение включено во второе, если все те пары, для которых выполняется первое отношение, являются подмножеством пар, для которых выполняется второе отношение. Если $A\subseteq B$, то $A\neq B$. Если $A\subseteq B$, то, когда любые два элемента из множества, на котором выполняется отношение $A$, связаны этим отношением, они связаны отношением $B$.

        • Очевидно, для любого отношения $A \varnothing\subseteq A\subseteq U$, где $\varnothing$ — пустое, а $U$- полное отношение.

      Графическое представление бинарных отношений

      Приведём в пример два графических представления бинарных отношений на множстве $X = \{a, b, c, d, e\}.$
      Первый способ тесно связан с аналитической геометрией. Пусть дана пара взаимно перпендикулярных осей ($Ox$ и $Oy$). На каждой оси нужно отметить точки которые являются элементами множества $X$.
      Будем считать, что $a, b, c, d, e$ — координаты точек на горизонтальной и вертикальной осях. Теперь отметим на плоскости точки с координатами $(x, y)$. На рисунке изображена совокупность точек, соответствующих следующему отношению: $R=\{(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)\}.$
      Image1

      Следующий способ, который мы рассмотрим, заключается в использовании ориентированных графов. Элементы множества $X$ становятся вершинами графа, а элементы $\langle x,y\rangle $ отношения $R$ ребрами, которые соединяют первый член $x$ отношения со вторым членом $y$. Граф, соответствующий бинарному отношению $R$, изображен на рисунке.
      Image1

      Задача

      Бинарное отношение $R$ задано на множестве $A=\{1,2,3,4\}$, определить его свойства.
      $R=\{(1,1),(1,2),(2,3),(2,2),(2,4)\}$

      Спойлер

      Проверим все свойства отношения:

      • Рефлексивность
        $(\forall x\in A)\langle x,x\rangle\in R$ – это ложное высказывание.
        Можно привести контрпример: $x=3$, пара $\langle 3,3\rangle$ не принадлежит множеству $R$. Бинарное отношение не является рефлексивным.
      • Антирефлексивность
        $(\forall x\in A)\langle x,x\rangle\notin R$ – это ложное высказывание.
        Можно привести контрпример: $x=1$, пара $\langle 1,1\rangle$ принадлежит множеству $R$. Бинарное отношение не является антирефлексивным.
      • Корефлексивность
        $(\forall x,y\in A)\langle x,y\rangle\notin R$ – это ложное высказывание.
        Можно привести контрпример: $x=1,y=2$, пара $\langle 1,2\rangle$ принадлежит множеству $R$, но $x\neq y$. Бинарное отношение не является антирефлексивным.
      • Симметричность
        $ \forall x,y\in A (\langle x,y\rangle\in R): \langle y,x\rangle\in R$ – это ложное высказывание.
        Можно привести контрпример, $x=1,y=2$ пара $\langle 1,2\rangle$ принадлежит множеству $R$, а пара $\langle 2,1\rangle$ не принадлежит множеству $R$. Бинарное отношение не является симметричным.
      • Антисимметричность
        $\forall x,y\in A(xRy\wedge yRx\Rightarrow x=y)$ – это истинное высказывание
        Контрпример подобрать невозможно. Бинарное отношение является антисимметричным.
      • Асимметричность
        Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения и отношение не является антирефлексивным, отношение не является асимметричным.
      • Транзитивность
        $\forall x,y,z\in A(xRy\wedge yRz\Rightarrow xRz)$– это ложное высказывание.
        Можно привести контр пример, $x=1,y=2,z=3$ пара $\langle 1,2\rangle$ принадлежит множеству R и пара $\langle 2,3\rangle$ принадлежит множеству $R$, а пара $\langle 1,3\rangle$ не принадлежит множеству $R$. Бинарное отношение не является транзитивным.
      • Связность
        $\forall x,y\in A(x\neq y\Rightarrow xRy\lor yRx)$ – это ложное высказывание.
        Можно привести контрпример, $x=3,y=4$, $3\neq 4$ пара $\langle 3,4\rangle$ не принадлежит множеству $R$ и пара $\langle 4,3\rangle$ не принадлежит множеству $R$. Бинарное отношение не является связанным.

      Вывод: заданное бинарное отношение обладает только одним свойством антисимметричности.

      [свернуть]

      Источники:

      • Галушкина, Марьямов, «Задачи и упражнения по дискретной математике», 2007 г., стр.51
      • С.В.Федоровский.Конспект лекций по математической логике
      • Кострикин А.В. , «Введение в алгебру», 1977, стр.134
      • А.И. Мальцев, «Алгебраические системы», 1970, стр.16-19

        • Бинарные отношения

        Вопросы для закрепления пройденного материала

        Таблица лучших: Бинарные отношения

        максимум из 15 баллов
        Место Имя Записано Баллы Результат
        Таблица загружается
        Нет данных

Компактные множества

КОМПАКТНЫЕ МНОЖЕСТВА

Определение. Пусть множество [latex]E \subset \mathbb{R}^n[/latex]. Семейство открытых множеств [latex]\left\{G_{\alpha}\right\}[/latex] называется открытым покрытием множества [latex]E[/latex], если каждая точка [latex]x \in E[/latex] принадлежит хотя бы одному из множеств [latex]G_{\alpha}[/latex], т. е. если [latex]E \subset \bigcup_{\alpha}G_{\alpha}[/latex].

Определение. Множество [latex]E \subset \mathbb{R}^n[/latex] называется компактным, если каждое его открытое покрытие содержит конечное подсемейство, также покрывающее множество [latex]E[/latex]. Это подсемейство называется конечным подпокрытием.

Например, множество, состоящее из одной точки, двух точек или любого конечного набора точек, очевидно, компактное. Пусть [latex]E \subset \mathbb{R}^n[/latex]. Диаметром множества [latex]E[/latex] называется число [latex]diam \> E = sup_{x,y \in E} \left | x — y \right |[/latex], т. е. верхняя грань расстояний между всевозможными парами точек из [latex]E[/latex]. Например, если [latex]E = \left [a^1,b^1;…;a^n,b^n \right ][/latex] – [latex]n[/latex]-мерный сегмент, то, очевидно, [latex]diam \> E = |b-a|[/latex], где [latex]a = (a^1,…,a^n), b = (b^1,…,b^n)[/latex].

Лемма (о вложенных сегментах). Пусть  [latex]\left\{I_{\nu}\right\}[/latex] – последовательность вложенных сегментов из [latex] \mathbb{R}^n [/latex], т. е. [latex]I_1 \supset I_2 \supset…\supset I_{\nu} \supset…[/latex], диаметры которых стремятся к нулю при [latex]\nu \mapsto \infty[/latex]. Тогда существует, и притом единственная, точка [latex]x_0[/latex], принадлежащая всем этим сегментам.
Доказательство. Пусть [latex]I_{\nu} = \left [a^1_{\nu},b^1_{\nu};…;a^n{\nu},b^n_{\nu} \right ] (\nu = 1,2,…)[/latex]. При каждом фиксированном [latex]i = 1,…,n[/latex] последовательность одномерных отрезков [latex] \left [a^i_{\nu},b^i_{\nu} \right ] (\nu = 1,2,…)[/latex] состоит из вложенных друг в друга отрезков, т. е. [latex][a^i_1,b^i_1] \subset [a^i_2,b^i_2] \subset … \subset [a^i_{\nu},b^i_{\nu}] \subset …[/latex], и длины этих отрезков стремятся к нулю при [latex]\nu \mapsto \infty[/latex]. По лемме Кантора, для зафиксированного [latex]i[/latex] найдется число [latex]x^i_0[/latex], такое, что [latex]x^i_0 \in [a^i_{\nu},b^i_{\nu}] (\nu = 1,2,…)[/latex], т. е. [latex]a^i_{\nu} \leq x^i_0 \leq b^i_{\nu} (\nu = 1,2,…)[/latex]. Но тогда точка [latex]x_0 = (x^1_0,…,x^n_0)[/latex], очевидно, принадлежит всем [latex]I_{\nu}[/latex]. Двух различных точек, принадлежащих всем [latex]I_{\nu}[/latex] одновременно, быть не может. Действительно, если [latex]{x}’,{x}» \in I_{\nu} (\nu = 1,2,…)[/latex], то [latex]|{x}’-{x}»| \leq diam \> I_{\nu}[/latex]. По условию правая часть стремится к нулю при [latex]\nu \mapsto \infty[/latex], так что [latex]{x}’={x}»[/latex].

Литература:

Компактные множества

Тест по теме «Компактные множества»

Таблица лучших: Компактные множества

максимум из 11 баллов
Место Имя Записано Баллы Результат
Таблица загружается
Нет данных

Примеры замкнутых множеств

  1. [latex]\varnothing[/latex] замкнуто (и, в то же время, открыто).
  2. Отрезок [latex]\left [a,b \right ] \subset \mathbb{R}[/latex] на вещественной прямой замкнут в стандартной топологии, поскольку его дополнение открыто.
  3. Множество [latex]\mathbb{Q} \bigcap \left [0,1 \right ][/latex] будет замкнутым в пространстве рациональных чисел [latex]\mathbb{Q}[/latex], но не будет замкнутым в пространстве вещественных чисел [latex]\mathbb{R}[/latex].
  4. Произвольный замкнутый шар [latex]B(x_0,r) = \left\{x : |x — x_0| \leq r \right\}[/latex] будет замкнутым множеством. Для доказательства данного утверждения, достаточно показать, что какую бы мы ни взяли точку [latex]x[/latex], не принадлежащую [latex]B(x_0,r)[/latex], она не будет являться предельной для этого шара, то есть. найдется такая окрестность [latex]B(x,\rho)[/latex], в которой нет ни одной точки данного шара (Достаточно взять [latex]\rho \leq |x-x_0|-r[/latex]).
  5. Произвольный сегмент [latex]I \equiv \left [a_1,b_1;…;a_n,b_n \right ][/latex] будет замкнутым множеством. Для доказательства данного утверждения, достаточно показать, что окрестность произвольной точки [latex]x[/latex], не принадлежащей [latex]I[/latex], не будет содержать точек из [latex]I[/latex]. Действительно, так как [latex]x \notin I[/latex], то найдется такое [latex]j[/latex], что [latex]x_j \notin \left [a_j,b_j \right ][/latex]. Пусть, к примеру, [latex]x_j < a_j[/latex]. Легко видеть, что шар [latex]B(x,\rho)[/latex], где [latex]0 < \rho \leq a_j — x_j[/latex], не имеет общих точек с [latex]I[/latex]. Следовательно, [latex]I[/latex] – замкнутое множество.
  6. Рассмотрим множество [latex]E \equiv \left\{(x,y) : y = sin \frac{1}{x}, x \neq 0\right\}[/latex]. Отрезок [latex] \left [-1,1 \right ][/latex] оси ординат целиком состоит из предельных точек множества [latex]E[/latex], но ни одна из точек этого отрезка не принадлежит [latex]E[/latex]. Поэтому множество [latex]E[/latex] не является замкнутым.

Литература:

Свойства замкнутых множеств

Теорема. Пусть [latex](X,\tau)[/latex] — произвольное топологическое пространство. Тогда  система всех его замкнутых множеств имеет такие свойства:

  1. Множества [latex]X[/latex] и [latex]\varnothing[/latex] будут замкнутыми;
  2. Произвольная система замкнутых множеств в пересечении дает замкнутое множество;
  3. Произвольная конечная система замкнутых множеств в объединении дает замкнутое множество;

Доказательство

  1. Обозначим через [latex](X,\tau)[/latex] произвольное топологическое пространство. В таком случае, [latex]X[/latex] и [latex]\varnothing[/latex] являются замкнутыми множествами (в то же время и открытыми по 3-ей аксиоме топологического пространства), так как [latex]X\setminus\varnothing=X[/latex] — открытое множество и [latex]X\setminus X=\varnothing[/latex] — также открытое множество.
  2. Обозначим через [latex]\left\{ F_{\alpha} \right\}[/latex] систему замкнутых множеств. Следовательно, с учетом того факта, что замкнутое множество есть дополнение открытого, получаем [latex]\bigcap_{\alpha} F_{\alpha} = \bigcap_{\alpha}(X \setminus G_{\alpha}) = X \setminus \bigcup_{\alpha}G_{\alpha}[/latex], так как. объединение открытых множеств есть множество открытое, а его дополнение — замкнуто, то множество [latex]X \setminus \bigcup_{\alpha}G_{\alpha}[/latex] — замкнуто.
  3. Аналогично попробуем найти объединение конечной системы замкнутых множеств: [latex]\bigcup_{n=1}^{k} F_{n} = \bigcup_{n=1}^{k}(X \setminus G_{n}) = X \setminus \bigcap_{n=1}^{k}G_{n}[/latex] , так как пересечение конечного числа открытых множеств [latex]G_k[/latex] будет открытым множество, то [latex]X \setminus \bigcap_{n=1}^{k}G_{n}[/latex] — замкнуто.

Вышеперечисленные свойства систем замкнутых множеств, однозначно их характеризуют, поэтому не исключается подход, при котором эти свойства принимаются за систему аксиом, определяющих топологическое пространства. Следовательно, имеет место следующая
Теорема. Если [latex]X[/latex] — произвольное множество и [latex]\lambda[/latex] семейство его подмножеств, обладающее следующими свойствами:

  1. [latex] X, \varnothing \in \lambda [/latex]
  2. Пересечение множеств любой подсистемы в [latex]\lambda[/latex] принадлежит [latex]\lambda[/latex]
  3. Объединение множеств любой конечной подсистемы в [latex]\lambda[/latex] принадлежит [latex]\lambda[/latex]

Предположим, что [latex]\upsilon[/latex] — семейство дополнений всех различных множеств из [latex]\lambda[/latex]. В таком случае [latex]\upsilon[/latex] будет топологией на [latex]X[/latex], а [latex]\lambda[/latex] — системой замкнутых множеств топологического пространства [latex](X,\upsilon)[/latex].

Литература:

Свойства замкнутых множеств

Тест по теме «Свойства замкнутых множеств»

Таблица лучших: Свойства замкнутых множеств

максимум из 20 баллов
Место Имя Записано Баллы Результат
Таблица загружается
Нет данных
/a. Тогда 

Двойственность открытых и замкнутых множеств

Пусть множество [latex]E \subset \mathbb{R}^n[/latex]. Тогда множество всех точек [latex]x \in \mathbb{R}^n[/latex], не принадлежащих множеству [latex]E[/latex], называется дополнением множества [latex]E[/latex] и обозначается [latex]cE[/latex] или [latex]E^c[/latex].

Теорема. Для того чтобы множество [latex]E \subset \mathbb{R}^n[/latex] было замкнутым, необходимо и достаточно, чтобы его дополнение [latex]G \equiv cF[/latex] было открытым. Доказательство.
Необходимость. Пусть [latex]E[/latex] замкнуто и [latex]x[/latex] – произвольная точка из [latex]G[/latex]. Докажем, что она будет внутренней в [latex]G[/latex]. Поскольку [latex]x \notin E[/latex], то она не будет предельной точкой для [latex]E[/latex] и найдется такая ее окрестность [latex]U_x[/latex], которая не содержит ни одной точки из [latex]E[/latex]. Следовательно, эта окрестность полностью содержится в [latex]G[/latex], так что [latex]x[/latex] – внутренняя точка множества [latex]G[/latex].
Достаточность. Предположим теперь, что [latex]G[/latex] – открыто. Докажем тогда, что [latex]E[/latex] замкнуто. Для этого достаточно показать, что любая точка [latex]x[/latex], которая не принадлежит [latex]E[/latex], не будет предельной для [latex]E[/latex]. Если [latex]x \notin E[/latex], то [latex]x \in G[/latex], а так как [latex]G[/latex] открыто, следовательно найдется окрестность [latex]U_x \subset G[/latex]. Она не будет содержать точек из [latex]E[/latex], так что [latex]x[/latex] не является предельной для [latex]E[/latex], ч. т. д.

Отношение двойственности. Пусть [latex] \left\{ E_{\alpha} \right\} [/latex] – произвольное семейство множеств. Тогда дополнение к объединению множеств [latex]E_{\alpha}[/latex] равно пересечению дополнений множеств [latex]E_{\alpha}[/latex], а дополнение к пересечению равно объединению дополнений, т. е. [latex]c(\bigcup E_{\alpha}) = \bigcap(cE_{\alpha}), c(\bigcap E_{\alpha}) = \bigcup(cE_{\alpha})[/latex].

Литература: