Специальные бинарные отношения

Доказать, что если отношения $R_{1}$ и $R_{2}$ рефлексивны, то рефлексивны отношения $R_{1} \cup R_{2}$, $R_{1} \cap R_{2}$, $R_{1}^{-1}$, $R_{1} \cdot R_{2}$.

Доказать, что если отношения $R_{1}$ и $R_{2}$ иррефлексивны, то иррефлексивны отношения $R_{1} \cup R_{2}$, $R_{1} \cap R_{2}$, $R_{1}^{-1}$. Показать, что произведение $R_{1} \cdot R_{2}$ иррефлексивных отношений может не быть иррефлексивным.

Доказать, что если отношения $R_{1}$ и $R_{2}$ симметричны, то симметричны отношения $R_{1} \cup R_{2}$, $R_{1} \cap R_{2}$, $R_{1}^{-1}$, $R_{1} \cdot R_{2}^{-1}$.

Доказать, что произведение $R_{1} \cdot R_{2}$ симметричных отношений $R_{1}$ и $R_{2}$ симметрично тогда и только тогда, когда $R_{1} \cdot R_{2} = R_{2} \cdot R_{1}$.

Доказать, что:

Построить бинарное отношение:

Доказать, что любое отношение $R$, симметричное и антисимметричное одновременно, является транзитивным.

Доказать, что отношение $R$ на множестве $A$ является одновременно эквивалентностью и частичным порядком в том и только том случае, когда $R = i_{A}$.

На множествах $\mathbb {N}$ и $\mathbb {N} \times \mathbb {N}$ определим $R_{m}$, $Q$, $S$ следующим образом:

Пусть $A$ --- множество всех прямых на плоскости. Являются ли эквивалентностями следующие отношения:

На множестве $\mathbb {R}$ действительных чисел определим отношение $R$ следующим образом:

Доказать, что $R$ есть эквивалентность.

Доказать, что если $R$ --- эквивалентность, то:

Доказать, что если $R$ есть эквивалентность, то $R^{-1}$ есть также эквивалентность.

Пусть $R \subseteq A^{2}$. Доказать, что

Доказать, что если $R_{1}$ и $R_{2}$ --- эквивалентности на $A$, то:

Доказать, что существует взаимно однозначное соответствие между классом всех разбиений множества $A$ на непересекающиеся непустые подмножества и семейством всех отношений эквивалентности на $A$. (Семейство $\left\{ A_{i}\right\}_{i \in I}$ называется разбиением $A$, если $\bigcup_{i \in I} A_{i} = A$ и множества $A_{i}$ попарно не пересекаются.)

Доказать, что $R$ тогда и только тогда является отношением эквивалентности на множестве $A$, когда существует система $P$ попарно непересекающихся множеств такая, что

Пусть $f: A \rightarrow B$ --- произвольная функция. Положим

Доказать, что $Q$ является эквивалентностью на $A$ и для отображения $f$ существует разложение

где $\varepsilon$ --- естественное отображение $A$ на $A/Q = \left\{ [x]_{Q} \mid x \in A\right\}$, т.е. $\varepsilon (x) = [x]_{Q}$, $f_{1}$ --- взаимно однозначное соответствие между $A/Q$ и $f(A)$.

Доказать, что пересечение любой системы эквивалентностей на множестве $A$ есть эквивалентность на $A$.

Доказать, что объединение $R_{1} \cup R_{2}$ эквивалентностей $R_{1}$ и $R_{2}$ является эквивалентностью тогда и только тогда, когда $R_{1} \cup R_{2} = R_{1} \cdot R_{2}$.

Доказать, что произведение $R_{1} \cdot R_{2}$ двух эквивалентностей $R_{1}$ и $R_{2}$ тогда и только тогда является эквивалентностью, когда $R_{1} \cdot R_{2} = R_{2} \cdot R_{1}$.

Доказать, что если $R_{1}$ и $R_{2}$ --- эквивалентности и $R_{1} \cdot R_{2} = R_{2} \cdot R_{1}$, то $R_{1} + R_{2} = R_{1} \cdot R_{2}$, где $R_{1} + R_{2}$ --- наименьшее отношение эквивалентности, включающее $R_{1} \cup R_{2}$.

Доказать, что для всякого семейства эквивалентностей $\left\{ R_{i}\right\}_{i \in I}$ существует эквивалентность $Q$ такая, что $\bigcup_{i \in I} R_{i} \subseteq Q$ и для всякого отношения эквивалентности $R$, если $\bigcup_{i \in I} R_{i} \subseteq R$, то $Q \subseteq R$.

Доказать, что

где $p_{n}$ --- число эквивалентностей на множестве из $n$ элементов.

Доказать, что множество всех подмножеств данного множества частично упорядоченно отношением включения $\subseteq$.

Пусть $\leq$ и $<$ на множестве $\mathbb {N} = \left\{ 0, 1, 2, \ldots \right\}$ определяются обычным образом. Доказать, что $< \cdot < \; \neq \; <$; $\leq \cdot < \; = \; <$; $\leq \cdot \geq \; = \; \mathbb {N}^{2}$.

Доказать, что $i_{A}$ есть частичный порядок на $A$.

Пусть $a \leq b \Leftrightarrow a, b \in \mathbb {N}$ и $a$ делит $b$. Считаем, что $0$ делит $0$. Доказать, что $\leq$ --- частичный порядок на $\mathbb {N}$.

Доказать, что если $R$ --- частичный порядок, то $R^{-1}$ --- частичный порядок.

Показать, что если $\left\{ R_{i}\right\}_{i \in I}$ --- система частичных порядков на множестве $A$, то $\bigcap_{i \in I} R_{i}$ --- частичный порядок на множестве $A$.

Доказать, что отношение $R$ на множестве $A$ есть предпорядок тогда и только тогда, когда $R = (R \cdot R) \cup i_{A}$.

Пусть $R$ --- отношение предпорядка на $A$. Положим

Доказать, что:

Доказать, что если $R$ --- частичный (линейный, полный) порядок на $X$ и $A \subseteq X$, то $R \cap A^{2}$ есть частичный (линейный, полный) порядок на $A$.

Пусть $\leq$ --- частичный порядок на $A$. Доказать, что $<$ иррефлексивно и транзитивно.

Доказать, что если некоторое отношение $<$ на $A$ иррефлексивно и транзитивно, то отношение

есть частичный порядок на $A$.

Показать, что если $A$ и $A_{1}$ --- частично упорядоченные множества и $f: A \rightarrow A_{1}$ --- монотонная функция, осуществляющая взаимно однозначное соответствие между $A$ и $A_{1}$, то $f^{-1}$ может не быть монотонной.

Рассмотреть случай, когда $A$ --- линейно упорядоченное множество.

Доказать, что любое частично упорядоченное множество $A$ изоморфно некоторой системе подмножеств множества $A$, упорядоченной включением $\subseteq$.

Пусть $R_{1}$ и $R_{2}$ --- линейные порядки на множестве $A$. Когда $R_{1} \cdot R_{2}$ --- линейный порядок?

Построить линейный порядок на множестве:

Доказать, что любое конечное множество можно линейно упорядочить.

Доказать, что всякий частичный порядок $R$ на конечном множестве $A$ может быть продолжен до линейного порядка $R \subseteq Q$ на множестве $A$ (см. также задачу I.5.69).

Пусть $A$ --- частично упорядоченное множество, в котором каждая цепь имеет не более $m$ элементов, а любое подмножество попарно несравнимых элементов состоит не более чем из $n$ элементов. Показать, что $A$ имеет не более $m \cdot n$ элементов.

Пусть $\leq_{A}$ есть частичный порядок на множестве $A$, $\leq_{B}$ --- частичный порядок на множестве $B$. Назовем прямым произведением частично упорядоченных множеств $A$ и $B$ множество $A \times B$ с заданным на нем отношением $\leq$:

Доказать, что $\leq$ есть частичный порядок на $A \times B$.

Пусть $A$ --- частично упорядоченное множество, $a, b \in A$ и $a \leq b$. Назовем сегментом множество $[a, b] = \left\{ x \mid a \leq x \leq b\right\}$. Показать, что множество всех сегментов множества $A$, частично упорядоченное по включению, изоморфно некоторому подмножеству прямого произведения $A$ и двойственного к нему частично упорядоченного множества.

Назовем частично упорядоченное множество $A$ самодвойственным, если оно изоморфно двойственному к нему частично упорядоченному множеству. Доказать, что:

Будем говорить, что частично упорядоченное множество $A$ удовлетворяет:

1. условию минимальности, если всякое непустое подмножество $M$ множества $A$ обладает по крайней мере одним минимальным элементом;

2. условию обрыва убывающих цепей, если всякая строго убывающая цепь в $A$ конечна;

3. условию индуктивности, если для любого свойства $T$ выполнено следующее:

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

Доказать, что частично упорядоченное множество удовлетворяет условию минимальности тогда и только тогда, когда все его цепи вполне упорядочены.

Описать все линейно упорядоченные множества $A$, обладающие таким свойством, что для любых $a \leq b$ существует только конечное число $c$ таких, что $a \leq c \leq b$.

Найти все множества $M$ такие, что существует полный порядок $R$ такой, что $R^{-1}$ также является полным порядком на $M$.

Пусть $\varphi : A \times A \rightarrow A$ и для всех $x, y, z \in A$

Определим $x \leq y \Leftrightarrow \varphi (x, y) = x$. Доказать, что:

Доказать, что любое подмножество множества $P(A)$, частично упорядоченное по включению, имеет точную верхнюю грань и точную нижнюю грань.

Доказать, что:

Доказать, что в решетке любой максимальный элемент является наибольшим, а любой минимальный элемент является наименьшим.

Доказать, что в любой конечной решетке существуют наибольший и наименьший элементы.

Привести примеры решеток:

Доказать, что в любой решетке выполнены тождества:

Пусть на множестве $M$ заданы двуместные функции $\cup$ и $\cap$, удовлетворяющие тождествам $(l_{1})$--$(l_{6})$ из предыдущей задачи.

Доказать, что во всякой булевой алгебре $M$:

Доказать, что алгебра подмножеств, упорядоченная включением, есть булева алгебра.

Доказать, что $1 \in D$ и $0 \notin D$ для любого фильтра $D$.

Пусть $M$ --- булева алгебра, $A \subseteq M$. Доказать, что если $a_{1} \cap \ldots \cap a_{n} \neq 0$ для любого $n > 0$ и любых элементов $a_{1}, \ldots , a_{n} \in A$, то множество

есть фильтр на $M$.

Пусть $D$ --- фильтр на булевой алгебре $M$ и $(x \cup y) \in D$. Доказать, что существует фильтр $D_{1} \supseteq D$ такой, что $x \in D_{1}$ или $y \in D_{1}$.

Доказать, что для любого фильтра $D$ следующие условия эквивалентны:

Доказать, что любой фильтр на булевой алгебре $M$ содержится в некотором максимальном фильтре на $M$.

Доказать, что для любых элементов $a, b$ булевой алгебры $M$, если неверно, что $a \leq b$, то существует простой фильтр $D$ такой, что $a \in D$ и $b \notin D$.

Пусть $M$ --- булева алгебра, $P$ --- множество всех простых фильтров на $M$. Положим для $a \in M$

Доказать, что множество

есть алгебра подмножеств множества $P$.

Доказать, что любая булева алгебра изоморфна некоторой алгебре подмножеств подходящего множества (теорема Стоуна).

Доказать, что любой фильтр на конечной булевой алгебре имеет наименьший элемент.

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