Давидович: "Отображения множеств"

[Ellan Vannin]

irod в сообщении #1104676 писал(а):

прошу дать подсказку как это лучше доказать

Опустим тот факт, что равенство у вас теоретико-множественное (в данном случае это несущественно). Вам нужно выписать четкие определения, что такое:
*образ множества при отображении
*объединение
и использовать эти определения. Вы вместо доказательств рисуете картинки, и, как можно видеть выше, делаете из-за них много ошибок. Картинки помогают представить задачу наглядно, но они не заменяют строгого доказательства.

[irod]

Ellan Vannin в сообщении #1104745 писал(а):

Вы вместо доказательств рисуете картинки, и, как можно видеть выше, делаете из-за них много ошибок. Картинки помогают представить задачу наглядно, но они не заменяют строгого доказательства.

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

в) $f(A_1 \cup A_2) = f(A_1) \cup f(A_2)$
-- да
Доказательство.
По определению, $A_1 \cup A_2 = \{ a \ | \ a \in A_1 \ \text{или} \ a \in A_2 \}$.
Тогда по определению образа множества

$$ f(A_1 \cup A_2) = \{ f(a) \ | \ a \in A_1 \ \text{или} \ a \in A_2 \} = $$

$$ = \{ f(a) \ | \ a \in A_1 \} \cup \{ f(a) \ | \ a \in A_2 \} = f(A_1) \cup f(A_2). $$

е) $f^{-1}(B_1 \cup B_2) = f^{-1}(B_1) \cup f^{-1}(B_2)$
-- да

Доказательство.
По определению прообраза множества

$$ f^{-1}(B_1 \cup B_2) = f^{-1} ( \{ b \ | \ b \in B_1 \ \text{или} \ b \in B_2 \} ) = $$

$$ = \{ a \ | \ f(a) \in B_1 \ \text{или} \ f(a) \in B_2 \} = \{ a \ | \ f(a) \in B_1 \} \cup \{ a \ | \ f(a) \in B_2 \} = $$

$$ = f^{-1}(B_1) \cup f^{-1}(B_2) $$

А пункт д) у меня правильно?

-- 08.03.2016, 11:28 --

Xaositect в сообщении #1103370 писал(а):

irod в сообщении #1103369 писал(а):

(Вопрос: правильно ли что $f(\varnothing)=\varnothing$ ?)

Да, а почему у Вас возникли сомнения по этому вопросу?

Не могу обьяснить :)

Xaositect в сообщении #1103370 писал(а):

irod в сообщении #1103369 писал(а):

ж) $f^{-1}(B_1 \cap B_2)=f^{-1}(B_1) \cap f^{-1}(B_2)$
-- нет

Неверно.

ж) Ответ - да.
Доказательство.

$$ f^{-1}(B_1 \cap B_2) = f^{-1} ( \{ b \ | \ b \in B_1 \ \text{и} \ b \in B_2 \} ) = $$

$$ = \{ a \ | \ f(a) \in B_1 \ \text{и} \ f(a) \in B_2 \} = $$

$$ = \{ a \ | \ f(a) \in B_1 \} \cap \{ a \ | \ f(a) \in B_2 \} = $$

$$ = f^{-1}(B_1) \cap f^{-1}(B_2) $$

Xaositect в сообщении #1103370 писал(а):

irod в сообщении #1103369 писал(а):

з) $f^{-1}(B_1 \setminus B_2)=f^{-1}(B_1) \setminus f^{-1}(B_2)$
-- нет

Тоже неверно.

з) Ответ - да.
Доказательство.

$$ f^{-1}(B_1 \setminus B_2) = f^{-1} ( \{ b \ | \ b \in B_1 \ \text{и} \ b \not\in B_2 \} ) = $$

$$ = \{ a \ | \ f(a) \in B_1 \ \text{и} \ f(a) \not\in B_2 \} = $$

$$ = \{ a \ | \ f(a) \in B_1 \} \setminus \{ a \ | \ f(a) \in B_2 \} = $$

$$ = f^{-1}(B_1) \setminus f^{-1}(B_2) $$

[Ellan Vannin]

Это было слишком опрометчиво ― предложить не использовать теоретико-множественное равенство. Оказывается определение равенства еще как необходимо для решения ваших задач.

irod в сообщении #1105007 писал(а):

сделать как Вы говорите, с использованием определений.

Я говорю, что
$f(X')=\{y \mid \langle x,y \rangle \in G_f \land x \in X' \}$
$f^{-1}(Y')=\{x \mid \langle x,y \rangle \in G_f \land y \in Y' \}$
где $G_f$ ― график функции, $X'$ и $Y'$ ― соответствующие подмножества. Логическое И обозначим символом $\land$, логическое ИЛИ ― символом $\lor$.

irod в сообщении #1105007 писал(а):

$\{ f(a) \ | \ a \in A_1 \ \text{или} \ a \in A_2 \} = \{ f(a) \ | \ a \in A_1 \} \cup \{ f(a) \ | \ a \in A_2 \}$

Грубо выражаясь, у вас объединение "берется не по $y$, а по $x$". В этом случае так просто выносить за фигурные скобки знак объединения нельзя. Вернее можно, но этот шаг надо обязательно обосновывать. Здесь доказательство примерно такое:
$(y_0 \in f(A_1 \cup A_2))\Leftrightarrow (y_0 \in \{y \mid \langle x,y \rangle \in G_f \land x \in A_1 \cup A_2\}) $ $ \Leftrightarrow (\langle x,y_0 \rangle \in G_f \land x \in A_1 \cup A_2) \Leftrightarrow (\langle x,y_0 \rangle \in G_f \land (x \in A_1 \lor x \in A_2))$ $\Leftrightarrow ((\langle x,y_0 \rangle \in G_f \land x \in A_1) \lor (\langle x,y_0 \rangle \in G_f \land x \in A_2)) $ $\Leftrightarrow ((y_0 \in \{y \mid \langle x,y \rangle \in G_f \land x \in A_1\}) \lor (y_0 \in \{y \mid \langle x,y \rangle \in G_f \land x \in A_2\}))$ $\Leftrightarrow (y_0 \in f(A_1) \lor y_0 \in f(A_2)) \Leftrightarrow (y_0 \in f(A_1) \cup f (A_2))$

irod в сообщении #1105007 писал(а):

А пункт д) у меня правильно?

Правильно. Как я уже говорил, теоретико-множественные операции нельзя свободно переносить с одних множеств на другие. В качестве домашнего упражнения объясните почему $\{y \mid \langle x,y \rangle \in G_f \land x \in A_1 \setminus A_2 \}$ $\neq \{y \mid \langle x,y \rangle \in G_f \land x \in A_1 \} \setminus \{y \mid \langle x,y \rangle \in G_f \land x \in A_2 \}$

irod в сообщении #1105007 писал(а):

е) $\{ a \ | \ f(a) \in B_1 \ \text{или} \ f(a) \in B_2 \} = \{ a \ | \ f(a) \in B_1 \} \cup \{ a \ | \ f(a) \in B_2 \}$

irod в сообщении #1105007 писал(а):

ж) $\{ a \ | \ f(a) \in B_1 \ \text{и} \ f(a) \in B_2 \} = \{ a \ | \ f(a) \in B_1 \} \cap \{ a \ | \ f(a) \in B_2 \}$

irod в сообщении #1105007 писал(а):

з) $\{ a \ | \ f(a) \in B_1 \ \text{и} \ f(a) \not\in B_2 \} = \{ a \ | \ f(a) \in B_1 \} \setminus \{ a \ | \ f(a) \in B_2 \}$

Эти равенства ― пока еще не равенства; их можно попытаться доказать тем способом, который я предложил выше. Потому что всегда возможно появление «подводных камней», как в пункте д).

[Ellan Vannin]

irod в сообщении #1103369 писал(а):

Вопрос: правильно ли что $f(\varnothing)=\varnothing$ ?

Ellan Vannin в сообщении #1105040 писал(а):

$f(X')=\{y \mid \langle x,y \rangle \in G_f \land x \in X' \}$
$f^{-1}(Y')=\{x \mid \langle x,y \rangle \in G_f \land y \in Y' \}$

Какие сомнения? Подставьте в эти определения пустые множества. И все получится.

[irod]

Ellan Vannin в сообщении #1105040 писал(а):

В качестве домашнего упражнения объясните почему $\{y \mid \langle x,y \rangle \in G_f \land x \in A_1 \setminus A_2 \}$ $\neq \{y \mid \langle x,y \rangle \in G_f \land x \in A_1 \} \setminus \{y \mid \langle x,y \rangle \in G_f \land x \in A_2 \}$

$( y_0 \in f(A_1 \setminus A_2) ) \Leftrightarrow (y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_1 \setminus A_2 \}) \Leftrightarrow ( \langle x,y_0 \rangle \in G_f \land x \in A_1 \setminus A_2 ) \Leftrightarrow ( \langle x,y_0 \rangle \in G_f \land x \in A_1 \land x \not\in A_2 ) \Leftrightarrow ( \langle x,y_0 \rangle \in G_f \land x \in A_1 ) \land ( \langle x,y_0 \rangle \in G_f \land x \not\in A_2 ) \Leftrightarrow (y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_1 \}) \land (y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \not\in A_2 \})$

$( y_0 \in f(A_1) \setminus f(A_2) ) \Leftrightarrow (y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_1 \} \setminus \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \}) \Leftrightarrow (y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_1 \}) \land (y_0 \not\in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \})$

Видно, что различие в том что

$(y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \not\in A_2 \}) \not\Leftrightarrow (y_0 \not\in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \})$

В этом можно убедиться, составив таблицу истинности для обеих частей, предварительно преобразовав их:

$(y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \not\in A_2 \}) \Leftrightarrow ( \langle x,y_0 \rangle \in G_f \land x \not\in A_2 )$

$(y_0 \not\in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \}) \Leftrightarrow ( \langle x,y_0 \rangle \not\in G_f \lor x \not\in A_2 )$

Таблица истинности:
\begin{tabular}{ |c|c|c|c| } \hline $\langle x,y_0 \rangle \in G_f$ & $x \in A_2$ & $\langle x,y_0 \rangle \in G_f \land x \not\in A_2$ & $\langle x,y_0 \rangle \not\in G_f \lor x \not\in A_2$ \\ \hline 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ \hline \end{tabular}

Правильно?

[Ellan Vannin]

Хорошо, что вы сделали попытку, но нет, неправильно. Был расчет, что вам удастся раскрыть тайный смысл неравенства $f(A_1 \setminus A_2) \neq f(A_1) \setminus f(A_2)$ и получить формулу $f(A_1 \setminus A_2) \supseteq f(A_1) \setminus f(A_2)$, справедливую не только для функций, но и для произвольных бинарных отношений, подставленных вместо $f$ (в контексте тех определений образа и прообраза, которые приведены выше). Поскольку у нас определение функции нигде не используется, можно просто считать, что мы имеем дело с некоторым отношением. Начнем с конца:

irod в сообщении #1105513 писал(а):

$(y_0 \not\in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \}) \Leftrightarrow ( \langle x,y_0 \rangle \not\in G_f \lor x \not\in A_2 )$

Это неверно. В качестве примера возьмем отображение $f : \{1,2\} \to \{0\}$ (единственное здесь возможное) и выберем два подмножества $A_1=\{1\}$ и $A_2=\{2\}$ и элемент $y_0=0$. Тогда высказывание слева принимает вид $0 \notin \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \}=f(A_2)=f(\{2\})=\{0\}$, что очевидно ложно. Но с другой стороны $(\langle 1,0 \rangle \not\in G_f \lor 1 \not\in A_2)$. Здесь $(1 \notin A_2)$ принимает истинное значение и делает всю дизъюнкцию истинной. То есть знак эквиваленции здесь ставить нельзя.

Рассмотрим возникшую ситуацию в общем виде. Обозначим $\langle x,y \rangle \in G_f$ через $P (x,y)$, $x \in A_1$ — через $Q(x)$, а $x \in A_2$ — через $R(x)$.
Тогда ваши утверждения для произвольного выбора $y_0$ могут быть записаны:
$(y_0 \not\in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \})$ как $\nexists x (P(x,y) \land R(x))$
$( \langle x,y_0 \rangle \not\in G_f \lor x \not\in A_2 )$ как $\exists x \overline{P(x,y) \land R(x)}$
Здесь должно быть совершенно ясно почему знак эквиваленции ставить нельзя.

irod в сообщении #1105513 писал(а):

1. $(y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_1 \}) \land (y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \not\in A_2 \})$

irod в сообщении #1105513 писал(а):

2. $(y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_1 \}) \land (y_0 \not\in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \})$

irod в сообщении #1105513 писал(а):

Видно, что различие в том что $(y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \not\in A_2 \}) \not\Leftrightarrow (y_0 \not\in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \})$

Различие между утверждениями 1 и 2 не только в этом. В первой записи у вас предполагается один и тот же $x$. Во второй записи у вас "иксы" разные (никто не обещал, что они равны). То есть первая запись у нас получилась кривая и, по правде говоря, неверная, потому что не поставлены кванторы. Беру часть вины на себя

irod в сообщении #1105513 писал(а):

$( \langle x,y_0 \rangle \in G_f \land x \in A_1 \land x \not\in A_2 )$ $\Leftrightarrow ( \langle x,y_0 \rangle \in G_f \land x \in A_1 ) \land ( \langle x,y_0 \rangle \in G_f \land x \not\in A_2 )$ $\Leftrightarrow (y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_1 \}) \land (y_0 \in \{ y \ | \ \langle x,y \rangle \in G_f \land x \not\in A_2 \})$

Вот где появилась ошибка. Если помните, я доказывал выше утверждение $f(A_1 \cup A_2) = f(A_1) \cup f(A_2)$. Я в нем использовал равносильность $\exists x ((P(x,y)\land Q(x))\lor (P(x,y) \land R(x))) \equiv$ $\exists x (P(x,y)\land Q(x))\lor \exists x (P(x,y) \land R(x))$. У вас ситуация абсолютно другая: $\exists x ((P(x,y)\land Q(x))\land (P(x,y) \land \overline{R(x)})) \not\equiv $ $\exists x (P(x,y)\land Q(x))\land \exists x (P(x,y) \land \overline{R(x)})$. Поэтому я думаю, лучше вообще не использовать бескванторные выражения, особенно если не до конца понятен смысл производимых в них действий.

irod, если вы сможете доказать в одну сторону, что $\exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \Leftarrow $ $\exists x (P(x,y)\land Q(x))\land $\nexists x (P(x,y) \land R(x))$, то это и будет доказательство утверждения $f(A_1 \setminus A_2) \supseteq f(A_1) \setminus f(A_2)$. Примерно то же самое вам придется сделать в задаче з): доказать сначала в одну сторону утверждение для произвольных отношений, а затем использовать определение функции, и доказать утверждение в другую сторону. Я чувствую интуитивно, что существует аналогия с этим нашим примером, поэтому так настойчиво предлагаю вам потренироваться на нём .

[irod]

Ellan Vannin о, Вы ответили, я очень ждал Вашего ответа. Большое спасибо что тратите свое время и помогаете мне )
По делу мне пока нечего сказать, на выходных буду разбираться с тем что Вы написали. Неожиданно непростые задачки-то для меня оказались.

[Ellan Vannin]

(Оффтоп)

Ellan Vannin в сообщении #1105788 писал(а):

$\exists x ((P(x,y)\land Q(x))\lor (P(x,y) \land R(x)))$
$\exists x (P(x,y)\land Q(x))\lor \exists x (P(x,y) \land R(x))$

Ellan Vannin в сообщении #1105788 писал(а):

$\exists x (P(x,y)\land Q(x) \land \overline{R(x)})$
$\exists x (P(x,y)\land Q(x))\land \nexists x (P(x,y) \land R(x))$

Поскольку мы всё тут доказываем для произвольного выбора $y_0$, то можно было бы каждое утверждение заключить в $\forall y (...)$. С другой стороны непонятно зачем это делать, если это ни на что не влияет. У нас тут доказательства и так неудобочитаемы, поэтому можно обойтись без лишних кванторов и скобок. В смысле требование $\forall y (...)$ — оно конечно правильное, но избыточное, лучше оставить всё как есть.
Кажется, я сейчас разговариваю сам с собой?

[irod]

Ellan Vannin в сообщении #1105788 писал(а):

Был расчет, что вам удастся раскрыть тайный смысл неравенства $f(A_1 \setminus A_2) \neq f(A_1) \setminus f(A_2)$ и получить формулу $f(A_1 \setminus A_2) \supseteq f(A_1) \setminus f(A_2)$

Хм, а зачем вообще получать эту формулу? Что это даст? Ведь
$f(A_1 \setminus A_2) = f(A_1) \setminus f(A_2) \Leftrightarrow [f(A_1 \setminus A_2) \supseteq f(A_1) \setminus f(A_2)] \land [f(A_1) \setminus f(A_2) \supseteq f(A_1 \setminus A_2)]$
С другой стороны, при $f(A_1 \setminus A_2) \neq f(A_1) \setminus f(A_2)$ также может выполняться в одну сторону $f(A_1 \setminus A_2) \supseteq f(A_1) \setminus f(A_2)$.
Таким образом, знание того что $f(A_1 \setminus A_2) \supseteq f(A_1) \setminus f(A_2)$ мало что говорит нам о том, всегда ли выполняется равенство $f(A_1 \setminus A_2) = f(A_1) \setminus f(A_2) $ или нет.

Или я зря сейчас такой вопрос задаю, и это доказательство нужно мне только для пункта з) ?

У меня есть еще вопрос. Почему в новых обозначениях

Ellan Vannin в сообщении #1105788 писал(а):

$(y_0 \not\in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \})$ как $\nexists x (P(x,y) \land R(x))$
$( \langle x,y_0 \rangle \not\in G_f \lor x \not\in A_2 )$ как $\exists x \overline{P(x,y) \land R(x)}$

(не)существует именно "икс" а не "игрек"? Разве не должно быть так:
$(y_0 \not\in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \})$ как $\nexists y (P(x,y) \land R(x))$
$( \langle x,y_0 \rangle \not\in G_f \lor x \not\in A_2 )$ как $\exists y \overline{P(x,y) \land R(x)}$
?
Подозреваю что ответ такой: потому что по определению отображения какой-то $y$ существует для любого $x$, а значит раз подходящий нам $x$ найден, то $y$ для него также обязательно найдется. Так?

-- 14.03.2016, 16:28 --

Кажется на мой последний вопрос Вы ответили своим вторым сообщением, но я все же уточняю этот момент, потому что это все пока довольно тонкие для меня материи, и я не чувствую уверенности.

[provincialka]

irod в сообщении #1106582 писал(а):

Таким образом, знание того что $f(A_1 \setminus A_2) \supseteq f(A_1) \setminus f(A_2)$ мало что говорит нам о том, всегда ли выполняется равенство $f(A_1 \setminus A_2) = f(A_1) \setminus f(A_2) $ или нет.

Ну почему! Если бы не выполнялось первое соотношение, то не выполнялось и второе. Кроме того, при поиске контрпримера к "равенству" можно не искать функцию, для которой выполняется (1). Ибо такой не существует.

[Ellan Vannin]

irod в сообщении #1106582 писал(а):

зачем вообще получать эту формулу? Что это даст?

Это задача на смекалку

irod в сообщении #1106582 писал(а):

это доказательство нужно мне только для пункта з) ?

Да, вам в нем придется делать почти то же самое.

irod в сообщении #1106582 писал(а):

Почему в новых обозначениях (не)существует именно "икс" а не "игрек"?

А что значит "игрек" не принадлежит множеству? Значит $y_0$ был выбран из области прибытия отношения, но "не прошел" по условию справа от вертикальной черты. Значит он входит в такое множество, где справедливо отрицание этого условия. Во-вторых (и это очень важно) мы доказываем равенство множеств всегда для произвольного выбора элемента. Сам факт существования заданных элементов еще не гарантирует совпадение множеств. Нам нужна произвольность. Поэтому перед $y$ должен стоять квантор $\forall$.

irod в сообщении #1106582 писал(а):

Разве не должно быть так:
$(y_0 \not\in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \})$ как $\nexists y (P(x,y) \land R(x))$
$( \langle x,y_0 \rangle \not\in G_f \lor x \not\in A_2 )$ как $\exists y \overline{P(x,y) \land R(x)}$
?

Должно быть так:
$(y_0 \not\in \{ y \ | \ \langle x,y \rangle \in G_f \land x \in A_2 \})$ как $\forall y \overline{\exists x (P(x,y) \land R(x))}$
$( \langle x,y_0 \rangle \not\in G_f \lor x \not\in A_2 )$ как $\forall y \exists x \overline{P(x,y) \land R(x)}$
Эта же самая неравносильность объяснена на конкретном примере функции.
И я очень советую в самих доказательствах не использовать понятия принадлежности-непринадлежности, а вместо этого освоить кванторы.

irod в сообщении #1106582 писал(а):

Подозреваю что ответ такой: потому что по определению отображения какой-то $y$ существует для любого $x$, а значит раз подходящий нам $x$ найден, то $y$ для него также обязательно найдется. Так?

Отложите пока определение функции. Сначала нужно хотя бы с множествами разобраться.

(Оффтоп)

По определению бинарного отношения у нас ничего не существует, и вряд ли что-то найдется Однако формула $f(A_1 \setminus A_2) \supseteq f(A_1) \setminus f(A_2)$ не перестает быть верной.

irod в сообщении #1106582 писал(а):

Кажется на мой последний вопрос Вы ответили своим вторым сообщением, но я все же уточняю этот момент, потому что это все пока довольно тонкие для меня материи, и я не чувствую уверенности.

Я ответил, что не вижу смысла каждый раз вокруг каждого утверждения рисовать $\forall y (...)$. Достаточно сразу оговорить произвольность $y$. Но если вдруг вам нужно, значит делайте, получится то же самое.

-- 14.03.2016, 22:01 --

Ellan Vannin в сообщении #1106652 писал(а):

"не прошел" по условию справа от вертикальной черты.

Условию существования икса, разумеется.

Ellan Vannin в сообщении #1106652 писал(а):

Значит он входит в такое множество, где справедливо отрицание этого условия.

Ага.

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

[irod]

Ок, я вроде бы понял.

Ellan Vannin в сообщении #1105788 писал(а):

irod, если вы сможете доказать в одну сторону, что $\exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \Leftarrow $ $\exists x (P(x,y)\land Q(x))\land $\nexists x (P(x,y) \land R(x))$, то это и будет доказательство утверждения $f(A_1 \setminus A_2) \supseteq f(A_1) \setminus f(A_2)$.

Перепишем со всеми кванторами:

$$ \forall y [ \exists x (P(x,y) \land Q(x)) \land \nexists x (P(x,y) \land R(x)) \Rightarrow \exists x ( P(x,y) \land Q(x) \land \overline{R(x)} ) ] $$

Доказательство.
Предположим, что левая от знака импликации часть истинна. Это значит что истинны оба конъюнкта $\exists x (...)$ и $\nexists x (...)$. Возьмем произвольный $x$ из первого конъюнкта, т.е. удовлетворяющий условиям $P(x,y)$ и $Q(x)$. Для такого $x$ существуют две возможности: либо $R(x)$ либо $\overline{R(x)}$. По нашему исходному предположению (второй конъюнкт), нет такого $x$, для которого бы выполнялось одновременно $P(x,y)$ и $R(x)$. Значит, одновременно с $P(x,y)$ независимо от выполнения $Q(x)$ может выполняться только $\overline{R(x)}$, а значит $\exists x ( P(x,y) \land Q(x) \land \overline{R(x)} )$.

[Ellan Vannin]

(Оффтоп)

Ладно, сейчас придется наводить строгость в наших рассуждениях. Даю себе совет на будущее: никогда не начинать с интуитивных определений. Интуитивно — значит неверно. Еще пока есть возможность сделать тотальный "апдейт" всего, что мною в этой теме понаписано. Но если этого не сделать, мы рискуем, что разговор дойдет до такой точки, когда объяснить что-либо будет уже невозможно.

$f(A_0)=\{y \mid \exists x ( x \in A_0 \land \langle x,y \rangle \in G_f ) \}$

(Оффтоп)

А почему все таки $x$ существует? Если выражаться фигурально, это означает следующее. Предположим, мы бы хотели пройти или проехать в конечный пункт местоназначения $y$ из региона $A_0$. Что такое $A_0$? Это может быть несколько близлежащих деревень, может быть район, область, или даже целое государство. Для начала нам нужно найти в нем некоторую точку отправления $x$. Такая точка может оказаться всего одна: пусть например нам нужно сплавляться на лодке вниз по реке, а в нашем регионе $A_0$ существует всего одна лодочная станция. Таких исходных пунктов $x$ может быть и несколько. Наконец их может быть даже бесконечно много: чисто гипотетически можно разровнять и заасфальтировать всю планету, тогда из любой точки региона $A_0$ существует прекрасный пешеходный маршрут Но в конечном счете всё это неважно: чтобы просто начать движение, нужен хотя бы один-единственный отправной пункт $x$. Именно поэтому мы перед $x$ ставим квантор существования. Итак, вы можете благополучно добраться до $y$, если во-первых существует пункт отправления, и во-вторых если известен маршрут. А уже множество всех таких $y$ обозначается $f(A_0)$ и называется образом множества.

Надеюсь, с таким рассказом определение выглядит немного понятнее. Я бы назвал это "пешеходная логика" или как-нибудь подобным образом

$f^{-1}(B_0)=\{x \mid \exists y ( y \in B_0 \land \langle x,y \rangle \in G_f ) \}$

(Оффтоп)

Теперь если $x_0 \notin f^{-1}(B_0)=\{x \mid \exists y ( \langle x,y \rangle \in G_f \land y \in B_0 ) \}$, значит $x_0$ входит в другое множество, где выполняется отрицание этого условия. А это в точности означает, что $x_0 \in \{x \mid \nexists y ( \langle x,y \rangle \in G_f \land y \in B_0 ) \}$

где $G_f$ ― график функции, $A_0$ и $B_0$ ― соответствующие подмножества.
Теорема. $f(A_1 \cup A_2) = f(A_1) \cup f(A_2)$
Доказательство. $\forall y \exists x (P(x,y)\land (Q(x)\lor R(x))) \equiv$$\forall y \exists x ((P(x,y)\land Q(x))\lor (P(x,y) \land R(x))) \equiv$ $\forall y (\exists x (P(x,y)\land Q(x))\lor \exists x (P(x,y) \land R(x)))$
Теорема. $f(A_1 \setminus A_2) \supseteq f(A_1) \setminus f(A_2)$

irod в сообщении #1106880 писал(а):

Доказательство. Предположим, что левая от знака импликации часть истинна. Это значит что истинны оба конъюнкта $\exists x (...)$ и $\nexists x (...)$. Возьмем произвольный $x$ из первого конъюнкта, т.е. удовлетворяющий условиям $P(x,y)$ и $Q(x)$. Для такого $x$ существуют две возможности: либо $R(x)$ либо $\overline{R(x)}$. По нашему исходному предположению (второй конъюнкт), нет такого $x$, для которого бы выполнялось одновременно $P(x,y)$ и $R(x)$. Значит, одновременно с $P(x,y)$ независимо от выполнения $Q(x)$ может выполняться только $\overline{R(x)}$, а значит $\exists x ( P(x,y) \land Q(x) \land \overline{R(x)} )$.

С точки зрения содержательной, я абсолютно с вами согласен. Но нам нужны формальные рассуждения:
$\exists x (P(x,y)\land Q(x))\land \nexists x (P(x,y) \land R(x)) $ $\equiv \exists x (P(x,y)\land Q(x))\land \forall x \overline {P(x,y) \land R(x)}$ $\equiv \exists x (P(x,y)\land Q(x))\land \forall x (\overline {P(x,y)} \lor \overline {R(x)})$ $\to \exists x (P(x,y)\land Q(x)\land (\overline {P(x,y)} \lor \overline {R(x)}))$ $\equiv \exists x ( P(x,y) \land Q(x) \land \overline{R(x)} )$
Если присмотреться, то у меня написано то же самое доказательство, просто со всей необходимой строгостью.

Короче сейчас тут всё "пропатчено", "отшлифовано", недоработки устранены, можете смело брать и делать всё по образцу. Теперь по поводу вашей задачи:
Теорема. $f(A_1 \setminus A_2) \not\subseteq f(A_1) \setminus f(A_2)$
Существует два варианта как это можно доказать (я рекомендую вам выполнить оба):
1. Нужно привести пример, опровергающий утверждение под отрицанием. Вы в самом начале экспериментировали с пустой разностью $f(A_1) \setminus f(A_2) = \varnothing$, это очень интересная и правильная идея. Осталось довести пример до конца: указать любую конкретную подходящую функцию.
2. Иногда бывает подобрать пример очень трудно. Но в любом случае можно попытаться доказать утверждение в общем виде: $\exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \not\Rightarrow $ $\exists x (P(x,y)\land Q(x))\land \nexists x (P(x,y) \land R(x))$. Эта совсем простая задача решается в два действия: если вы покажете, что наша формула является тождественно истинной (всегда истинной), тогда действительно из левой части не следует правая. И тогда действительно $f(A_1 \setminus A_2) \not\subseteq f(A_1) \setminus f(A_2)$, что и требуется доказать.

(Оффтоп)

Я нашел по кванторам небольшой видеоурок: https://www.youtube.com/watch?v=n0ViBuKcbKk Может кому-то для чего-то пригодится.

[irod]

Ellan Vannin в сообщении #1107044 писал(а):

1. Нужно привести пример, опровергающий утверждение под отрицанием. Вы в самом начале экспериментировали с пустой разностью $f(A_1) \setminus f(A_2) = \varnothing$, это очень интересная и правильная идея. Осталось довести пример до конца: указать любую конкретную подходящую функцию.

Например, пусть $f: \{ 1,2,3 \} \to \{ 4 \}$, $A_1 = \{ 1,2 \}$, $A_2 = \{ 2,3\}$, $f(A_1) = f(A_2) = \{ 4 \}$. Тогда $f(A_1) \setminus f(A_2) = \varnothing$, а $f(A_1 \setminus A_2) = f( \{ 1 \} ) = \{ 4 \}$.

Ellan Vannin в сообщении #1107044 писал(а):

2. Иногда бывает подобрать пример очень трудно. Но в любом случае можно попытаться доказать утверждение в общем виде: $\exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \not\Rightarrow $ $\exists x (P(x,y)\land Q(x))\land \nexists x (P(x,y) \land R(x))$. Эта совсем простая задача решается в два действия: если вы покажете, что наша формула является тождественно истинной (всегда истинной), тогда действительно из левой части не следует правая. И тогда действительно $f(A_1 \setminus A_2) \not\subseteq f(A_1) \setminus f(A_2)$, что и требуется доказать.

Я думал над этим, и простите, но я в упор не понимаю с чего бы этой формуле быть тождественно истинной.
Поправьте меня если я не прав, но тождественно истинная формула или тавтология - это формула, принимающая значение $1$ при любых значениях входящих в нее подформул, так ведь?
Давайте для удобства введем короткие обозначения. Пусть $S(y) := \exists x (P(x,y)\land Q(x) \land \overline{R(x)})$, $T(y) := \exists x (P(x,y)\land Q(x))$ и $U(y) := \nexists x (P(x,y) \land R(x))$.
Наша формула тогда принимает вид $S(y) \not\Rightarrow T(y) \land U(y) \equiv S(y) \land \overline{T(y) \land U(y)} \equiv S(y) \land ( \overline{T(y)} \lor \overline{U(y)} )$.
Я не буду здесь приводить таблицу истинности для этой формулы, но очевидно что там в итоговом столбце будут далеко не все $1$. Даже если выкинуть из ТИ "невозможные" строки (например строки где $S(y) = 1$, а $T(y) = 0$, чего быть не может) -- я правда не уверен что так можно делать, но думаю это не важно сейчас.
Далее, я посмотрел урок по Вашей ссылке:

Ellan Vannin в сообщении #1107044 писал(а):

Я нашел по кванторам небольшой видеоурок: https://www.youtube.com/watch?v=n0ViBuKcbKk Может кому-то для чего-то пригодится.

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

[irod]

$$\exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \not\Rightarrow \exists x (P(x,y)\land Q(x))\land \nexists x (P(x,y) \land R(x)) $$

$$\equiv \exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \land \overline{ ( \exists x (P(x,y)\land Q(x))\land \nexists x (P(x,y) \land R(x)) ) }$$

$$\equiv \exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \land ( \overline{ \exists x (P(x,y)\land Q(x)) } \lor \overline{ \nexists x (P(x,y) \land R(x)) } )$$

$$\equiv \exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \land ( \nexists x (P(x,y)\land Q(x)) \lor \exists x (P(x,y) \land R(x)) ) $$

$$\equiv \exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \land ( \forall x (\overline{ P(x,y) \land Q(x) } ) \lor \exists x (P(x,y) \land R(x)) )$$

$$\equiv \exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \land ( \forall x (\overline{ P(x,y) } \lor \overline{ Q(x) } ) \lor \exists x (P(x,y) \land R(x)) )$$

$$\equiv ( \exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \land \forall x (\overline{ P(x,y) } \lor \overline{ Q(x) } ) ) \lor ( \exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \land \exists x (P(x,y) \land R(x)))$$

Первый дизъюнкт $\exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \land \forall x (\overline{ P(x,y) } \lor \overline{ Q(x) } )$ - очевидно невозможен. Что тогда? Просто отбрасываем его? Или же у меня где-то ошибка? Предположим, ошибки нет, и мы его отбросили. Осталось

$$\exists x (P(x,y)\land Q(x) \land \overline{R(x)}) \land \exists x (P(x,y) \land R(x)) $$

Непонятно, что мне это дает, и что с этим делать дальше.