Использование непустоты множеств при доказательстве

[Zhilbyldyr]

Хочу доказать, что для любых множеств X и Y верно \cup X \subseteq Y \Rightarrow X \subseteq P(Y).
Рассмотрим произвольный элемент x множества X и его произвольный элемент y
y \in x \in X \Rightarrow y \in \cup X \Rightarrow y \in Y \Rightarrow x \subseteq Y \Rightarrow x \in P(Y)
Правильно ли я понимаю, что в самом начале я воспользовался тем, что X и x непустые? Так как для того, чтобы y \in \cup X, по определению необходимо и достаточно существования x \in X такого, что y \in x. Таким образом, мне ещё нужно отдельно рассмотреть другие случаи. Если X пустое, то очевидно, что X \subseteq P(Y). Если X непустое и x пустое, то x \subseteq Y \Rightarrow x \in P(Y). Случаев, когда когда X пустое, а Y непустое и наоборот не бывает в силу \cup X \subseteq Y И теперь всё доказано. К тому же я попутно доказал, что любой элемент непустого множества X является подмножеством множества \cup X, верно? Меня волнует, не запутался ли я где, все ли случаи рассмотрел и как лучше здесь перебирать случаи с пустыми множествами. Может я рассмотрел лишние случаи?

[Babken]

Решили вы все правильно, но рассуждения после решения не совсем верные, потому что вы не пользовались тем, что $X$ и $x$ непустые. Дело в том, что ваше доказательство верно независимо от того, пустые множества или нет, и следует это из законов логики, таблицы истинности операции "следствие" (или "импликация"). Например, давайте рассмотрим случай, когда $x$ - пустое множество. Вы хотите сказать, что $y \in x$ в таком случае ложно. С этим я спорить не буду, но если мы с вами посмотрим на вашу цепочку рассуждений, то увидим, что это никак не влияет на истинность вашего вывода, потому что по законам логики изо лжи следует все, что угодно. По таблице истинности, если посылка ложна ($y \in x \in X$), то заключение ($y \in \cup{X}$) может быть, как ложным, так и истинным, поэтому в этом случае дело ни в том, что вы воспользовались тем, что эти множества не пустые, здесь просто нецелесообразно рассматривать пустые множества, потому что из ложных высказываний может следовать все, что угодно.

[svv]

А что буква $P$ обозначает?

[arseniiv]

Zhilbyldyr в сообщении #1516888 писал(а):

Правильно ли я понимаю, что в самом начале я воспользовался тем, что X и x непустые?

Не обязательно, если аккуратно оформить доказательство. Раскроем сначала левую часть доказываемой импликации: $\cup X \subset Y$ означает $\forall y. \; (\exists x. \; x \in X. \wedge y \in x) \to y \in Y$. Раскроем правое: $\forall x. x \in X \to \forall y. \; y \in x \to y \in Y$. Теперь соберём некоторые знания о выводимости в логике первого порядка вместе:

• чтобы доказать $\forall x. A[x]$, достаточно взять произвольный «свежий» объект $v$ и показать $A[v]$, после чего мы можем выкинуть $v$ из рассмотрения везде, где используется $\forall x. A[x]$;
• из $\forall x. A[x]$ мы получаем $A[t]$ для любого выражения $t$, включая свежевведённые переменные как выше;
• чтобы доказать $\exists x. A[x]$, достаточно доказать $A[t]$ для произвольного выражения $t$;
• если $\exists x. A[x]$, то мы можем доказать оттуда некоторое $B$, если можем доказать $B$ из $A[c]$ для некоторой свежей (не входит в $B$) «переменной-константы» $c$.

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

Теперь следите за руками.
У нас есть $\forall y. \; (\exists x. \; x \in X. \wedge y \in x) \to y \in Y$ и мы собираемся показать $\forall x. x \in X \to \forall y. \; y \in x \to y \in Y$.
Введём свежий $x'$, для него нам надо показать $x' \in X \to \forall y. \; y \in x' \to y \in Y$.
Значит мы можем принять $x' \in X$, а показать надо будет $\forall y. \; y \in x' \to y \in Y$.
Введём свежий $y'$, для которого надо показать $y' \in x' \to y' \in Y$.
Мы можем принять $y' \in x'$, осталось показать $y' \in Y$…

И вот теперь мы начнём вгрызаться в первую, изначальную, посылку!
У нас есть $\forall y. A[y]$, значит мы можем сказать в частности $A[y']$, то есть $(\exists x. \; x \in X. \wedge y' \in x) \to y' \in Y$.
Если теперь мы покажем, что $\exists x. \; x \in X. \wedge y' \in x$, то мы можем получить $y' \in Y$ (и нам повезло, это как раз сразу наша цель).
У нас активно предположение, что $x' \in X$, и также что $y' \in x'$. Это ровно такое $B[x']$, что требуется, чтобы доказать $\exists x. \; B[x]$!
Значит, $y' \in Y$, и значит, мы доказали всё, что хотели.

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

-- Ср май 05, 2021 17:28:52 --

svv в сообщении #1516963 писал(а):

А что буква $P$ обозначает?

Скорее всего множество всех подмножеств.

-- Ср май 05, 2021 17:54:13 --

Кстати отсюда видно, что мы доказывали очень естественный факт (плюс там ведь ещё и в обратную сторону следует): в доказательстве мы просто распаковывали и запаковывали и перекладывали без взывания к каким-то аксиомам теории множеств кроме тех, что нужны для выписывания смысла $\cup X \subset Y$ и $X \subset P(Y)$ в самом начале.

[Zhilbyldyr]

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

некоторые знания о выводимости в логике первого порядка вместе

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

[arseniiv]

Не знаю книг, которые бы не ударялись совсем в формализм, притом с учётом, что уже заранее известен смысл кванторов, к сожалению. У меня плохо с библиографией, увы, так что есть надежда, что где-то рассказывается.

-- Пн май 10, 2021 18:29:26 --

Но как отправная точка может сгодиться и https://en.wikipedia.org/wiki/Natural_deduction, вероятно.

[Zhilbyldyr]

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

Но как отправная точка может сгодиться и https://en.wikipedia.org/wiki/Natural_deduction
, вероятно.

Спасибо.