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

[G00gle]

В книге "Антидемидович Часть 1" 2001 года издания УРСС В Главе 1 параграф 2 встретился с таким доказательством.
15. Доказать, что если $f : E \rightarrow F$ и $A \subset E$, $B \subset E$, то справедливо равенство $f(A \cup B) = f(A) \cup f(B) $.
Доказательство:
$\triangleleft$ Согласно определению 1, п.п. 2.2 (определение образа множества), имеем $f(A \cup B)=\lbrace f(x) : x \in A \cup B\rbrace$.
Пусть $f(x) \in f(A \cup B)$, тогда $x \in (A \cup B)$, т. е. $x\in A \vee x \in B$. Но если $x\in A \vee x \in B$, то $f(x)\in f(A) \vee f(x) \in f(B)$ и $f(x) \in (f(A) \cup f(B))$. Этим доказано включение $f(A \cup B) \subset (f(A) \cup f(B))$.
Пусть $f(x) \in (f(A) \cup f(B))$, тогда $f(x) \in f(A) \vee f(x) \in f(B)$, откуда $x \in A \vee x \in B$, т. е. $x \in (A \cup B)$, а поэтому $f(x) \in f(A \cup B)$ и $(f(A) \cup f(B)) \subset f(A \cup B)$. Из доказанных выше выше включений следует требуемое утверждение.$\triangleright$
Смущает следующее. Очевидно, что $x \in A \Rightarrow f(x) \in f(A)$. В приведенном выше доказательстве предлагается по определению принять, что $f(x) \in f(A) \Rightarrow x \in A$, то есть $f(x) \in f(A) \Leftrightarrow x \in A$.
Вот тут получаются неожиданные следствия.
Докажем заведомо неверное утверждение $f(A) \cap f(B) \subset f(A \cap B)$. То, что оно неверно легко показать. Возьмем такую функцию и такие два множества $A = \lbrace x_1\rbrace$ и $B = \lbrace x_2\rbrace$, что $f(x_1)=f(x_2) \wedge x_1 \neq x_2$, тогда $f(A) \cap f(B) = f(x_1) = f(x_2)$, а $f(A \cap B) = \varnothing$. Противоречие.
Тем не менее мы можем "доказать" эту формулу вышеприведенным способом.
Действительно:
$f(x) \in (f(A) \cap f(B)) \Rightarrow f(x) \in f(A) \wedge f(x) \in f(B) \Rightarrow x \in A \wedge x \in B \Rightarrow x \in A \cap B \Rightarrow f(x) \in f(A \cap B)$
Что и требовалось доказать.
Помогите разобраться, где подвох.
Мне думается, что $(x \in A) \Rightarrow (f(x) \in f(A)) \not \Rightarrow (x \in A)$. Но тогда, как доказывать верную формулу без этого?

[demolishka]

Ваши мысли правильны. Доказательство оформлено неряшливо. На самом деле там неявно имеется в виду, что нас интересуют только образы тех самых $x$. Чтобы было яснее, надо

G00gle в сообщении #1224439 писал(а):

Пусть $f(x) \in f(A \cup B)$, тогда $x \in (A \cup B)$, т. е. $x\in A \vee x \in B$.

Заменить на

$$\text{Пусть } y \in f(A \cup B), \text{ тогда } y=f(x), \text{ где } x \in (A \cup B), \text{т. е. } x\in A \vee x \in B.$$

[G00gle]

demolishka в сообщении #1224472 писал(а):

Ваши мысли правильны. Доказательство оформлено неряшливо. На самом деле там неявно имеется в виду, что нас интересуют только образы тех самых $x$. Чтобы было яснее, надо

G00gle в сообщении #1224439 писал(а):

Пусть $f(x) \in f(A \cup B)$, тогда $x \in (A \cup B)$, т. е. $x\in A \vee x \in B$.

Заменить на

$$\text{Пусть } y \in f(A \cup B), \text{ тогда } y=f(x), \text{ где } x \in (A \cup B), \text{т. е. } x\in A \vee x \in B.$$

Я понял это, и в доказательстве есть ссылка на определение образа функции, которая значит именно то, что вы написали. Вопрос в том, почему получается доказать заведомо ложное утверждение $(f(A) \cap f(B)) \subset f(A \cap B)$, используя это определение. Или ошибка где-нибудь в другом месте? Если так, не могли бы вы указать незаконную импликацию и объяснить, почему она незаконна.

[Otta]

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

А уже потом можно браться за пересечение.

[G00gle]

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

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

А уже потом можно браться за пересечение.

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

[Otta]

G00gle в сообщении #1224795 писал(а):

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

Нет ни одного квантора. А должны быть.

G00gle в сообщении #1224439 писал(а):

$f(A \cup B) = f(A) \cup f(B) $.

Покажем, что $f(A \cup B)\subset f(A) \cup f(B) $.
Для этого нужно взять произвольный элемент $y$ из левого множества и показать, что он лежит в правом.
$y\in f(A \cup B)$, следовательно, найдется $x\in A \cup B$ такой, что $f(x)=y$. Этот $x$ принадлежит хотя бы одному из множеств $A$ или $B$. Тогда $y=f(x)$ принадлежит хотя бы одному из множеств $f(A)$ или $f(B)$, а значит, лежит в их объединении.

В одну сторону включение доказано.

В другую. Покажем, что $f(A) \cup f(B)\subset f(A \cup B)$.
Точно также, берем произвольный $y\in f(A) \cup f(B)$. Тогда $y$ принадлежит хотя бы одному из множеств $f(A)$ или $f(B)$. В первом случае найдется $x\in A$ такой, что $f(x)=y$. Раз $x\in A$, то тем более, $x\in A\cup B$. Что означает, что $y= f(x)\in f(A \cup B)$.
Во втором случае найдется $x\in B$ такой, что что $f(x)=y$. Раз $x\in B$, то тем более, $x\in A\cup B$. Что также означает, что $y= f(x)\in f(A \cup B)$. То есть в любом случае из $y\in f(A) \cup f(B)$ следует $y\in f(A \cup B)$.

В другую сторону тоже доказано. Что и требовалось.

А вот теперь попробуйте сами посмотреть, что в этой цепочке ломается, если заменить объединения на пересечения.

[G00gle]

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

Нет ни одного квантора. А должны быть.

А вот теперь попробуйте сами посмотреть, что в этой цепочке ломается, если заменить объединения на пересечения.

Спасибо огромное. Кажется, я более-менее разобрался. Приведу доказательство в кванторной форме, и если вам не трудно, посмотрите его на наличие ошибок. Еще хотел бы спросить о следующем. Среди математической литературы сложно найти книги, где бы подробно разбирались решения задач. Дается условие, но нередко даже не дают ответа, не говоря уже о примерах решения. Антидемидович - это редкое исключение, я надеялся, что в этой книге приведены более-менее строгие рассуждения, но, как оказалось, рассуждения касательно теории множеств оформлены, как минимум, неряшливо. Вопрос следующий. У этой книги везде стиль такой неряшливый, или только в этом разделе? Просто я в каком-то смысле самоучка, и если я буду постоянно натыкаться на такие сбивающие с толку доказательства, то потрачу уйму времени зря. В учебнике Зорича, кстати, дано формально правильное определение: $f(X):= \lbrace y \in Y | \exists (( x \in X) \wedge (y = f(x)))\rbrace $

Итак, покажем, что $f(A \cup B) = f(A) \cup f(B)$.
В доказательстве я использовал следующие, как мне показалось, верные утверждения:
$(\forall y(y \in A) \Rightarrow \forall y (y \in B)) \Leftrightarrow \forall y (y \in A \Rightarrow y \in B)$;
$ \exists x (x \in A) \vee \exists x (x \in B) \Leftrightarrow \exists x (x \in A \vee x \in B)$;
$y \in f(A) \Leftrightarrow \exists x (x \in A \wedge (y = f(x)))$.
Еще парочку более очевидных утверждений я здесь не записал. Последнее утверждение пришлось записать без кванторов, потому что, если записать с кванторами, то доказательство не получается. Там есть место, где, грубо говоря, $\forall x (A \vee B) $, но $ \forall x (A \vee B) \not \Rightarrow (\forall x A \vee \forall x B) $. Но с другой стороны такое часто используемое преобразование как $ x \in A \cup B \Leftrightarrow (x \in A \vee x \in B)$ тоже записывают без кванторов. Не знаю, достаточно ясно ли я выразился, но прошу вас пояснить допустимо ли записывать подобные формулы без кванторов? И если да, то когда использовать кванторы обязательно? (предположение: когда мы доказываем утверждения для множеств или говорим о множествах, а не о/для единичных элементах/-ов).
Доказательство:
\begin{multline*} \forall y (y \in f(A \cup B)) \Leftrightarrow \forall y (\exists x ((x \in A \cup B)\wedge (y=f(x)))) \Leftrightarrow \forall y (\exists x (((x \in A)\vee (x \in B)) \wedge (y=f(x)))) \Leftrightarrow \\ \Leftrightarrow \forall y(\exists x ((x \in A \wedge (y=f(x))) \vee (x \in B \wedge (y=f(x))))) \Leftrightarrow \forall y(\exists x (x \in A \wedge (y=f(x))) \vee \\ \vee \exists x (x \in B \wedge (y=f(x)))) \Leftrightarrow \forall y (y \in f(A) \vee y \in f(B)) \Leftrightarrow \forall y (y \in f(A) \cup f(B)) \end{multline*}
Если попытаться доказать формулу $ (f(A) \cap f(B)) \subset f(A \cap B) $, то получаем следующее:
\begin{multline*} \forall y (y \in (f(A) \cap f(B))) \Leftrightarrow \forall y(y \in f(A) \wedge y \in f(B)) \Leftrightarrow \forall y (\exists x (x \in A \wedge (y=f(x))) \wedge \exists x (x \in B \wedge (y=f(x)))) \end{multline*}, но $ (\exists x (x \in A) \wedge \exists x(x \in B)) \not \Rightarrow \exists x (x \in A \wedge x \in B)$. Поэтому дальнейшее продвижение в доказательстве невозможно.

[Otta]

G00gle в сообщении #1224992 писал(а):

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

По отзывам - много где. Я, к счастью, ничего не могу про него сказать, кроме как "не читал, но осуждаю".
У меня лет 10-15 назад была девочка одна очень способная, фанатевшая от матана (который мне довелось ей читать), так вот она от Антидемидовича плевалась страшно и говорила, надо ж было так все испохабить. Но никаких иных сведений, кроме косвенных, у меня о нем нет. Даже в руках не держала.

Кванторы в этом случае - обязательны. Если они опускаются, то по умолчанию считается, что высказывание верно для всех значений переменной. Как здесь: $ x \in A \cup B \Leftrightarrow (x \in A \vee x \in B)$
На самом деле, это означает, что $\forall x\ (x \in A \cup B) \Leftrightarrow (x \in A \vee x \in B)$. Если не оговорено иное.

Где ломается доказательство, Вы уловили верно.

Но кванторы в середину высказывания не цепляют. Например, не пишут вот так:
$(\forall y\ (y \in A) \Rightarrow \forall y\ (y \in B))$, как у Вас.
Пишут $(\forall y \ (y \in A) \Rightarrow (y \in B))$. Ну и так далее везде по тексту. Я его в деталях весь сейчас не проверяю, только что особо в глаза бросилось.

G00gle в сообщении #1224992 писал(а):

$ \exists x (x \in A) \vee \exists x (x \in B) \Leftrightarrow \exists x (x \in A \vee x \in B)$;

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

Где пример Вам найти, как писать правильно, я даже и не соображу сейчас. Может, кто-то еще подскажет. В курсах матлогики, конечно, обязательно есть.

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

Я же сама за кванторами не гоняюсь. Гораздо эффективнее для понимания (на мой взгляд) сказать все то же, но словами.

[G00gle]

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

Кванторы в этом случае - обязательны. Если они опускаются, то по умолчанию считается, что высказывание верно для всех значений переменной. Как здесь: $ x \in A \cup B \Leftrightarrow (x \in A \vee x \in B)$
На самом деле, это означает, что $\forall x\ (x \in A \cup B) \Leftrightarrow (x \in A \vee x \in B)$. Если не оговорено иное.

Где ломается доказательство, Вы уловили верно.

Но кванторы в середину высказывания не цепляют. Например, не пишут вот так:
$(\forall y\ (y \in A) \Rightarrow \forall y\ (y \in B))$, как у Вас.
Пишут $(\forall y \ (y \in A) \Rightarrow (y \in B))$. Ну и так далее везде по тексту. Я его в деталях весь сейчас не проверяю, только что особо в глаза бросилось.
Где пример Вам найти, как писать правильно, я даже и не соображу сейчас. Может, кто-то еще подскажет. В курсах матлогики, конечно, обязательно есть.

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

Я же сама за кванторами не гоняюсь. Гораздо эффективнее для понимания (на мой взгляд) сказать все то же, но словами.

Спасибо за ответ! Смотрел книги по мат. логике, но там почти сразу такие дерби начинаются, что меня это сразу отпугивало. К сожалению, в книге Зорича ликбез по мат. логике очень короткий, во всяком случае мне его недостаточно. Насчет того, что без кванторов понимать легче, тут я с вами соглашусь, но есть какая-то прелесть в том, что доказательство получается как бы почти автоматически (вообще, так и должно быть, ведь все теоремы - это тавтологии).

[Otta]

G00gle в сообщении #1225014 писал(а):

доказательство получается как бы почти автоматически

Пока этот автоматизм ничего хорошего не несет. Лучше сперва понять, что откуда берется.
Я там, кстати, один абзац вставила, - почему-то мне кажется, что именно в этом месте (где существование), видимость легкости автопилотирования играет с Вами дурную шутку.

-- 13.06.2017, 18:29 --

(Оффтоп)

И не цитируйте без нужды все полностью. Модераторы ругаться будут. Там кнопочка есть "Вставка". Выделяете нужное и жмете.

[G00gle]

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

G00gle в сообщении #1224992 писал(а):

$ \exists x (x \in A) \vee \exists x (x \in B) \Leftrightarrow \exists x (x \in A \vee x \in B)$;

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

Мне думалось, что здесь, как раз, все корректно.
Если левая часть неверна, то не существует ни элемента $x \in A$, ни какого-нибудь другого элемента $x \in B$, и значит нет такого элемента $x$, который бы принадлежал $A$ или $B$. И наоборот, если нет такого элемента $x$, который бы принадлежал $A$ или $B$, то нет ни элементов $x \in A$, ни элементов $x \in B$.
Если левая часть верна, то существует либо элемент $x \in A$, либо $x \in B$, либо оба таких элемента, возможно разные. Но тогда точно есть элемент, принадлежащий либо $A$, либо $B$, а может и обоим множествам вместе.
Если правая часть верна, то существует элемент принадлежащий либо $A$, либо $B$, а может и обоим множествам вместе, тогда этот элемент принадлежит либо $A$, либо $B$.
Еще можно доказать, что:
$ \exists x (x \in A \wedge x \in B) \Rightarrow \exists x (x \in A) \wedge \exists x (x \in B) \not \Rightarrow \exists x (x \in A \wedge x \in B)$
$ \forall x (x \in A) \vee \forall x (x \in B) \Rightarrow \forall x (x \in A \vee x \in B) \not \Rightarrow \forall x (x \in A) \vee \forall x (x \in B) $
$ \forall x (x \in A) \wedge \forall x (x \in B) \Leftrightarrow \forall x (x \in A \wedge x \in B) $
Я эти формулы получил, когда переводил логические высказывания на язык теории множеств.
Например, $ (A \Rightarrow B \wedge C) \Leftrightarrow ((A \Rightarrow B)\wedge (A \Rightarrow C))$. Если теперь понимать $A$ как $x \in A$ и поставить кванторы с обеих сторон, то получим: $ (A \subset B \cap C) \Leftrightarrow ((A \subset B)\wedge (A \subset C)) $.
Но если преобразовать таким же образом утверждение $ (A \Rightarrow B \vee C) \Leftrightarrow ((A \Rightarrow B)\vee (A \Rightarrow C))$, то получим утверждение $ (A \subset B \cup C) \Leftrightarrow ((A \subset B)\vee (A \subset C)) $, которое верно только в одну сторону, справа налево. Но если учесть, что $\forall x (x \in A \vee x \in B) \not \Rightarrow \forall x (x \in A) \vee \forall x (x \in B)$, тогда проблем не возникает.