2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



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


11/02/13
7
Задача из учебника Н.К. Верещагин, А. Шень (ч. 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 
Заслуженный участник


27/04/09
28128
musius в сообщении #682549 писал(а):
Если бы я пользовался соответствующим свойством симметрической разности, то доказательство было бы гораздо проще, но проблема была в том, что надо либо привести доказательство этого свойства, либо доказывать без него (непосредственно).
Если проще, можно и привести — будет лемма.

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


11/02/13
7
arseniiv в сообщении #682578 писал(а):
musius в сообщении #682549 писал(а):
Если бы я пользовался соответствующим свойством симметрической разности, то доказательство было бы гораздо проще, но проблема была в том, что надо либо привести доказательство этого свойства, либо доказывать без него (непосредственно).
Если проще, можно и привести — будет лемма.


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

 Профиль  
                  
 
 Re: Проверьте доказательство включения множеств, пожалуйста.
Сообщение11.02.2013, 20:16 
Заслуженный участник


27/04/09
28128
А. Мне показалось, что вы уже решили, что если бы доказали это свойство и использовали, то было бы проще. Лично я могу посоветовать разве что попробовать и этим способом и сравнить результаты, но это плохой совет.

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


11/02/13
7
Знаю, что по правилам апать темы нельзя, но пожалуйста, прошу вас, ответьте на вопрос: можно было доказать более простым способом? Разве сведение задачи из т. множеств к мат.логике — это верный путь?

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


03/08/11
1613
Новосибирск
musius в сообщении #684538 писал(а):
Разве сведение задачи из т. множеств к мат.логике — это верный путь?

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

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


20/12/10
9110
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 
Заслуженный участник
Аватара пользователя


03/08/11
1613
Новосибирск
nnosipov в сообщении #684573 писал(а):
Зачем эта груда формул да ещё и рассуждение по индукции, когда утверждение непосредственно следует из определений?

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

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


20/12/10
9110
Ну, разве что потренироваться в формализме ...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group