Главная (Newsland) Раиса Захаровна Для противников и комментаторов.

05.09.2012 04:00

Для противников и комментаторов.

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

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

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

Задать множества можно многими способами, самый простой из которых заключается в простом перечислении элементов множества. Например, множество всех гласных английского алфавита можно записать как $V = \{a, e, i, o, u\}$ . Можно было бы впрочем описать его и просто словами: « $V$ — это множество гласных английского алфавита». Суть от этого не поменялась бы.

Обратим внимание на слова «неупорядоченный» и «различимые». Неупорядоченность означает, что $\{a, e, i, o, u\} = \{u, o, a, e, i\}$ , то есть нам не важно в каком порядке множество задано, важен лишь его состав. «Различимость» говорит о том, что набор элементов $\{a, a, e, e, i\}$ множеством в математическом смысле уже не является — множество не может по определению содержать совершенно одинаковые объекты, которые мы не можем различить.

В первой главе мы уже сталкивались со многими понятиями, которые являются множествами (могут рассматриваться как множества), и которые могут быть хорошими примерами: множество логических значений $\{0, 1\}$ , множество всех формул, множество моделей заданной теории $\mathrm{Mod}(T)$ , множество логических функций, и так далее. Из более приземленных примеров можно рассматривать множество всех звезд на небе, множество учащихся младших классов, множество монет у меня в кармане и подобные.

Отдельного упоминания заслуживает следующее тривиальное, но очень важное множество:

Определение. Множество $\emptyset=\{\}$ , не содержащее ни одного элемента, называется пустым множеством.

Если $x$ является элементом множества $S$ , то это обозначается как $x \in S$ . Если не является, то это обозначается как $x \not\in S$ .

Пустое множество таким образом можно охарактеризовать следующим логическим утверждением: $\forall x, x \not \in \emptyset$ .

Второе определение, которое было в первой главе, это определение подмножества:

Определение. Множество $A$ называется подмножеством множества $B$ (обозначение $A\subset B$ ), если любой элемент из $A$ содержится так же и в множестве $B$ .

На языке логики это определение можно записать так: $\forall x, (x\in A\rightarrow x\in B)$ .

Очевидно следующее простое свойство: $\forall X, \emptyset\subset X$ , то есть пустое множество является подмножеством любого другого множества. Это может быть непонятно исходя из интуитивного словесного определения, но идеально вписывается в приведенную логическую формулу для подмножеств: высказывание $x\in\emptyset$ всегда ложно, следовательно, импликация $x\in\emptyset \rightarrow X$ , всегда истинна, чем бы не являлось $X$ . Это демонстрирует преимущество строгих логических формулировок над интуитивными определениями: определение на языке логики всегда позволяет однозначно ответить на ряд вопросов, которые в противном случае могут даже не иметь смысла. По этой причине (а так же в качестве упражнения для мозга) последующие определения мы будем давать сразу сразу и на языке логики, и на обычном человеческом языке.

Так же полезно вспомнить, что каждое подмножество может быть задано некоторым предикатом, и по каждому подмножеству можно построить предикат. Множества, заданные предикатами, записываются так: $\{x \in A|P(x)\}$ — так описывается подмножество множества $A$ , для элементов которых оказывается истинным предикат $P$ .

Определение. Множества $A$ и $B$ называются равными ( $A=B$ ), если они состоят из одних и тех же элементов: $\forall x, (x\in A \leftrightarrow x\in B)$ .

Кто читал первую главу, знает, что $(x\in A \leftrightarrow x\in B) = (x \in A \rightarrow x \in B) \wedge (x \in B \rightarrow x \in A)$ , поэтому можно сформулировать следующее свойство:

Теорема. $A=B$ тогда и только тогда, когда $A\subset B$ и $B \subset A$ .

Определение. Объединением множеств $A$ и $B$ ( $A\cup B$ ) называется множество, которое содержит элементы обоих множеств: $\forall x, (x\in A \vee x \in B \leftrightarrow x\in A\cup B)$ .

Понятно, что если какие-то элементы входят одновременно и во множество $A$ и во множество $B$ , то в объединение множеств они войдут лишь в единственном экземпляре:

Пример. Пусть $A = \{a, b, c, d\}$ и $B = \{b, c, d, e, f\}$ . Тогда $A\cup B = \{a, b, c, d, e, f\}$

Логические операции удобно наглядно изображать с помощью так называемых кругов Эйлера. Пример, который я только что привел, может быть графически изображен следующим образом:

Здесь $x$ , $y$ и $z$ — это просто некоторые элементы, которые не вошли ни в одно из множеств. Всегда при работе со множествами (да и вообще всегда) важно рассматривать не только объекты, с которыми мы непосредственно работаем, но и внешние факторы. Красным цветом обозначено объединение двух множеств, представляемых кругами.

Определение. Пересечением множеств $A$ и $B$ ( $A\cap B$ ) называется множество, которое содержит лишь те элементы которые принадлежат сразу обоим множествам: $\forall x, (x\in A \wedge x \in B \leftrightarrow x\in A\cap B)$ .

Пример. Пусть $A = \{a, b, c, d\}$ и $B = \{b, c, d, e, f\}$ . Тогда $A\cap B = \{b, c, d\}$

Упражнение. Нарисуйте круги Эйлера для пересечения множеств (какую часть рисунка надо закрасить цветом?)

Определение. Множества называются непересекающимися, если $A\cap B = \emptyset$ (то есть множества не имеют общих элементов). В противном случае множества называются пересекающимися.

Пример. Множества $\{a, b, c\}$ и $\{d, e, f\}$ не пересекаются. Множества $\{a, b\}$ и $\{b, c\}$ пересекаются, и их пересечением является множество $\{b\}$ .

Определение. Разностью множеств $A\setminus B$ называется множество, содержащее все те элементы $A$ , которые не содержатся в $B$ : $\forall x, (x \in A\cap B \leftrightarrow x\in A \wedge x \not \in B)$ .

Пример. Пусть $A = \{a, b, c, d\}$ и $B = \{b, c, d, e, f\}$ . Тогда $A\setminus B = \{a\}$

Упражнение. Нарисуйте круги Эйлера для разности множеств.

Определение. Симметрической разностью множеств $A\bigtriangleup B$ называется множество $(A\setminus B)\cup (B\setminus A)$ , то есть множество элементов, принадлежащих либо $A$ , либо $B$ , но не их пересечению: $\forall x,(x\in A\bigtriangleup B \leftrightarrow x\in A \oplus x\in B)$ .

Пример. Пусть $A = \{a, b, c, d\}$ и $B = \{b, c, d, e, f\}$ . Тогда $A\bigtriangleup B = \{a, e, f\}$ .

Упражнение. Нарисуйте круги Эйлера для симметрической разности множеств.

Часто при работе со множествами, мы держим в уме, что все элементы нашего множества являются элементами некоторого другого более крупного множества, содержащего все возможные объекты рассматриваемой нами задачи. Например, если мы говорим о множестве звёзд на небе, то мы можем держать в уме так же множество всех звезд вообще, а не только видимых нам. Если мы говорим о множестве учеников десятого класса школы N469, то как более общее множество мы можем подразумевать множество вообще всех учеников этой школы, либо же множество всех школьников страны, либо же множество всех людей. Смотря что за задачу мы решаем. Поэтому оказывается полезным ввести следующее определение:

Определение. Универсальным множеством, или универсумом, называется множество всех возможных элементов, имеющих смысл в решаемой задаче.

Пример. Если посмотреть на круги Эйлера, приведенные выше для иллюстрации объединения множеств и считать, что на картинке представлены все интересные нам элементы, то там универсумом в этом случае является множество $U = \{a, b, c, d, e, f, x, y, z\}$ .

Определение. Дополнением множества $A$ (обозначается как $A^C$ ) называется множество элементов универсума, не принадлежащих множеству $A$ : $\forall x, x\in A^C \leftrightarrow x\in U \wedge x \not \in A$ , где $U$ — универсум. Это же можно записать и без упоминания универсума, если предположить, что мы держим его «в уме»: $\forall x, x\in A^C \leftrightarrow x\not \in A$ .

Понятно, что для операции дополнения необходимо строгое задание универсума, иначе она теряет смысл.

Пример. Пусть $U = \{a, b, c, d, e, f, x, y, z\}$ и $A = \{a, b, c, d\}$ . Тогда $A^C = \{e, f, x, y, z\}$ .

Упражнение. Нарисуйте круги Эйлера для дополнения.

Основные понятия мы определили, теперь надо разобраться с их свойствами. Однако прежде чем мы сформулируем нашу первую теорему о множествах, сделаем такое существенное наблюдение: практически все логические операции и операции над множествами находятся в соответствии друг с другом и операции над множествами определяются просто через логические операции. Так, логическое И задает пересечение множеств. Логическое ИЛИ — объединение. Исключающее ИЛИ — симметрическую разность. Отрицание высказываний — дополнение множеств. Эквиваленция — равенство множеств. Импликация — подмножества. В некотором смысле можно так же провести аналогию между универсумом и истинным высказыванием, а так же пустым множеством и ложным высказыванием.

Для продвинутых читателей, которые целиком осилили и поняли первую главу, отмечу, что сильно извратившись (как раз как я люблю), определить можно не только операции над множествами через операции над высказываниями, но и наоборот. Пусть, например, у нас есть теория $T_0$ и формулы $\phi$ и $\psi$ .

Пусть у нас так же есть теория $T_1$ , для которой известно, что $\mathrm{Mod}(T_1) = \mathrm{Mod}(T_0, \phi) \cup \mathrm{Mod}(T_0, \psi)$ . Тогда можно показать (сделайте это самостоятельно), что теория $T_1 = T_0 \cup \{\phi\vee \psi\}$ будет иметь как раз требуемое множество моделей (хотя такая теория может быть конечно не единственна), и именно через свойства моделей при добавлении формул можно определить логическое ИЛИ. Нечто аналогичное мы делали, когда определяли понятие импликации. Нечто аналогичное можно сделать и для всех других логических операций.

Теорема 1. Для операций над множествами справедливы следующие законы:

Ассоциативность:

1) $(A \cap B) \cap C = A \cap (B \cap C)$
2) $(A \cup B) \cup C = A \cup (B \cup C)$
3) $(A \bigtriangleup B) \bigtriangleup C = A \bigtriangleup (B \bigtriangleup C)$

Коммутативность:

4) $A \cap B = B \cap A$
5) $A \cup B = B \cup A$
6) $A \bigtriangleup B = B \bigtriangleup A$
7) $A = B$ равносильно $B = A$ .

Дистрибутивность:

8) $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
9) $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
10) $A \cap (B \bigtriangleup C) = (A \cap B) \bigtriangleup (A \cap C)$

Двойное дополнение:

11) $(A^C)^C = A$

Законы де Моргана:

12) $(A \cap B)^C = A^C \cup B^C$

13) $(A \cup B)^C =A^C \cap B^C$

Еще по мелочам (здесь $U$ — универсальное множество):

14) $A \cap U = A$

15) $A \cap \emptyset = \emptyset$

16) $A \cup U = U$

17) $A \cup \emptyset = A$

18) $A \bigtriangleup \emptyset = A$

19) $A \bigtriangleup U = A^C$

20) $A \cap A^C = \emptyset$

21) $A \cup A^C = U$

22) $A \bigtriangleup A^C = U$

23) $A\cap A = A$

24) $A\cup A = A$

25) $A \bigtriangleup A = \emptyset$

26) $A \cap (A^C \cup B) = A \cap B$

27) $A \cup (A^C \cap B) = A \cup B$

Новенькое для отрицания:

28) $A \setminus B = A \cap B^C$

Свойства подмножеств:

29) Если $A \not \subset B$ , то $A$ и $B^C$ пересекаются.

30) $A \subset A$

31) Транзитивность: $A \subset B \wedge B \subset C \rightarrow A \subset C$ (думаю на всякий случай это свойство полезно проговорить словами: если $A\subset B$ и $B\subset C$ , то $A\subset C$ )

32) $A \subset B\cap C \rightarrow A \subset B$

33) Если $A \subset B$ , то $B^C \subset A^C$ и наоборот.

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

Доказательства всех этих свойств оказываются совершенно элементарны и сводятся, как можно догадаться, к простой переформулировке на языке логики. Давайте докажем, например свойство 10 (мы здесь активно используем задание подмножеств предикатами, которые в нашем случае являются простой логической формулой, а так же дистрибутивность из теоремы 1 главы 1):

$A \cap (B \bigtriangleup C) = \{x|x\in A \wedge x \in B\bigtriangleup C\} = \{x|x\in A \wedge (x \in B \oplus x \in C)\}\\ = \{x|(x\in A \wedge x \in B) \oplus (x \in A \wedge x \in C)\} = \{x|(x\in A \cap B) \oplus (x \in A \cap C)\} \\ = \{x|x\in (A \cap B) \bigtriangleup (A \cap C)\} = (A \cap B) \bigtriangleup (A \cap C)$

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

Остальные свойства докажите самостоятельно в качестве упражнения, а так же нарисуйте круги Эйлера для этих свойств — они должны дать довольно не плохую интуицию относительно свойств множеств (и заодно логики). $\blacksquare$

В завершение параграфа определим еще одну операцию, которая уже не имеет никакого прообраза в логике.

Определение. Булеаном множества $A$ (обозначается $2^A$ ) называется множество всех его подмножеств.

Пример. Пусть $A = \{a, b, c\}$ . Тогда $2^A = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, A\}$ .

Обратите внимание, что всегда $\emptyset \in 2^A$ и $A\in 2^A$ . Так же обратите внимание на то, что булеан, сам являясь множеством, содержит в качестве своих элементов другие множества (это ничему не противоречит — элементами множеств могут быть и другие множества, почему бы и нет?).

Так же важно отметить такой нюанс: если $a \in A$ , то $\{a\} \in 2^A$ , но $a \not \in 2^A$ . Это довольно очевидно: $a\not = \{a\}$ , ведь множество состоящее из одного элемента и сам этот элемент логически разные сущности.

Понятие булеана будет активно использоваться нами в дальнейшем, а пока мы рассмотрим опять же аналогию булеана с логикой (это только для дотошных читателей). Пусть $A$ — некоторое одноэлементное множество. Тогда $2^A = \{\emptyset, A\}$ .Теперь, если рассматривать наши операции над множествами, ограничившись лишь этим булеаном, то если назвать $\emptyset$ ложью, а $A$ истиной, то наша аналогия между логическими операциями и операциями над множествами станет уже не примерной, а совершенно однозначной.

Таким образом можно считать, что логика — это в некотором смысле частный случай теории множеств, которая в свою очередь является обобщением логики. Если рассматривать $A$ , который состоит из многих элементов, то можно в некотором смысле говорить, что $2^A$ — это модель нечеткой логики, где $A$ — истинное высказывание, $\emptyset$ — ложное высказывание, а остальные множества являются истинными высказываниями лишь с некоторой степенью вероятности. Это далеко не самый удобный подход для определения нечеткой логики, и на практике математиками не используется наверное никогда, кроме очень узких областей, однако мы будем иногда обращаться к этому примеру в качестве иллюстраций и более интуитивного понимания отдельных понятий.

Так же у дотошного читателя может возникнуть определенный дискомфорт от той последовательности изложения, которую он до сих пор наблюдает: говоря о логике и предикатах мы ввели понятие множеств, говоря о множествах мы во всю опирались на логигу. Это как в России: чтобы получить работу по специальности, надо иметь опыт работы по этой специальности, а чтобы получить опыт, надо проработать по этой специальности. Такие ситуации допустимы в быту, но не в науке, поэтому порочные круги необходимо разрывать.

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

PS.

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

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

Любые советы и ценные указания крайне приветствуются.

PS2

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

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

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

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

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

В-третьих, надо дописать всякие объясняющие фрагменты текста.

Большинство читателей как я поняла просто не готовы к чтению математической литературы, ибо читали до этого лишь учебники для обезьяноподобных инженеров, где под математикой подразумевалось решение набора стандартных задач, либо вообще читали Хокинга и ждали, что я тоже буду без единой формулы рассказывать псевдонауку на пальцах.

Поэтому думаю написать какое-то дополнительное введение в духе «Как это читать» просто необходимо. Ну то есть я как само собой разумеющееся считала, что нормально, если читатель поймёт процентов 20 материала, и будет просто пропускать непонятные места, а то и вообще читать избирательно — я думаю так все читают математическую литературу, во всяком случае на каком-то этапе математического развития.

Большинство решило разобраться во всём на 100% досконально, и в результате застряло в первой четверти первого параграфа. Желание такое похвально, но вряд ли реализуемо сразу сходу.

Главное требование, которое выдвигается к читателю для понимания материала — это наличие хоть какого-то абстрактного мышления.

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

В итоге первый и второй параграфы начало читать пару тысяч человек, а до последнего не добралось вроде бы ни одного.

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

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

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

Это просто относится к совсем уж минимуму мозговых навыков, и не уметь рассуждать подобным образом должно быть очень сложно по жизни. Если читатель осилит хотя бы правила вывода (именно осознает на уровне интуиции и научится применять), то это ему будет сразу пунктов 15-20 к интеллекту, не иначе.

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

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