Почему вещественные числа такие странные / Хабр

В прошлом посте я писал о попытках вывести математику из принципов формальной логики. Мы начали с арифметики Пеано, в которой построение натуральных чисел выполнялось из двух произвольных конструкций: элемента, обозначающего ноль, и абстрактной функции следования S(…).

Затем мы перешли к теории множеств, позволившей закодировать внутреннюю структуру этих символов. В результате получилась иерархия натуральных чисел теории множеств, называемых ординалами. Также это привело к интересному выводу: если мы допускаем существование бесконечных множеств, то и само множество всех натуральных чисел (ℕ) имеет структуру ординала. В статье мы обозначили это бесконечное число как ω и продемонстрировали, что им можно манипулировать при помощи тех же арифметических правил, что и конечными числами, но иногда оно ведёт себя неожиданным образом. Например, мы выяснили, что ω + 1 ≠ 1 + ω.

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

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

Натуральные числа (ℕ)

Напомню, что в предыдущей статье мы построили последовательность меток, соответствующих идущим по порядку натуральным числам, создав объект, обозначающий ноль, а затем последовательно применяя к нему функцию S(…):

$\begin{align} 1 &:= S(0) \\ 2 &:= S(1) = S(S(0)) \\ 3 &:= S(2) = S(S(S(0))) \\ 4 &:= S(3) = S(S(S(S(0)))) \\ &... \end{align}$

Оператор «:=» обозначает «определяется как». Так же его иногда обозначают ≝, ≜ или обычным =.

В арифметике Пеано обозначение «0» и функция следования S(…) не имеют какого-то более глубокого смысла: это просто «объекты» с парой сформулированных логичных свойств. Понятие лишь показывает, что у каждой последующей метки есть некое фиксированное отношение с предыдущей. В подходе на основе теории множеств мы определили эти концепции гораздо точнее, но эти подробности сейчас неважны.

Важно то, что в обеих моделях отношения следования позволили нам определить поведение оператора «+» с помощью двух простых правил подстановки:

$\begin{alignat}{1} a &+ 0 \;&&:=\; a&&\qquad (\textrm{правило 1}) \\ a &+ S(b) \;&&:=\; S(a+b) &&\qquad ( \textrm{правило 2}) \end{alignat}$

Хоть эти правила и могут показаться загадочными, по сути, они просто кодифицируют, что прибавление нуля — это отсутствие операции, а a + (b + 1) эквивалентно (a + b) + 1. Этого простого набора правил достаточно для решения задач вида 2 + 2 без каких-либо допущений о фундаментальном смысле символов «2» и «+».

Например, из определения чисел Пеано следует, что «2» эквивалентно S(1), поэтому 2 + 2 можно переформулировать как 2 + S(1). Перейдя на эту форму, можно применить правило 2, переписав 2 + S(1) как S(2 + 1):

После этого можно снова воспользоваться теми же этапами, чтобы развернуть сумму 2 + 1:

Теперь у нас есть сумма двойной вложенности с нулём, поэтому можно применить правило 1, избавиться от суммы (2 + 0 = 2) и «раскрутить» функции следования, чтобы получить результат:

Если вам интересно более подробное описание, в том числе и код на C, объясняющий процесс понятным программистам образом, то прочитайте статью по ссылке выше.

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

$\begin{alignat}{1} a &\cdot 0 \;&&:=\; 0 &&\qquad (\textrm{правило 1}) \\ a & \cdot S(b) \;&&:=\; a \cdot b + a &&\qquad ( \textrm{правило 2}) \end{alignat}$

Фактически, без необходимости определять вычитание явным образом, мы говорим, что a · b можно переписать в виде a · (b-1) + a. Этот процесс можно продолжать, пока мы не получим a · 0; здесь часть с умножением будет равна нулю, так что можно просто раскрутить стек и собрать все члены «+ a». Например, вот процесс вычисления 5 · 3:

$\begin{align} 5 \cdot 3 &= 5 \cdot 2 + 5 \\ &= 5 \cdot 1 + 5 + 5 \\ &= \underbrace{5 \cdot 0}_{=\ 0} + \underbrace{5 + 5 + 5}_{= \ 15} \\ \end{align}$

Скоро всё это нам пригодится.

Целые числа (ℤ)

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

Чтобы расширить ℕ на отрицательные числа, можно немного побаловаться со способом кодирования знака минуса, добавив его в наборы правил арифметики в качестве особого случая. Тем не менее, более привычный подход заключается в определении целых чисел в виде отдельной иерархии чисел: каждое целочисленное i состоит из упорядоченной пары натуральных чисел: i = (a, b). Первый элемент пары описывает положительный компонент, второй — отрицательную часть. Таким образом, целочисленное +5 можно закодировать, как (5, 0), а целочисленное -5 превращается в (0, 5).

Вы можете задаться вопросом, не взялась ли ниоткуда концепция «упорядоченной пары». И да, и нет: здесь она новая, но в теории множеств такие пары соответствуют обычным множествам, за исключением того, что мы проектируем соответствие таким образом, что (a, b) отличается от (b, a). Это можно сделать различными способами, но распространённый подход, выведенный Казимежем Куратовским, выглядит так:

$(a, b) := \{ \{a\}, \{a, b\} \}$

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

Чтобы определить сложение целых чисел на основе пар, можно просто по отдельности складывать «положительные» и «отрицательные» половины. Так как элементы — это натуральные числа, мы уже знаем, как их суммировать, поэтому можем записать:

$\underbrace{(a, b)}_{\textrm{целое 1}} + \underbrace{(c, d)}_{\textrm{целое 2}} \; := \; \underbrace{(\;\overbrace{\vphantom{|}a + c}^{\substack{\textrm{натуральное} \\ \textrm{сложение}}}, \; \overbrace{\vphantom{|}b + d}^{\substack{\textrm{натуральное} \\ \textrm{сложение}}}\;)}_{\textrm{целочисленный результат}}$

Аналогично, поскольку каждое целое число, по сути, выражает разность между двумя числами пары, результат умножения двух целых (a, b) и (c, d) будет соответствовать изучаемому в школе паттерну (a - b) · (c - d) = ac - ad - bc + bd. Отделив положительные и отрицательные части решения, можно записать:

$\underbrace{(a, b)}_{\textrm{целое 1}} \cdot \underbrace{(c, d)}_{\textrm{целое 2}} \; := \; \underbrace{(ac+ bd, ad + bc)}_{\textrm{целочисленный результат}}$

И это как бы работает. Например, сложив целочисленные +5 и -5, получим:

Результат (5, 5) как будто бы обозначает «ноль», но в качестве канонического описания этого значения мы бы его не выбрали; предпочтительнее (0, 0). В более общем случае мы скажем, что любые две пары (a, b) и (c, d) описывают одинаковое целое число, если a - b = c - d. Тем не менее, наша система не учитывает это свойство.

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

Определив это отношение эквивалентности пар, мы присваиваем целочисленные обозначения наподобие «+5» не конкретной паре, а всему классу эквивалентности: коллекции упорядоченных пар, удовлетворяющих приведённому выше критерию. В такой модели наша новая иерархия чисел выглядит так:

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

Это работает, потому что каждый элемент в этих множествах конечен, но верхней границы нет; для любого конечного +n число 2n тоже будет конечным и находиться в ℕ. Существование соответствия один к одному подразумевает, что эти множества имеют одинаковую кардинальность.

Рациональные числа (ℚ)

Рациональные числа — это значения, которые можно выразить как соотношение двух целых чисел: a / b. В предыдущем разделе мы определили целые числа в виде упорядоченной пары, по сути, кодирующей вычитание: a - b. И вот, что здорово: ничто не препятствует нам взять два целых числа и превратить их в новый тип пары, кодирующий деление. Каждая из этих целочисленных пар образует новую иерархию рациональных чисел: q = (a, b).

В этой модели мы считаем рациональные числа (a, b) и (c, d) эквивалентными, если их внутренние целые числа удовлетворяют критерию a / b = c / d. Мы пока не определили деление, но знаем, как умножать целые, поэтому можем переформулировать правило эквивалентности следующим образом:

$a \cdot d = c \cdot b$

При этом мы получаем следующую классификацию:

Правило умножения для двух пар, описывающих рациональные числа, можно определить как тривиальную переформулировку a/b · c/d = ac/(bd):

$\underbrace{(a, b)}_{\textrm{рациональное 1}} \cdot \underbrace{(c, d)}_{\textrm{рациональное 2}} \; := \;\underbrace{(a \cdot c, b \cdot d)}_{\textrm{рациональный результат}}$

Сложение рациональных чисел формализуется столь же простым способом, в соответствии с обычным паттерном a/b + c/d = (ad + cb) / (bd):

Каков «размер» множества всех рациональных чисел? Это опять-таки зависит от того, как на это посмотреть, но мы можем показать, что его кардинальность не больше, чем ℕ. Визуальный способ показать это заключается в построении двухмерного массива дробей вида x/y:

Должно быть очевидно, что поскольку координаты x и y по отдельности проходят по всем возможным натуральным числам, массив содержит все положительные рациональные дроби. Часть квадратов избыточна (например, 2 эквивалентно 4/2), но для доказательства это не важно.

Выстроив рациональные числа, мы можем обойти эту сетку таким образом, чтобы можно было присвоить каждый квадрат целому числу, не оставляя пробелов и не исчерпав члены ℕ. Начало такого паттерна обхода обозначено на рисунке стрелками. Мы начинаем с левого верхнего угла, сдвигаемся на один квадрат вправо, делаем резкий поворот и начинаем двигаться по диагонали, пока не наткнёмся на вертикальную грань, смещаемся на один квадрат вниз, а затем снова следуем по диагональному паттерну. И так будет дальше. По аналогии с тем, что мы сделали для целых чисел, можно сказать, что результат не изменится, если мы добавим сюда отрицательные рациональные числа.

Вычислимые числа

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

Хоть эти числа нельзя представить в виде рациональных, их можно объяснить с точки алгоритма, который необходимо выполнить, чтобы аппроксимировать их с произвольной точностью. Например, сумма следующих членов, начинающихся с n = 0, будет медленно, но верно сходиться к π с увеличением количества суммируемых элементов:

${8 \over (4n + 1)(4n + 3)}$

В пределах точности чисел с плавающей запятой можно наблюдать это поведение, запустив следующий код на C (демо):

#include <stdio.h>
#include <stdint.h>

int main() {
  double sum = 0;
  for (uint64_t n = 0, pos = 0; n <= 65536; n++) {
    sum += 8.0 / ((4*n + 1) * (4*n + 3));
    if (n >> pos) { printf("[%5ld] %.05f\n", n, sum); pos++; }
  }
}

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

Любопытно, что кардинальность множества вычислимых чисел по-прежнему такая же, как кардинальность ℕ. Интуитивно понятное объяснение этого заключается в том, что существует сколько вычислимых чисел, сколько машин Тьюринга, способных их вычислить. Набор правил каждой машины Тьюринга можно закодировать в виде конечного натурального числа — можно просто записать его, а затем преобразовать спецификацию в значения ASCII, поэтому мы всё ещё находимся в области счётных бесконечностей.

Вещественные числа (ℝ)

Разумеется, нас не учат вычислимым числам в школе. Вместо них в качестве самого распространённого «апгрейда» ℚ служат вещественные числа: идеализированное непрерывное множество, в котором, если говорить простым языком, существует каждое число, вне зависимости от того, знаем ли мы, как его аппроксимировать, или нет.

Разумеется, моя формулировка крайне неполна. Множество включает не всё подряд: 🥔 (картошка) — это не вещественное число, и, чтобы избежать кучи сложностей, не является им и √-1. Множество ℝ расширяет ℚ, но только в непосредственной близости от рациональных чисел. Если выбрать любое вещественное число, то можно найти рациональную дробь, которая произвольно близка к нему.

Чтобы описать внутреннюю структуру вещественных чисел более строго, можно обратиться к дедекиндовым сечениям. Неформально принцип можно объяснить так: мы можем однозначно идентифицировать каждое вещественное число, ассоциировав его со множеством всех рациональных чисел, идущих до него. В частности, описывая вещественное число x, мы можем взять множество рациональных чисел и разбить его на такую упорядоченную пару множеств (A, B), что множество A содержит каждое рациональное q < x, а множество B содержит каждое q ≥ x.

Это описание может показаться опирающимся на само себя: для построения описания вещественного числа нам нужно знать, где нужно провести сечение, что как будто требует предшествующего знания о том, как x относится к ℚ. Тем не менее, смысл заключается в том, что наша методика позволяет описывать местоположение числа наподобие π; вселенная вещественных чисел строится из всех возможных дедекиндовых сечений множества ℚ. Числа и есть сечения, а π находится где-то там, даже если мы не можем указать его точное местоположение.

Разумеется, некоторые другие иррациональные сечения можно описать более подходящим образом. Например, чтобы определить ∛5, можно сказать, что множество A состоит из каждого рационального q, такого, что q³ < 5, а множество B содержит каждое q, такое, что q³ ≥ 5. Такое уточнение в высшей степени полезно, но опять-таки, существование вещественного числа не зависит от возможности описания его местоположения в ℚ.

Выразив числа в виде дедекиндовых сечений, мы можем определить для вещественных чисел и арифметические операции. Например, для сложения вещественных (A, B) и (C, D) можно построить новое число (E, F), такое, что для каждого возможного рационального a, выбранного из A, и для каждого рационального c, выбранного из C, сумма a + c располагается в E. Аналогично, для каждых b в B и d в D сумма b + d располагается в F.

Я избавлю вас от записи абстрактных множеств, но приведу практический пример: если (A, B) описывает 2, а (C, D) описывает 3, то мы знаем, что каждое a, выбранное из A, будет меньше 2, а каждое c, выбранное из C, будет меньше 3. Следовательно, каждое значение a + c, расположенное в E, всегда будет меньше 5. Аналогично, каждое b + d, располагающееся в F, будет больше или равно 5. Следовательно, получившаяся пара (E, F) совпадает с сечением, представляющим число 5.

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

Мы исследовали это свойство в предыдущей статье, но я вкратце напомню рассуждения: предположим существование некоего соответствия один к одному между целыми числами и бесконечными десятичными дробями, описывающими вещественные числа в интервале от 0 до 1. Конкретика этого соответствия нас не волнует; мы просто допускаем, что оно существует:

$\begin{array}{c} 1 & \leftrightarrow & 0.\underline{\textbf{1}}23456\ldots \\ 2 & \leftrightarrow & 0.6\underline{\textbf{5}}4321\ldots \\ 3 & \leftrightarrow & 0.99\underline{\textbf{9}}000\ldots \\ 4 & \leftrightarrow & 0.454\underline{\textbf{5}}45\ldots \\ 5 & \leftrightarrow & 0.1111\underline{\textbf{1}}1\ldots \\ 6 & \leftrightarrow & 0.03133\underline{\textbf{7}}\ldots \\ & \ldots & \end{array}$

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

Исходя из построения, наше новое число обязательно отличается хотя бы одним разрядом от каждого присвоенного вещественного. Наличие члена ℝ, у которого нет соответствия целому числу — это противоречие, сообщающее нам, что постулируемое соответствие не может существовать, даже если ограничиться интервалом (0, 1). Существует фундаментально большее «количество» вещественных чисел, чем натуральных — несчётная бесконечность.

Ну и что?

Из предыдущего объяснения можно вспомнить, что кардинальность вычислимых чисел была такой же, как кардинальность ℕ. Кардинальность ℝ («величина» множества вещественных чисел) фундаментально больше её. Иными словами, мы можем утверждать, что большинство вещественных чисел невычислимо.

Но каким может быть пример невычислимого вещественного числа? Хороший вопрос! Одним из примеров может быть любое число, кодирующее решение проблемы остановки. Компьютерная программа, позволяющая нам решать в общем случае, должна ли какая-то другая программа останавливаться, приведёт к парадоксу. То есть если процедура для аппроксимации конкретного вещественного числа требует решения проблемы остановки, её существовать не может.

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