2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Проверьте доказательство включения множеств, пожалуйста.
Сообщение11.02.2013, 18:38 
Задача из учебника Н.К. Верещагин, А. Шень (ч. 1):

Докажите, что $(A_1 \cap \ldots \cap A_n) \vartriangle (B_1 \cap \ldots \cap B_n) \subset (A_1 \vartriangle B_1) \cup \ldots \cup  (A_n \vartriangle B_n)$ для любых множеств $A_1, \ldots ,A_n$ и $B_1, \ldots ,B_n$.
(Обозначение $\vartriangle $ — симметрическая разность)

Доказательство:
Введем обозначения:
  • множество $(A_1 \cap \ldots \cap A_n) \vartriangle (B_1 \cap \ldots \cap B_n)\ \eqno(1)$
  • множество $(A_1 \vartriangle B_1) \cup \ldots \cup  (A_n \vartriangle B_n)\ \eqno(2)$
Пусть $x$ — любая точка множества $(1)$.
Тогда $x \in \lbrace a \mid (a\in\bigwedge\limits_{i=1}^n A_i)\oplus(a\in\bigwedge\limits_{i=1}^n B_i)\rbrace$. А из $(2)$ получим $x\in\lbrace a \mid \bigvee\limits_{i=1}^n{(a\in A_i \oplus a\in B_i)}\rbrace$
Тогда исходное выражение перепишем в виде:
$$x \in \Bigl\lbrace a\mid\bigl((a\in\bigwedge\limits_{i=1}^n A_i)\oplus(a\in\bigwedge\limits_{i=1}^n B_i)\bigr) \rightarrow \bigvee\limits_{i=1}^n{(a\in A_i \oplus a\in B_i)}\Bigr\rbrace$$
Для простоты переобозначим $a \in A_i$ как $A_i$, а $a \in B_i$ как $B_i$. Тогда:
$$\bigwedge\limits_{i=1}^n A_i\oplus\bigwedge\limits_{i=1}^n B_i \rightarrow \bigvee\limits_{i=1}^n{(A_i \oplus B_i)} \eqno(3)$$
Докажем, что формула общезначима по индукции.
База: очевидно $$A_1\oplus B_1 \rightarrow A_1\oplus B_1$$
Шаг индукции:
Предположим, что $(3)$ верно. Докажем общезначимость данного факта:
$$A_{n+1}\wedge\bigwedge\limits_{i=1}^n A_i\oplus B_{n+1}\wedge\bigwedge\limits_{i=1}^n B_i \rightarrow (A_{n+1} \oplus B_{n+1})\vee\bigvee\limits_{i=1}^n{(A_i \oplus B_i)}$$
Или
$$A_{n+1}A_1\ldots A_n\oplus B_{n+1}B_1\ldots B_n \rightarrow (A_{n+1} \oplus B_{n+1})\vee\bigvee\limits_{i=1}^n{(A_i \oplus B_i)} \eqno(4)$$

Перебрав все варианты $(A_{n+1},B_{n+1}) \in \lbrace0,1\rbrace \times \lbrace0,1\rbrace$ можно непосредственно удостоверится в этом.

$\hline$

Если бы я пользовался соответствующим свойством (3-ее с низу) симметрической разности, то доказательство было бы гораздо проще, но проблема была в том, что надо либо привести доказательство этого свойства, либо доказывать без него (непосредственно).

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

 
 
 
 Re: Проверьте доказательство включения множеств, пожалуйста.
Сообщение11.02.2013, 19:50 
musius в сообщении #682549 писал(а):
Если бы я пользовался соответствующим свойством симметрической разности, то доказательство было бы гораздо проще, но проблема была в том, что надо либо привести доказательство этого свойства, либо доказывать без него (непосредственно).
Если проще, можно и привести — будет лемма.

 
 
 
 Re: Проверьте доказательство включения множеств, пожалуйста.
Сообщение11.02.2013, 20:01 
arseniiv в сообщении #682578 писал(а):
musius в сообщении #682549 писал(а):
Если бы я пользовался соответствующим свойством симметрической разности, то доказательство было бы гораздо проще, но проблема была в том, что надо либо привести доказательство этого свойства, либо доказывать без него (непосредственно).
Если проще, можно и привести — будет лемма.


В этом мой вопрос и заключался!

 
 
 
 Re: Проверьте доказательство включения множеств, пожалуйста.
Сообщение11.02.2013, 20:16 
А. Мне показалось, что вы уже решили, что если бы доказали это свойство и использовали, то было бы проще. Лично я могу посоветовать разве что попробовать и этим способом и сравнить результаты, но это плохой совет.

 
 
 
 Re: Проверьте доказательство включения множеств, пожалуйста.
Сообщение16.02.2013, 08:59 
Знаю, что по правилам апать темы нельзя, но пожалуйста, прошу вас, ответьте на вопрос: можно было доказать более простым способом? Разве сведение задачи из т. множеств к мат.логике — это верный путь?

 
 
 
 Re: Проверьте доказательство включения множеств, пожалуйста.
Сообщение16.02.2013, 12:04 
Аватара пользователя
musius в сообщении #684538 писал(а):
Разве сведение задачи из т. множеств к мат.логике — это верный путь?

Ничего никуда не сводится. Вы пользовались определением перечения, объединения и т.д.. Без этого уж никак.

 
 
 
 Re: Проверьте доказательство включения множеств, пожалуйста.
Сообщение16.02.2013, 12:10 
musius в сообщении #682549 писал(а):
Докажите, что $(A_1 \cap \ldots \cap A_n) \vartriangle (B_1 \cap \ldots \cap B_n) \subset (A_1 \vartriangle B_1) \cup \ldots \cup (A_n \vartriangle B_n)$ для любых множеств $A_1, \ldots ,A_n$ и $B_1, \ldots ,B_n$.
(Обозначение $\vartriangle $ — симметрическая разность)
А разве это не очевидно? Пусть $x$ принадлежит левому множеству. В силу симметрии можно считать, что $x \in A_1 \cap \ldots \cap A_n$ (т.е. $x$ принадлежит всем $A_i$) и $x \not\in B_1 \cap \ldots \cap B_n$ (т.е. $x$ не принадлежит какому-то $B_{i_0}$). Но тогда $x \in A_{i_0} \setminus B_{i_0}$ и всё. Зачем эта груда формул да ещё и рассуждение по индукции, когда утверждение непосредственно следует из определений?

 
 
 
 Re: Проверьте доказательство включения множеств, пожалуйста.
Сообщение16.02.2013, 12:14 
Аватара пользователя
nnosipov в сообщении #684573 писал(а):
Зачем эта груда формул да ещё и рассуждение по индукции, когда утверждение непосредственно следует из определений?

Я думаю, что ТС просто все очень подробно написал. Для произвольного $n$, формально, все равно нужна индукция.

 
 
 
 Re: Проверьте доказательство включения множеств, пожалуйста.
Сообщение16.02.2013, 12:18 
Ну, разве что потренироваться в формализме ...

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group