Треп о математике 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)

Alexander Hohryakov написал(а) к Sergei Nickolaev в Mar 23 11:17:30 по местному времени:

Здpавствуй, Sergei!

Воскресенье 12 Марта 2023 14:52, ты писал(а) All, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+640ded9c:

SN> 4. Докажите, что если какое-то равенство (содержащее переменные для
SN> множеств и

Что такое "переменная для множеств"?


С уважением - Alexander
--- -

Sergei Nickolaev написал(а) к Alexander Hohryakov в Mar 23 13:50:30 по местному времени:

Привет, Alexander!

SN>> 4. Докажите, что если какое-то равенство (содержащее переменные
SN>> для множеств и

AН> Что такое "переменная для множеств"?

Это значит, что переменная может принимать множества (и только их), как значения. Здесь полная аналогия с арифметическими равенствами, содержащими переменные для чисел.
Скажем, (x+y)^2=x^2+2xy+y^2 - равенство, содержащее переменные для чисел и операции сложения, умножения и возведения в степень. Является тождеством - превращается в истинное утверждение о числах при подстановке любых конктретных чисел вместо переменных x и y. А вот (x+y)^2=x^2+xy - равенство, тождеством не являющееся, можно привести контрпример x=1, y=1.
Если такое объяснение оставляет непонятности - могу сделать более развернутое ...
Задачка мне очень понравилась, я не знал, что при построении контрпримеров для таких равенств можно обойтись пустыми и одноэлементными множествами. Еще не так давно разбирался с построениями контрпримеров с внуком, обычно мы совместными усилиями строили более громоздкие конструкции :-)

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

Alexander Hohryakov написал(а) к Sergei Nickolaev в Mar 23 20:46:50 по местному времени:

Здpавствуй, Sergei!

Понедельник 13 Марта 2023 13:50, ты писал(а) мне, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+640f06ad:

SN> Задачка мне очень понравилась, я не знал, что при построении
SN> контрпримеров для таких равенств можно обойтись пустыми и
SN> одноэлементными множествами. Еще не так давно разбирался с
SN> построениями контрпримеров с внуком, обычно мы совместными усилиями
SN> строили более громоздкие конструкции :-)

Разве она не сводится к банальному {}U{}=={} {}П{}=={} {}\{}=={}, соответственно любая комбинация операций даёт верное равенство?


С уважением - Alexander
--- -

Sergei Nickolaev написал(а) к Alexander Hohryakov в Mar 23 11:32:20 по местному времени:

Привет, Alexander!

SN>> Задачка мне очень понравилась, я не знал, что при построении
SN>> контрпримеров для таких равенств можно обойтись пустыми и
SN>> одноэлементными множествами. Еще не так давно разбирался с
SN>> построениями контрпримеров с внуком, обычно мы совместными
SN>> усилиями строили более громоздкие конструкции :-)

AН> Разве она не сводится к банальному {}U{}=={} {}П{}=={} {}\{}=={},
AН> соответственно любая комбинация операций даёт верное равенство?

Ты решил совсем другую задачу :-). В исходной задаче речь шла о том, что если равенство - не тождество, то должен быть контрпример, то есть конкретный набор множеств, для которого равенство не выполняется. Требовалось показать, что такой контрпример можно составить из пустых и одноэлементных множеств.
Пример: равенство A \ (B U C) = A \ (B П C). С первого взгляда видно, что не тождество. Контрпример: A = {1}, B = {1}, C = {}. Результат слева будет {}, справа {1}.
Подсказка: способ решения задачи можно увидеть, если внимательно посмотреть на диаграммы Венна. Что за штука - находится в Интернете сполпинка :-)

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

Alexander Hohryakov написал(а) к Sergei Nickolaev в Mar 23 11:43:54 по местному времени:

Здpавствуй, Sergei!

Вторник 14 Марта 2023 11:32, ты писал(а) мне, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+64103772:

SN> Ты решил совсем другую задачу :-).

Я ж не знал, что такое "контрпример".

SN> Подсказка: способ решения задачи можно увидеть, если внимательно
SN> посмотреть на диаграммы Венна. Что за штука - находится в Интернете
SN> сполпинка :-)

Диаграмму Вейча помню, диаграмму Венна не помню. Будем искать... :-)


С уважением - Alexander
--- -

Alexander Hohryakov написал(а) к Sergei Nickolaev в Mar 23 12:53:38 по местному времени:

Здpавствуй, Sergei!

Воскресенье 12 Марта 2023 14:52, ты писал(а) All, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+640ded9c:

SN> 7. Сколько существует подмножеств у n-элементного множества?

У 1-элементного множества 2 подмножества: оно само и пустое множество, которое является подмножеством любого множества. У (m+1)-элементного вдвое больше, чем у m-элементного: к каждому из них можно или добавить эдемент номер (m+1) или не добавлять. У 2-элементного 4 подмножеств, у 3-элементного 8, и т. д. 2^n


С уважением - Alexander
--- -

Alexander Hohryakov написал(а) к Sergei Nickolaev в Mar 23 13:02:44 по местному времени:

Здpавствуй, Sergei!

Воскресенье 12 Марта 2023 14:52, ты писал(а) All, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+640ded9c:


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

SN> 1. Старейший математик среди шахматистов и старейший шахматист
SN> среди математиков - это один или тот же человек или (возможно) разные?
SN> 2. Лучший математик среди шахматистов и лучший шахматист среди
SN> математиков - это один или тот же человек или (возможно) разные?

Ясно, что математики, не играющие в шахматы и шахматисты, не играющие в математику нас не интересуют. Интересуют только универсалы: У = М П Ш = Ш П М.


С уважением - Alexander
--- -

Sergei Nickolaev написал(а) к Alexander Hohryakov в Mar 23 16:40:18 по местному времени:

Привет, Alexander!

SN>> 1. Старейший математик среди шахматистов и старейший шахматист
SN>> среди математиков - это один или тот же человек или (возможно)
SN>> разные? 2. Лучший математик среди шахматистов и лучший шахматист
SN>> среди математиков - это один или тот же человек или (возможно)
SN>> разные?

AН> Ясно, что математики, не играющие в шахматы и шахматисты, не играющие
AН> в математику нас не интересуют. Интересуют только универсалы: У = М П
AН> Ш = Ш П М.

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

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

Sergei Nickolaev написал(а) к Alexander Hohryakov в Mar 23 16:53:52 по местному времени:

Привет, Alexander!

SN>> 7. Сколько существует подмножеств у n-элементного множества?

AН> У 1-элементного множества 2 подмножества: оно само и пустое множество,
AН> которое является подмножеством любого множества. У (m+1)-элементного
AН> вдвое больше, чем у m-элементного: к каждому из них можно или добавить
AН> эдемент номер (m+1) или не добавлять. У 2-элементного 4 подмножеств, у
AН> 3-элементного 8, и т. д. 2^n

Здесь все правильно :-)

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