Мат. логика. Формальное доказательство

[Evgeni2011]

Здравствуйте. Подскажите пожалуйста, кто знает, как формально можно доказать истинность предложения: ''для любых множеств $ A $ и $ B $ $ A\cap B\subset A $''. Интересует в каком исчислении это надо делать и как. Сам я попробовал свести все к исчислению высказываний и получилось вот что (истинные предложения занумерованы):

1. $ x\in A\cap B \Longleftrightarrow $($x\in A $ и $ x\in B $).
2. $ A\subset B \Longleftrightarrow (x\in A \Longrightarrow x\in B) $.

из 1 следует 3 (это получается по следующему формальному правилу: если нарисовать таблицу истинности на входе которой стоят высказывания $ x\in A\cap B $, $ x\in A $ и $ x\in B $ то во всех строчках в которых предложение 1 имеет значение ''истина'' предложение 3 тоже имеет значение ''истина'', иными словами предложение 1 $ \Longrightarrow $ 3 - тавтология)

3. $ x\in A\cap B \Longrightarrow x\in A $.

из 2 следует 4 (подстановка в предложение 2 $ A\cap B $ вместо $ A $ и $ A $ вместо $ B $ )

4. $ A\cap B\subset A \Longleftrightarrow (x\in A\cap B \Longrightarrow x\in A) $.

из 3 и 4 следует 5 (так как предложение (3 и 4) $ \Longrightarrow $ 5 - тавтология)

5. $ A\cap B\subset A $.

Если кто знает как это можно сделать правильнее напишите пожалуйста.

[Kallikanzarid]

ИМХО доказывать нужно в логике первого порядка, т.к. именно в ней сформулирована ZF :)

-- Сб окт 22, 2011 09:37:15 --

Докажите более общее утверждение: $\forall A \forall B \forall C (A \subset B \implies A \cap C \subset B \cap C)$. Распишите его подробней: $\forall A \forall B \forall C [(\forall x (x \in A \implies x \in B)) \implies (\forall x (x \in A \wedge x \in C \implies x \in B \wedge x \in C))]$, ну и дальше, пока не получите истину.

[Evgeni2011]

Kallikanzarid в сообщении #494983 писал(а):

Докажите более общее утверждение: $\forall A \forall B \forall C (A \subset B \implies A \cap C \subset B \cap C)$.

Не понял, как это сделать?

Kallikanzarid в сообщении #494983 писал(а):

ну и дальше, пока не получите истину.

Какими правилами здесь нужно пользоваться?

[Joker_vD]

$A\cap B\subset A$ означает, что предикат $F(x)=(P_A(x)\wedge P_B(x) \implies P_A(x))$ — тождественно истинный. А это, извините, банальность.

[FFMiKN]

А на кругах Эйлера проще всего это проглядывается... И наглядно и точно.

[Kallikanzarid]

Evgeni2011 в сообщении #494989 писал(а):

Какими правилами здесь нужно пользоваться?

Аксиомами логики первого порядка.

[molokowoz]

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

[Joker_vD]

FFMiKN
Ну вы еще квадраты Кэрролла вспомните

[Evgeni2011]

Joker_vD в сообщении #494994 писал(а):

$A\cap B\subset A$ означает, что предикат $F(x)=(P_A(x)\wedge P_B(x) \implies P_A(x))$ — тождественно истинный.

Откуда это следует? Я подозреваю, что Вы пользуетесь здесь предложением $ A\cap B\subset A\Longleftrightarrow \forall x((x\in A \wedge x\in B)\Longrightarrow x\in A)$. Но пардон, кто сказал что оно истина. Понимаете, интересует именно формальное доказательство, когда под доказательством понимается цепь истинных предложений в которой последенее есть доказываемое предложение и истинность каждого из них либо оговорена заранее либо следует из истинности других предложений по определенным правилам (посмотрите как это сделано у меня).

[Evgeni2011]

Kallikanzarid в сообщении #495031 писал(а):

Evgeni2011 в сообщении #494989 писал(а):

Какими правилами здесь нужно пользоваться?

Аксиомами логики первого порядка.

Что за аксиомы? Можно поподробнее?

Kallikanzarid в сообщении #494983 писал(а):

Докажите более общее утверждение: $\forall A \forall B \forall C (A \subset B \implies A \cap C \subset B \cap C)$.

Как это сделать (в логике первого порядка)?

Kallikanzarid в сообщении #494983 писал(а):

Распишите его подробней: $\forall A \forall B \forall C [(\forall x (x \in A \implies x \in B)) \implies (\forall x (x \in A \wedge x \in C \implies x \in B \wedge x \in C))]$, ну и дальше, пока не получите истину.

Что должно получится в итоге?

[xmaister]

(Оффтоп)

Посмотрите Куратовского и Мостовского "Теория множеств", там про Вашу проблему довольно подробно написано

[Joker_vD]

Evgeni2011
Ну как откуда? Каждому множеству $A$ соответствует предикат $P_A(x)$, который истинен тогда и только тогда, когда $x\in X$.

Пересечением множеств $A$ и $B$ называется множество, предикат которого $P_{A\cap B}(x)\equiv P_A(x)\cap P_B(x)$. Множество $A$ называется подмножеством $B$, если предикат $P_A(x)\implies P(B)$ — тождественно истинный.