3Индукция и последовательности

3.1Метод математической индукции

3.1.1Описание метода

Часто нам нужно доказать, что какое-то утверждение верно при всех натуральных

n

. Иными словами, у нас есть предикат

P (n)

и мы хотим доказать утверждение

\forall n : P (n)

. Иногда это можно сделать с помощью следующих двух шагов:

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

Заметим, что доказать утверждение

\forall k : P (k) \Rightarrow P (k + 1)

проще, чем доказать утверждение

\forall n : P (n)

: в первом случае при доказательстве

P (k + 1)

мы можем пользоваться утверждением

P (k)

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

P (k)

неверно, импликация верна автоматически и ничего доказывать не надо.

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

P (1), P (2), P (3), P (4), \dots

Утверждение

P (1)

доказано, поскольку это база индукции. Мы также доказали, что если

P (1)

верно, то

P (2)

тоже верно — это наш индуктивный переход, который доказан для всех натуральных

k

, и значит для

k = 1

тоже. Таким образом, комбинируя доказанность

P (1)

P (1) \Rightarrow P (2)

, приходим к выводу, что

P (2)

тоже верно. Посмотрим ещё раз на последовательность утвержений и подчеркнём доказанные:

P (1) \Rightarrow P (2) - --------- -, P (3), P (4), \dots

Теперь можно в шаг индукции подставить

k = 2

. Имеем:

P (2) \Rightarrow P (3)

. Но мы только что доказали, что

P (2)

верно. Значит,

P (3)

тоже верно.

P (1) \Rightarrow P (2) \Rightarrow P (3) - ---------------- -, P (4), \dots

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

P (4)

, потом

P (5)

и т.д. Рано или поздно мы доберемся до любого натурального числа

n

, и докажем

P (n)

. Раз так, то

P (n)

доказано для всех натуральных

n

Замечание 1. Рассуждение выше выглядит довольно убедительным и соответствует нашим представлениям о натуральных числах, но строго говоря не является доказательством. Более того: утверждение о том, что индукция работает, принимается за аксиому при попытке определить, что такое натуральное число (см. статью про аксиоматику Пеано).

3.1.2Неравенство Бернулли

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

Утверждение 1. Для всякого натурального

n

и всякого

x \geq - 1

, верно неравенство:

(1 + x)^{n} \geq 1 + n x .

Доказательство. Формально это утверждение записывается так:

\begin{matrix} \forall n \forall x : (x \geq - 1) \Rightarrow ((1 + x)^{n} \geq 1 + n x) \end{matrix}

\begin{matrix} \forall n \forall x : (x \geq - 1) \Rightarrow \Rightarrow ((1 + x)^{n} \geq 1 + n x) \end{matrix}

Поскольку мы делаем утверждение про выполнение неравенства не для всех вещественных

x

, а только для

x \geq - 1

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

\forall n \in N \forall x \geq - 1 : (1 + x)^{n} \geq 1 + n x .

Заодно напишем явно, что

n

натуральное.

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

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

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

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

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

(1 + x)^{k + 1} ? \geq 1 + (k + 1) x .

Преобразуем левую часть:

(1 + x)^{k + 1} = (1 + x)^{k} (1 + x) .

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

(1 + x)^{k}

. Заметим, что мы доказываем импликацию

P (k) \Rightarrow P (k + 1)

. То есть в текущем доказательстве мы можем воспользоваться тем, что

P (k)

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

P (k)

утверждает, что при всех

x \geq - 1

верно неравенство

(1 + x)^{k} \geq 1 + k x .

Умножая обе его части на

(1 + x)

, мы можем заключить, что для всех

x \geq - 1

\begin{matrix} (1 + x)^{k} (1 + x) \geq (1 + k x) (1 + x) . \\ (3.1) \end{matrix}

Теперь преобразуем правую часть (3.1):

\begin{matrix} (1 + k x) (1 + x) & = 1 + k x + x + k x^{2} = 1 + (k + 1) x + k x^{2} \geq 1 + (k + 1) x . \end{matrix}

\begin{matrix} (1 + k x) (1 + x) & = 1 + k x + x + k x^{2} = = 1 + (k + 1) x + k x^{2} \geq \geq 1 + (k + 1) x . \end{matrix}

Последнее неравенство следует из того факта, что

x^{2} \geq 0

при всех вещественных

x

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

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

Вопрос 1. Укажите в доказательстве место, где мы воспользовались неравенством

x \geq - 1

, за которым на протяжении всего рассуждения так бережно следили. Если сразу это сделать не получается, можно воспользоваться таким приёмом: возьмите какое-нибудь

x < - 1

, для которого неравенство неверно, и проследите, шаг за шагом, на каком месте доказательство «ломается», какой из переходов оказывается неверным.

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

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

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

Пример 1.

Последовательность $1, 4, 9, 16, \dots, n^{2}, \dots$ , состоящая из квадратов натуральных чисел. Обозначим её через ${a_{n}}$ , $a_{n} = n^{2}$ , $n \in N$ . Обозначение с фигурными скобками ${a_{n}}$ используется, чтобы назвать всю бесконечную последовательность целиком, тогда как $a_{n}$ — это её член с номером $n$ .
Последовательность $1, - 1, 1, - 1, 1, - 1, \dots$ , состоящая из чередующихся чисел $1$ и $- 1$ . Пусть эта последовательнсоть ${b_{n}}$ . Тогда её можно задать как $b_{n} = (- 1)^{n + 1}$ . (Если из контекста понятно, что $n$ — натуральное число, и равенство верно для всех $n$ , соответствующие кванторы и уточнения часто не пишут.)
Последовательность $1, 1, 2, 3, 5, 8, 13, \dots$ — последовательность чисел Фибоначчи. Обозначим её через ${f_{k}}$ . Тогда имеем:
$\begin{matrix} f_{1} = 1, f_{2} = 1, \forall k \in N : f_{k + 2} = f_{k + 1} + f_{k} . \end{matrix}$

$\begin{matrix} f_{1} = 1, f_{2} = 1, \forall k \in N : f_{k + 2} = f_{k + 1} + f_{k} . \end{matrix}$
Это пример последовательности, заданной рекуррентно — каждый следующий член задаётся предыдущими. Общая формула, позволяющая найти $f_{k}$ , зная $k$ без вычисления всех предыдущих членов, тоже существует (она называется формулой Бине), хотя из способа задания последовательности она совершенно не выглядит очевидной.
Можно рассмотреть такую рекуррентную последовательность: ${x_{n}}$ , $x_{1} = 1$ , $x_{n + 1} = 3, 57 (x_{n} - x_{n}^{2})$ . Несмотря на то, что она задаётся простым рекуррентным законом, написать общую формулу для её $n$ -го элемента скорее всего невозможно. (Можете запрограммировать эту последовательность и попробовать уловить в ней какую-нибудь закономерность. Только не увлекайтесь этим слишком сильно!)
Последовательность $1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots, \frac{1}{n}, \dots$ . Её можно задать как ${d_{n}}$ , $d_{n} = \frac{1}{n}$ .

Итак, последовательность — это бесконечный ряд чисел (мы рассматриваем именно числовые последовательности). Формальное определение использует понятие отображения (см. раздел 1.3 лекции 1):

Определение 1. Числовая последовательность — это отобржаение из множества натуральных чисел

N

в множество вещественных чисел

R

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

3.2.2Монотонность

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

Определение 2. Последовательность

{a_{n}}

называется (строго) возрастающей, если для всех натуральных

n

a_{n + 1} > a_{n}

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

Определение 3. Последовательность

{a_{n}}

называется неубывающей или нестрого возрастающей, если для всех натуральных

n

a_{n + 1} \geq a_{n}

Определение 4. Последовательность

{a_{n}}

называется (строго) убывающей, если для всех натуральных

n

a_{n + 1} < a_{n}

Определение 5. Последовательность

{a_{n}}

называется невозрастающей или нестрого убывающей, если для всех натуральных

n

a_{n + 1} \leq a_{n}

Замечание 2. Заметим, что если последовательность не является возрастающей, это не значит, что она является невозрастающей. Например, последовательность

(- 1)^{n}

не является возрастающей, но она также не является невозрастающей. Аналогичная ситуация и с убыванием.

3.2.3Ограниченность

Определение 6. Последовательность

{a_{n}}

называется ограниченной сверху, если найдётся такое число

C \in R

, что для всех

n \in N

a_{n} < C

. В кванторах это звучит так:

\exists C \in R \forall n \in N : a_{n} < C .

В этом определении мы использовали строгое неравенство. Что будет, если использовать нестрогое неравенство? Следует ли нам ввести понятие «нестрой ограниченности сверху», по аналогии с нестрогим возрастанием? Давайте рассмотрим такое альтернативное определение:

Определение 7. Последовательность

{a_{n}}

называется ограниченной сверху, если

\exists C \in R \forall n \in N : a_{n} \leq C .

Посмотрим внимательно на определения 6 и 7. Задают ли оно одно и то же понятие, или разные? Иными словами, существует ли последовательность, которая удовлетворяет условию одного из этих определений, и не удовлетворяет другому?

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

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

Утверждение 2. Рассмотрим последовательность

{a_{n}}

. Рассмотрим два утверждения:

\begin{matrix} A & = (\exists C_{1} \in R \forall n \in N : a_{n} < C_{1}); B & = (\exists C_{2} \in R \forall n \in N : a_{n} \leq C_{2}) . \\ (3.2) (3.3) \end{matrix}

Утверждения

A

B

эквивалентны: если верно одно, то верно и другое.

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

Доказательство. Докажем, что если

A

верно, то

B

тоже верно. Утверждение

A

гарантирует, что существует такое

C_{1}

, что для всех натуральных

n

a_{n} < C_{1}

. Чтобы доказать

B

, нужно предъявить такое

C_{2}

, что для всех натуральных

n

a_{n} \leq C_{2}

. Возьмём в качестве

C_{2}

число

C_{1}

, существование которого гарантируется утверждением

A

C_{2} := C_{1} .

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

Из определения $C_{1}$ , мы знаем, что для любого натурального $n$ , $a_{n} < C_{1}$ . Но тогда для любого натурального $n$ , $a_{n} \leq C_{1} = C_{2}$ . (Условие $a_{n} < C_{1}$ влечёт $a_{n} \leq C_{1}$ — если верно строгое неравенство, нестрогое гарантированно верно.) Таким образом, $A \Rightarrow B$ .

Докажем в другую сторону, если $B$ верно, то и $A$ верно. Согласно утверждению $B$ , найдётся такое число $C_{2}$ , что для всех натуральных $n$ , $a_{n} \leq C_{2}$ . Положим:

C_{1} := C_{2} + 1.

Тогда

C_{2} = C_{1} - 1 < C_{1}

. (Конечно, вместо единицы можно было взять любое положительное число.)

Из утверждения $C_{2}$ имеем: для всякого натурального $n$ ,

a_{n} \leq 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$ , эти утверждения эквивалентны: всегда оба верны или оба неверны.∎

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

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

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

Определение 8. Последовательность

{a_{n}}

называется ограниченной снизу, если найдётся такое число

C \in R

, что для всех

n \in N

a_{n} > C

Определение 9. Последовательность

{a_{n}}

называется ограниченной, если найдётся такое число

C \in R

, что для всех

n \in N

| a_{n} | < C

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

3.3Счётные и несчётные множества

3.3.1Счётность множества рациональных чисел

Существует ли последовательность, в которой записаны все рациональные числа? Иными словами, существует ли сюръективное отображение из

N

Q

? Можно ли каждому рациональному числу присвоить по номеру, так, чтобы разные числа получили разные номера?

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

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

Это можно сделать по-разному. Мне нравится такой подход. Мы знаем, что рациональные числа задаются обыкновенными дробями $\frac{p}{q}$ , где $p$ целое число, а $q$ натуральное. Рассмотрим обыкновенную декартову плоскость, пусть горизонтальная ось — $O p$ , а вертикальная — $O q$ . Тогда каждой дроби $\frac{p}{q}$ будет соответствовать точка на плоскости, лежащая в верхней части плоскости, на «решетке», состоящей из точек с целочисленными координатами, см. рис. 3.1. Конечно, разные точки могут задавать одно и то же число — например, точка $(1, 2)$ соответствует дроби $\frac{1}{2}$ , которая равна дроби $\frac{2}{4}$ , соответствующей точке $(2, 4)$ . Но важно, что абсолютно все рациональные числа представлены на этой картинке.

Представление рациональных чисел в виде точек на декартовой
плоскости, см. описание в тексте.

Рис. 3.1: Рациональные числа в виде решетки.

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

Обход множества рациональных чисел, описание процедуры обхода см. в
тексте

Рис. 3.2: «Змейка», обходящая все рациональные числа

Начнём с середины картинки — точка

(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$ конечно. Значит, их можно записать в нашу последовательность на очередном шаге. Поскольку у любого рационального числа есть натуральный псевдомодуль, рано или поздно мы дойдём до любого из них и запишем его в нашу последовательность.

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

Определение 10. Если множество равномощно

N

, говорят, что оно счётно.

Мы доказали, что множество рациональных чисел счётно.

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

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

Существует ли последовательность, в которой перечислены все вещественные числа? Давайте даже упростим задачу: пусть не все вещественные числа, а только принадлежащие полуинтервалу

[0, 1)

. Оказывается, такой последовательности нет.

Теорема 1. (Кантор) Не существует сюръективного отображения

N

[0, 1)

Доказательство. Докажем от противного. Пусть такое отображение существует. Иными словами, пусть существует такая последовательность

{x_{n}}

, что в ней перечислены все вещественные числа из

[0, 1)

. Значит, для всякого

x \in [0, 1)

найдётся такое

k

, что

x_{k} = x

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

Можно записать последовательность $x_{1}, x_{2}, \dots$ в виде: $\begin{matrix} x_{1} & = 0, x_{1}^{(1)} x_{1}^{(2)} x_{1}^{(3)} x_{1}^{(4)} \dots x_{2} & = 0, x_{2}^{(1)} x_{2}^{(2)} x_{2}^{(3)} x_{2}^{(4)} \dots x_{3} & = 0, x_{3}^{(1)} x_{3}^{(2)} x_{3}^{(3)} x_{3}^{(4)} \dots x_{4} & = 0, x_{4}^{(1)} x_{4}^{(2)} x_{4}^{(3)} x_{4}^{(4)} \dots \dots \end{matrix}$ Рассмотрим теперь число $z = 0, z^{(1)} z^{(2)} z^{(3)} \dots$ . Построим его следующим образом. В качестве первой цифры $z$ возьмём не первую цифру числа $x_{1}$ . В качестве второй цифры $z$ возьмём не вторую цифру числа $x_{2}$ . И так далее. В качестве $n$ -й цифры $z$ возьмём не $n$ -ю цифру числа $x_{n}$ . Потребуем также, чтобы все цифры числа $z$ не были девятками (чтобы избежать ситуации, когда построенное нами число оканчивается хвостом из девяток).

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

Например, если последовательность ${x_{n}}$ выглядит так (подчёркнуты цифры, участвующие в построении $z$ ): $\begin{matrix} x_{1} & = 0, 3 - 781 \dots x_{2} & = 0, 2 0 - 94 \dots x_{3} & = 0, 52 8 - 3 \dots x_{4} & = 0,432 1 - \dots \dots \end{matrix}$ то число $z = 0,277 0 \dots$ (см. рис. 3.3).

Построение числа $z$, см. описание в тексте

Рис. 3.3: Построение числа

z

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

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

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

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

Замечание 3. Мы показали, что множество вещественных чисел на полуинтервале

[0, 1)

не равномощно

N

, то есть не счётно. Его мощность больше мощности множества натуральных чисел: она называется мощностью континуум. Множество вещественных чисел

R

также имеет мощность континуум, то есть существует взаимно однозначное отображение

R

на

[0, 1)

Упражнение 2. Рассмотрим множество всевозможных пар чисел

(x, y)

, где

x \in [0, 1)

y \in [0, 1)

. Докажите, что это множество также имеет мощность континуум, то есть существует взаимно однозначное отображение этого множества на

[0, 1)

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

← Предыдущая глава Следующая глава →

Математический анализ Записки лекций

3Индукция и последовательности

3.1Метод математической индукции

3.1.1Описание метода

3.1.2Неравенство Бернулли

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

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

3.2.2Монотонность

3.2.3Ограниченность

3.3Счётные и несчётные множества

3.3.1Счётность множества рациональных чисел

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

Математический анализ
Записки лекций