Забавная ссылка:

What are some reasonable-sounding statements that are independent of ZFC?

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

Самый удачный пример - это выглядящее несомненно верным утверждение: если множество A меньше размером множества B, то у A есть меньше подмножеств, чем у B.

Это хороший пример, потому что на первый взгляд это выглядит как одно из типичных утверждений, которые несоменно верны, но требуют аксиомы выбора для своего доказательства (т.е. C в ZFC, Choice в системе Zermelo-Fraenkel with Choice). Например, без аксиомы выбора нельзя доказать, что счетное объединение счетных множеств само счетно. Или еще хороший парадоксальный пример: без аксиомы выбора, в одной ZF, возможна ситуация, в которой квадрат можно разбить на больше частей, чем в нем есть точек.

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

1+2+3

Jan. 19th, 2014 07:56 pm
Всюду в последнее время попадаются ссылки на научно-популярное видео, где объясняют зрителю, что сумма всех натуральных чисел 1+2+3+4+5+... вовсе не уходит в бесконечность, а равна на самом деле -1/12.



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

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

Что на самом деле происходит? Предположим, у нас есть формула, которая выражает сумму сходящегося бесконечного ряда. Ну скажем, 1 + 1/2 + 1/4 + 1/8 + ... - хорошо известно, что этот ряд все время приближается к двойке, никогда не достигая ее (сумма становится один и три четвертых... один и семь восьмых... один и пятнадцать шестнадцатых....), и поэтому математики называют двойку суммой этого всего бесконечного ряда. Есть формула, которую легко вывести, что сумма сходящейся бесконечной геометрической прогрессии, в которой каждый следующий член получается из предыдущего умножением на X - в этом примере X = 1/2 - сумма всего ряда равна 1/(1-X). Если подставить вместо X 1/2, получится двойка, все сходится.

Но теперь, когда у нас есть формула 1/(1-X), мы можем применить ее, и когда X равно 3, например, т.е. каждый следующий член в три раза больше предыдущего: 1 + 3 + 9 + 27 +... Получим, что "сумма" равна -1/2. Значит ли это, что действительно, суммируя 1 + 3 + 9 + 27 + ... мы будем приближаться к минус половине? Нет, конечно. Формула для суммы геометрической прогрессии верна только когда эта сумма сходится; для X=3 мы ее применили неправомерно, как бы метафорически. По аналогии с сходящимся рядом, можно записать как бы метафорическую "сумму" расходящегося ряда 1+3+9+27+... Есть ли в этом какой-то смысл? Какой-то есть, но не прямой. В математике все настолько взаимосвязано, что даже неправомерное применение формулы скорее всего как-то связано с членами ряда, хоть суммой его результат можно назвать лишь метафорически. Если мы подробнее разберем, как получилась формула 1/(1-X), и более тщательно рассмотрим промежуточные вычисления перед ее получением, то может выйти, скажем, что мы получим что-то вроде 1/(1-X) плюс "еще что-то", так, что это "еще что-то" уходит в ноль для рядов, которые сходятся, а в рядах, которые расходятся, подавляет собой все остальное.

То есть, может быть, верно сказать что-то вроде: в сумме 1 + 3 + 9 + 27 + ... в определенном смысле "таится" минус половина, но ее вклад затмевается собственно огромными и быстро растущими членами ряда; а в сумме 1 + 1/2 + 1/4 + 1/8 + ... "таится" двойка, которую не удается затмить уменьшающимся и уходящим в ноль членам ряда. Но это, конечно, не дает нам оснований утверждать, что сумма 1 + 3 + 9 + 27 + ... "на самом деле" равна -1/2.

С суммой натуральных чисел 1+2+3+... все происходит примерно так же, просто формулы там сложнее, чем 1/(1-X). Там тоже "таится" в определенном смысле -1/12, и это очень интересно, и возможно даже объясняет кое-что в физике теории струн, хоть до конца непонятно, как это в точности там работает; но называть это суммой в прямом смысле, а не в метафорическом - нонсенс.

(при этом в том видео, на которые все дают ссылки, все "объясняют" даже не в таком метафорическом духе, что я описал выше, а как бы получают это -1/12 путем манипуляции расходящихся рядов вроде 1-1+1-1+1-1+1-1... Это чистый обман народа и фричество; хорошо известно, что складывая и переставляя члены в таких рядах, можно получить любой желаемый результат, математики это учат на первом курсе университета. То есть, если в принципе -1/12 имеет некое отношение к ряду 1+2+3+..., в научно-популярным видео к нему приходят фальшивым путем, не имеющим ничего общего с реальной связью)

Более подробные объяснения есть в этом блоге, а совсем строгий математический вывод есть у Терри Тао.
Прекрасная подборка, кто-то постарался - The P-versus-NP page. Ссылки на 100 разных решений знаменитой математической проблемы - равно P NP, или не равно. Я подсчитал - там 50 доказательств того, что равно, 42 доказательства того, что не равно, и 8 - того, что этот вопрос не решается с помощью обычных аксиом математики, и другие редкие варианты.

Любопытно, что половина доказательств добавлена в последние пять лет!
"Имеются вещи, число их неизвестно. Если считать их тройками, то остаток 2; если считать их пятерками, то остаток 3; если считать их семерками, то остаток 2. Спрашивается, сколько вещей?"

Эта задача - из древнекитайского математического трактата Сунь Цзы (это имя автора; не путать с другим Сунь Цзы, автором "Искусства войны"). Трактат был написан где-то между 3 и 5 веками нашей эры, точнее неизвестно. Требуется найти число, которое при делении на три дает остаток 2, на пять остаток 3, на семь остаток 2. Что такое число существует, и как его найти - есть частный случай теоремы, которую называют "Китайской теоремой об остатках" именно из-за этой задачи. На западе ее открыли на тысячу лет позже, в 13-м веке.

Вот решение задачи, из того же трактата:

"Ответ: 23.

Способ: при счете их тройками и остатке 2 установи 140; при счете их пятерками и остатке 3 установи 63; при счете их семерками и остатке 2 установи 30. Сложи это, получишь 233. Из этого вычти 210 и получишь [искомое]. Вообще [если] при счете их тройками остаток 1, то установи 70; [если] при счете их пятерками остаток 1, то установи 21; [если] при счете их семерками остаток 1, то установи 15. [Если сумма] больше 106, то вычитай 105 и получишь [искомое]".

Сначала не вполне понятно, откуда берутся эти числа, но можно разобраться. Здесь вторая половина решения, начиная со слов "вообще", важнее первой. Объясняется, как поступать в частном случае, когда требуется добиться остатка 1 по модулям 3,5,7. Казалось бы, зачем тогда нужно что-то считать, просто возьми число 1, у него тривиальным образом есть нужные остатки. Но дело в том, что способ решения для этого частного случая потом обобщается на любые желаемые остатки.

Предлагается взять числа 70,21,15 и сложить, и легко проверить, что их сумма 106 дает остаток 1 при делении на 3,5,7. Почему так получилось, и что это за числа? Число 70 дает остаток 1 при делении на 3 и делится без остатка на оба остальных числа, 5 и 7. То же самое с другими: 21 дает остаток 1 при делении на 5, и делится без остатка на 3 и 7, и так далее. Значит, если мы возьмем их сумму, и посмотрим на остаток при делении на 5, например, то первое и третье слагаемое дадут остаток 0, т.к. они делятся на 5, а второе даст остаток 1. И то же самое случится при делении на 3 и 7: одно из слагаемых даст нужный остаток 1, остальные будут делится без остатка.

Теперь предположим, что мы хотим добиться не остатков 1,1 и 1, а остатков 2,3 и 2, как в условии. Просто берем эти "магические" числа 70, 21 и 15 и умножаем вначале на желаемые остатки, перед сложением: 70*2 + 21*3 + 15*2 = 233. Теперь при делении на 3, скажем, первое слагаемое даст остаток 2, а остальные два слагаемых как делились на 3 без остатка, так и продолжают делиться, так что они не мешают. Из этого числа 233 можно вычесть любое кратное 105 (105 = 3*5*7, произведение всех делителей), и это не изменит остатки от деления на 3,5,7, так что можно заменить 233 на 233-210=23. Это и есть то, что написано в первой части решения. Из того, что есть вторая часть, понятно, что в первой части числа 140,63,30 взялись не "от фонаря", а именно по этому методу, хоть это и не сказано прямо.

Откуда же нашлись числа 70,21,15? В тексте это не объясняется никак. Может, так: поскольку мы хотим, чтобы первое число делилось на 5 и 7 без остатка, ясно, что оно должно быть кратным 5*7=35. Поэтому просто будем брать кратные 35: 35,70,105 итд. пока не дойдем до числа, которое дает 1 при делении на 3 (второе требование к этому числу). Это получается 70. С двумя оставшимися "магическими" числами нам повезло: это просто произведения 21=3*7 и 15=3*5, и так удачно получилось, что они уже дают нужный остаток 1 при делении на 5 и 7 соответственно. Если б не давали, мы бы тоже брали их кратные, пока не нашли бы нужное.

Вышеописанное - уже полное описание алгоритма решения китайской теоремы об остатках в общем случае. Его можно применять к любому набору попарно простых делителей, а не только 3,5,7. Но поскольку в трактате это подробно не написано, считается, что Сунь Цзы решил только частный случай. Мне кажется, однако, что он нашел что-то вроде вышеописанного - иначе я не понимаю, откуда он взял числа 70,21,15.

(цитаты из русского перевода Эльвиры Березкиной, который был опубликован ровно полвека назад, в 1963г.)
В замечательной книге T.W.Korner'а A Companion to Analysis автор обсуждает вкратце вопрос, стоит ли вообще не преподавать студентам интеграл Римана, а начинать сразу с интеграла Лебега. Были и есть видные математики, которые считают, что именно так следует поступать. Замечание Корнера на эту тему заслуживает цитирования:

"It is frequently claimed that Lebesgue integration is as easy to teach as Riemann integration. This is probably true, but I have yet to be convinced that it is as easy to learn."
(эта запись может быть интересна тем, кто интересуется логикой и компьютерными науками)

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

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

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

Предположим, что формальная система T, кроме указанных выше условий, еще и корректна - т.е. она доказывает только истинные утверждения о натуральных числах. Тогда мы можем доказать, что T неполна, с помощью проблемы остановки. Действительно, предположим, что T полна, т.е. любое утверждение она либо доказывает, либо опровергает (доказывает его отрицание). Построим алгоритм решения проблемы остановки следующим образом. Если нам дана машина M и входные данные X, мы можем сформулировать и записать на языке арифметики утверждение P = "машина M рано или поздно остановится, если запустить ее с данными X" (нам для этого нужно придумать способ представлять описание машины M и данных X в виде натуральных чисел, но это легко - и в курсе теории вычислимости, когда изучают машины Тьюринга, и так делается). Будем перебирать все возможные доказательства в системе T, по возрастанию длины, ища доказательство или опровержение P. Согласно предположению о полноте, рано или поздно мы одно из них найдем. Но поскольку T доказывает только истинные факты, то ее доказательство (или опровержение) P означает, что M действительно останавливается (или не останавливается) на X, т.е. наш алгоритм решил проблему остановки.

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

Мы будем рассматривать машины Тьюринга, которые, останавливаясь, дают результат "да" или "нет" (а также могут никогда не остановиться, конечно). Вместо корректности в доказательстве Ааронсона нам нужны от системы аксиом T лишь непротиворечивость, а также достаточная мощность, чтобы не просто иметь возможность формулировать утверждения о машинах Тьюринга, но и доказывать все истинные утверждения вида "машина M останавливается на входных данных X за Y шагов и говорит да", или "... и говорит нет". Это очень слабое требование, потому что если это утверждение истинно, т.е. это действительно так, она останавливается за Y шагов, то можно выписать последовательные состояния машины после каждого шага, и написать длинное утверждение, которое проверяет, что эта последовательность шагов действительно описывает запуск машины M, действительно останавливается в конце, действительно говорит да. Все это будут простые арифметические отношения между конкретными числами (кодами машин и состояний), поэтому достаточно мощная система T - такой мощи, какая обычно требуется для теоремы о неполноте в любом случае - сможет их доказать.

Из этого условия также следует, что T доказывает любое истинное утверждение вида "M останавливается на X и говорит да/нет", потому что если оно истинно, то есть какое-то число шагов Y, за которые она останавливается, и T доказывает утверждение про конкретное число шагов Y, а более общее сразу из него следует. Если P - истинное утверждение такого вида, то T доказывает P, и следовательно не может доказать не-P, потому что T непротиворечива (но заметим, что хотя не-P - пример ложного утверждения, которое T не доказывает, у нас нет общего ограничения корректности: T может доказывать всякие другие ложные утверждения других видов).

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

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

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

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

У ОТА (Основной Теоремы Арифметики) есть две части: существование разложения на простые множители, и его единственность. Существование доказать тривиально по индукции, и тут проблем или вариантов нет. Предположим, что мы уже доказали существование для всех чисел меньше n. Если n простое, то оно само себе разложение, доказывать нечего. Иначе n = a*b, где a и b какие-то числа меньше его. По предположению индукции у каждого из них есть разложение; соединяя эти разложения вместе, получаем разложение для n.

Единственность - это нетривиальная часть ОТА. Нам нужно доказать, что если n = p1*p2*...*pk = q1*q2*...*qs - два разложения числа n, то числа p должны быть на самом деле равны числам q, разве что расположены в другом порядке. Для начала отметим, что достаточно доказать, что не может быть двух разложений, в которых ни одно p не равно ни одному q, т.е. у разложений нет общих простых множителей. Этого случая достаточно, потому что если у двух разных разложений есть общие множители, на них всегда можно поделить, и убрать их с обеих сторон, пока не останутся два разных разложения числа поменьше без общих множителей, а такого (как мы докажем) не может быть.

Итак, предположим, что ни одно p не равно ни одному q. На этом месте доказательства ОТА делятся на две группы: те, которые доказывают с помощью леммы Евклида, и те, которые доказывают напрямую по индукции.

Лемма Евклида гласит следующее: если простое число p делит произведение a*b (p|a*b), то p делит отдельно a или b (или оба): p|a или p|b. Эта лемма была известна Евклиду и появляется именно в таком виде в 7-й книге его Начал.

Предположим, мы доказали лемму Евклида; единственность разложение в ОТА следует из нее немедленно следующим образом. p1 делит все число n = q1*q2*...*qs, значит (применяя лемму Евклида много раз), оно должно делить какое-то qi. Поскольку мы предполагаем, что p1 не равно ни одному qi, и они разные простые числа, это невозможно. Так что главная работа в этом подходе - доказать лемму Евклида.

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

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

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

1. Сначала опишу более элегантное, на мой взгляд. Это доказательство принадлежит Цермело, он опубликовал его в 1934 году, но упомянул тогда же, что нашел его еще примерно в 1912-м.

Предположим, мы доказали единственность для всех чисел, меньших n, и теперь доказываем для n. Мы можем предположить, что n непростое, иначе все тривиально. Пусть p - наименьший делитель n из всех делителей n, больших 1; очевидно, что p обязан быть простым делителем, иначе были бы делители еще меньше.

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

Пусть n = q*q1*...*qs - произвольное разложение n, в котором множитель q отличается от p. Мы хотим доказать, что несмотря на это, p все равно найдется где-то среди других множителей q1...qs. Поскольку p минимальный делитель, q > p, так что посмотрим на число n - p*n/q. Оно меньше n и потому имеет единственное разложение; поскольку p делит это число, p должно участвовать в этом разложении. Однако это число равно также (q-p)*q1*...*qs. p не делит q-p, так что он обязан участвовать в разложении среди
q1*...*qs, что и требовалось доказать.

2. Теперь второе доказательство по индукции.

Предположим, n = p1*p2*...*pk = q1*q2*...*qs, и у разложений нет общих элементов. Мы можем предположить, что в каждом разложении есть хотя бы два множителя - иначе все тривиально - и пусть p1, q1 будут минимальными множителями в каждом разложении. Тогда p12 ≤ n, и то же верно насчет q1; поскольку они разные, одно из неравенств должно быть строгим, и следовательно p1*q1 < n. Рассмотрим число X = n - p1*q1; согласно индуктивному предположению у него есть единственное разложение. Поскольку и p1 и q1 делят n и делят p1*q1, каждое из них делит X и поэтому встречается в его единственном разложении. Единственность разложения X поэтому дает нам право записать X = p1*q1*Y, и соответственно n = p1*q1(1+Y). Но теперь, если мы посмотрим на n/p1, у которого тоже обязано быть единственное разложение, оно с одной стороны должно быть p2*...*pk, а с другой включать в себя q1, потому что n/p1 = q1(1+Y). Это противоречие, потому что q1 не встречается среди p2*...*pk.
Наверное, многие знают, и не только физики, но и лирики, что любое натуральное число можно разложить на простые множители (например, 120 = 2*2*2*3*5), и что такое разложение есть только одно, оно единственно. Что это значит? Понятно, что можно поменять множители местами - например, 120 = 5*3*2*2*2. Но любое разложение 120 на простые множители включает в себя ровно три двойки, одну тройку и одну пятерку. Никакие другие простые множители типа 7 или 23 не могут там появиться, а те, что есть, обязаны повторяться ровно это число раз.

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

Британский математик Тимоти Гоуэрс написал целую запись об том, почему основная теорема арифметики на самом деле не очевидна: Why isn’t the fundamental theorem of arithmetic obvious? Не буду повторять все его аргументы, но приведу один: действительно ли очевидно нам, не вычисляя, что 23*1759 не равно 53*769? Если я вам скажу, что все четыре числа простые, неужели вам немедленно станет очевидно (не ввиду этой теоремы, а непосредственным восприятием), что произведения не равны, а если окажется, что я соврал и одно из них не простое - что, может быть, равны?

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

Мне попался недавно замечательный пример того, что это на самом деле неочевидно - его привел знаменитый английский математик Харди в 1929 году. Харди известен помимо прочего своим классическим учебником "Введение в теорию чисел", в соавторстве с Райтом. Он вышел в свет в 1938 году, но до того, в 1929 году, Харди прочитал публичную лекцию под тем же названием (кстати, очень интересную, рекомендую к прочтению).

Как известно, древние греки еще во времена Пифагора обнаружили, что квадратный корень из двух - иррациональное число (открытие приписывается самому Пифагору, но точно это неизвестно). Пифагор жил в 6-м веке до нашей эры, за сто лет до Сократа и Платона. Харди рассказывает, что одним из учителей Платона был Феодор Киренский, математик пифагоровской школы. Мы знаем о нем потому, что Платон рассказал о нем немного в двух своих диалогах, и в частности там упомянуто, что Феодор доказал иррациональность всех квадратных корней из чисел от 3 до 17 (не включая, конечно, те числа, которые действительно являются целыми квадратами, то есть 4, 9 и 16: два, три и четыре в квадрате). Про корень из двух ему не надо было доказывать, это было известно со времен Пифагора, а вот от 3 до 17 было его собственным вкладом, который в то время высоко оценили современники.

Позвольте напомнить вам греческое доказательство иррациональности корня из двух, весьма простое. Предположим, что корень из двух на самом деле рационален и равен дроби A/B, и это сокращенная дробь - A и B уже нельзя вместе сократить еще больше. Если мы возведем в квадрат обе части A/B = √2, то увидим, что A2/B2 = 2 или A2 = 2B2. Отсюда следует, что A2 четное число, значит, и A четное, то есть можно записать A = 2*C. Тогда A2 = 4C2 = 2B2, и отсюда B2 тоже четное, и значит, B четное. Но это значит, что A и B вместе можно сократить, потому что они оба делятся на 2 - а это противоречит тому, с чего мы начали. Значит, наше начальное предположение было неверно и √2 нельзя записать как дробь, что и требовалось доказать.

В этом доказательстве я выделил ключевую часть, на которой основан весь аргумент. Почему это верно, что из "A2 четное число" следует "A четное", и то же самое для B? Это действительно очевидно - это следует из того, что квадрат нечетного числа остается нечетным - и легко строго доказать: запишем нечетное число в виде 2k+1 для какого-то k, возведем в квадрат, раскроем все скобки, упростим и увидим, что получится опять нечетное.

Но теперь представим себе, что вместо √2 мы хотим доказать теорему для √5. У нас опять будет тот же ключевой шаг, который выглядит так: из
"A2 делится на пять" следует "A делится на пять". Как это доказать? Можно опять напрямую, но придется отдельно рассмотреть все возможные числа, которые не делятся на пять (то есть, дают остаток 1, 2, 3 или 4), и для каждого вида отдельно доказать, что его квадрат опять не делится. Это громоздко, длинно, и нужно отдельно делать для каждого числа. Можно намного проще! Просто представьте себе разложение A на простые множители. Если в нем нет пятерки, то и в разложении A2, в котором ровно те же множители, повторенные дважды, ее тоже нет, вот и все доказательство.

Почему же тогда, задает Харди риторический вопрос, Феодор Киренский написал длинный трактат о том, как доказать иррациональность чисел от 3 до 17, и почему только до 17? Ведь обычное доказательство для двойки тривиальным образом обобщается на все эти случаи, да и для чисел больше 17 тоже! Что же он там доказывал?

(если быть немного точнее, то вышеприведенный аргумент для пятерки работает для всех "бесквадратных чисел", в которых простые множители повторяются не больше одного раза; например, 5, 7, 10 = 2*5 или 15 = 5*3, но не 12 = 2*2*3. Но из таких чисел как 12, всегда можно заранее "вытащить" их квадратную часть: √12 = √(2*2*3) = 2*√3 - и доказать иррациональность того, что осталось).

Так вот, разгадка состоит в том, что очевидное для нас разложение чисел на простые множители единственным способом - основная теорема арифметики - была, увы, Феодору неизвестна. Ее сформулировал (не целиком, но почти целиком) Евклид, в седьмой и девятой книгах своих "Элементов", около 300 г. до нашей эры. Феодор умер за сто лет до того, и то, что для нас совершенно "очевидно", ему было недоступно. Мы не знаем, как в точности он доказал иррациональность корней от 3 до 17; наверняка это было не с помощью подробного пересчета остатков и квадратов, но как именно? - современные математики выдвинули несколько разных гипотез. Но для его времени, не знавшего "очевидную" основную теорему арифметики, это действительно было выдающимся достижением.

P.S. Я планирую написать отдельную запись о доказательствах основной теоремы арифметики.
1. Gauss's Day of Reckoning. Историю про Гаусса, который складывал числа от 1 до 100 в семь лет, видимо, надо считать мифом. Очень жаль, я поражен и огорчен. Что-то там было, возможно, связанное с вычислением - и то, первое упоминание уже после смерти Гаусса, не факт, что достоверное. А конкретная задача с числами от 1 до 100 появляется впервые в 1938 (!!) году.

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

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

4. Любопытное обсуждение того, как мотивировать студентам изучение комплексного анализа. Красивый пример предлагает Keith Conrad: посмотреть на радиус сходимости рядов Тейлора. Например, у функции 1/(1+x) в нуле радиус сходимости равен единице, и понятно, почему; а у функции 1/(1+x^2) он тоже равен единице, несмотря на то, что она хорошо себя ведет, гладкая на всей действительной прямой. Но вот если посмотреть на комплексную плоскость, немедленно становится ясно, откуда выскочила эта единица...

5.
On April 9, 1975, Congressman Robert Michel brandished a list of new NSF grants on the floor of the House of Representatives and selected a few that he thought might represent a waste of the taxpayers’ money. One of them (on which I happened to be one of the investigators) was called “Studies in Complex Analysis.” Michel’s comment was, ” ‘Simple Analysis’ would, hopefully, be cheaper.” I shudder to think of what might happen if certain members of the current Congress discover that the NSF is supporting research on perverse sheaves.”

6. Красивое доказательство иррациональности квадратных корней из целых чисел (не являющихся полными квадратами), приписывается Конвею. Мы доказываем, что если √n рациональное число, то оно целое число.

Сначала нам нужна элементарная (и интуитивно очевидная) лемма о дробях. Среди всех возможных представлений данного рационального числа в виде дроби A/B всегда можно выбрать такое, в котором B минимальное положительное (по сути дела, это представление - сокращенная дробь, но нам этот факт не нужен). Утверждение: если C/D другое представление того же числа, A/B = C/D, то D делится на B. Доказательство: перепишем A/B = C/D в виде D/B = C/A, и оставим у каждой дроби только дробную ее часть: d/B = c/A, где 0 <= d < B. Если d не равно 0, то отсюда следует A/B = c/d и это противоречит минимальности B; значит, d=0 и D делится нацело на B.

Теперь пусть √n = A/B, выберем такое представление, в котором B минимальное положительное. Поскольку √n = n/√n, мы видим, что A/B = n*B/A, и немедленно заключаем из вышесказанного, что A делится на B; ввиду минимальности B из этого следует B=1.
Любопытная статья математика Филипа Дэвиса:

What Do I Know? A Study of Mathematical Self-Awareness

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

Переведу только названия основных "states of knowledge" - подробное описание того, что они значат, и примеры см. в статье.

Итак, у нас есть некоторая математическая проблема P. Примеры того, что мы можем о нем знать (необязательно взаимоисключающие):

1. P - проблема, у которой есть математический смысл.
2. Я не знаю, как решить P, но если подумаю, то возможно решу.
3. Я не знаю решение P, но может быть, оно уже известно.
4. Я не знаю, есть у P вообще решение или нет.
5. Я могу доказать, что у P есть ответ.
6. Я могу доказать, что у P нет ответа.
7. Я могу доказать, что у P нет ответа, но если мы расширим контекст проблемы, у P появится ответ в расширенном контексте (частая и полезная ситуация в математике).
8. Я могу доказать, что у P есть ответ, но я не знаю, какой он.
9. У P есть ответ. Вот он (в некотором представлении). Я могу его проверить. Я могу доказать, что он единственен в некотором смысле.
10. Проблема P обсуждается. A заявляет, что у него есть ответ и предлагает его. B оспаривает это утверждение.
11. Я не знаю ответ на P. У меня есть алгоритм, который ищет ответ. Если алгоритм остановился, значит, он нашел правильный ответ.
12. Я не знаю ответ на P. Но P содержит в своем определении параметр, скажем P(n), и я знаю ответ в частных случаях P(1)...P(N). Если бы я знал ответ на все P(n), я знал бы ответ на P.

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

Еще процитирую оттуда то, что понравилось, когда автор обсуждает нетривиальность состояния "это уже известно", и как в общем случае мы можем или не можем это проверить:
With regard to buried concepts and altered contexts, consider this example. In one of the first issues of the American Journal of Mathematics (1879), Arthur Cayley, world-renowned British mathematician, works out the number of asyzygetic covariants of degorder (Θ, μ) for the binary seventhic. I do not know what these words mean. I have a vague feeling of what kind of mathematics this is likely to be, and I would suspect that whatever it means, it would be said differently today. How can an information system be devised that will make Cayley's result comprehensible to me quickly and cheaply?
Небольшая статья с интересным названием "Какие числа лучше всего подходят для описания эмпирической реальности?"

Which number system is “best” for describing empirical reality?

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

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

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

Автор статьи занимается только первой из этих двух сложностей, предлагая возможные "промежуточные" варианты между рациональными и действительными числами (например, числа, которые можно построить с помощью циркуля и линейки; или алгебраические числа); ни один из них не кажется мне особенно привлекательным. С другой стороны, хочу порекомендовать гораздо более подробную запись [livejournal.com profile] akuklev об этих материях, которая больше говорит о необходимости (по утверждению автора) вещественных чисел для описания реальности:

О бесконечности и о точке

Я немного думал об этих вопросах несколько с другой стороны, нежели автор первой статьи. Его интересует вопрос: какие числа лучше всего отражают то, что мы наблюдаем в реальности? Я к тому же вопросу подходил немного с другой стороны. Представьте себе, что мы встречаем-таки инопланетян, находим их или они находят нас, и начинаем пытаться понимать друг друга. В научной фантастике не раз и не два авторы обсуждали вопрос о том, будет ли у нас "одна и та же математика", и это вопрос философский, вопрос философии математики, собственно. Большинство профессиональных математиков являются - иногда бессознательно, иногда осознанно - "платонистами", т.е. они считают, что математические формулы, гипотезы и теоремы суть не бессмысленные закорючки на бумаге, которые придуманы человеческим мозгом и только к нему имеют отношение, а отражают некую фундаментальную реальность, независимую от нас, "платонический" мир математических идей, который один и тот же для всех: теорема Ферма верна и на Земле, и у инопланетян, и она была бы верна, даже если бы никакого человечества никогда не возникло. Мы "открываем" математические истины, а не "создаем" их - в этом суть платонизма. Так вот, предположив, что платонизм верен, и что как мы, так и инопланетяне "видим" ту же математическую реальность, все равно можно задать вопрос: насколько их математика будет похожа на нашу? Если предположить, что счет отдельных объектов - нечто совершенно фундаментальное для всех, то у них, наверное, будут те же натуральные, целые, и рациональные числа, что у нас - но будут ли вещественные числа? Возможно, они понимают, что это такое математически, но не считают их важными, потому что для развития теорий о том, как устроен физический мир, им хватило рациональных? Возможно, то, что нам кажется излишне громоздким и неэлегантным описанием в терминах рациональных чисел, для них приемлемо, потому что мозги у них устроены по-другому, и понятия громоздкости и элегантности совсем другие?
Читаю сборник научно-популярных статей о математике (еще не знаю, хороший или нет). В предисловии составитель сборника рассуждает о том, как он отобрал статьи и эссе - из книг, веблогов, сайтов итд., потом делает небольшой обзор книг, сайтов и веблогов в этой области за последний год (я это упоминаю, чтобы было понятно: он активно пользовался интернетом при составлении сборника). И наконец, пишет: я буду рад вашим замечаниям и предложениям, пишите мне на... и приводит почтовый адрес, с номером дома, улицей, городом. Я чуть не поперхнулся. Может, это такой тонкий троллинг. Интересно, сколько читателей ему туда напишут; я ставлю на ноль.

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

Российская команда победила на Mеждународной Mатематической Oлимпиаде, которая только что закончилась вo Вьетнаме. Ура! От всей души поздравляю команду, Россию, и лично одного ЖЖ-френда :)

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

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

  • Смешной и весьма показательный пример curve-fitting прямо с редакционной страницы Wall Street Journal. Удивительная то ли наглость, то ли глупость.

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

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

Есть наборы, для которых "жадный" алгоритм всегда приведет к наименьшему возможному количеству монет (скажем, набор из 10, 5, 3 и 1 - такой). А есть наборы, для которых иногда можно воспользоваться меньшим количеством монет, чем дает "жадный" алгоритм (например, набор достоинств в 25, 20, 10, 5 и 1 такой: сумму в 40 денежных единиц можно в нем выразить двумя монетами по 20, а "жадный" алгоритм дает три монеты: 25, 10 и 5).

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

P.S. Если вы просто знаете правильное решение (а не придумали его сами), не надо им делиться пока, хочу подумать сам.

March 2014

S M T W T F S
       1
2 3 4 5 6 7 8
9 10 11 12 131415
16171819202122
23242526272829
3031     

Syndicate

RSS Atom

Style Credit

Expand Cut Tags

No cut tags
Page generated Aug. 22nd, 2017 10:35 pm
Powered by Dreamwidth Studios