Несколько задач по теории множеств

[Asker Tasker]

Необходимо доказать следующие утверждение:

1) $\left(\bigcap_{i = 1}^{n} A_{i} \right) \oplus \left(\bigcap_{i = 1}^{n} B_{i} \right) \subseteq \bigcup_{i=1}^{n}\left(A_{i}\oplus B_{i} \right)$
Сначала думал по индукции. Для i=1 очевидно. А вот когда предположение индукции для i=n написано и (n+1)-е множество добавляю, происходит глубокое зависание. Как вывести из n-го шага (n+1)-й не знаю. Попробовал от противного: ну, пусть принадлежит какой-то х левой части и не принадлежит правой. Тогда верно одно и ровно одно из двух утверждений: $ \forall i \in \left{ 1, ..., n \right} x \in A_{i}$ или $ \forall i \in \left{ 1, ..., n \right} x \in B_{i}$. А вот как связать это с правой частью пока не понял.


2) Если какое-то равенство, содержащее переменные-множества и операции объединения, пересечения и разности, неверно, то к нему можной найти контрпример, в котором все множества пусты или состоят из одного элемента.
Пусть $ S_{1} \left( A_{1}, A_{2}, ..., A_{n} \right) = S_{2} \left( A_{1}, A_{2}, ..., A_{n} \right) $ - данное неверное равенство.

И пусть набор множеств $ \left{ C_{1}, ..., C_{n} \right} $ - контрпимер к этому равенству. Первый вопрос, который у меня возник - по формулировке условия - "все множества или состоят из одного элемента" - это означает, что либо все множества одновременно пустые, либо все одновременно одноэлементны или что каждое пусто либо одноэлементно по отдельности?
Я исходил из второго вариант трактовки. И всё равно запутался.

Раз для множеств $ C_{i} $ исходное равенство не выполняется, то $ S_{1} \left( C_{1}, C_{2}, ..., C_{n} \right) \neq S_{2} \left( C_{1}, C_{2}, ..., C_{n} \right) $, то есть $\left( \exists x \in S_{1} : x \notin S_{2}\right) \vee \left( \exists x \in S_{2} : x \notin S_{1}\right)$

Но вот что делать дальше?! Если мы хотим, чтобы в контрпримере были одноэлементные множества логично выбрать этот элемент в одном из множеств $C_{i}$, но как? Если все C_{i} пусты, то утверждение доказано. Если есть хоть одно непустое, возьмём $c \in C_{i}$. Тогда для всех множеств из набора $ \left{ C_{1}, ..., C_{n} \right} $ будет справедливо одно и только одно из двух соотношений: $ \left( C_{i} \bigcap \left\{c \right\} = \left\{c \right\}\right) \vee \left( C_{i} \bigcap \left\{c \right\} = \varnothing \right) $. А вот как дальше доказывать - запутался.

[ewert]

Asker Tasker в сообщении #585068 писал(а):

$\left(\bigcap_{i = 1}^{n} A_{i} \right) \oplus \left(\bigcap_{i = 1}^{n} B_{i} \right) \subseteq \bigcup_{i=1}^{n}\left(A_{i}\oplus B_{i} \right)$

Что такое "oplus"?

[Asker Tasker]

Я не нашёл в Tex'е треугольничек, которым симметрическую разность обозначаем
Пришлось воспользоваться значком дизъюнктивной суммы.

[Asker Tasker]

Я обновил условие первой задачи. Так, думаю, будет удобнее читать:
$ \left(\bigcap_{i = 1}^{n} A_{i} \right) \Delta \left(\bigcap_{i = 1}^{n} B_{i} \right) \subseteq \bigcup_{i=1}^{n} \left(A_{i} \Delta B_{i} \right) $

Всё еще надеюсь на Ваши ответы.

[muzeum]

Пусть х принадлежит левой части. Тогда он принадлежит одному из дизъюнктов и не принадлежит второму. В силу симметрии условия будем считать, что принадлежит левому и не принадлежит правому. Подумайте, что это означает и укажите то слагаемое в правой части, которому он принадлежит.

[Asker Tasker]

muzeum в сообщении #585798 писал(а):

Пусть х принадлежит левой части. Тогда он принадлежит одному из дизъюнктов и не принадлежит второму. В силу симметрии условия будем считать, что принадлежит левому и не принадлежит правому. Подумайте, что это означает и укажите то слагаемое в правой части, которому он принадлежит.

Попробую.
$ x \in \left(\bigcap_{i = 1}^{n} A_{i} \right) \Leftrightarrow \forall i \in \left\{ 1, ..., n \right\} \left( x \in A_{i} \right) $
$ x \notin \left(\bigcap_{i = 1}^{n} B_{i} \right) \Leftrightarrow \exists i \in \left\{ 1, ..., n \right\} : \left( x \notin B_{i} \right) $

Тогда для всех $ i \in \left\{ 1, ..., n \right\} : \left( x \in A_{i} \wedge x \notin B_{i} \right) $ будет справедливо включение $ x \in \left( A_{i} \Delta B_{i} \right) $.

И значит, х принадлежит объединению слагаемых правой части. Верно?

P. S.
А если описать левую и правую части характеристическими функциями:
$ a_{i} \equiv \chi_{A_{i}} $
$ b_{i} \equiv \chi_{B_{i}} $
$ \left(\bigcap_{i = 1}^{n} A_{i} \right) \Delta \left(\bigcap_{i = 1}^{n} B_{i} \right) = \left\{ x : \left( a_{1}\cdot ... \cdot a_{n} \right) \Delta \left( b_{1}\cdot ... \cdot b_{n} \right) = 1 \right\} $
$ \bigcup_{i = 1}^{n} \left( A_{i} \Delta B_{i} \right) = \left\{ x : \left( a_{1} \Delta b_{1} \right) \vee ... \vee \left( a_{n} \Delta b_{n} \right) = 1 \right\} $
А затем доказать тождественную истинность импликации $ \left( a_{1}\cdot ... \cdot a_{n} \right) \Delta \left( b_{1}\cdot ... \cdot b_{n} \right) \right\ \rightarrow \left( a_{1} \Delta b_{1} \right) \vee ... \vee \left( a_{n} \Delta b_{n} \right) \equiv 1 $ - тоже ведь будет правильное решение?
Ведь, насколько я понимаю, $ \left (A \subseteq B \right ) \Leftrightarrow \left( \chi_{A} \rightarrow \chi_{B} \equiv 1 \right) $

[arseniiv]

Asker Tasker в сообщении #585182 писал(а):

Я не нашёл в Tex'е треугольничек, которым симметрическую разность обозначаем

Вроде бы это $\vartriangle$.

[Asker Tasker]

arseniiv в сообщении #586148 писал(а):

Вроде бы это $\vartriangle$.

Теперь буду знать)

[Dave]

Asker Tasker в сообщении #585068 писал(а):

1) $\left(\bigcap_{i = 1}^{n} A_{i} \right) \oplus \left(\bigcap_{i = 1}^{n} B_{i} \right) \subseteq \bigcup_{i=1}^{n}\left(A_{i}\oplus B_{i} \right)$

Asker Tasker в сообщении #586075 писал(а):

Попробую.
$ x \in \left(\bigcap_{i = 1}^{n} A_{i} \right) \Leftrightarrow \forall i \in \left\{ 1, ..., n \right\} \left( x \in A_{i} \right) $
$ x \notin \left(\bigcap_{i = 1}^{n} B_{i} \right) \Leftrightarrow \exists i \in \left\{ 1, ..., n \right\} : \left( x \notin B_{i} \right) $

Тогда для всех $ i \in \left\{ 1, ..., n \right\} : \left( x \in A_{i} \wedge x \notin B_{i} \right) $ будет справедливо включение $ x \in \left( A_{i} \Delta B_{i} \right) $.

И значит, х принадлежит объединению слагаемых правой части. Верно?

Неверно. Не для всех $i$, а только для тех, для которых $x \notin B_{i}$.

Asker Tasker в сообщении #586075 писал(а):

А если описать левую и правую части характеристическими функциями:

Можно доказать и через характеристические функции, но лучше не мудрить, ибо только усложните себе задачу. muzeum подсказал самый простой способ решения.

Asker Tasker в сообщении #585068 писал(а):

2) Если какое-то равенство, содержащее переменные-множества и операции объединения, пересечения и разности, неверно, то к нему можной найти контрпример, в котором все множества пусты или состоят из одного элемента.
Первый вопрос, который у меня возник - по формулировке условия - "все множества или состоят из одного элемента" - это означает, что либо все множества одновременно пустые, либо все одновременно одноэлементны или что каждое пусто либо одноэлементно по отдельности?

Имеется ввиду, что там участвуют только два множества (возможно, повторяясь) - пустое и одноэлементное. Возьмите (так же, как Вы и начинали) набор множеств $C_i$, составляющих контрпример и конкретный элемент $x$, который принадлежит одной из частей равенства и не принадлежит другой. Потом выбросьте из всех $C_i$ все элементы, кроме $x$. Какие множества останутся? Как эта операция повлияет на принадлежность $x$ левой и правой частям равенства. Разбейте $S_1$ и $S_2$ на элементарные операции и проанализируйте каждую из них по отдельности на предмет принадлежности $x$ аргументам и результату операции - до и после выбрасывания остальных элементов.

[Asker Tasker]

Dave в сообщении #586212 писал(а):

Неверно. Не для всех , а только для тех, для которых .

Так я ведь это и написал

Цитата:

Тогда для всех $ i \in \left\{ 1, ..., n \right\} : \left( x \in A_{i} \wedge x \notin B_{i} \right) $ будет справедливо включение $ x \in \left( A_{i} \Delta B_{i} \right) $.

"Тогда для всех i, таких, что х принадлежит $A_{i}$ и одновременно не принадлежит $B_{i}$, справедливо..."



К решению второй задачи.
Останутся множества либо пустые, либо состоящие из единственного элемента х.

Итак, имеем:
Набор множеств $ \left{ C_{1}, ..., C_{n} \right} $ - контрпимер к заданному равенству.
$ S_{1} \left( C_{1}, C_{2}, ..., C_{n} \right) \neq S_{2} \left( C_{1}, C_{2}, ..., C_{n} \right) $
$\left( \exists x \in S_{1} : x \notin S_{2}\right) \vee \left( \exists x \in S_{2} : x \notin S_{1}\right)$

Достаточно доказать для одного случая, когда х не принадлежит, например, левой части - $ S_{1}$. Возьмём этот х - тогда будет справедливо одно и только одно из двух равенств: $ \left( C_{i} \bigcap \left\{x \right\} = \left\{x \right\}\right) $ или $ \left( C_{i} \bigcap \left\{x \right\} = \varnothing \right) $.

Есть три варианта простейших связок (а левая и правая часть состоят из комбинаций этих связок с операциями пересечения, объединения и разности):
(1) $ A \bigcap B $
(2) $ A \bigcup B $
(3) $ A \backslash B $

Я расписал эти три случая:
(1) $ \begin{bmatrix} \left\{ x \right\} \bigcap \left\{ x \right\} = \left\{ x \right\} \ & \ \left\{ x \right\} \bigcap \varnothing = \varnothing \\ \varnothing \bigcap \varnothing = \varnothing \ & \ \varnothing \bigcap \left\{ x \right\} = \varnothing \end{bmatrix} $

(2) $ \begin{bmatrix} \left\{ x \right\} \bigcup \left\{ x \right\} = \left\{ x \right\} \ & \ \left\{ x \right\} \bigcup \varnothing = \left\{ x \right\} \\ \varnothing \bigcup \varnothing = \varnothing \ & \ \varnothing \bigcup \left\{ x \right\} = \left\{ x \right\} \end{bmatrix} $

(3) $ \begin{bmatrix} \left\{ x \right\} \backslash \left\{ x \right\} = \varnothing \ & \ \left\{ x \right\} \backslash \varnothing = \left\{ x \right\} \\ \varnothing \backslash \varnothing = \varnothing \ & \ \varnothing \ \backslash \left\{ x \right\} = \varnothing \end{bmatrix} $


Значит, и левая, и правая часть сведётся либо к $\varnothing$, либо к $\left\{ x \right\}$.
Вот тут у меня снова зависание. Если одна из частей пуста, а другая - нет, то равенство, очевидно, не выполнено. Но что, если обе окажутся пусты или обе сведутся ко множеству, содержащему только х?

[Dave]

Asker Tasker в сообщении #586655 писал(а):

Но что, если обе окажутся пусты или обе сведутся ко множеству, содержащему только х?

Не окажутся и не сведутся. Ваша ошибка состоит в том, что Вы рассматриваете тождества с $x$ в отрыве от исходных. А нужно было не просто расписать 3 случая, как Вы это сделали выше, а сравнить участвующие в них множества с исходными множествами на предмет принадлежности $x$.

[Asker Tasker]

Не совсем понял, но попробую.
Дополним старые обозначения:
- набор множеств $ \{ C_{i} \}_{i=1}^{n}$ является контрпримером к заданному равенству: $ S_{1} ( C_{1}; ...; C_{n} ) \neq S_{2} ( C_{1}; ...; C_{n} ) $;
- выбираем х так, что: $ x \in S_{1} $ и $ x \notin S_{2} $ (существование такого х гарантирует предыдущий пункт);
- обозначим $ C_{i}^{*} = C_{i} \bigcap \{ x \} = \left\{ \begin{matrix} \varnothing , x \notin C_{i} \\ \{ x \} , x \in C_{i} \end{matrix}\right. $

Теперь рассмотрим три допустимых по условию вида элементарных связок, в которых участвует по два множества - $ C_{i}^{*}$ и $ C_{j}^{*} $
Возможны три ситуации:
(1) х принадлежит обоим множествам сразу, тогда:
$ x \in C_{i}^{*} \rightarrow x \in C_{i} \\ x \in C_{j}^{*} \rightarrow x \in C_{j} \\ \begin{bmatrix} x \in C_{i}^{*} \bigcap C_{j}^{*} & x \in C_{i} \bigcap C_{j} \\ x \in C_{j}^{*} \bigcup C_{j}^{*} & x \in C_{j} \bigcup C_{j} \\ x \notin C_{i}^{*} \backslash C_{j}^{*} & x \notin C_{i} \backslash C_{j} \end{bmatrix} $

(2) x принадлежит только одному из двух множеств - например, $ C_{i} $, тогда:
$ x \in C_{i}^{*} \rightarrow x \in C_{i} \\ x \notin C_{j}^{*} \rightarrow x \notin C_{j} \\ \begin{bmatrix} x \notin C_{i}^{*} \bigcap C_{j}^{*} & x \notin C_{i} \bigcap C_{j} \\ x \in C_{j}^{*} \bigcup C_{j}^{*} & x \in C_{j} \bigcup C_{j} \\ x \in C_{i}^{*} \backslash C_{j}^{*} & x \in C_{i} \backslash C_{j} \end{bmatrix} $

(3) х не принадлежит ни одному из двух множеств, тогда:
$x \notin C_{i}^{*} \rightarrow x \notin C_{i} \\ x \notin C_{j}^{*} \rightarrow x \notin C_{j} \\ \begin{bmatrix} x \notin C_{i}^{*} \bigcap C_{j}^{*} & x \notin C_{i} \bigcap C_{j} \\ x \notin C_{j}^{*} \bigcup C_{j}^{*} & x \notin C_{j} \bigcup C_{j} \\ x \notin C_{i}^{*} \backslash C_{j}^{*} & x \notin C_{i} \backslash C_{j} \end{bmatrix} $

А как дальше? Соорентируйте, пожалуйста!

[Dave]

Дальше берём множества $D_1, \ldots, D_m$, являющиеся результатами этих операций и повторяем те же самые рассуждения для них и т.д., до тех пор, пока не придём к множеству $S_1 \cap \{x\}=\{x\}$ слева и $S_2 \cap \{x\}=\varnothing$ справа.

[Asker Tasker]

Dave в сообщении #587448 писал(а):

Дальше берём множества $D_1, \ldots, D_m$, являющиеся результатами этих операций и повторяем те же самые рассуждения для них и т.д., до тех пор, пока не придём к множеству $S_1 \cap \{x\}=\{x\}$ слева и $S_2 \cap \{x\}=\varnothing$ справа.

Наверное, я уже окончательно торможу, но я не понял переход от рассмотрения промежуточных множеств $D_{i}$ к нашему конечному выводу. Как мы его делаем? В частности, мне непонятно, как мы исключили равенство левой части пустому множеству.

[Dave]

Asker Tasker в сообщении #587452 писал(а):

Наверное, я уже окончательно торможу, но я не понял переход от рассмотрения промежуточных множеств к нашему конечному выводу. Как мы его делаем?

А как вообще конечный вывод получается? Через цепочку промежуточных множеств. Мы взяли конкретный контрпример, взяли $x$ из участвующих в нём множествах, на котором различие левой и правой частей проявляется, а потом доказываем, что это различие не исчезнет, если во всех участвующих множествах (начальных $C_i$, промежуточных $D_i$, которых может быть несколько этапов и конечных $S_i$) останется только $x$. Проще всего понять на рассмотрении какого-нибудь конкретного примера неверного равенства. Например, $A \cup (B \cap C)=(A \cup B) \cap C$ с контрпримером $A=\{1,2,3\}, B=\{2,3\}, C=\{3\}$.

Asker Tasker в сообщении #587452 писал(а):

В частности, мне непонятно, как мы исключили равенство левой части пустому множеству.

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