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

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

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

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

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

SN> Верно, но чуть-чуть недо :-)

Я не хотел лишать возможности высказаться других математиков :-)


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

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

Привет, Alexander!

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

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

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

Какие из равенств являются тождествами, а какие нет:
а) (A П B) U C = (A U C) П (B U C)
б) (A U B) П C = (A П С) U (B П C)
в) (A U B) \ C = (A \ C) U B
г) (A П B) \ C = (A \ C) П B
д) A \ (B U C) = (A \ B) П (A \ C)
е) A \ (B П C) = (A \ B) U (A \ C)

Эту задачку удобнее всего решать на диаграмме Венна для 3-х множеств. И идея для той задачки, скорее всего, будет видна ...

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

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

Привет, Alexander!

SN>> Верно, но чуть-чуть недо :-)

AН> Я не хотел лишать возможности высказаться других математиков :-)

Давай предоставим им возможность высказаться насчет задачи 3. Она примерно на ту же тему но чуть более высокоинтеллектуальна :-)

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

Michael Olshevski написал(а) к Sergei Nickolaev в Mar 23 21:11:45 по местному времени:

Пpивет, Sergei!

Sunday 12 March 2023 14:52, Sergei Nickolaev wrote to All:

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

То есть сундук с одинаковыми бильярдными шарами -- не множество? А кто он (и они) тогда?

Мои наилучшие пожелания,
Michael.


--- GoldED+/W32 1.1.5-021109

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

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

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

SN> Для того, чтобы понять в чем дело и придумать идею доказательства,
SN> достаточно повозиться с диаграммой для 3-х множеств. Для большего
SN> числа их труднее рисовать, да и разбираться на более сложной картинке
SN> труднее. Мне стоило предложить перед этой задачей другую задачу из
SN> этой же книжки:

Как я понимаю, даже трёх множеств много. Любая комбинация операций над множествами сводится к (((AB)*C)*D)*... = ((M*C)*D)... = N*D =... Z ( - U, П или \) Для любой из трёх операций (контр)пример из множеств, состоящих из одного и/или ни одного элемента подобрать можно, следовательно и для любой комбинации операций можно подобрать подходящий пример, если я чего-то не упустил в своих рассуждениях.


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

Sergei Nickolaev написал(а) к Michael Olshevski в Mar 23 14:47:42 по местному времени:

Привет, Michael!

SN>> Существенный момент - все элементы множества-разные.

MO> То есть сундук с одинаковыми бильярдными шарами -- не множество? А кто
MO> он (и они) тогда?

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

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

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

Привет, Alexander!

SN>> Для того, чтобы понять в чем дело и придумать идею
SN>> доказательства, достаточно повозиться с диаграммой для 3-х
SN>> множеств. Для большего числа их труднее рисовать, да и
SN>> разбираться на более сложной картинке труднее. Мне стоило
SN>> предложить перед этой задачей другую задачу из этой же книжки:

AН> Как я понимаю, даже трёх множеств много. Любая комбинация операций над
AН> множествами сводится к (((AB)*C)*D)*... = ((M*C)*D)... = ND =...
AН> Z (* - U, П или \) Для любой из трёх операций (контр)пример из
AН> множеств, состоящих из одного и/или ни одного элемента подобрать
AН> можно, следовательно и для любой комбинации операций можно подобрать
AН> подходящий пример, если я чего-то не упустил в своих рассуждениях.

После бани и 2-х л пива мне сложно разобрать :-) Завтра еще посмотрю ...

На самом деле идея диаграмм Венна - графическое изображение совершенно замечательного разбиения объединения множеств на некий набор непересекающихся подмножеств. Это разбиение обладает удивительным свойством: для любого подмножества определяемого любым выражением из переменных для множеств A1...An с операциями U, П, \, каждый кусочек в этом разбиении либо полностью входит в подмножество, либо полностью не входит. Если два выражения не равны тождественно, то в разбиении есть кусок, входящий в подмножество для одного и не входящий в подмножество для другого. Контрпример строится так: населяем этот кусок единственным элементом, остальные куски оставляем пустыми. Получаем контрпример из одноэлементных и пустых множеств. На диаграмме Венна для трех множеств это очень легко пронаблюдать ...
Что в задаче остается: описать (аналитически) подмножества - куски разбиения для диаграммы Венна для n множеств; показать, что любой кусок либо полностью входит в подмножество, описываемое любым выражением из A1...An с использованием операций U, П, \, либо с ним не пересекается.
Здесь же ключик к решению задачи о количестве не тождественно равных выражений вышеуказанного вида.

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

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

Привет, Alexander!

AН> Любая комбинация операций над
AН> множествами сводится к (((AB)*C)*D)*... = ((M*C)*D)... = ND =...
AН> Z (* - U, П или \)

Такое утверждение неочевидно и требует доказательства. Я возиться пока не пробовал, но у меня есть подозрение, что можно подобрать выражение, которое к такому виду привести невозможно. Но могу и ошибаться.
Есть общая рекурсивная процедура построения произвольных синтактически корректных выражений из переменных A1, ... An и набора операций U, П и \.
Именно:

1. Для любого 1 <= i <= n Ai корректное выражение.
2. Если E1 и E2 - корректные выражения, то
(E1) U (E2)
(E1) П (E2)
(E1) \ (E2)
(E2) \ (E1)
корректные выражения.

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

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

Sergei Nickolaev написал(а) к Alexander Hohryakov в Mar 23 15:21:24 по местному времени:

Привет, Alexander!

SN>> Для того, чтобы понять в чем дело и придумать идею
SN>> доказательства, достаточно повозиться с диаграммой для 3-х
SN>> множеств. Для большего числа их труднее рисовать, да и
SN>> разбираться на более сложной картинке труднее. Мне стоило
SN>> предложить перед этой задачей другую задачу из этой же книжки:

AН> Как я понимаю, даже трёх множеств много. Любая комбинация операций над
AН> множествами сводится к (((AB)*C)*D)*... = ((M*C)*D)... = ND =...
AН> Z (* - U, П или \) Для любой из трёх операций (контр)пример из
AН> множеств, состоящих из одного и/или ни одного элемента подобрать
AН> можно, следовательно и для любой комбинации операций можно подобрать
AН> подходящий пример, если я чего-то не упустил в своих рассуждениях.

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

Я в следующем сообщении расскажу, как я решил задачу (намеки на это уже делал).

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

Sergei Nickolaev написал(а) к All в Mar 23 15:39:58 по местному времени:

Привет, All!

Итак, задача была такая: Рассматриваются равенства, в которых по обе стороны от = выражения, составленные из переменных для множеств A1, ... An и операций U, П и \. Требуется доказать, что, если равенство не является тождеством (равенство есть тождество означает: остается верным, какие бы мы множества не подставляли вместо переменных), то можно предъявить контрпример (набор конкретных множеств, при подстановке которых вместо переменных, равенство оказывается не верным), состоящий только из пустых и одноэлементных множеств.

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

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

Я уже писал, что ключиком к этой задачке являются диаграммы Венна. Надеюсь, что интересующиеся заглянули куда-нибудь, объяснениями Интернет полон. Классическая картинка - для случая n=3, три пересекающихся круга. На самом деле, собственно диаграммы - иллюстрация, для рассуждений лучше использовать выражения. Да и для n > 3 картинки становятся все менее наглядными.

Я приведу набор выражений для n=3, надеюсь, что повторить для общего случая вам будет нетрудно :-) A1, A2, A3 - переменные для множеств. Буквы E буду использовать для выражений.

Итак:
1-я пачка выражений: E1 = A1 \ (A2 U A3); E2 = A2 \ (A1 U A3); E3 = A3 \ (A1 U A2). Множества, которые определяют эти выражения: все элементы одного из множеств минус элементы остальных множеств, то есть элементы, принадлежащие ровно одному множеству. На картинке это - самые внешние части диаграммы.
2-я пачка выражений: E4 = (A1 П A2) \ A3; E5 = (A1 П A3) \ A2; E6 = (A2 П A3) \ A1. Смысл - элементы, принадлежащие ровно двум множествам. На картинке это - чуть более внутренние части диаграммы.
3-я пачка выражений (из одного выражения): E7 = A1 П A2 П A3. Здесь - элементы, принадлежащие всем трем множествам. На диаграмме - самая внутренняя часть.

Очевидно, что :-):
1. i не равно j => Ei П Ej = {}
2. E1 U ... U E7 = A1 U A2 U A3
3. любое выражение из A1, A2, A3 с операциями U, П, \ является подмножеством A1 U A2 U A3 (намек: неоткуда взяться дополнительным элементам).

Самое главное утверждение в этом рассмотрении:
Для любого выражения F из переменных A1, A2, A3 с операциями U, П, \ и для любого из выражений E1 ... E7 выполняется одно из двух:
1. Множество, определяемое Ei не пересекается с множеством, определяемым F (в соответствии с одной из оговорок в начале - Ei не пересекается с F)
2. Ei является подмножеством F.

(Существенный для нас очевидный вывод: F является объединением каких-то Ei, для случая n=3 - объединение какого-то количества из 7 множеств, всего 128 вариантов не эквивалентных выражений. Для общего случая: множеств Ei 2^n-1 штук. Это сумма биноминальных коэффициентов за исключением одного, равного 1. Не эквивалентных между собой выражений в общем случае 2^(2^n-1). в качестве бонуса получится решение следующей задачи).

Доказательство главного утверждения (индукция по построению выражения F):
1. База (для простейшего выражения). F=A1 или F=A2 или F=A3. Рассмотрения для A1 - достаточно, другие два случая получаются заменой индексов.
E1 = A1 \ (A2 U A3) очевидно подмножество A1
E2 = A2 \ (A1 U A3) столь же очевидно не пересекается с A1
E3 = A3 \ (A1 U A2) - аналогично
E4 = (A1 П A2) \ A3 - подмножество A1
E5 = (A1 П A3) \ A2 - подмножество A1
E6 = (A2 П A3) \ A1 - не пересекается с A1
E7 = A1 П A2 П A3 - подмножество A1
2. Индукционный переход (по построению выражений). Докажем, что если утверждение верно для F1 и F2, то оно верно для
F = (F1) U (F2)
F = (F1) П (F2)
F = (F1) \ (F2)
Для E1:
Если E1 - подмножество F1 или F2, то оно - подмножество F
Если E1 не пересекается с F1 и с F2, то оно не пересекается с F
Остальные варианты столь же очевидны :-)

Собственно решение задачи: Если равенство F1 = F2 - не тождество, то среди множеств, на которые диаграмма Венна делит объединение A1 U ... U An есть хотя бы одно, являющееся подмножеством одной стороны равенства и не являющееся подмножеством другой стороны. Берем его одноэлементным множеством, все остальные - пустыми. Из этого мигом вычисляется, какими будут A1, ... An, очевидно, что все они будут либо пустыми, либо одноэлементными.

Псевдофилософская болтовня на тему:
Выражения из A1, ... An с операциями объединения, пересечения и разности можно строить любой длины и сложности. Казалось бы этим бесконечным разнообразием выражений можно "пощупать" множества сколь угодно детально. Это рассмотрение показывает, что "фигвам", детали мельче частей диаграммы Венна - не видны.
Как задачку могу предложить посмотреть на 3 подмножества натуральных чисел: делящиеся на 2, делящиеся на 3 и делящиеся на 5. Какие множества будут частями диаграммы Венна? Какие множества можно описать с помощью операций (U, П и \) над этими тремя подмножествами натуральных чисел.

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

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