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

Sergei Nickolaev написал(а) к All в Apr 23 12:58:42 по местному времени:

Привет, All!

Продолжение.

Два множества называют равномощными, если между ними можно установить взаимно однозначное соответствие, при котором каждому элементу одного множества соответствует ровно один элемент другого.
Для конечных множеств это означает, что в них одинаковое число элементов, но определение имеет смысл и для бесконечных множеств.
Например, отрезки [0, 1] и [0, 2] равномощны, поскольку отображение x -> 2x осуществляет искомое соответствие.

Простые задачки:

1. Докажите, что любые два интервала (a, b) и (c, d) на прямой равномощны.
2. Докажите, что любые две окружности на плоскости равномощны. Докажите, что любые два круга на плоскости равномощны.
3. Докажите, что полуинтервал [0, 1) равномощен полуинтервалу (0, 1].

Задачка чуть сложнее: доказать, что интервал (0, 1) и луч (0,+бесконечность) равномощны.
Соответствие x -> 1/x - взаимно однозначное для (0, 1) и (1,+бесконечность), а соответствие x -> (x-1) - взаимно однозначное для (1,+бесконечность) и (0,+бесконечность), получаем: x -> (1/x)-1 - искомое взаимно однозначное соответствие.

Еще задачки разной сложности:

4. Множество бесконечных последовательностей нулей и единиц равномощно множеству всех подмножеств натурального ряда.
5. Возьмем четыре цифры: 0, 1, 2, 3. Множество бесконечных последовательностей из этих цифр равномощно множеству бесконечных последовательностей нулей и единиц.
6. Множество бесконечных последовательностей цифр 0, 1, 2 равномощно множеству бесконечных последовательностей цифр 0 и 1.
7. Обобщение задачи 4: множество подмножеств любого множества W (оно обычно обозначается P(W)) равномощно множеству всех функций, которые ставят в соответствие каждому элементу из W одно из чисел 0 и 1.

Немного теоретического трепа: в математике есть понятие "отношение". Его можно определить строго, но это - потом. По сути это - утверждение об упорядоченной паре элементов некоторого множества, которое для каких-то пар может быть истинно, для каких-то - ложно. (на самом деле я определил то, что называется "двуместным отношением", в математике рассматриваются и многоместные, но пока они нам не нужны).
Примеры: равенство для натуральных чисел (=), 3=5 - ложно, 7=7 - истинно; отношение "больше" (>) для натуральных чисел, 2>5 - ложно, 5>2 - истинно, 2>2 - ложно.
"Равномощность" - отношение между множествами. Относится к категории "отношений эквивалентности".
Отношение ~ называется отношением эквивалентности, если оно обладает следующими тремя свойствами:
1. Рефлексивность (всегда верно x~x).
2. Симметричность (если верно x~y, то верно и y~x).
3. Транзитивность (из x~y и y~z следует, что x~z).
Примеры отношений эквивалентности: равенство чисел; подобие фигур на плоскости; одинаковый остаток от деление на 3 для натуральных чисел.
А вот отношение "скрещиваемость" для (популяций) живых организмов отношением эквивалентности не является, почему понятие вида не может быть четко определено на основании этого отношения ...

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

Alexander Hohryakov написал(а) к Sergei Nickolaev в Apr 23 15:48:22 по местному времени:

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

Понедельник 10 Апреля 2023 12:58, ты писал(а) All, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+6433f1a2:


SN> 1. Докажите, что любые два интервала (a, b) и (c, d) на прямой
SN> равномощны. 2. Докажите, что любые две окружности на плоскости
SN> равномощны. Докажите, что любые два круга на плоскости равномощны. 3.
SN> Докажите, что полуинтервал [0, 1) равномощен полуинтервалу (0, 1].

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

SN> Задачка чуть сложнее: доказать, что интервал (0, 1) и луч
SN> (0,+бесконечность) равномощны. Соответствие x -> 1/x - взаимно
SN> однозначное для (0, 1) и (1,+бесконечность), а соответствие x -> (x-1)
SN> - взаимно однозначное для (1,+бесконечность) и (0,+бесконечность),
SN> получаем: x -> (1/x)-1 - искомое взаимно однозначное соответствие.

SN> Еще задачки разной сложности:

SN> 4. Множество бесконечных последовательностей нулей и единиц равномощно
SN> множеству всех подмножеств натурального ряда.
SN> 5. Возьмем четыре цифры:
SN> 0, 1, 2, 3. Множество бесконечных последовательностей из этих цифр
SN> равномощно множеству бесконечных последовательностей нулей и
SN> единиц.

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

SN> 6. Множество бесконечных последовательностей цифр 0, 1, 2
SN> равномощно множеству бесконечных последовательностей цифр 0 и 1. 7.

А это кажется настолько само собой разумеющимся, что в доказательстве не нуждается.

SN> Обобщение задачи 4: множество подмножеств любого множества W (оно
SN> обычно обозначается P(W)) равномощно множеству всех функций, которые
SN> ставят в соответствие каждому элементу из W одно из чисел 0 и 1.


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

Sergei Nickolaev написал(а) к Alexander Hohryakov в Apr 23 14:08:12 по местному времени:

Привет, Alexander!

SN>> 1. Докажите, что любые два интервала (a, b) и (c, d) на прямой
SN>> равномощны. 2. Докажите, что любые две окружности на плоскости
SN>> равномощны. Докажите, что любые два круга на плоскости
SN>> равномощны. 3. Докажите, что полуинтервал [0, 1) равномощен
SN>> полуинтервалу (0, 1].

AН> Эти задачки я помню из "Детской энциклопедии". К ним была картинка:
AН> лампа, по-научному "точечный источник света", отрезок, (окружность или
AН> круг) и тени от них. Каждой точке отрезка (окружности или круга)
AН> соответствует точка тени.

Все верно. Математик к этому добавляет аналитическое выражение для взаимно-однозначного соответствия. Строятся, разумеется, для этих задачек просто. Для 1-й, например, x->c+((d-c)/(b-a))*(x-a). Для окружностей и кругов - в полярных координатах.

SN>> 4. Множество бесконечных последовательностей нулей и единиц
SN>> равномощно множеству всех подмножеств натурального ряда.

4 и 7 задачи - просто напоминание о характеристических функциях. Любая функция, определенная на элементах некоторого множества и принимающая значения 0 и 1 - является характеристической функцией некоторого подмножества.

SN>> 5. Возьмем четыре цифры: 0, 1, 2, 3. Множество бесконечных
SN>> последовательностей из этих цифр равномощно множеству бесконечных
SN>> последовательностей нулей и единиц.

AН> А тут мне вспомнились системы счисления. Множество чисел, записанных в
AН> десятичной, двоичной, четверичной системах - одно и то же множество.

Здесь есть нюанс. Бесконечные последовательности цифр соответствуют записям вещественных чисел, но там есть повторы (разные формально записи одного и того же числа, например 0.0111... и 0.100...). Для установления однозначного соответствия требуются некоторые технические трюки. Для конкретно этой задачи все можно сделать проще:
Табличка:
00 - 0
01 - 1
10 - 2
11 - 3
Последовательность цифр 0, 1, 2, 3 по этой таблице преобразуется в последовательность нулей и единиц однозначно. Последовательность нулей и единиц преобразуется в последовательность цифр 0, 1, 2, 3 последовательным выделением пар.

SN>> 6. Множество бесконечных последовательностей цифр 0, 1, 2
SN>> равномощно множеству бесконечных последовательностей цифр 0 и 1.

AН> А это кажется настолько само собой разумеющимся, что в доказательстве
AН> не нуждается.

Здесь тоже есть свой нюанс: если воспользоваться, как в предыдущей задаче, двоичными записями цифр
00 - 0
01 - 1
10 - 2,
то справа налево все тривиально, но слева направо, увы :-(. Не все двоичные последовательности преобразуются. Помогает фокус, называемый "префиксная запись".
Используется табличка
0 - 0
10 - 1
11 - 2.
Нетрудно сообразить, что любая последовательность нулей и единиц однозначно разбивается на такие блоки.

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

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

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

Суббота 15 Апреля 2023 14:08, ты писал(а) мне, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+643a900f:

SN>>> 1. Докажите, что любые два интервала (a, b) и (c, d) на прямой
SN>>> равномощны. 2. Докажите, что любые две окружности на плоскости
SN>>> равномощны. Докажите, что любые два круга на плоскости
SN>>> равномощны. 3. Докажите, что полуинтервал [0, 1) равномощен
SN>>> полуинтервалу (0, 1].

AН>> Эти задачки я помню из "Детской энциклопедии". К ним была
AН>> картинка: лампа, по-научному "точечный источник света", отрезок,
AН>> (окружность или круг) и тени от них. Каждой точке отрезка
AН>> (окружности или круга) соответствует точка тени.

SN> Все верно. Математик к этому добавляет аналитическое выражение для
SN> взаимно-однозначного соответствия. Строятся, разумеется, для этих
SN> задачек просто. Для 1-й, например, x->c+((d-c)/(b-a))*(x-a). Для
SN> окружностей и кругов - в полярных координатах.

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

SN>>> 5. Возьмем четыре цифры: 0, 1, 2, 3. Множество бесконечных
SN>>> последовательностей из этих цифр равномощно множеству
SN>>> бесконечных последовательностей нулей и единиц.

AН>> А тут мне вспомнились системы счисления. Множество чисел,
AН>> записанных в десятичной, двоичной, четверичной системах - одно и
AН>> то же множество.

SN> Здесь есть нюанс. Бесконечные последовательности цифр соответствуют
SN> записям вещественных чисел,

Не натуральных?


SN>>> 6. Множество бесконечных последовательностей цифр 0, 1, 2
SN>>> равномощно множеству бесконечных последовательностей цифр 0 и 1.

AН>> А это кажется настолько само собой разумеющимся, что в
AН>> доказательстве не нуждается.

SN> Здесь тоже есть свой нюанс: если воспользоваться, как в предыдущей
SN> задаче, двоичными записями цифр 00 - 0 01 - 1 10 - 2, то справа налево
SN> все тривиально, но слева направо, увы :-(. Не все двоичные
SN> последовательности преобразуются.

Какие не?


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

Sergei Nickolaev написал(а) к Alexander Hohryakov в Apr 23 19:40:34 по местному времени:

Привет, Alexander!

Ответ на сообщение Alexander Нohryakov (2:6035/3.8) к Sergei Nickolaev, написанное 16 апр 23 в 23:46:

SN>>>> 5. Возьмем четыре цифры: 0, 1, 2, 3. Множество бесконечных
SN>>>> последовательностей из этих цифр равномощно множеству
SN>>>> бесконечных последовательностей нулей и единиц.

AН>>> А тут мне вспомнились системы счисления. Множество чисел,
AН>>> записанных в десятичной, двоичной, четверичной системах - одно и
AН>>> то же множество.

На самом деле ты совершенно прав: Приписываем перед последовательностью 0. - получаем запись некоторого вещественного числа из отрезка [0,1] в соответствующей системе счисления. Здесь есть свой нюанс: некоторые рациональные числа будут представлены дважды (можно считать задачкой - какие). Еще - мы пока не разбирали, почему добавление к континууму (или вычитание из него) счетного множества не меняет мощность.

SN>> Здесь есть нюанс. Бесконечные последовательности цифр
SN>> соответствуют записям вещественных чисел,

AН> Не натуральных?

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

SN>>>> 6. Множество бесконечных последовательностей цифр 0, 1, 2
SN>>>> равномощно множеству бесконечных последовательностей цифр 0 и
SN>>>> 1.

AН>>> А это кажется настолько само собой разумеющимся, что в
AН>>> доказательстве не нуждается.

SN>> Здесь тоже есть свой нюанс: если воспользоваться, как в
SN>> предыдущей задаче, двоичными записями цифр 00 - 0 01 - 1 10 - 2,
SN>> то справа налево все тривиально, но слева направо, увы :-(. Не
SN>> все двоичные последовательности преобразуются.

AН> Какие не?

Где выскочит пара 11. Тот вариант, что я приводил, позволяет однозначно разбить последовательность на одноциферные (0) и двухциферные (10 и 11) блоки и заменить на цифры 0, 1 и 2

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

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

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

Понедельник 17 Апреля 2023 19:40, ты писал(а) мне, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+643d7ba8:


SN> На самом деле ты совершенно прав: Приписываем перед
SN> последовательностью 0. - получаем запись некоторого вещественного
SN> числа из отрезка [0,1] в соответствующей системе счисления. Здесь есть
SN> свой нюанс: некоторые рациональные числа будут представлены дважды
SN> (можно считать задачкой - какие).

Хрестоматийный пример 0.999999999 и 1.000000000

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

Сорок лет назад что-то, помню, было, но в инженерских трудах не пригодилось и, соответственно, забылось. Часть вспоминается, но не всё, многое узнаЮ заново.

SN>>>>> 6. Множество бесконечных последовательностей цифр 0, 1, 2
SN>>>>> равномощно множеству бесконечных последовательностей цифр 0 и
SN>>>>> 1.

AН>>>> А это кажется настолько само собой разумеющимся, что в
AН>>>> доказательстве не нуждается.

SN>>> Здесь тоже есть свой нюанс: если воспользоваться, как в
SN>>> предыдущей задаче, двоичными записями цифр 00 - 0 01 - 1 10 - 2,
SN>>> то справа налево все тривиально, но слева направо, увы :-(. Не
SN>>> все двоичные последовательности преобразуются.

AН>> Какие не?

SN> Где выскочит пара 11. Тот вариант, что я приводил, позволяет
SN> однозначно разбить последовательность на одноциферные (0) и
SN> двухциферные (10 и 11) блоки и заменить на цифры 0, 1 и 2

Виноват, погорячился (с)


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