Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

непрерывнось и несчётность

Несколько человек попросили меня объяснить подробнее решение задачи про непрерывную функцию, принимающую каждое значение несчётное число раз.

Вот подробное объяснение решения в очень элементарных терминах.


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

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

Любое действительное число имеет десятичное разложение, которое мы можем считать бесконечно длинным даже в случае, когда оно заканчивается, путём добавления бесконечно длинной последовательности нулей в конце: 0.234 = 0.234000000000000... С другой стороны, любое двоичное разложение, которое мы можем получить в результате нашего определения, соответствует какому-то числу от 0 до 1. Это, думаю, объяснять не надо.

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

Вот, ещё раз, определение функции:

Разложим аргумент в десятичное разложение: x=0.a1a2a3... , каждая цифра от 0 до 9.
А значение функции будет выражено в бесконечном двоичном разложении: f(x)=0.b1b2b3... , каждая цифра 0 или 1.

  • если an от 1 до 4, то bn=0;
  • если an от 5 до 8, то bn=1;
  • если an=0 или 9, и равна an-1, то bn=bn-1;
  • если an=0 или 9, и не равна an-1, то bn=1 - bn-1.


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

0.a1a2a3...an99999999... ,

или так:

0.a1a2a3...(an+1)00000000.... ,

но это одно и то же число в обоих случаях. Когда мы определями значение функции, первые n-1 двоичных разрядов будут определены одинаково в любом случае: 0.b1b2b3...bn-1 . Дальше разберём раздельно наши два разложения:
  • Если выбрано разложение вида 0.a1a2a3...an99999999... , то мы знаем, что an не равно 9. Поэтому если an переходит в единицу, то первая из последующих девяток перейдёт в 0, а все остальные её скопируют (согласно правилу), и мы получим результат вида 0.b1b2b3...bn-1100000000000000... Если же an переходит в ноль, то первая из последующих девяток перейдёт в 1, а все остальные её скопируют, и мы получим результат вида 0.b1b2b3...bn-10111111111111... -- но это то же самое число, просто в другой двоичной записи, здесь имеет место та же двойственность, что и с десятками и нулями в десятичном случае.
  • Если выбрано разложение 0.a1a2a3...(an+1)00000000.... , то происходит практически то же самое, т.к. мы знаем, что an+1 не равно 0. Если эта цифра (an+1) переходит в 1, то вся строка нулей перейдёт в 0, и мы получим 0.b1b2b3...bn-1100000000000000... ; если эта цифра перейдёт в 0, то вся строка нулей перейдёт в 1, и мы получим 0.b1b2b3...bn-101111111111111... .

Мы видим, что в любом случае всегда получаем число 0.b1b2b3...bn-11, иногда только записанное по-другому; следовательно, наша функция хорошо определена и всегда выдаёт одно и то же значение для данного аргумента.


Итак, у нас есть функция, определённая на отрезке (0,1). Докажем теперь, что она действительно принимает каждое своё значение несчётное число раз. Пусть x - какое-то число от 0 до 1, а f(x) - значение функции; распишем f(x) в бесконечное двоичное разложение 0.b1b2b3...bn.... (если двоичное разложение f(x) заканчивается на какой-то цифре, просто добавим неограниченное число нулей после неё). Докажем теперь, что есть несчётное число таких y от 0 до 1, что f(y)=f(x). Для этого докажем, что число таких y не меньше, чем число разных подмножеств натуральных чисел (кол-во подмножеств множества натуральных чисел N несчётно).

Будем определять наш аргумент y по индукции через его десятичное разложение. На каждом шагу у нас есть возможность выбрать несколько разных десятичных цифр an в y, дающих одну и ту же двоичную цифру bn в f(y) (согласно нашему правилу определения функции). Условимся, что если соответсвующий n-ный разряд в f(x) равен 0, то мы всегда выберем an равным 2 или 3, а если n-ный разряд в f(x) равен 1, то мы всегда выберем an равным 7 или 8. Тогда мы сразу видим, что, выбирая по индукции an подобным образом, мы определяем некоторое число y, так, что f(y)=f(x). Более того, мы не используем 0 или 9 в нашем построении y, поэтому нет опасности того, что два разных разложения будут обозначать одно и то же число. Следовательно, разные последовательности выборов an дают разные значения y (иными словами, даже если всего в одном разряде мы выбрали 2 в одном аргументе, и 3 в другом (или 7 в одном и 8 в другом), то мы получаем разные значения y в конце концов).

Теперь сопоставим каждому подмножеству натуральных чисел своё значение y, такое, что f(y)=f(x). Пусть M - какое-то подмножество натуральных чисел. Тогда построим yM следующим образом: на n-ном шаге будем выбирать an равным 2 или 7 (в зависимости от значения bn в числе f(x)) если n принадлежит подмножеству M, и будем выбирать an равным 3 или 8, если n не принадлежит подмножеству M. Легко видеть, что если два подмножества M1 и M2 не идентичны, то они разнятся в каком-то числе n (скажем, n входит в M2 и не входит в M1), но тогда соответствующие этим подмножествам числа y будут различаться в n-ном разряде (например, в одном из них будет 2, а в другом 3; или в одном 7, а в другом 8). Поэтому разных чисел y, дающих f(y)=f(x), как минимум столько же, сколько разных подмножеств натуральных чисел, т.е. несчётное число.


Наконец, докажем строго непрерывность нашей функции.

Функция f непрерывна на отрезке (0,1), если она непрерывна в каждой точке этого отрезка; и она непрерывна в точке x0, если выполняется следующее: для любого ε>0 существует некоторое δ>0, так, что если x находится на расстоянии меньшем или равным δ от x0, то f(x) находится на расстоянии меньшем или равным ε от f(x0). Таково формальное определение, к-е используют обычно в курсах по введению в матанализ.

Выберем произвольную точку x0 между 0 и 1, и докажем, что наша функция непрерывна в этой точке. Пусть десятичное разложение x0 будет 0.a1a2a3...an.... , а у f(x0) пусть будет двоичное разложение 0.b1b2b3...bn.... (в обоих случаях, если есть два возможных разложения, выберем то из них, которое с бесконечным рядом девяток или единиц). Пусть нам дано некоторое ε>0 . Найдём такое натуральное число N, что 1/2N < ε, т.е. N настолько велико, что обратное к 2N число меньше ε . Если мы теперь зафиксируем первые N+1 знаков числа f(x) -- т.е. 0.b1b2b3...bN+1 -- то легко видеть, что разница между любыми двумя числами, которые начинаются (в двоичном разложении) с этих N+1 знаков, будет меньше, чем 1/2N (т.к. первые N двоичных разрядов в этой разнице будут 0), и следовательно, меньше ε . Поэтому нам достаточно найти такую δ > 0, что любой x на расстоянии, меньшем или равном δ от x0, всё ещё будет давать в f(x) те же первые N+1 знаков, что и x0 . Тогда из вышесказанного будет следовать, что расстояние от f(x) до f(x0) меньше ε , и следовательно, f действительно непрерывна в точке x0.

Посмотрим на наше число x0 начиная с N+2-го разряда и дальше. Мы хотим найти такой разряд номер K, что при добавлении к x0 или вычитании из x0 числа, меньшего 1/10K (т.е. у него первые K разрядов нули), изменения в разложении x0 не продвигаются "левее" K-го разряда. Если мы найдём такое K >= N+2, то мы можем взять δ = 1/10K и всё доказано, т.к. тогда любое x на расстоянии δ или меньше от x0 сохраняет первые N+1 разрядов x0, а значит и первые N+1 разрядов f(x) у него такие же, как у f(x0), к чему мы и стремимся. Всегда ли мы сможем найти такой разряд N? Не всегда, т.к. может быть, что в числе x0 в N+2-м разряде и дальше уже идёт бесконечная череда девяток. Но если это не так, если есть хотя бы один разряд, отличный от девятки и больший по индексу, чем N+1, то мы сможем найти такое K -- оно будет либо самим этим разрядом, либо, в случае, если этот разряд 0, надо будет пропустить ещё какое-то конечное количество разрядов, равных нулю, и назначить K-тым следующий после них (нули нужно пропустить, чтобы можно было спокойно вычитать, не опасаясь "продвижения" результатов слишком далеко влево; нулей будет конечное кол-во, т.к. мы договорились в случае, когда у x0 есть два разложения, выбрать то, которое с девятками, а не то, которое с нулями).

В случае, если начиная с N+2-го разряда в x0 уже идёт бесконечная череда девяток, у нас есть маленькая техническая сложность, с которой легче всего справиться вот как. Для таких значений x0 (которые заканчиваются бесконечной чередой девяток) мы будем отдельно доказывать непрерывность сверху и непрерывность снизу; вместе они доказывают непрерывность вообще. Непрерывность сверху означает, что для любого ε > 0 существует δ > 0, так, что если x больше x0 и их разность не больше δ , то f(x) находится на расстоянии не больше ε от f(x0); и аналогично определяется непрерывность снизу (где x меньше x0). Для нашего числа теперь очень легко доказать непрерывность с помощью следующего трюка; сначала мы берём его разложение "с девятками", где оно заканчивается чередой девяток, и доказываем для него непрерывность снизу совершенно аналогично общему случаю выше (но т.к. нам нужно только вычитать из числа, а не прибавлять, вся эта череда девяток не "распостраняет" результат слишком далеко влево, чего мы и хотим избежать); потом берём то же число в разложении "с нулями", и доказываем для него непрерывность сверху (теперь мы только прибавляем, и опять-таки нет проблем с сохранением первых N+1 разрядов). Вот и всё.

В результате мы доказали, что наша функция непрерывна на каждом аргументе в отрезке (0,1).
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments