chapter03.qq

\chapter Индукция и последовательности \label chap:03:seq

\section Метод математической индукции
\subsection Описание метода

Часто нам нужно доказать, что какое-то утверждение верно при всех натуральных
$n$. Иными словами, у нас есть предикат $P(n)$ и мы хотим доказать утверждение
$\forall n\colon P(n)$. Иногда это можно сделать с помощью следующих двух шагов:

\enumerate
    \item Доказать $P(1)$. Это называется \emph{база индукции}.
    \item 
        Доказать утверждение $\forall k\colon P(k) \Rightarrow P(k+1)$, то есть
        доказать, что для всех натуральных $k$ выполняется утверждение «если
        $P(k)$ верно, то $P(k+1)$ тоже верно». Это называется \emph{индуктивный
        переход}.

Заметим, что доказать утверждение $\forall k\colon P(k) \Rightarrow P(k+1)$
проще, чем доказать утверждение $\forall n \colon P(n)$: в первом случае при
доказательстве $P(k+1)$ мы можем пользоваться  утверждением $P(k)$, как если бы
оно было уже доказанным, поскольку по определению операции импликации (см.
\ref[раздел][sec:02:impl] в предыдущей лекции), если так оказалось, что $P(k)$
неверно, импликация верна автоматически и ничего доказывать не надо.

Почему индукция работает? Давайте рассмотрим бесконечную последовательность
наших утверждений:

\eq
    P(1), \quad P(2), \quad P(3), \quad P(4), \ldots

Утверждение $P(1)$ доказано, поскольку это база индукции. Мы также доказали, что
если $P(1)$ верно, то $P(2)$ тоже верно — это наш индуктивный переход, который
доказан для всех натуральных $k$, и значит для $k=1$ тоже. Таким образом,
комбинируя доказанность $P(1)$ и $P(1) \Rightarrow P(2)$, приходим к выводу, что
$P(2)$ тоже верно. Посмотрим ещё раз на последовательность утвержений и
подчеркнём доказанные:
\eq
    \underline{P(1) \Rightarrow P(2)}, \quad P(3), \quad P(4), \ldots
Теперь можно в шаг индукции подставить $k=2$. Имеем: $P(2) \Rightarrow P(3)$. Но
мы только что доказали, что $P(2)$ верно. Значит, $P(3)$ тоже верно.
\eq
    \underline{P(1) \Rightarrow P(2) \Rightarrow P(3)}, \quad P(4), \ldots
И так далее. Двигаясь каждый раз на один шаг вправо, мы последовательно докажем
$P(4)$, потом $P(5)$ и т.д. Рано или поздно мы доберемся до любого натурального
числа $n$, и докажем $P(n)$. Раз так, то $P(n)$ доказано для всех натуральных
$n$.

\remark
    Рассуждение выше выглядит довольно убедительным и соответствует нашим
    представлениям о натуральных числах, но строго говоря не является
    доказательством. Более того: утверждение о том, что индукция работает,
    принимается за аксиому при попытке определить, что такое натуральное число
    (см. статью про \href[аксиоматику
    Пеано][https://ru.wikipedia.org/wiki/Аксиомы_Пеано]).

\subsection
    Неравенство Бернулли
В качестве примера давайте докажем неравенство Бернулли, которое нам понадобится
в дальнейшем.

\proposition
    Для всякого натурального $n$ и всякого $x \ge -1$, верно неравенство:
    \eq 
        (1+x)^n \ge 1+nx.
\proof
    Формально это утверждение записывается так:
    \align \nonumber
        \item \forall n \\ \forall x \colon (x \ge -1) \Rightarrow 
        \splitem \splonly{\Rightarrow} ((1 + x)^n \ge 1+nx)
    Поскольку мы делаем утверждение про выполнение неравенства не для всех
    вещественных $x$, а только для $x \ge -1$, приходится записывать формулу с
    импликацией. Но, как мы обсуждали \ref[на предыдущей
    лекции\nonumber][ssec:02:short], часто вместо этого пишут условие сразу после
    квантора, и мы тоже так будем делать:
    \eq
        \forall n \in \mathbb N\\ \forall x  \ge -1\colon (1 + x)^n \ge 1+nx.
    Заодно напишем явно, что $n$ натуральное.

    Мы хотим применить метод математической индукции. Что является предикатом
    $P(n)$, который мы хотим доказать для всех $n$?

    В данном случае, $P(n):=(\forall x  \ge -1\colon (1 + x)^n \ge 1+nx)$.
    Обратите внимание: написать просто $P(n):=((1 + x)^n \ge 1+nx)$ было бы
    некорректно — нужно что-то сказать про $x$, иначе получается предикат,
    который зависит не только от $n$, но и от $x$.

    Итак, теперь нам нужно доказать два шага индукции.

    \paragraph База индукции 

    Пусть $n=1$. Утверждение, которое мы хотим
    доказать, выглядит так: для всех $x \ge -1$ верно неравенство $(1+x)^1\ge
    1+1\cdot x$. После упрощения это неравенство превращается в $1+x \ge 1+x$,
    являющееся верным при всех $x$, а значит и при $x \ge -1$. База доказана.

    \paragraph Индуктивный переход

    Теперь мы хотим доказать, что при всех $k$, если $P(n)$ верно для $n=k$, то
    оно также верно и для $n=k+1$. Пусть $k$ — какое-то натуральное число, и
    пусть $n=k+1$. Пусть также $x\ge -1$. Рассмотрим неравенство, которое мы
    хотим доказать:

    \eq
        (1+x)^{k+1} \stackrel{?}{\ge} 1 + (k+1)x.
    Преобразуем левую часть:
    \eq
        (1+x)^{k+1}=(1+x)^k (1+x).
    У нас есть произведение двух чисел, и мы хотим доказать оценку снизу на него
    (то есть доказать, что оно больше какой-то величины). Первый сомножитель
    равен $(1+x)^k$. Заметим, что мы доказываем импликацию $P(k) \Rightarrow
    P(k+1)$. То есть в текущем доказательстве мы можем воспользоваться тем, что
    $P(k)$ верно. (В этот момент говорят, что мы воспользовались
    \emph{предположением индукции}.) При этом $P(k)$ утверждает, что при всех $x
    \ge -1$ верно неравенство 
    \eq
        (1+x)^k \ge 1+kx. 
    Умножая обе его части на
    $(1+x)$, мы можем заключить, что для всех $x \ge -1$:
    \equation \label eq:03:ge
        (1+x)^k (1+x) \ge (1+kx) (1+x).
    Теперь преобразуем правую часть \ref{eq:03:ge}:
    \align \nonumber
        \item (1+kx) (1+x) & = 1 + kx + x + kx^2 = 
        \splitem \splonly{&=} 1 + (k+1)x + kx^2 \ge
        \splitem \splonly{&\ge} 1 + (k+1)x.
    Последнее неравенство следует из того факта, что $x^2\ge 0$ при всех
    вещественных $x$.

    Если у нас есть цепочка равенств и неравенств, направленных в одну сторону
    (например, $A=B\ge C=D\ge E$), мы получаем неравенство, которое связывает
    начало этой цепочки и её конец ($A \ge E$), в силу свойства
    \emph{транзитивности} неравенства (если $A \ge B$ и $B \ge C$, то $A \ge
    C$). Значит, мы доказали, что $(1+x)^{k+1} \ge 1+(k+1)x$ для всех $x \ge -1$
    при условии, что предположение индукции выполнено.

    Индуктивный переход доказан, а с ним и всё утверждение.

\question
    Укажите в доказательстве место, где мы воспользовались неравенством $x \ge
    -1$, за которым на протяжении всего рассуждения так бережно следили. Если
    сразу это сделать не получается, можно воспользоваться таким приёмом:
    возьмите какое-нибудь $x < -1$, для которого неравенство неверно, и
    проследите, шаг за шагом, на каком месте доказательство «ломается», какой из
    переходов оказывается неверным.

\section Последовательности и их свойства

\subsection Примеры и определения

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

\example
    \itemize
        \item Последовательность $1, 4, 9, 16, \ldots, n^2,\ldots$, состоящая из
            квадратов натуральных чисел. Обозначим её через $\set{a_n}$,
            $a_n=n^2$, $n\in \mathbb N$. Обозначение с фигурными скобками
            $\set{a_n}$ используется, чтобы назвать всю бесконечную
            последовательность целиком, тогда как $a_n$ — это её член с номером
            $n$.
        \item Последовательность $1, -1, 1, -1, 1, -1,\ldots$, состоящая из
            чередующихся чисел $1$ и $-1$. Пусть эта последовательнсоть
            $\set{b_n}$. Тогда её можно задать как
            $b_n=(-1)^{n+1}$. (Если из контекста понятно, что $n$ — натуральное
            число, и равенство верно для всех $n$, соответствующие кванторы и
            уточнения часто не пишут.)
        \item Последовательность $1, 1, 2, 3, 5, 8, 13, \ldots$ —
            последовательность чисел Фибоначчи. Обозначим её через $\set{f_k}$.
            Тогда имеем:
            \gather \nonumber
                \item f_1=1,\quad f_2=1,\longonly{\quad} 
                \splitem \forall k\in \mathbb N\colon f_{k+2}=f_{k+1}+f_{k}.
            Это пример последовательности, заданной \emph{рекуррентно} — каждый
            следующий член задаётся предыдущими. Общая формула, позволяющая
            найти $f_k$, зная $k$ без вычисления всех предыдущих членов, тоже
            существует (она называется \href[формулой
            Бине][https://ru.wikipedia.org/wiki/Числа_Фибоначчи#Формула_Бине]),
            хотя из способа задания последовательности она совершенно не
            выглядит очевидной.
        \item
            Можно рассмотреть такую рекуррентную последовательность:
            $\set{x_n}$, $x_1=1$, $x_{n+1}=3{,}57(x_n - x_n^2)$. Несмотря на то,
            что она задаётся простым рекуррентным законом, написать общую
            формулу для её $n$-го элемента скорее всего невозможно. (Можете
            запрограммировать эту последовательность и попробовать уловить в ней
            какую-нибудь закономерность. Только не увлекайтесь этим слишком
            сильно!)
        \item Последовательность $1, \frac{1}{2}, \frac{1}{3},
            \frac{1}{4},\ldots, \frac{1}{n}, \ldots$. Её можно задать как
            $\set{d_n}$, $d_n=\frac{1}{n}$.

Итак, последовательность — это бесконечный ряд чисел (мы рассматриваем именно
числовые последовательности). Формальное определение использует понятие
отображения (см. \ref[раздел][sec:01:maps] лекции \ref{chap:01:setsnumbers}):

\definition
    \emph{Числовая последовательность} — это отобржаение из множества
    натуральных чисел $\mathbb N$ в множество вещественных чисел $\mathbb R$.

Действительно, чтобы задать последовательность, нужно указать, чему равен её
первый элемент, второй элемент и так далее, для каждого натурального $n$ нужно
задать, чему равен элемент с номером $n$. То есть нужно задать отображение из
$\mathbb N$ в $\mathbb R$. Как правило, элемент с номером $n$ обозначается
нижним индексом (например, $a_n$), но мы могли бы обозначать его как обычно
обозначается значение функции в точке: $a(n)$.

\subsection Монотонность

Если элементы последовательности возрастают или убывают, такая
последовательность называется монотонной. Дадим формальные определения.

\definition
    Последовательность $\set{a_n}$ называется (строго) \emph{возрастающей}, если
    для всех натуральных $n$, $a_{n+1}>a_n$ (каждый следующий член строго больше
    предыдущего). Слово «строго» часто опускают, обычно когда говорят, что
    последовательность возрастает, подразумевается, что она возрастает строго.

\definition
    Последовательность $\set{a_n}$ называется \emph{неубывающей} или
    \emph{нестрого возрастающей}, если для всех натуральных $n$, $a_{n+1} \ge
    a_n$.

\definition
    Последовательность $\set{a_n}$ называется (строго) \emph{убывающей}, если
    для всех натуральных $n$, $a_{n+1}<a_n$. 

\definition
    Последовательность $\set{a_n}$ называется \emph{невозрастающей} или
    \emph{нестрого убывающей}, если для всех натуральных $n$, $a_{n+1} \le
    a_n$.

\remark
    Заметим, что если последовательность не является возрастающей, это не
    значит, что она является невозрастающей. Например, последовательность
    $(-1)^n$ не является возрастающей, но она также не является невозрастающей.
    Аналогичная ситуация и с убыванием.

\subsection Ограниченность \label ssec:03:bound

\definition \label def:03:bounded
    Последовательность $\set{a_n}$ называется \emph{ограниченной сверху}, если
    найдётся такое число $C \in \mathbb R$, что для всех $n \in \mathbb N$, $a_n
    < C$. В кванторах это звучит так:
    \eq
        \exists C \in \mathbb R \\ \forall n \in \mathbb N\colon a_n < C.
В этом определении мы использовали строгое неравенство. Что будет, если
использовать нестрогое неравенство? Следует ли нам ввести понятие «нестрой
ограниченности сверху», по аналогии с нестрогим возрастанием? Давайте рассмотрим
такое альтернативное определение:
\definition \label def:03:bounded-nonstrict
    Последовательность $\set{a_n}$ называется \emph{ограниченной сверху}, если
    \eq
        \exists C \in \mathbb R \\ \forall n \in \mathbb N\colon a_n \le C.
Посмотрим внимательно на определения \ref{def:03:bounded} и
\ref{def:03:bounded-nonstrict}. Задают ли оно одно и то же понятие, или разные?
Иными словами, существует ли последовательность, которая удовлетворяет условию
одного из этих определений, и не удовлетворяет другому?

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

Важный момент состоит в следующем. В каждом из определений фигурирует
константа $C$, которая выбирается по последовательности. Каждое из определений
говорит, что такая константа существует. В обоих определениях для её
обозначения используется одна и та же буква. Однако, как мы обсуждали, если
какая-то переменная «связывается» квантором, она как бы не существует за
пределами соответствующей формулы. Поэтому константы $C$ в этих двух
определениях не имеют никакого отношения друг к другу. Иными словами, их можно
выбирать по-разному. Этот факт позволяет доказать, что эти два определения на
самом деле эквивалентны.

\proposition
    Рассмотрим последовательность $\set{a_n}$. Рассмотрим два утверждения:
    \align
        \item 
            A& = (\exists C_1 \in \mathbb R \\ \forall n \in \mathbb N\colon a_n < C_1);
        \item 
            B& = (\exists C_2 \in \mathbb R \\ \forall n \in \mathbb N\colon a_n \le C_2).
    Утверждения $A$ и $B$ эквивалентны: если верно одно, то верно и другое.

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

\proof
    Докажем, что если $A$ верно, то $B$ тоже верно. Утверждение $A$ гарантирует,
    что существует такое $C_1$, что для всех натуральных $n$, $a_n < C_1$. Чтобы
    доказать $B$, нужно предъявить такое $C_2$, что для всех натуральных $n$,
    $a_n \le C_2$. Возьмём в качестве $C_2$ число $C_1$, существование которого
    гарантируется утверждением $A$:
    \eq
        C_2:=C_1.
    (Вообще говоря, таких подходящих чисел может быть много, возьмём любое из них.)

    Из определения $C_1$, мы знаем, что для любого натурального $n$, $a_n <
    C_1$. Но тогда для любого натурального $n$, $a_n \le C_1=C_2$. (Условие $a_n
    < C_1$ влечёт $a_n \le C_1$ — если верно строгое неравенство, нестрогое
    гарантированно верно.) Таким образом, $A \Rightarrow B$.

    Докажем в другую сторону, если $B$ верно, то и $A$ верно. Согласно
    утверждению $B$, найдётся такое число $C_2$, что для всех натуральных $n$,
    $a_n \le C_2$. Положим: 
    \eq
        C_1:=C_2+1.
    Тогда $C_2 = C_1 - 1 < C_1$. (Конечно, вместо единицы можно было взять любое
    положительное число.)

    Из утверждения $C_2$ имеем: для всякого натурального $n$,
    \eq
        a_n \le C_2 = C_1 - 1 < C_1.
    Из этого следует, что $a_n < C_1$ (самое большое значение, которое $a_n$
    может применять, это $C_2$, но $C_2$ строго меньше $C_1$, значит, $a_n$
    строго меньше $C_1$). Условие утверждения $A$ выполняется.

    Таким образом, мы доказали $A$, предположив, что $B$ верно. То есть $B
    \Rightarrow A$.

    Раз $A$ влечёт $B$ и $B$ влечёт $A$, эти утверждения эквивалентны: всегда
    оба верны или оба неверны.

Таким образом, никакой необходимости вводить новое понятие «нестрогой
ограниченности сверху» нет: вне зависимости от того, строгое или нестрогое
неравенство использовать в определении, получится одно и то же понятие.

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

Теперь можно дать ещё два определения.

\definition \label def:03:bounded-below
    Последовательность $\set{a_n}$ называется \emph{ограниченной снизу}, если
    найдётся такое число $C \in \mathbb R$, что для всех $n \in \mathbb N$, $a_n
    > C$.


\definition \label def:03:bounded-abs
    Последовательность $\set{a_n}$ называется \emph{ограниченной}, если найдётся
    такое число $C \in \mathbb R$, что для всех $n \in \mathbb N$, $|a_n| < C$.

\exercise
    Докажите, что последовательность является ограниченной тогда и только тогда,
    когда она ограничена сверху и ограничена снизу.

\section Счётные и несчётные множества
\subsection Счётность множества рациональных чисел
Существует ли последовательность, в которой записаны все рациональные числа?
Иными словами, существует ли сюръективное отображение из $\mathbb N$ в $\mathbb
Q$? Можно ли каждому рациональному числу присвоить по номеру, так, чтобы разные
числа получили разные номера?

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

Тем не менее, оказывается, что рациональных чисел «так же много», как
натуральных. Иными словами, можно сопоставить каждому натуральному числу по
рациональному, так, что все рациональные числа получат по номеру.

Это можно сделать по-разному. Мне нравится такой подход. Мы знаем, что
рациональные числа задаются обыкновенными дробями $\frac{p}{q}$, где $p$
целое число, а $q$ натуральное. Рассмотрим обыкновенную декартову плоскость,
пусть горизонтальная ось — $Op$, а вертикальная — $Oq$.  Тогда каждой дроби
$\frac{p}{q}$ будет соответствовать точка на плоскости, лежащая в верхней части
плоскости, на «решетке», состоящей из точек с целочисленными координатами, см.
\ref[рис.][fig:03:qplane].  Конечно, разные точки могут задавать одно и то же
число — например, точка $(1, 2)$ соответствует дроби $\frac{1}{2}$, которая
равна дроби $\frac{2}{4}$, соответствующей точке $(2, 4)$. Но важно, что
абсолютно все рациональные числа представлены на этой картинке. 
\figure
    \img
        \src pic-4.svg
        \style
            padding: 2em;
        \alt
            Представление рациональных чисел в виде точек на декартовой
            плоскости, см. описание в тексте.
    \caption
        Рациональные числа в виде решетки.
    \label fig:03:qplane

Теперь укажем, в каком порядке мы будем помещать числа в нашу
последовательность. См. \ref[рис.][fig:03:snake].

\figure
    \img
        \src pic-5.svg
        \style
            padding:1em;
        \alt
            Обход множества рациональных чисел, описание процедуры обхода см. в
            тексте
    \caption «Змейка», обходящая все рациональные числа
    \label fig:03:snake

Начнём с середины картинки — точка $(0, 1)$ соответствует числу 0. Поместим её в
последовательность. Затем сдвинемся вправо, получим точку $(1, 1)$ (число 1).
Добавим её. Затем вверх, в точку $(1, 2)$ (число $\frac{1}{2}$). Теперь влево,
$(0, 2)$ ($0$ уже был, но можно вписать ещё раз), снова влево, $(-1, 2)$, потом
вниз, $(-1, 1)$, потом влево $(-2, 1)$, потом вверх $(-2, 2)$, снова вверх $(-2,
3)$, потом вправо несколько шагов (пока не дойдём до $p=3$), потом вниз до
$q=1$, потом вправо на один шаг и т.д. Получится такая «змейка». Понятно, что
двигаясь таким образом мы дойдём до любой из рассматриваемых точек, и значит
переберем все рациональные числа.

Если вам кажется это рассуждение недостаточно строгим, можно предложить такое.
Для всякого рационального числа определим его «псевдомодуль»: если число $x$
равно $\frac{p}{q}$ и это несократимая дробь, псевдомодулем $x$ будет $|p|+q$.
Псевдомодуль — натуральное число. Рассмотрим все рациональные числа с
псевдомодулем 1 — это единственное число $0$. Поместим его в нашу
последовательность. Рассмотрим теперь рациональные числа с псевдомодулем $2$
(это $1$). Поместим его в нашу последовательность. Рациональных чисел с
псевдомодулем $3$ уже больше: это $\frac{2}{1}$, $\frac{-2}{1}$, $\frac{1}{2}$
и $\frac{-1}{2}$. Поместим их в нашу последовательность (в любом порядке). Будем
продолжать этот процесс. Для каждого фиксированного $n$, количество рациональных
чисел с псевдомодулем $n$ конечно. Значит, их можно записать в нашу
последовательность на очередном шаге. Поскольку у любого рационального числа
есть натуральный псевдомодуль, рано или поздно мы дойдём до любого из них и
запишем его в нашу последовательность.

Заметим, что если мы каким-то образом построили последовательность, в которой
есть все рациональные числа, то из неё легко построить последовательность, в
которой каждое рациональное число встречается ровно один раз. Для этого из
исходной последовательности можно просто выкинуть все повторы. Получающаяся
последовательность задаст не просто сюръекцию, а взаимно однозначное отображение
$\mathbb N$ на $\mathbb Q$. Таким образом, $\mathbb N$ и $\mathbb Q$
\snref{равномощны}.

\definition
    Если множество равномощно $\mathbb N$, говорят, что оно \emph{счётно}.
Мы доказали, что множество рациональных чисел счётно.

А бывают ли несчётные множества? Сейчас узнаем.

\subsection Несчётность континуума

Существует ли последовательность, в которой перечислены все вещественные числа?
Давайте даже упростим задачу: пусть не все вещественные числа, а только
принадлежащие полуинтервалу $[0, 1)$.  Оказывается, такой последовательности
нет.

\theorem (Кантор)
    Не существует сюръективного отображения $\mathbb N$ в $[0, 1)$.
\proof
    Докажем от противного. Пусть такое отображение существует. Иными словами,
    пусть существует такая последовательность $\set{x_n}$, что в ней перечислены
    все вещественные числа из $[0, 1)$. Значит, для всякого $x\in [0, 1)$
    найдётся такое $k$, что $x_k=x$.

    Будем записывать вещественные числа из $[0, 1)$ в виде бесконечных
    десятичных дробей. Они все будут иметь нулевую целую часть (до запятой будет
    ноль). Договоримся никогда не использовать запись с хвостом из девяток. В
    этом случае каждое число получит единственную запись. Всякое число $a
    \in [0, 1)$ будем записывать в виде $0{,}a^{(1)}a^{(2)}\ldots$,
    где $a^{(i)}$ — $i$-я цифра числа $a$. (Здесь верхний индекс обозначает не
    степень, а просто номер.)

    Можно записать последовательность $x_1, x_2, \ldots$ в виде:

    \align \nonumber
        \item x_1 & = {0{,}x_1^{(1)}x_1^{(2)}x_1^{(3)}x_1^{(4)}}\ldots
        \item x_2 & = {0{,}x_2^{(1)}x_2^{(2)}x_2^{(3)}x_2^{(4)}}\ldots
        \item x_3 & = {0{,}x_3^{(1)}x_3^{(2)}x_3^{(3)}x_3^{(4)}}\ldots
        \item x_4 & = {0{,}x_4^{(1)}x_4^{(2)}x_4^{(3)}x_4^{(4)}}\ldots
        \item \ldots
    Рассмотрим теперь число $z=0{,}z^{(1)}z^{(2)}z^{(3)}\ldots$. Построим его
    следующим образом. В качестве первой цифры $z$ возьмём \emph{не первую цифру}
    числа $x_1$. В качестве второй цифры $z$ возьмём \emph{не вторую цифру}
    числа $x_2$. И так далее. В качестве $n$-й цифры $z$ возьмём \emph{не $n$-ю} цифру
    числа $x_n$. Потребуем также, чтобы все цифры числа $z$ не были девятками
    (чтобы избежать ситуации, когда построенное нами число оканчивается хвостом
    из девяток).

    Для определенности, можно выбрать конкретный алгоритм выбора цифр числа $z$.
    Например, давайте скажем, что $z^{(i)}$ равно $x_i^{(i)}-1$ (то есть мы
    взяли $i$'ую цифру $i$-го числа последовательности и уменьшили на 1), если
    только $x_i^{(i)}\ne 0$. Если эта цифра оказалась нулём, возьмём в качестве
    $z^{(i)}$ цифру 7. (Нам всё равно, какую цифру брать, лишь бы не $x_i^{(i)}$
    и не 9.)

    Например, если последовательность $\set{x_n}$ выглядит так (подчёркнуты
    цифры, участвующие в построении $z$):
    \align \nonumber
        \item x_1 &= 0{,}\underline{3}781\ldots
        \item x_2 &= 0{,}2\underline{0}94\ldots
        \item x_3 &= 0{,}52\underline{8}3\ldots
        \item x_4 &= 0{,}432\underline{1}\ldots
        \item \ldots 
    то число $z=0{,}2770\ldots$ (см. \ref[рис.][fig:03:cantor]).

    \figure
        \img
            \src pic-10.svg
            \style
                padding: 2em;
            \alt
                Построение числа $z$, см. описание в тексте
        \caption
            Построение числа $z$ путём выбора диагональных цифр и их
            изменения. Все цифры, кроме 0, уменьшаются на 1, цифра 0 заменяется
            на 7.
        \label fig:03:cantor
        

    Рассмотрим теперь $z$. Это вещественное число из полуинтервала $[0, 1)$.
    Значит, оно находится в нашей последовательности на каком-то месте. На
    каком? Оно не может находиться на первом месте, потому что по крайней мере в
    первой цифре гарантированно не совпадает с $x_1$ (мы так выбрали его первую
    цифру). Оно не может находиться на втором месте, потому что по крайней мере
    во второй цифре гарантированно не совпадает с $x_2$. И так далее. Отсюда
    видно, что оно не может находиться \emph{ни на каком месте} нашей
    последовательности.

    Формально, пусть это не так, и существует такое $k$, что $z=x_k$. Но по
    построению, $z^{(k)}\ne x_k^{(k)}$, то есть $k$-я цифра числа $z$ не
    совпадает с $k$-й цифрой числа $x_k$. Противоречие.

    Таким образом, мы построили число из $[0, 1)$, которого нет в нашей
    последовательности. Значит, неверно, что последовательность содержит все
    числа из этого множества.

\remark
    Мы показали, что множество вещественных чисел на полуинтервале $[0, 1)$ не
    равномощно $\mathbb N$, то есть не счётно. Его мощность больше мощности
    множества натуральных чисел: она называется \emph{мощностью континуум}.
    Множество вещественных чисел $\mathbb R$ также имеет мощность континуум, то
    есть существует взаимно однозначное отображение $\mathbb R$ на $[0, 1)$.

\exercise
    Рассмотрим множество всевозможных пар чисел $(x, y)$, где $x\in [0, 1)$ и
    $y\in [0, 1)$. Докажите, что это множество также имеет мощность континуум,
    то есть существует взаимно однозначное отображение этого множества на $[0,
    1)$.
\remark
    Приведенное доказательство использует приём, известный как \emph{канторов
    диагональный процесс}. Он лежит в основе и других глубоких фактов в
    математике, например, \href[теоремы Гёделя о
    неполноте][https://ru.wikipedia.org/wiki/Теорема_Гёделя_о_неполноте].