Наверняка уже все знают, но чтобы никто точно не пропустил, тоже напишу.

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

В прошлый раз курсов предлагалось три:

1. Artificial Intelligence
2. Databases
3. Machine Learning

Внимание общественности главным образом привлек Artificial Intelligence по трем причинам:

1. Название курса «искусственный интеллект» звучит круто.
2. Ведут курс прославившиеся ученые Peter Norwig и Sebastian Thrun (у обоих послужные списки очень обширные, но общественностью наиболее была замечена попбеда в DARPA Grand Challenge робота Stanley, разработанного командой Себастьяна).
3. В конце обещали дать сертификат об окончании курса, что многими было воспринято чуть ли ни как диплом Стэнфорда (на деле это просто электронный документ, подписанный цифровой подписью Питера и Себастьяна, что к Стэнфорду никакого юридического отношения не имеет).

Собственно на деле курс по AI оказался наиболее слабым: слишком много времени уделялось подстановке цифр в формулы, слишком частные случаи рассматривались, слишком низкий уровень математической подготовки студентов предполагался, домашние задания сводились так же к подстановке цифр в формуле и не предполагали никакой интеллектуальной работы.

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

Для сравнения, в МИФИ я отучился на CS четыре года и если бы не бунтовал, то был бы сейчас бакалавром. За время обучения я прошел несколько связных с AI курсов типа «Искусственные нейронные сети», «Цифровая обработка сигналов», «Анализ данных» и еще что-то  (все это очень условные названия курсов на самом деле, так, в курсе по нейронным сетям в том числе читались генетические алгоритмы как способ решения оптимизационных задач), но из всего перечисленного у нас были только регрессионные модели, да и те ограничивались простейшими видами — не было даже логистической регрессии, которая вообще самая базовая после линейной.

Итогом курса AI стало приглашение тысячи лучших студентов прислать авторам курса свое резюме. Правда, насколько я понял, рассылались приглашения только студентам из США, но мне в общем-то пофигу

Что касается курсов Machine Learning и Databases, то они оказались очень крутыми. Machine Learning слабенький в плане математики, но требует программировать на языке Octave (open-source аналог MATLAB) всякие вещи. Это довольно полезное занятие — материал лучше откладывается в мозгах и в общем-то изложенный материал становится понятным не только на уровне абстракций, но и как-то на уровне физических ощущений. Опять же как общеобразовательный курс, развивающий параллельно простые навыки работы в математических пакетах, очень он очень хорош.

Databases же вообще выше всяких похвал. С ними у меня всегда были проблемы — мне никогда не приходилось программировать ничего более-менее сложного, связанного с базами данных, а задания в соответствующем курсе в МИФИ были слишком тривиальны (уровня «вывести все университеты, на которых читается CS» без каких-либо изысков). Книжки и онлайн-лекции так же практики не представляли.

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

Кстати хотя этого и не объявлялось и не пиарилось, но курсы по Machine Learning и Databases в результате так же дали подписанные сертификаты, ни чуть не более худшие чем сертификат AI. А понимающие люди согласятся, что они и куда более серьезны.

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

(Кстати, справедливости ради надо сказать, что сам я в результате балл набрал невысокий — точно не помню сейчас, но что-то вроде 77% или около; я забил на часть домашних заданий, а что-то мне было лень считать).

В наступающем семестре Стэнфорд предлагает вообще огромную кучу курсов:

Lean Launchpad

Technology Enterpreneurship

Anatomy

Making Green Buildings

Information Theory

Model Thinking

CS 101

Machine Learning (повтор)

Software as a Service

Human-Computer Interaction

Natural Language Processing

Game Theory

Probabilistic Graphic Models

Cryptography

Design and Analisys of Algorithms

Computer Security

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

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

А решение простое, и чтобы его понять, достаточно разбить все норки на четные и нечетные, и рассмотреть начальное положение мышки в четной или нечетной норке отдельно.

Пронумеруем все норки цифрами от 1 до 5 и предположим, что мышка изначально находится в норке с четным номером, то есть с номером 2 или 4.

Суем лапу в норку 2. Либо мы ее поймали, либо она была в норке 4 и после может перебежать лишь в норки 3 и 5. Суем лапу в норку 3. Либо поймали, либо она из пятой норки теперь перебежала в норку 4. Суем лапу в норку 4 и ловим мышь.

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

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

В итоге наша последовательность засовывания лап в норку выглядит так:

2, 3, 4, 2, 3, 4

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

2, 3, 4, 5, …, N − 1

В предположении, что изначально мышка была в четной норке, эта последовательность в итоге ее дожмет за N−2 шагов. Если же изначально она была в нечетной норке, то надо теперь исходить из этого знания.

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

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

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

2, 3, 4, …, N − 1, N − 1, N − 2, …, 2

Итого 2N−4 шагов.

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

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

Итого любой нашей игре можно сопоставить последовательность последовательность значений функции неопределенности. Начальное значение неопределенности N, а конечное (если кошка ловит мышку) — 0. Для пяти ячеек последовательность неопределенностей будет выглядеть следующим образом:

5, 4, 4, 2, 2, 1, 0

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

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

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

Подробные выкладки приводить сейчас не хочется (придется писать до фига нудных вещей), но вообще довольно не сложно увидеть, что если у нас неопределенность в четных ячейках x, а в нечетных y, и мы обозначаем это парой (x, y), то в наиболее благоприятном случае если мы выбираем четную ячейку, то после нашей попытки мы получаем неопределенность (y + 1, x − 1). Если выбираем нечетную, то наоборот.

Здесь на самом деле куча деталей. Например, если N нечетное, а x = (N + 1)/2, то выбивая четную ячейку, у нас пара неопределенностей (x, y) перейдет в пару (y − 1, x − 1). Все подобные частные случаи наобходимо рассмотреть в отдельности  и понять когда они происходят.

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

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

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

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

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

Ответ наверняка кто-то приведет в комментариях, либо если никто не приведет, то я напишу его в следующем году.

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

Определение.  Счетное множество это такое множество, элементы которого можно расположить в последовательность.

Теорема. Множество вещественных чисел несчетно.

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

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

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

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

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

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

(Обратите внимание, что это доказательство практически дублирует доказательство существования трансцендентных чисел).

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

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

По наводке читателя.

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

По сигналу гномики одновременно выкрикивают цвета (синий или красный), пытаясь угадать цвет своей шапки.

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

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

Однако оказалось, что при использовании аксиомы выбора задача все же решается. Сам я ее решить не смог, потребовав решения от задавшего задачу, и вот собственно это решение я теперь и привожу (сама задача изначально читателем как я понимаю была обнаружена в блоге «The everything seminar», перевод на русский здесь).

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

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

Очевидно, что представитель класса отличается от любой другой раскраски данного класса лишь конечным количеством цветов. Так что ошибку допустит лишь конечное число гномиков. Что и требовалось.

Аксиома выбора вообще замечательная, но эта головоломка с гномиками до сих пор на мой взгляд самый яркий пример ее применения (абсурдный конечно, как может показаться, но вполне себе занятный). Здесь был бы уместен рассказ и о других применениях аксиомы выбора, но его не будет, так как одного только подготовительного текста о лемме Цорна и базисе Гамеля будет довольно много, и он будет не слишком тривиален. Поэтому всех интересующихся отправляю за книжкой Верещагина и Шеня «Начала теории множеств». Она как раз во многом об этом, и понять ее сможет почти каждый, что важно.

Вот вам загадка: как можно разместить шар большего радиуса  в шаре меньшего радиуса?

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

Эту задачку выискал в «Элементарной топологии» Виро, Нецветаева, Иванова и Харламова. Задачка совершенно бесхитростная, но позабавила. Книжку кстати тоже рекомендую — она оказалась совсем для начинающих, но изложение хорошее, интересующимся математикой будет полезно почитать. Что примечательно — вполне подойдет даже для людей с минимальной подготовкой, хотя для них я бы начинал с «Наглядной топологии» Болтянского. А потом уже к этой переходил.

Подсмотрел у Вербицкого ссылку на чудесную статью: «Down with determinants!». Ну вряд ли для кого-то станет новостью, так как скорее всего мои читатели математической части сильно пересекаются с читателями Миши, но не продублировать ссылку не могу. Потому что поистине прекрасное.

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

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

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

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

Сам определитель в конце вводится как произведение собственных значений. Единственное, что не понравилось, так это вывод формулы определителя матрицы. Чрезвычайно сложно, правильнее все же выводить ее через кососимметрические формы, ну а там показывать, что это то же, что и произведение собственных значений. Ну сугубо мое ИМХО.

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

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

UPD: Хотя если подумать по-лучше, то крутость подхода в общем-то не в отсутствии определителя, а в том, что на начальном этапе пространство раскладывается на корневые подпространства.

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

Теорема. В единичном отрезке столько же точек, сколько и в единичном квадрате.

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

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

А это и есть, что и требовалось доказать.

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

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

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

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

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

На самом деле с учетом всего вышеозначенного, это не столь тривиальное утверждение, так как мы опять ссылаемся на «интуитивно ясно», что как мы уже видели далеко не всегда правомерно.  На самом же деле это утверждение в более общем виде составляет знаменитую теорему Кантора-Бернштейна, которую я тут не привожу и не доказываю, но вы можете найти ее где угодно.

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

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

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

Чтобы проиллюстрировать это, рассмотрим известный «парадокс Галилея». Выделим в натуральном ряду подмножество точных квадратов (это не принципиально — можно рассматривать любое бесконечное подмножество, но по традиции принято говорить о квадратах), то есть чисел, из которых вычисляется квадратный корень (). С одной стороны очевидно, что , и понятно, что точных квадратов намного меньше, чем натуральных чисел. С другой стороны каждому натуральному числу мы можем сопоставить квадрат, и каждому квадрату натуральное число (), и таким образом получается однозначное соответствие между множествами натуральных чисел и рассуждая таким образом выходит, что натуральных чисел столько же, сколько и квадратов.

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

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

Теорема Кантора. Пусть дано произвольное множество . Множество всех его подмножеств более мощно, чем оно само.

Доказательство. Предположим обратное. Тогда существует взаимооднозначное отображение . Рассмотрим множество . Это множество само является подмножеством , а стало быть так как — отображение однозначное, найдется такой , что . Предположим, что . Тогда , что противоречит . Если предположить, что , то — опять противоречие. Стало быть исходное предположение о существовании взаимооднозначного отображения было неверным. Что и требовалось доказать.

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

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

Возникает еще вопрос: а является ли множество счетным? (Я выкинул граничные точки, но это не влияет на мощность — это так же не сложно доказать самостоятельно).  Чтобы понять это, вспомним, что числа из единичного интервала могут быть записаны как бесконечная дробь, причем нам будет удобнее рассматривать двоичные дроби. Например:

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

Кстати, про множества той же мощности, что и принято говорить, что они имеют мощность континуума. Это так, к слову.

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

Определение. Алгебраическое число — это такое, которое является корнем некоторого многочлена с целыми коэффициентами. Тренсцендентное — это такое, которое не является корнем некоторого многочлена с целыми коэффициентами.

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

Теорема. Трансцендентные числа существуют.

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

Ну и еще пара простых примеров.

Теорема. На вещественной оси можно выбрать не более чем счетное число непересекающихся интервалов.

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

Теорема. Вещественнозначная функция может иметь не более чем счетное множество строгих локальных экстремумов.

Доказательство. Каждый экстремум — это максимум или минимум на каком-то интервале. Поскольку интервалов не более чем счетное число, то и экстремумов не более чем счетное число.

Теорема. Монотонная функция имеет не более чем счетное число разрывов.

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

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

В комментариях попросили попиарить блог popmath.ru, ну а мне и не сложно.

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

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

Или цикл статей про алгебраические структуры. Во-первых, куча ненужной совершенно информации. Чего только стоит фраза: «Как класс, группа содержит такие виды структур (элементы), как группоид, квазигруппа, лупа, моноид и т.п.». Ну и зачем это? Причем я сомневаюсь, что многие из этих определений сходу вспомнят даже профессиональные математики.

Во-вторых, нет никакого практического выхлопа. Куча слов о том, что «математика — красиво и просто»,  но из статей я этого совершенно не вижу. Рассказали про изоморфизмы, но нафиг они нужны — нет. Есть два банальных примера, но они совершенно не мотивируют. Понятно, что изоморфизмы интересны с точки зрения разных там геометрий, например, но только прежде чем об этом говорить, нужно чтобы читатель уже владел значительным количеством содержательных примеров.  На начальном же уровне я бы рассказывал скорее про гомоморфизмы и факторизацию — отсюда сразу можно вывести всякие интересные и неочевидные свойства, заодно рассказав про нормальные подгруппы и идеалы. А изоморфизм был бы частным случаем.

В-третьих, при явном уклоне в формализм, сами определения вводятся не особо-то строго и не самым явным образом. Например:

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

Лично мне такие формулировки взывают мозг, а там такого через слово, и это не  самый страшный пример (двумя абзацами выше все намного хуже, но с формулами). И это на фоне слов о том, что «Математика — просто!». При этом блог уже пишется какое-то время, а никакого содержательного результата еще не изложено — только определения. Это не правильно. Блог продолжает классическую традицию принятую в России: «Сиди зубри, пидор, а зачем это надо потом поймешь». Это не верно и убивает мозг. Математику имеет смысл изучать только для того, чтобы открыть для себя что-то содержательно новое, а не напичкать мозг определениями.

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

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