Доказательство транзитивности строгого включения

[CMTV]

Здравствуйте!

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

Цитата:

Доказать, что для произвольных множеств $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$, а не какой-нибудь другой вывод?

[Mikhail_K]

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

[gefest_md]

CMTV в сообщении #1249683 писал(а):

И действительно ли получается, что из получившегося противоречия следует, что $A\neq C$, а не какой-нибудь другой вывод?

Если из допущений $A\subseteq B$, $B\subset C$ и $A=C$ Вы вывели противоречие, тогда отрицание любого из этих трех допущений выводится из двух остальных. Например, из $B\subset C$ и $A=C$ следует $A\nsubseteq B.$

[CMTV]

gefest_md в сообщении #1249709 писал(а):

Например, из $B\subset C$ и $A=C$ следует $A\nsubseteq B.$

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

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

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

[gefest_md]

Полезно знать несколько тавтологий. Доказываемое предложение имеет вид $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$ - знак выводимости; здесь неформальной).

[kernel1983]

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$?

[arseniiv]

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$?

Хоть бы и его, да.

[kernel1983]

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

Не в обоих случаях тогда и только тогда.

Почему?

-- 23.09.2017, 16:02 --

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

[arseniiv]

Угу.