Теневая бухгалтерия
Nov. 26th, 2017 11:10 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
xaxam
Продолжение банкета: чек к оплате
Подведём предварительные итоги. В бюрократическом порыве мы напечатали много паспортов. Каждый паспорт содержит результат сравнения (больше-меньше-равно) обладателя паспорта со всеми рациональными числами. С типографской точки зрения в паспорте есть две бесконечных строчки рациональных чисел, первая (L) - те, что меньше подателя, вторая (R) - те, что больше подателя. Ну, и если податель сам рационален, то его самого можем записать в любую из строк или в обе. Раздавши паспорта рациональным числам, мы остаёмся с бесконечным количеством паспортов, не соответствующих пока никаким числам.Заглядывая в эти паспорта (официально они называются дедекиндовыми сечениями), сферический чиновник, способный выполнить бесконечно много действий, сможет сказать, какой паспорт надо выдать сумме/разности двух паспортов-слагаемых, а какой - произведению/частному. Более того, на основании паспортных данных можно паспорта сравнивать не только с рациональными числами, но и между собой. Все обозначения которыми мы пользовались при действиях с рациональными числами, можно теперь спокойно использовать для действий с новыми, вещественными числами. В частности, мы будем пользоваться обозначениями для открытых интервалов (a,b), не включающих концы, и замкнутых отрезков [c,d], эти концы включающих, разумеется, в предположении, что a < b, и c ≤ d.
Торжественная процедура выдачи паспорта (L,R) вещественному числу, обозначаемому иксом, означает, по правилам нашего МВД, что икс как раз и затыкает дырку между множествами L и R, если такая дырка не соответствовала никакому рациональному числу. Поэтому-то у нас есть основания считать, что, раздав все легальные паспорта, мы в самом деле заткнули все дыры. Что надо сделать, чтобы в этом убедиться? Надо проверить, что не появилось дыр между новыми числами.
Самый простой сценарий, в котором такая дыра могла бы появиться, описывается следующим образом. Предположим, что у нас есть монотонно неубывающая бесконечная последовательность вещественных чисел a1 ≤ a2 ≤ a3 ≤ ... и другая бесконечная последовательность, на этот раз невозрастающая: b1 ≥ b2 ≥ b3 ≥ ... и предположим, что все члены первой последовательности меньше или равны всем членам второй последовательности. Это очень похоже на то, как мы поступали, когда начинали выдавать паспорта. Разница в том, что в паспортах записаны были только рациональные числа, а здесь мы имеем дело с вещественными числами, и не требуем, чтобы все вещественные числа появились бы в одной из этих двух последовательностей (это невозможно, см. ниже). С другой стороны, и интересует нас только одно: есть ли вещественное число, разделяющее две последовательности, которое было бы больше или равно всех а-чисел, и меньше или равно всех b-чисел.
Геометрически задача выглядит очень просто. Рассмотрим перенумерованные отрезки Sn=[an,bn] при n=1,2,3, ... Неравенства, которые наложены на наши последовательности, означают, что все эти отрезки непусты и вложены друг в друга: отрезок с бо́льшим номером лежит внутри отрезка с меньшим номером. Это значит, что пересечение первых n отрезков попросту совпадает с последним из них, Sn, и значит, их пересечение непусто. Вопрос, который нас интересует, - пусто или нет пересечение всех отрезков сразу.
Ситуация неочевидная. Скажем, если вместо замкнутых отрезков (включающих концы) мы рассмотрим открытые интервалы, то пересечение запросто может оказаться пустым: подумайте, что будет, если мы возьмём интервалы In=(0,1/n), n=1,2,3,... Для таких интервалов любое конечное пересечение тоже непусто и равно интервалу с самым большим номером, но бесконечное пересечение пусто. Если мы на секундочку вернёмся в рациональный мир и предположим, что концы замкнутых отрезков сидят в рациональных точках, то бесконечное пересечение может быть "рационально пусто" (т.е., не иметь рациональных точек), хотя вещественные точки там будут.
Мы утверждаем, что для замкнутых вложенных отрезков пересечение всегда непусто. Чтобы в этом убедиться, рассмотрим паспорта а-чисел и b-чисел. У а-чисел возьмём "левые части" и положим L равным их объединению, а у b-чисел - правые части, которые мы тоже объединим в одно множество R. Оба множества состоят из рациональных чисел. Является ли оно паспортом? Как там насчёт Трёх Правил?
Непустота L,R очевидна, точно также очевидно, что любое число из L не превосходит любого числа из R. Проблема лишь в третьем правиле, гарантирующем единственность, но оно нам и не надо. Если объединение L∪R не покрывает все рациональные числа, значит, есть рациональное число, разделяющее L и R. Это число по определению принадлежит бесконечному пересечению отрезков. А если все рациональные числа поделены между L и R, значит, (L,R) таки является легальным паспортом и соответствующее число (единственное) будет общей точкой всех отрезков. Так или иначе, но непустота бесконечного пересечения гарантирована.
Этот принцип вложенных отрезков - отличная штука для того, чтобы доказывать разные полезные утверждения типа существования решений без того, чтобы явно предъявлять сами эти решения (опытная кухарка должна насторожиться в этом месте: как же можно доказать, что решение есть, но не уметь его найти? не иначе, мухлёж какой...). Например, как увидеть, что из любого положительного вещественного числа можно извлечь квадратный корень? Давайте для простоты предположим, что это число A находится на отрезке [0,1]. Выберем середину, точку 1/2, и сравним А с квадратом, 1/4. Если А=1/4, то бинго! корень извлекли. Если же равенства нет, то А < 1/4, либо A > 1/4. В первом случае корень должен лежать где-то на отрезке [0,1/2], во втором - на [1/2, 1]. Выбираем нужный отрезок, смотрим на его середину и сравниваем её квадрат с А. Опять три варианта, - угадали, промахнулись с недостатком, промахнулись с избытком. Выбираем нужный отрезок и т.д. Такой процесс пристрелки приводит к построению последовательности вложенных отрезков, длины которых убывают, как геометрическая прогрессия со знаменателем 1/2. По принципу вложенных отрезков, бесконечное пересечение непусто и там есть хотя бы одно вещественное число. Несложно проверить, что это число - в точности положительный корень уравнения x2=A.
Однако этот же принцип позволяет понять, почему вещественных чисел (всевозможных "легальных паспортов") существенно больше, чем натуральных или рациональных. Этот факт оказался полной неожиданностью в
Итак, предположим, что удалось все вещественные числа выписать через запятую в одну бесконечную строку, подобно тому, как мы выписывали все рациональные числа:
a1, a2, a3, a4, a5,...
Мы сейчас, глядя на эту строку, предъявим действительное число, которое в ней было пропущено. Возьмём отрезок [0,1], но на этот раз разделим его на три равные части, [0, 1/3], [1/3, 2/3], [2/3, 1] и посмотрим, где оказалось число a1. Оно может попасть внутрь отрезков или в точки, их разделяющие (и тогда оно будет принадлежать двум смежным отрезкам), но в любом случае оно не может попасть во все три отрезка. Обозначим через S1 тот отрезок, куда не попало число a1. Разделим точно так же отрезок S1 на три равные части и посмотрим, в какую из них не попало число a2. Продолжая подобным образом, мы построим последовательность вложенных замкнутых отрезков, которая должна иметь непустое пересечение. Обозначим его иксом. Мы утверждаем, что икс пропущен в написанной выше бесконечной строке. В самом деле, икс не может совпадать с первым числом a1 - по построению, эти два числа принадлежат двум непересекающимся отрезкам. По этой же причине икс не может совпадать со вторым числом, с третьим, .... - в общем, ни с одним числом в строке икс совпадать не может, значит, оно было пропущено.
Конечно, найти всего одно пропущенное число кажется не слишком большой проблемой: ну, допишем его слева, самым первым элементом в строке, и дело с концом. Однако ж мы предположили, что последовательность уже содержит все числа, и привели это предположение к противоречию. Значит, само предположение было неверным, и нельзя выписать все вещественные числа через запятую: их реально больше, чем рациональных чисел. Георг Кантор (см. на фото), придумавший этот трюк (т.н. "диагональный процесс"), совершил революцию. Курт Гёдель, открывший теоремы невозможности в логике, фактически использовал модификацию канторовского диагонального процесс.
Это обстоятельство, называемое несчётностью множества вещественных чисел, на самом деле означает, что подавляющее большинство из них никто никогда не увидит (не встретит, не опознает, ...). В самом деле, чтобы ткнуть пальцем в какое-то конкретное число, надо объяснить, как ты на него набрёл (поделил два целых числа одно на другое, решал алгебраическое уравнение, решал тригонометрическое уравнение, суммировал бесконечный ряд, доказал существование решения в какой-то конкретной задаче, считал площадь круга или написал какой другой интеграл и т.д.). Такое объяснение-описание, даже если оно описывает какие-то бесконечные процессы, само по себе обязано быть конечным текстом на человеческом языке с вкраплениями математических закорючек, если хочется. А множество конечных текстов (и осмысленных, и бессмысленных) - счётно, все такие тексты можно выписать в одну бесконечную строку (сначала выписываем все тексты из одной буквы, считая пробел и закорючки, потом - тексты из двух букв, из трёх и т.д.). Значит, подавляющее большинство вещественных чисел так и останется навеки безымянными.
Понять это по-другому можно, сообразивши, что почти все "легальные паспорта" должны иметь бесконечную толщину. Конечно, любое рациональное число можно записать, используя лишь конечное число битов (символов), но перечислить все рациональные числа невозможно, даже с учётом того, что некоторые из неравенств вида l ≤ x ≤ r, l∈ L, r∈ R следуют из других и могут быть пропущены. Поэтому никакой реальный полицейский, глядя в паспорт, не сможет за конечное время однозначно опознать разыскиваемого преступника, если список разыскиваемых достаточно велик.
Возникает законный вопрос, - зачем нам весь этот геморрой, с мириадами безымянных чисел, которые нам никогда не понадобятся? Наверное, правильный ответ, - это как перила ограждений на строительных лесах. Никто никогда не висит на этих перилах, но они - гарантия, что случайное движение, умышленное или нет, не приведёт к падению. Даже не зная заранее, какой будет ответ в задаче, которую мы решаем, мы берёмся за неё с уверенностью, что в каком-то смысле ответ существует. Если задача окажется интересной и полезной, для ответа придумают специальное имя ("псевдоним", "сценическое имя"), под которым этот ответ приобретёт мировую известность. Общеизвестные примеры - π=3.141... (площадь круга), e=2.71828... (сумма ряда обратных факториалов), и их разные алгебраические комбинации. Но большинство вещественных чисел так и останется невостребованными.
Заинтересованно
Date: 2017-11-26 01:47 pm (UTC)А вот алгебраическая комбинация π+e, она рациональная или не очень?
Re: Заинтересованно
Date: 2017-11-26 01:54 pm (UTC)П.С. Посмотрел вики по ссылке: ровно этот пример и приводится в списке следствий из гипотезы Шануэля. По-видимому, это означает, что прямого доказательства неизвестно, значит, ответа про трансцендентность мы не знаем.
Re: Заинтересованно
Date: 2017-11-27 04:39 pm (UTC)Верю :) но это разве доказано? Вольфрам пишет, что нет: http://mathworld.wolfram.com/e.html
Re: Заинтересованно
Date: 2017-11-27 04:52 pm (UTC)Хотя в любом случае это никак не моя епархия, и не меня надо расспрашивать на эти темы. Иррациональность е - на уровне хорошего курса матана. Трансцендентность е - ой-ой-ой...
Re: Заинтересованно
Date: 2018-05-12 11:02 pm (UTC)Ай-й-яй