Треп о математике 1

Sergei Nickolaev написал(а) к All в Mar 23 14:52:12 по местному времени:

Привет, All!

Я сам читаю постоянно (в последнее время) разные интересные книжки по математике и, что особенно важно, решаю (или пытаюсь решать) всякие интересные задачки. Совершенно искренне убежден в том, что если мозги не упражнять постоянно, то (в нашем возрасте) они весьма быстро "ржавеют". Недавно своему однокласснику и однокурснику переслал те книжки, что сейчас читаю, в ответ получил: "как громко мозги скрипят на этих задачках". Он всегда со всеми задачами справлялся сильно быстрее меня ;-)
Есть у меня подозрение, что подобные развлечения могут быть полезны и нашему старперскому сообществу :-) Если кому-то здесь будет интересно - продолжу, нет - я могу всем этим заниматься и без соучастников.
Почему сначала теория множеств - примерно с последней четверти 19-го века она стала одним из столпов, на которых нынешняя математика стоит. И задачки там интересные :-) Для меня лично - большая часть того, что я сейчас читаю, знакома мне давно, но давность этого знакомства - примерно полвека, так, что многое читается по принципу "какая хорошая болезнь склероз - ничего не болит, но каждый день столько нового ...".

Итак, основные и простейшие положения теории множеств:
1. Исследуется одна из простейших абстрактных структур: есть всяческие объекты и их совокупности. Совокупности называются множествами, объекты - элементами множеств. Есть хорошая иллюстрация (не очень работает, как аналогия): сундук, в котором лежат всякие разные вещи. Сундук вместе с содержимым - множество. Предметы в сундуке - элементы множества. Элемент принадлежит множеству, если он лежит в сундуке. Хорошая иллюстрация пустого множества: сундук остается сундуком, даже если в нем ничего не лежит. Элемент множества сам может быть множеством (в сундуке иожет лежать сундучок поменьше). Здесь работает принцип: "вассал моего вассала - не мой вассал", то есть если множество B является элементом множества A, то элементы множества B не обязаны быть (хотя и могут быть) элеиентами множества A.
Существенный момент - все элементы множества - разные.
Во многих случаях есть какая-то возможность иметь список элементов множества. В таких случаях множество записывается так: A = {a0, a1, ...}. Для пустого множества есть специальное обозначение - перечеркнутый кружок. Здесь такого символа нет, поэтому я буду использовать {}. На мой взгляд это обозначение лучше типового :-)
Все элементы множества разные - означает, что запись типа {1,1,1} - кривая. Практически удобно считать, что множества {1,1,1}, {1,1} и {1} совпадают.

2. Возможна ситуация, что все элементы множества B являются заодно и элементами
множества A (можно перефразировать: в B нет никаких элементов кроме некоторых элементов множества A). Такая ситуация обозначается: B является подмножеством A. Пустое множество является подмножеством любого множества. Любое множество является своим подмножеством. Конструкция "множество всех подмножеств множества A" - является вполне законной и весьма важной в теории множеств.

3. Множества A и B равны, если они состоят из одних и тех же элементов. Другая формулировка: A и B равны если каждое из них является подмножеством другого.

4. Есть совершенно естественные операции над множествами: Объединением A и B называется множество C, каждый элемент которого является или элементом A или элементом B. Пересечением A и B называется множество C, каждый элемент которого является элементом A и элементом B. Разностью A и B называется множество C, каждый элемент которого является элементом A, но не является элементом B.
Объединение обычно обозначается символом, похожим на латинскую букву U, такого символа здесь нет, буду использовать букву U. Пересечение обычно обозначается как нечто похожее на перевернутую букву U, буду использовать букву П. Для разности используется символ \.

5. Есть еще (несколько реже используемая) операция - симметрическая разность. Множество C есть симметрическая разность множеств A и B, если оно состоит из элементов A, не являющиеся элеметами B и элементов B, не являющихся элементами A. ( Вот и первая задачка - записать симметрическую разность через объединение, пересечение и разность. Вторая задача - доказать, что симметрическая разность является ассоциативной операцией, т.е. в симметрической разности трех множеств неважно, как расставить скобки).

Задачи на первый раз:
(Первые две практически для прикола. Или для того, чтобы понять, понял ли вообще что-либо :-)

1. Старейший математик среди шахматистов и старейший шахматист
среди математиков - это один или тот же человек или (возможно) разные?
2. Лучший математик среди шахматистов и лучший шахматист среди
математиков - это один или тот же человек или (возможно) разные?
3. Каждый десятый математик - шахматист, а каждый шестой шахматист - математик. Кого больше - математиков или шахматистов - и во сколько раз?
4. Докажите, что если какое-то равенство (содержащее переменные
для множеств и операции U, П и \) неверно, то можно найти контрпример
к нему, в котором множества пусты или состоят из одного элемента.
5. Сколько различных выражений для множеств можно составить из
переменных A и B с помощью (многократно используемых) операций пе-
ресечения, объединения и разности? (Два выражения считаются одинако-
выми, если они равны при любых значениях переменных.) Тот же вопрос
для трёх множеств и для n множеств. (Ответ в общем случае: 2^(2^n - 1))
6. Нерешенная задача: задача 5 для случая, когда используются только объединение и пересечение. Легко считается для 2-х или 3-х множеств, труднее для большего числа множеств, но общей формулы пока никто не придумал. Эту задачу называют также задачей о числе монотонных булевых функций от n аргументов.
7. Сколько существует подмножеств у n-элементного множества?

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

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

Еще дальше - не планирую принципиально, запросто может оказаться, что все это хозяйство здесь не интересно никому, кроме меня :-)

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)