Задачки из книги Зорича

[Denis Russkih]

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


В данный момент мне интересно, правильно ли я записал решение вот этой задачи:

Цитата:

Через $A$, $B$ и $C$ обозначены подмножества некоторого множества $M$. Проверить соотношение:

$C_M(C_MA) = A$

Я записал решение так:

Цитата:

\parindent=0px $C_M(C_MA) \,\Leftrightarrow\, (x \in M) \wedge (x \notin C_MA) \,\Leftrightarrow\, (x \in M) \wedge \neg (x \in C_MA) \,\Leftrightarrow\, \\\\ \,\Leftrightarrow\, (x \in M) \wedge \neg ((x \in M) \wedge (x \notin A)) \,\Leftrightarrow\, (x \in M) \wedge (\neg (x \in M) \vee \neg (x \notin A)) \,\Leftrightarrow\, \\\\ \,\Leftrightarrow\, (x \in M) \wedge (\neg (x \in M) \vee (x \in A)) \,\Leftrightarrow\, ((x \in M) \wedge (\neg (x \in M))) \vee \\\\ \vee ((x \in M) \wedge (x \in A)) \,\Leftrightarrow\, 0 \vee ((x \in M) \wedge (x \in A)) \,\Leftrightarrow\, (x \in M) \wedge (x \in A) \,\Leftrightarrow\, \\\\ \,\Leftrightarrow\, (x \in (M \cap A)) \,\Leftrightarrow\, (x \in A), \,\text{т.к.}\, A \subset M \,\text{по условию задачи}$

Общая идея, по-моему, правильна, но вот её запись вызывает у меня сомнения.

1. Можно ли вообще так записывать (ноль здесь означает заведомо ложное утверждение):
$((x \in M) \wedge (\neg (x \in M)) \vee ((x \in M) \wedge (x \in A))) \,\Leftrightarrow\, 0 \vee ((x \in M) \wedge (x \in A))$

2. Допустимо ли $A \subset M$ упомянуть лишь в самом конце?
Или я должен был ставить это после каждого значка "равносильно"?..
Или я должен был выполнить вот такое преобразование:
$A \subset M \,\Leftrightarrow\, ((x \in A) \Rightarrow (x \in M)) \,\Leftrightarrow\, (\neg (x \in A) \vee (x \in M))$
и затем использовать это в дальнейших рассуждениях?..

3. Переход $(A \subset M) \wedge (x \in (M \cap A)) \,\Leftrightarrow\, (x \in A)$, вероятно, сам нуждается в доказательстве?..

Хотелось бы узнать ответы на эти три вопроса.

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

Цитата:

\parindent=0px $C_M(C_MA) \,\Leftrightarrow\, (A \subset M) \wedge (x \in M) \wedge (x \notin C_MA) \,\Leftrightarrow\, \\\\ \,\Leftrightarrow\, ((x \in A) \Rightarrow (x \in M)) \wedge (x \in M) \wedge \neg (x \in C_MA) \,\Leftrightarrow\, \\\\ \,\Leftrightarrow\, (\neg (x \in A) \vee (x \in M)) \wedge (x \in M) \wedge \neg ((x \in M) \wedge (x \notin A)) \,\Leftrightarrow\, \\\\ \,\Leftrightarrow\, (\neg (x \in A) \vee (x \in M)) \wedge (x \in M) \wedge (\neg (x \in M) \vee \neg (x \notin A)) \,\Leftrightarrow\, \\\\ \,\Leftrightarrow\, (\neg (x \in A) \vee (x \in M)) \wedge (x \in M) \wedge (\neg (x \in M) \vee (x \in A)) \,\Leftrightarrow\, \\\\ \,\Leftrightarrow\, (\neg (x \in A) \vee (x \in M)) \wedge (((x \in M) \wedge (\neg (x \in M))) \vee ((x \in M) \wedge (x \in A))) \,\Leftrightarrow\, \\\\ \,\Leftrightarrow\, (\neg (x \in A) \vee (x \in M)) \wedge (((x \in M) \wedge (x \in A))) \,\Leftrightarrow\, \\\\ \,\Leftrightarrow\, (\neg (x \in A) \vee (x \in M)) \wedge (x \in M) \wedge (x \in A) \,\Leftrightarrow\, (x \in A) \Rightarrow (C_M(C_MA) = A)$

Заключительный этап решения можно проверить таблицей истинности:

$\begin{array}{c|c|c|c|c} (x \in A) & (x \in M) & \neg (x \in A) & \neg (x \in A) \vee (x \in M) & (\neg (x \in A) \vee (x \in M)) \wedge (x \in M) \wedge (x \in A) \\ \hline 0 & 0 & 1 & 1 & 0 \\ \hline 0 & 1 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 1 & 1 \\ \end{array} $

И вот тут ОПАНЬКИ, как обухом по башке! :) Первый столбец не совпадает с последним, хотя и должен, по идее!

Получается, я вообще капитально чего-то не понимаю в математике, в жизни, в логическом мышлении...

Короче, я окончательно увяз, просто утопаю! В такой простенькой на вид задачке! Может, кто-нибудь кинет мне верёвку? Чтобы удавиться выбраться из этих зыбучих песков.

[gris]

Дополнение к дополнению подмножества равно этому подмножеству.

Вроде бы достаточно скобки раскрыть. Ну не может быть так сложно.

[Denis Russkih]

gris в сообщении #769635 писал(а):

Вроде бы достаточно скобки раскрыть. Ну не может быть так сложно.

А как именно раскрывают скобки в таких случаях? Я пока что умею доказывать только так, как написал.

(У Зорича вообще как-то очень сжато изложены все эти правила, связанные с логическими операциями... Просто галопом по европам. Возможно, дело в том, что книга-то по матанализу, а не по математической логике?.. Тогда посоветуйте, пожалуйста, какую-нибудь литературу, где более подробно всё разжёвывается.)

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

[gris]

А нельзя разве просто написать:

$(x\in C_M(C_MA)) \,\Leftrightarrow\, (x \notin C_MA) \,\Leftrightarrow\, (x \in A) $

Насчёт логической части не знаю.

[Sonic86]

Denis Russkih в сообщении #769641 писал(а):

(У Зорича вообще как-то очень сжато изложены все эти правила, связанные с логическими операциями... Просто галопом по европам. Возможно, дело в том, что книга-то по матанализу, а не по математической логике?.. Тогда посоветуйте, пожалуйста, какую-нибудь литературу, где более подробно всё разжёвывается.)

Ну да, на уровне Зорича логические операции и работа со множествами уже считается элементарной.
Возьмите какую-нибудь простую книжку по матлогике и теории множеств. Можно даже без матлогики, поскольку там все крайне просто. Можно даже не глубоко теоретическую, а простую (я, честно говоря, читал это все в какой-то вообще левой книге, посоветовать толком не могу ). Игошина тут много слишком. Верещагина и Шеня тоже. А в теме с литературой пробовали смотреть?

Там просто все: простые операции со множествами сводятся к логике. В частности $C_M(C_M(A))=A$ сводится к закону двойного отрицания.
А! Я вспомнил книжку: Л.Я. Куликов Алгебра и теория чисел. Но могу наврать. Т.е. там страниц 20-30, остальное - не нужно пока.

[Denis Russkih]

gris в сообщении #769644 писал(а):

А нельзя разве просто написать:

$(x\in C_M(C_MA)) \,\Leftrightarrow\, (x \notin C_MA) \,\Leftrightarrow\, (x \in A) $

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

Ясно, что нельзя просто сказать "ну смотрите же, это ясно как божий день". С другой стороны, а чем запись $(x\in C_M(C_MA)) \,\Leftrightarrow\, (x \notin C_MA) \,\Leftrightarrow\, (x \in A) $ принципиально отличается от такого высказывания?.. Такое куцее "доказательство" больше похоже на самоуспокоение. :) Если уж браться доказывать то, что ни в каких доказательствах не нуждается, то надо, получается, добираться до самых основ, копать не менее чем на километр вглубь!.. Вот я и копаю, до тех пор, пока меня не завалит камнями. :)



Sonic86

Благодарю за фамилии авторов и название книжки! Нужно будет посмотреть.

Sonic86 в сообщении #769655 писал(а):

В частности $C_M(C_M(A))=A$ сводится к закону двойного отрицания.

Это как? Примерно вот так?

$C_M(C_MA) \Leftrightarrow \neg (x \in C_MA) \Leftrightarrow \neg (\neg (x \in A)) \Leftrightarrow (x \in A) \Rightarrow (C_M(C_MA) = A)$

Если так, то и впрямь просто. :) Спасибо! Но неужели можно ограничиться такой записью?

[provincialka]

Можно. Не усложняйте!

[Denis Russkih]

Да, думаю, Вы правы, нужно стараться не усложнять, а упрощать. Постараюсь в будущем так и делать. :) Спасибо всем за ответы!

[Denis Russkih]

Возник ещё один дурацкий вопрос. :) Никак не могу избавиться от буквоедства.

Допустима ли запись

$(x \in C_MA) \Leftrightarrow \neg (x \in A)$

Или надо писать так:

$(x \in C_MA) \Leftrightarrow (x \in M) \wedge (\neg (x \in A ))$

Вроде бы достаточно первой записи, но почему?.. Играет ли здесь роль тот факт, что $M$ подразумевается как множество, содержащее все множества?

Что, если мы возьмём не множество $M$, а множество $B$, к примеру? Сохранится ли тогда равносильность?

Пусть у нас есть маленький кружочек, это множество $A$. Вокруг него есть кружочек побольше, это множество $B$, такое, что $A \subset B$. Ну и остальное поле — это множество $M$, т.е. $B \subset M$. Разве можно тогда написать, что

$(x \in C_BA) \Leftrightarrow \neg (x \in A)$

По-моему, нет. Ведь запись $\neg (x \in A)$ означает не только то, что $(x \in C_BA)$, но и то, что $(x \in C_MA)$, т.е. мы получаем, что

$(x \in C_BA) \Leftrightarrow \neg (x \in A) \Leftrightarrow (x \in C_MA)$

Что, очевидно, неверно, если $B \not = M$.

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

$(x \in C_MA) \Leftrightarrow \neg (x \in A)$

то это означает, что $M$ включает в себя все множества? А в остальных случаях надо писать

$(x \in C_BA) \Leftrightarrow \neg (x \in A) \wedge (x \in B)$

Я прав?

[arseniiv]

Denis Russkih в сообщении #770577 писал(а):

Вроде бы достаточно первой записи

Разумеется, нет. $\{x\mid x\notin A\}$ — вообще не множество. Хотя тут уместны другие соображения: существуют такие $M, N$, что $C_M A \ne C_N A$, а если $x\in C_M A \Leftrightarrow x\notin A$, то всегда $C_M A = C_N A$.

[Denis Russkih]

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

Разумеется, нет. $\{x\mid x\notin A\}$ — вообще не множество.

Да ладно? А как же тогда вот здесь, я ведь написал:

Denis Russkih в сообщении #769684 писал(а):

Sonic86 в сообщении #769655 писал(а):

В частности $C_M(C_M(A))=A$ сводится к закону двойного отрицания.

Это как? Примерно вот так?

$C_M(C_MA) \Leftrightarrow \neg (x \in C_MA) \Leftrightarrow \neg (\neg (x \in A)) \Leftrightarrow (x \in A) \Rightarrow (C_M(C_MA) = A)$

Если так, то и впрямь просто. :) Спасибо! Но неужели можно ограничиться такой записью?

И мне ответили:

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

Можно. Не усложняйте!

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

-- 04.10.2013, 16:41 --

И как в общем случае отличить "множество" от "не множества"?.. Есть ли какой-то алгоритм, какие-то критерии, в общем, что-то, что поможет понять, множество передо мной или нет?.. А то я окончательно запутался. :)

[arseniiv]

Denis Russkih в сообщении #770577 писал(а):

Или надо писать так:

$(x \in C_MA) \Leftrightarrow (x \in M) \wedge (\neg (x \in A ))$

Вроде бы достаточно первой записи, но почему?.. Играет ли здесь роль тот факт, что $M$ подразумевается как множество, содержащее все множества?

Ну, если у вас для всех рассматриваемых множеств $A \subset M$, то для всех их $x \in M \wedge x \notin A \Leftrightarrow x \notin A$. Кстати, обычно подразумевается, что приоритет у внелогических предикатов и операций выше, чем у логических, так что скобок можете меньше писать.

Но лучше никогда не писать $x\in C_M A \Leftrightarrow x\notin A$ — ещё ладно, если обозначение раскрывается во что-то с дополнительными вещами, но не наоборот.

Denis Russkih в сообщении #770601 писал(а):

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

Ну, это решение идейно правильное, его можно переписать в точное. В одном и том же контексте или вы понимаете $C_MA$ как $\{x\mid x\in M\wedge x\notin A\}$, или как $\{x\mid x\notin A\}$, и тогда вы должны быть готовы к встрече с собственными классами (этой записи не соответствует никакого множества, но если оперировать классами, ей соответствует класс). С ними можно делать многое то, что можно делать с множествами, но не всё, и обычно всем хватает одних множеств. В общем, даже если забыть о классах, $x\in M\wedge x\notin A \not\equiv x\notin A$, поэтому если доказываете про первое, второе тут не очень уместно. Точнее, вы докажете про второе, а про первое не докажете.

-- Пт окт 04, 2013 19:49:15 --

Denis Russkih в сообщении #770601 писал(а):

И как в общем случае отличить "множество" от "не множества"?.. Есть ли какой-то алгоритм, какие-то критерии, в общем, что-то, что поможет понять, множество передо мной или нет?.. А то я окончательно запутался. :)

Практически все вещи, которые вы встретите в книгах не по теории множеств, точно представимы множествами. В общем случае для этого есть разные аксиоматики теории множеств. В ZFC если $x$ существует — $x$ множество.

[Denis Russkih]

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

Ну, это решение идейно правильное, его можно переписать в точное.

То есть, точной будет вот такая запись:

\parindent=0px$C_M(C_MA) \Leftrightarrow \neg (x \in C_MA) \wedge x \in M \Leftrightarrow \neg (\neg (x \in A)) \wedge x \in M \Leftrightarrow \\\\ \Leftrightarrow x \in A \wedge x \in M \Rightarrow (C_M(C_MA) = A)$

Я правильно понимаю? :)

Но как же тогда совершается последний переход? Ведь, по моему скромному мнению,
$x \in A \wedge x \in M $ \Leftrightarrow x \in (A \cap M)
и не более того. Как же доказать, что из $x \in (A \cap M)$ вытекает $x \in A$ и, соответственно, $C_M(C_MA) = A$, или это считается само собой разумеющимся?..

Лично у меня вот такое чувство, что я никуда не пришёл в рассуждениях, а просто потоптался на месте.

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

Практически все вещи, которые вы встретите в книгах не по теории множеств, точно представимы множествами.

Как же тогда объяснить, что я всего на 10 странице учебника Зорича уже встретил задачку, которая сожрала мой мозг? :)

Может, это потому, что я слишком глубоко копаю? Наверное, просто не стоит заморачиваться с такими мелочами, и не буду знать проблем?.. Но я никак не могу заставить себя проходить мимо таких непоняток. Кажется, будто оставляю неприятеля в тылу. :)

[arseniiv]

Denis Russkih в сообщении #770628 писал(а):

То есть, точной будет вот такая запись:

\parindent=0px$C_M(C_MA) \Leftrightarrow \neg (x \in C_MA) \wedge x \in M \Leftrightarrow \neg (\neg (x \in A)) \wedge x \in M \Leftrightarrow \\\\ \Leftrightarrow x \in A \wedge x \in M \Rightarrow (C_M(C_MA) = A)$

Я правильно понимаю? :)

Неправильно. У вас изниоткуда появляется никак не связанный $x$, а потом пропадает. Если вы запишете аккуратно, как раньше, $x\in C_M(C_MA) \Leftrightarrow \cdots \Leftrightarrow x\in A$, и аккуратно будете раскрывать… (Зря я написал про приоритеты — лучше вы пока пишите все скобки.)

-- Пт окт 04, 2013 20:35:57 --

Кстати, часто помогает писать формулы одну над другой. Так получается яснее, какая подформула заменена, а что нужно переписать как было. (В $\TeX$е для этого есть окружения gather* (не помню уже, как работает) и банальный array (пример посмотрите в одной из тем про формулы). В коде при этом тоже удобно писать на нескольких строках, но придётся нажимать кнопку math, иначе форум запнётся на многострочности формулы (может, сейчас уже нет, не проверял). Если строки короткие и ясно видимые через код, это даже иногда может избавить от выкладок где-то на отдельном листе и переписывания.)

[gris]

Denis Russkih, не надо пытаться быть святее Папы, то бишь, строже Зорича. Если вы посмотрите двумя страницами ранее на его доказательство правила де Моргана, то Вы увидите ровно ту конструкцию $(x\in C_M(A\cup B)) \,\Rightarrow\, (x \notin (A\cup B)) \,\Rightarrow\, ...$, которая приводилась в этой теме в эквивалентных формах. Совершенно ясно, что мы находимся во множестве $M$, и упоминание этого факта в формулах будет только утяжелять рассуждения. Зорич и далее часто опускает чисто формальные подробности, тем самым выделяя существенное именно для предмета "математический анализ".
Но, разумеется, стремление к глубокому пониманию похвально. Лишь бы оно не сводилось к схоластике.