2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Доказательство транзитивности строгого включения
Сообщение22.09.2017, 10:50 
Аватара пользователя


26/08/16
91
Москва
Здравствуйте!

Имеется следующая задача:

Цитата:
Доказать, что для произвольных множеств $A,B,C$ выполняется следующее утверждение: $$ (A\subseteq B) \wedge (B\subset C) \Rightarrow A\subset C $$


Понимаю, что это тривиальная задача. Тем не менее, прошу проверить правильность моего доказательства.

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

Докажем, что любой элемент из $A$ принадлежит $C$. Рассмотрим любой элемент $a\in A$. По условию $A\subseteq B$, а значит $a\in B$. По условию $B\subset C$, а значит $a\in C$. Доказали.

Из определения строгого включения сразу следует, что если $B\subset C$, значит $B\neq C$. Это означает, что существует некоторый элемент $c'\in C$, такой, что $c'\notin B$.

Пусть $A=C$. Это означает, что любой элемент $C$ принадлежит $A$, в том числе и элемент $c'$:

$$ c'\in A $$

По условию $A\subseteq B$, а значит $c'\in B$. Получаем, что $c'\in B$ и одновременно $c'\notin B$. Противоречие, а значит утверждение, что $A=C$ ложное. А значит $A\neq C$.

Получаем, что любой элемент из $A$ принадлежит $C$ и $A\neq C$. По определению строгого включения это означает, что $A\subset C \ \blacksquare$

---

Так как я еще не проходил логику и исчисление высказываний, я не до конца уверен в правильности своих рассуждений. В особенности, меня смущает мое решение принять $A=C$. Можно ли так поступать? И действительно ли получается, что из получившегося противоречия следует, что $A\neq C$, а не какой-нибудь другой вывод?

 Профиль  
                  
 
 Re: Доказательство транзитивности строгого включения
Сообщение22.09.2017, 10:55 
Заслуженный участник
Аватара пользователя


26/01/14
4935
Всё верно, обычное доказательство от противного.
Предположили, что $A=C$, пришли к противоречию, значит $A\neq C$.

 Профиль  
                  
 
 Re: Доказательство транзитивности строгого включения
Сообщение22.09.2017, 12:38 
Аватара пользователя


01/12/06
760
рм
CMTV в сообщении #1249683 писал(а):
И действительно ли получается, что из получившегося противоречия следует, что $A\neq C$, а не какой-нибудь другой вывод?
Если из допущений $A\subseteq B$, $B\subset C$ и $A=C$ Вы вывели противоречие, тогда отрицание любого из этих трех допущений выводится из двух остальных. Например, из $B\subset C$ и $A=C$ следует $A\nsubseteq B.$

 Профиль  
                  
 
 Re: Доказательство транзитивности строгого включения
Сообщение22.09.2017, 12:50 
Аватара пользователя


26/08/16
91
Москва
gefest_md в сообщении #1249709 писал(а):
Например, из $B\subset C$ и $A=C$ следует $A\nsubseteq B.$

Правильно ли я понимаю, что если бы $A\subseteq B$ и $B\subset C$ являлись введенными мною допущениями (наподобие $A=C$), а не условиями доказываемого утверждения, то получившееся противоречие означало бы, что мне пришлось бы проверить все возможные комбинации введенных допущений?

Но так как я ввел всего одно допущение, то полученное противоречие говорит именно о его ложности.

Надеюсь, я правильно понял вашу мысль...

 Профиль  
                  
 
 Re: Доказательство транзитивности строгого включения
Сообщение22.09.2017, 14:16 
Аватара пользователя


01/12/06
760
рм
Полезно знать несколько тавтологий. Доказываемое предложение имеет вид $X\to Y\wedge Z$. Оно равносильно $(X\to Y)\wedge(X\to Z)$.
$A\subseteq B$ и $B\subset C$ такие же допущения. Они вводятся на первом этапе. (Это $X$). На следующем этапе надо доказать $A\ne C$. (Это $Z$). $A\ne C$ равносильно $A=C\Rightarrow A\ne C$. Поэтому сейчас делаем допущение $A=C$ и пытаемся доказать новое заключение $A\ne C$. Первые два допущения сохраняются. Из трех допущений выводится противоречие. Из противоречия следует все, что угодно. Следовательно $A\ne C$. (здесь использовал тавтологии $(X\to\neg X)\leftrightarrow\neg X$ и $X\wedge\neg X\to Y$ и транзитивность).

Это рассуждение показывает также, что для некоторого предложения $X$
$A\subseteq B,\,B\subset C,\,A= C\vdash X$
$A\subseteq B,\,B\subset C,\,A= C\vdash \neg X$.
Поэтому можно утверждать, что $A\subseteq B,\,B\subset C\vdash A\ne C$. Чтобы это получить нужна теорема дедукции и тавтология $(Y\to X)\wedge(Y\to\neg X)\to\neg Y$; ( $\vdash$ - знак выводимости; здесь неформальной).

 Профиль  
                  
 
 Re: Доказательство транзитивности строгого включения
Сообщение23.09.2017, 15:23 


10/11/15
142
CMTV в сообщении #1249683 писал(а):
Рассмотрим любой элемент $a\in A$. По условию $A\subseteq B$, а значит $a\in B$. По условию $B\subset C$, а значит $a\in C$. Доказали.


Ясно, что $A\subseteq B$ тогда и только тогда, когда $a \in A \to a \in B$, $B\subset C$ тогда и только тогда, когда $a \in B \to a \in C$, где $a$ - произвольный элемент. Но как отсюда следует $a \in C$? В силу закона цепного заключения: $P \to Q, Q \to R \models P \to R$?

 Профиль  
                  
 
 Re: Доказательство транзитивности строгого включения
Сообщение23.09.2017, 15:55 
Заслуженный участник


27/04/09
28128
kernel1983 в сообщении #1250028 писал(а):
Ясно, что $A\subseteq B$ тогда и только тогда, когда $a \in A \to a \in B$, $B\subset C$ тогда и только тогда, когда $a \in B \to a \in C$
Не в обоих случаях тогда и только тогда.

kernel1983 в сообщении #1250028 писал(а):
В силу закона цепного заключения: $P \to Q, Q \to R \models P \to R$?
Хоть бы и его, да.

 Профиль  
                  
 
 Re: Доказательство транзитивности строгого включения
Сообщение23.09.2017, 15:56 


10/11/15
142
arseniiv в сообщении #1250034 писал(а):
Не в обоих случаях тогда и только тогда.


Почему?

-- 23.09.2017, 16:02 --

А... Потому что $A \subset B \stackrel{def}{\Leftrightarrow} A \subseteq B \wedge A \not = B$?

 Профиль  
                  
 
 Re: Доказательство транзитивности строгого включения
Сообщение23.09.2017, 16:12 
Заслуженный участник


27/04/09
28128
Угу.

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

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



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

Сейчас этот форум просматривают: Alex Krylov, YandexBot [bot]


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

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