Проверка соотношения подмножеств

[arseniiv]

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

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

Не совсем понял, кого/что и как стеснить.

Допустим доказана формула:
$\forall x[(x\in C\to x\in A)\wedge(x\in C\to x\in B)\leftrightarrow(x\in C\to x\in A\wedge x\in B)]$
Чтобы использовать её в цепочке, мне нужна равносильная формула с распределённым квантором:
$\forall x[(x\in C\to x\in A)\wedge(x\in C\to x\in B)]\leftrightarrow\forall x(x\in C\to x\in A\wedge x\in B)$
Но они не равносильны ( $2\nvdash 1$ ).

Да. Только ведь $1\vDash 2$, и, коль уж мы показали $\vDash \forall A\forall B\forall C.1$, получим $\vDash \forall A\forall B\forall C.2$.

[timber]

kernel1983 в сообщении #1120069 писал(а):

Вспомните определение включения, тот факт, что квантор общности проносится через конъюнкцию, а также определение пересечения. И доказательство получится как цепочка равносильностей.

provincialka в сообщении #1120090 писал(а):

Пусть выполняется $(C\subset A)\wedge(C\subset B)$. Что означает эта запись? На самом деле, вам нужны только $x\in C$. Что ещё можно сказать про каждый такой $x$?
Можно считать, что множества $A$ и $B$ заданы, и мы что-то утверждаем про множество $C$. Поэтому достаточно проверить элементы этого самого $C$.

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

Любую задачу стоит начинать решать в лоб. И если уж не выходит — только тогда усложнять себе жизнь и (в данном случае) рассматривать какие-то там альтернативы. Как предлагает kernel1983, тут легко провести цепь эквивалентностей от левого утверждения к правому.

kernel1983 в сообщении #1120284 писал(а):

В Вашем случае нужно доказать равносильность замкнутых формул логики предикатов $\forall x (C(x) \to A(x)) \wedge \forall x (C(x) \to B(x))$ и $\forall x (C(x) \to (A(x) \wedge B(x)))$ (точнее высказываний, являющихся интерпретациями этих формул, если понимать $A(x), B(x),C(x)$ как $x \in A, x \in B, x \in C$ соответственно).

Otta в сообщении #1120354 писал(а):

Короче, Вам нужно доказать, что из левой части исходного утверждения следует (или равносильна) правая. Правую я вижу. Что Вы сделали с левой, зачем Вы ее привели в такой бессмысленный вид?

Это понятно, что нужно построить такую цепочку равносильностей, чтобы из левой части получалась правая.
Постараюсь выразить словами. Затрудняюсь как это точно записать символами.

В левой части нам заданы соотношения между множествами $A, B, C$. В общем сказано, что ($C$ является собственным подмножеством $A$) И ($C$ является собственным подмножеством $B$). То есть сказано, что (все элементы множества $C$ включены в $A$) И (все те же элементы множества $C$ включены и в $B$).

Вопрос: когда такое возможно?
Ответ (который приводится в правой части): такое возможно тогда и только тогда (то есть только в том единственном случае и ни в каком больше), когда все элементы множества $C$ включены в множество образованное пересечением $A, B$ (все элементы множества $C$ одновременно являются и элементами множества $A \cap B$).

Что нужно, чтобы проверить/доказать истинность такого ответа/утверждения?
Один из вариантов -- это построить цепочку равносильных высказываний слева-направо. Постараюсь это сделать словами, как понимаю.
Из левой части мы знаем, что любой элемент $x$ подмножества $C$ является одновременно элементом $A$ и элементом $B$. Это же не нужно доказывать, это нам дано. Запишем эту конъюнкцию так: $(\forall x)((x\in A) \wedge (x\in B))$. В Зориче написано, что это выражение и есть определение пересечения множеств $A \cap B$. Это тоже доказательств не требует (или требует?). Ну тогда, вроде и так все очевидно -- если все элементы $C$ определенным в левой части образом включены в $A, B$, то и все они же включены в $A \cap B$. Вот вроде и все. Или что-то не понимаю "садись, двойка" :)?

-- 03.05.2016, 17:19 --

Кажется осознал, чего не понимаю в случае построения цепочки равносильности.
Мне не понятно как действовать и преобразовывать выражения, когда у нас указывается в формуле/выражении отношение между множествами (как здесь -- отношение включения, его же за скобку выражения просто так не вынесешь?). Хотя в данном примере я так и сделал, сначала вынес из левой части отношение включения (сам символ $\subset$), а потом его включил/добавил в правую часть.
На что его нужно менять не ясно, это же не логическая и не множественная операция, которые можно преобразовывать из одного в другое, исходя из свойств (ассоциативность, коммутативность, дистрибутивность и т.д.) и определений.

[gefest_md]

timber в сообщении #1120476 писал(а):

То есть сказано, что (все элементы множества $C$ включены в $A$) И (все те же элементы множества $C$ включены и в $B$).
...
Из левой части мы знаем, что любой элемент $x$ подмножества $C$ является одновременно элементом $A$ и элементом $B$. Это же не нужно доказывать, это нам дано.

Вы не задались вопросами относительно того, что дано: (одна буква называет одно множество) могут $A$ и $B$ не пересекаться? Если нет, тогда может ли $C$ лежать вне пересечения множеств $A$ и $B$. Если нет, тогда $C\subset A\cap B.$

[timber]

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

timber в сообщении #1120476 писал(а):

То есть сказано, что (все элементы множества $C$ включены в $A$) И (все те же элементы множества $C$ включены и в $B$).
...
Из левой части мы знаем, что любой элемент $x$ подмножества $C$ является одновременно элементом $A$ и элементом $B$. Это же не нужно доказывать, это нам дано.

Вы не задались вопросами относительно того, что дано: (одна буква называет одно множество) могут $A$ и $B$ не пересекаться? Если нет, тогда может ли $C$ лежать вне пересечения множеств $A$ и $B$. Если нет, тогда $C\subset A\cap B.$

Не совсем понял Вас в этой части вопроса: "(одна буква называет одно множество) могут ...".
Но если бы $A$ и $B$ не пересекались (вернее сказать, наверное, так -- если бы $C$ выходило за область пересечения множеств $A, B$), то не имела бы смысла левая часть, то есть не выполнялось бы условие, что все элементы $C$ одновременно принадлежали и $A$ и $B$.

[Someone]

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

могут $A$ и $B$ не пересекаться?

А разве это условием запрещено?

[gefest_md]

timber в сообщении #1120514 писал(а):

Но если бы $A$ и $B$ не пересекались ..., то не имела бы смысла левая часть, то есть не выполнялось бы условие, что все элементы $C$ одновременно принадлежали и $A$ и $B$.

Значит если $A$ и $B$ не пересекаются (и если

Someone в сообщении #1120530 писал(а):

А разве это условием запрещено?

ещё $C$ не пусто), тогда получаем противоречие с условием. Значит $A$ и $B$ всё же пересекаются! (если $C$ не пусто). Тогда может ли (не пустое) $C$ лежать целиком (не отвлекаемся от условия) либо только в $A$, либо только в $B$, т.е. не лежать в пересечении?

[ewert]

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

(если $C$ не пусто)

А если пусто?

Не могу понять, как можно переливать из пустого в порожнее на протяжении четырёх страниц. Когда в самом что ни на есть третьем посте ветки была дана исчерпывающая рекомендация:

kernel1983 в сообщении #1120069 писал(а):

Вспомните определение включения, тот факт, что квантор общности проносится через конъюнкцию, а также определение пересечения. И доказательство получится как цепочка равносильностей.

[timber]

ewert в сообщении #1120548 писал(а):

Не могу понять, как можно переливать из пустого в порожнее на протяжении четырёх страниц. Когда в самом что ни на есть третьем посте ветки была дана исчерпывающая рекомендация:

kernel1983 в сообщении #1120069 писал(а):

Вспомните определение включения, тот факт, что квантор общности проносится через конъюнкцию, а также определение пересечения. И доказательство получится как цепочка равносильностей.

Ну и мне, если честно, тоже уже весьма надоело обсуждение этой темы. Такими темпами далеко не уедешь. Как-то уже все это напрягает.
Мне действительно от этих рекомендаций не стало очевидно как правильно построить и записать(!) цепочку равносильностей.
Разобраться до конца, чтобы стало все максимально ясно, очень же хочется. Мне больше и не к кому обратиться.
Единственный выход -- писать на форум (где могут быть релевантные ответы) до бесконечности, пока предельно точно не пойму, что к чему и почему :). Ну а как еще учиться самостоятельно.

Итак, с вашего позволения, уважаемые знатоки форума, попробую еще раз написать цепочку, следуя совету "вспомните определение включения, тот факт, что квантор общности проносится через конъюнкцию, а также определение пересечения" (хотя мне не до конца понятно, что означает "факт, что квантор общности проносится через конъюнкцию" -- как это отражается в записи -- добавлением значков $\forall x$ в каждом выражении или как?):

$\begin{array}{l} (C \subset A) \wedge (C \subset B) \,\Leftrightarrow\, \\ \,\Leftrightarrow\, ((x \in C) \Rightarrow (x \in A)) \wedge ((x \in C) \Rightarrow (x \in B)) \,\Leftrightarrow\, \\ \,\Leftrightarrow\, (x \in C) \Rightarrow ((x \in A) \wedge (x \in B)) \,\Leftrightarrow\, \\ \,\Leftrightarrow\, C \subset (A \cap B) \end{array}$

или так:

$\begin{array}{l} (\forall x) ((C \subset A) \wedge (C \subset B)) \,\Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x)((x \in C) \Rightarrow (x \in A)) \wedge (\forall x)((x \in C) \Rightarrow (x \in B)) \,\Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x)(x \in C) \Rightarrow ((\forall x)(x \in A) \wedge (\forall x)(x \in B)) \,\Leftrightarrow\, \\ \,\Leftrightarrow\, (\forall x)(C \subset (A \cap B)) \end{array}$

Что здесь не так?

[kernel1983]

timber в сообщении #1120612 писал(а):

хотя мне не до конца понятно, что означает "факт, что квантор общности проносится через конъюнкцию

$\forall x P(x) \wedge \forall x Q(x) \Leftrightarrow \forall x (P(x) \wedge Q(x))$

А через дизъюнкцию не проносится, поэтому, например, не верно следующее высказывание: $C \subset A \vee C \subset B \Leftrightarrow C \subset (A \cup B)$, но верно высказывание $C \subset A \vee C \subset B \Rightarrow C \subset (A \cup B)$.

P. S. Есть хорошая книжка по математической логике: Игошин, Математическая логика и теория алгоритмов. Лучше с неё начать (главы I и IV и параграф 8 главы II; остальное лучше оставить на потом).

-- 03.05.2016, 22:38 --

$C \subset A \wedge C \subset B \stackrel{\textrm{def}}{\Leftrightarrow} (\forall x) (x \in C \to x \in A) \wedge (\forall x)(x \in C \to x \in B) \Leftrightarrow (\forall x)(\overline{x \in C} \vee (x \in A \wedge x \in B)) \Leftrightarrow (\forall x)(x \in C \to (x \in A \wedge x \in B)) \stackrel{\textrm{def}}{\Leftrightarrow} C \subset (A \cap B) $

[timber]

kernel1983 в сообщении #1120630 писал(а):

timber в сообщении #1120612 писал(а):

хотя мне не до конца понятно, что означает "факт, что квантор общности проносится через конъюнкцию

$\forall x P(x) \wedge \forall x Q(x) \Leftrightarrow \forall x (P(x) \wedge Q(x))$

А через дизъюнкцию не проносится, поэтому, например, не верно следующее высказывание: $C \subset A \vee C \subset B \Leftrightarrow C \subset (A \cup B)$, но верно высказывание $C \subset A \vee C \subset B \Rightarrow C \subset (A \cup B)$.

А вот что! Спасибо!
Наверное Вы хотели записать: верно высказывание $C \subset A \wedge C \subset B \Rightarrow C \subset (A \cap B)$?

[gefest_md]

ewert в сообщении #1120548 писал(а):

А если пусто?

timber в сообщении #1120476 писал(а):

$C$ является собственным подмножеством $A$

[kernel1983]

timber в сообщении #1120642 писал(а):

Наверное Вы хотели записать: верно высказывание $C \subset A \wedge C \subset B \Rightarrow C \subset (A \cup B)$.

Нет, у меня дизъюнкция в посылке. То, что Вы написали, тоже верно.

[timber]

Что то глючит. Я там значки меняю, а Вы цитируете устаревшую версию.
У меня написано: верно высказывание $C \subset A \wedge C \subset B \Rightarrow C \subset (A \cap B)$ :).

[kernel1983]

timber в сообщении #1120653 писал(а):

У меня написано: верно высказывание $C \subset A \wedge C \subset B \Rightarrow C \subset (A \cap B)$.

Верно, конечно.

И то, что я процитировал тоже верно, поскольку формула $\forall x P(x) \wedge \forall x Q(x) \to \forall x (P(x) \vee Q(x))$ является общезначимой.

[ewert]

(Оффтоп)

timber в сообщении #1120642 писал(а):

$C \subset A \wedge C \subset B \Rightarrow C \subset (A \cap B)$

Что занятно: в правой части скобки точно не нужны, а вот в левой -- как раз желательны (хоть и необязательны).