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

Пусть $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)\}.$

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

Задача

Бинарное отношение $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

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

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

Задание 1 из 3

1.
Пусть $A={1}$ .Запишите хотя бы один элемент декартового произведения $A\times A$ как пару чисел, разделённых запятой. Например: $8,9.$
Правильно

Неправильно
Задание 2 из 3

2.
Бинарное отношение $xRy\leftrightarrow x^2=y^2$ определено на множестве действительных чисел $R$ . Какими свойствами из приведенных ниже оно обладает?
- Рефлексивность
- Антирефлексивность
- Симметричность
- Антисимметричность
- Связность
- Транзитивность
Правильно

Неправильно
Задание 3 из 3

3.
Для бинарного отношения $R$ множество, состоящее из таких $x$ , для которых $\langle x,y\rangle\in R$ хотя бы для одного $y$ называется
Правильно

Неправильно

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

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

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

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

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

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

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

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

Литература:

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

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

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

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

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

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

Литература:

В.И. Коляда, А.А. Кореновский. Курс лекций по математическому анализу — Одесса, «Астропринт», 2009. (с.235)
Замкнутое множество. Материал из Википедии — свободной энциклопедии.

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

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

Множества $X$ и $\varnothing$ будут замкнутыми;
Произвольная система замкнутых множеств в пересечении дает замкнутое множество;
Произвольная конечная система замкнутых множеств в объединении дает замкнутое множество;

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

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

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

$X, \varnothing \in \lambda$
Пересечение множеств любой подсистемы в $\lambda$ принадлежит $\lambda$
Объединение множеств любой конечной подсистемы в $\lambda$ принадлежит $\lambda$

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

Литература:

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

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

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

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

/a. Тогда

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

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

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

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

Литература:

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

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

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

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

Задача

Источники:

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

Навигация (только номера заданий)

Информация

Результаты

Рубрики

1.

2.

3.

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

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

Навигация (только номера заданий)

Информация

Результаты

Рубрики

1.

2.

3.

Элементы сортировки

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

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

Навигация (только номера заданий)

Информация

Результаты

Рубрики

1.

2.

3.

4.

5.

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