Что такое конечное число
Неисчислимое: в поисках конечного числа
Древние греки — приверженцы концепций, имеющих строгий логический смысл — всячески избегали концепции бесконечности. Действительно, какое нам дело до бесконечного ряда чисел, если ни записать, ни представить его мы не можем.
В средние века логическую строгость отбросили ради математических результатов и разработали чрезвычайно эффективные алгоритмические методы, оперирующие в вычислениях бесконечностью.
В XX в. стала отчетливо проступать другая проблема. С бесконечностью мы можем разобраться при помощи одного символа (∞), но что делать с числами, которые меньше бесконечности, но при этом невообразимо огромны?
Мы вплотную подошли к числам, едва уступающим «уроборосу», но при этом все еще имеющим теоретическое и практическое значение. Вы, вероятно, могли слышать о числе Грэма, которое является верхней границей для решения определенной проблемы в теории Рамсея. Спустя 88 лет после появления теоремы Рамсея математики готовы отбросить старые методы и пойти еще дальше.
Добро пожаловать в кроличью нору без дна.
Вступление, в котором нужно вспомнить прошлое
В XVII в. математик и философ Блез Паскаль писал о своем страхе перед бесконечностью, о чувстве собственной незначительности при мысли о безбрежных просторах космоса. Интересно, что сказал бы Паскаль о числе Грэма, состоящем из башни чисел высотой от Земли до самой отдаленной звезды, в каждом числе которой прячется своя башня из чисел? Каждый изгиб числа в башне чисел, которая состоит из башни чисел, вмещает в себя башню других чисел — но даже с такой формулировкой мы и близко не подошли к открытию, сделанному Грэмом.
Истоки числа Грэма следует искать в 1928 г., когда молодой математик Фрэнк Рамсей во время работы над статьей о логике заметил удивительную вещь: полная неупорядоченность невозможна. Каждое достаточно большое множество чисел, точек или объектов обязательно содержит высокоупорядоченную структуру.
Догадка, которая была лишь небольшой частью работы о логике, положила начало совершенно новой области математики, называемой теорией Рамсея. Ее часто объясняют на примере вечеринки: предположим, вы хотите найти идеальный баланс между теми, кто знает друг друга, и незнакомцами. Вы рисуете карту отношений всех ваших друзей, связывая двух людей, если они являются друзьями, синей линией, и красной — если они не знакомы друг с другом. Тогда может получиться подобная иллюстрация:
Красота теории Рамсея заключается в том, что задачи в этой области всегда очень легко формулировать. Рассматривая пример с вечеринкой, очень интересно понять, какого количества людей достаточно для образования группы, в которой всегда окажется четверо людей либо знакомых, либо не знакомых друг с другом.
В группе из 17 точек, изображенных на рисунке выше, невозможно найти четыре точки, для которых сеть соединяющих их ребер была бы целиком красной или синей. Поэтому требуется более 17 человек, чтобы среди них обязательно оказалось четверо людей, знакомых или не знакомых друг с другом. На самом деле в группе из 18 человек всегда найдутся либо четверо знакомых, либо четверо не знакомых друг с другом.
Возьмем любое звездное скопление. В нем всегда можно найти группу, которая с очень большой точностью образует какую-нибудь заданную конфигурацию — прямую линию, прямоугольник, ковш.
Математики стараются вычислить, сколь велико должно быть множество звезд, чисел или каких-либо объектов, чтобы можно было гарантировать существование определенной желаемой подструктуры. На решение таких задач часто уходят десятилетия.
Теория Рамсея также имеет большое практическое значение — от организации хорошей вечеринки до построения более совершенных сетей коммуникации и систем передачи и поиска информации. На самом деле очень сложно представить, для каких целей могут послужить многие методы, разработанные для решения задач в теории Рамсея — это самый передовой край математики.
Как и почему Грэм пришел к своему числу
Американский математик Рональд Льюис Грэм (родился в 1935 г.) внес значительный вклад в дискретную математику. Грэм — личность разносторонняя. В свое время он даже был президентом международной ассоциации жонглеров, но прославился исключительно за счет большого положительного целого числа, которое служит верхней границей конкретной проблемы в теории Рамсея.
N-мерный куб всегда содержит 2n вершин. Несмотря на их размерность, n-мерные кубы — это просто графы, вершины которых связаны ребрами
Любой n-мерный куб мы можем превратить в полный граф, просто соединив все вершины. Остальные ребра, сформированные таким образом, находятся внутри или на одной из граней. Представим, что эти края имеют два цвета — красный и синий. Таким образом, Грэм сформулировал интересный вопрос, лежащий в плоскости классической теории Рамсея: при каком минимальном значении N двухцветного k-мерного куба каждая такая раскраска обязательно содержит раскрашенный в один цвет полный подграф с четырьмя вершинами, каждая из которых лежит в одной плоскости?
Полный граф на трехмерном кубе с раскраской ребер в два цвета
В 1971 г. Рональд Грэм и Брюс Ли Ротшильд доказали, что у этой задачи есть решение, и оно представляет собой число, которое больше 6 (нижняя граница), и меньше некоего N. Нижняя граница впоследствии была повышена до 13, а верхняя граница получила название малого числа Грэма. Малое число Грэма меньше числа, попавшего в Книгу рекордов Гиннесса, но это все равно невообразимо огромное число.
В общем-то, задача Грэма не звучит как нечто сверхъестественное — ее может понять и пятиклассник. Но на простые вопросы иногда очень трудно получить ответы. Если решение меньше, чем число Грэма, которое мы знаем, то каков же ответ? Число Грэма, как и некоторые другие большие числа, просто говорит нам, что у некоторой задачи в принципе есть решение, и это решение можно найти. Оптимизировав решение задачи, мы можем сдвинуть число Грэма ближе к 1, и двигать его до тех пор, пока не найдем реального решения.
Как число стало легендой
Итак, Рональд Грэм написал профессиональную математическую работу по теории Рамсея, которая привлекла внимание журналиста Мартина Гарднера. Именно Гарднер ипоспособствовал попаданию числа Грэма в Книгу рекордов Гиннесса, после чего число привлекло внимание широкой общественности.
Проблема, которую Грэм пытался решить, на самом деле была лишь одним конкретным примером применения теории Рамсея. Дальнейшие исследования в этой теории дали математикам бóльшие числа, чем даже число Грэма. Эти числа не являются точным решением проблем, а выступают верхней границей.
Чем же очаровал Грэм людей? Красотой и наглядностью.
Чтобы оперировать гигантскими числами, Грэм использовал быстрорастущие функции. Многие из этих функций знакомы всем — сложение, умножение и возведение в степень. Математики создали новые функции, которые масштабируются намного быстрее.
Для записи числа Грэм использовал стрелочную нотацию Кнута — расширение возведения в степень. Точно так же, как возведение в степень является повторным умножением и обозначается одной стрелкой, направленной вверх, две стрелки вверх обозначают итерационное возведение в степень, три стрелки — повторное итерационное возведение в степень и т.д.
3↑↑5 = 3↑3↑3↑3↑3 = три в степени три в степени 7 625 597 484 987.
Математики поняли, что, имея дело с большими числами, требуется каждый раз использовать новый оператор, который должен быть мощнее предыдущего. ↑↑ — следующий оператором от ↑, так же как ↑ — следующий оператор от умножения, и точно так же, как умножение — это один оператор от сложения. Таким образом, увеличение количества последовательных стрелок увеличивает способность работать с большими числами.
Если добавить еще одну стрелку, то скорость формирования новых чисел значительно возрастет:
3 ↑↑↑ 3 дает нам башню из степеней троек высотой в 7 трлн чисел.
Четыре стрелочки даст число, записать которое будет уже очень трудно. Обратимся к примеру из замечательной статьи «Число Грэма на пальцах»:
А вот оригинальная иллюстрация, которую Гарднер использовал для объяснения числа Грэма:
Самый верхний уровень равен 3 ↑↑↑↑ 3. Формулу вы видели выше. Под ним находится слой, в котором число стрелочек равно 3 ↑↑↑↑ 3. Далее идет слой, в котором число стрелочек равно числу стрелочек в предыдущем слое. И так до 64-го слоя.
Красота этого выражения в том, что если вы захотите превзойти число Грэма и напишите «супербольшое число = число Грэма + 1», то в математических масштабах ничего не изменится. Все равно что залезть на вершину Эвереста и прыгать на ней — Эверест все равно останется самой высокой горой, на вершину которой вы можете взобраться.
Но где-то в Солнечной системе есть и Олимп, не так ли?
Нотация Бауэрса: начало кроличьей норы
Дальнейшая работа с теорией Рамсея математиков Джозефа Краскала и Харви Фридмана привела к числу TREE(3), у которого даже самая нижняя граница решения является сверхогромной, не говоря о верхней.
Если число Грэма мы хотя бы можем записать, то число TREE(3) невозможно поместить в рамки нотации Кнута. Судите сами:
TREE (3) = … > A A(187196) (4), где даже A 2 (4) больше, чем число атомов во Вселенной, ведь А — функция Аккермана, которая определяется рекурсивно для неотрицательных целых чисел m и n следующим образом:
Используя функцию Аккермана, можно очень легко записать число Грэма ≈ A64(4).
Математики вычислили, что у TREE(3) есть теоретическая граница, которую можно записать с помощью массивной нотации, предложенной в 2002 г. Джонатаном Бауэрсом. В массивной нотации существует пять правил:
Функция возрастает невероятно быстро. Массив из трех элементов <10,100,2>в стрелочной нотации Кнута будет иметь следующий вид: 10 ↑ 2 100.
Тройные массивы Бауэрса полностью идентичны тройным цепочкам обозначения Конвея (еще один метод записи — соединенные горизонтальными стрелками (цепочками) числа, растут быстрее нотации Кнута):
<3,3,3>= 3 → 3 → 3 = 3 ^ (3 ^ (3 ^ (3 ^… 7 625 597 484 987 раз… ^ 3) ^ 3) ^ 3)
Массив из четырех элементов (например <10,100,1,2>) уже больше самого числа Грэма — благодаря хитрости, придуманной Бауэрсом: на четвертом элементе он «оптимизирует» формулу, как раньше мы оптимизировали умножение и возведение в степень, только теперь математик занимается удвоением скобок:
Более подробный разбор этой операции вы можете найти в статье «Bird’s Linear Array Notation».
При этом «самое больше число, использованное в серьезном математическом доказательстве», ограничено между <3,65,1,2>и <3,66,1,2>. Речь сейчас идет только о линейных массивах, а ведь они могут быть и гипермерными. В принципе массив Бауэрса из четырех элементов способен вместить в себя всю нотацию Конвея, а гипермерные массивы (на иллюстрации выше) уже становятся математической гиперигрой.
Красота математики в том, что мы можем работать с данными, которые даже представить невозможно. Любую сложную задачу можно облегчить до невероятно простых значений. Возможно, ответы на некоторые вопросы мы никогда не найдем, но методы, использованные для их решения, могут пригодиться в других областях знаний. Сама проработка этих методов построения иерархий по скорости роста функций совершенствует многие разделы математики.
Бауэрс сделал удачную попытку ответить на вопрос, как с помощью иерархии приемов расширить возможности формальной системы. Фактически мы записываем не само число иносказательным образом, а способ когда-нибудь прийти к этому числу хотя бы в теории.
Нотации Бауэрса стали отличной возможностью подобраться к пониманию функции TREE. Конечно, определить величину TREE(3) мы не можем, но с помощью итерационного «улучшения» нотации, проведенного английским математиком Крисом Бердом, удалось выяснить, что TREE(3) > <3,6,3[1[1¬1,2]2]2>.
TREE(3)
TREE — быстрорастущая функция в теории графов, разработанная математиком Харви Фридманом.
Предположим, что мы имеем последовательность k-пронумерованных деревьев T1, T2,… со следующими свойствами:
BIG FOOT является аналогом числа Райо — его определение почти идентично. BIG FOOT расширяет теорию множеств первого порядка, используя уникальную область дискурса, называемую oodleverse, с использованием языка, называемого first-orderoodletheory (FOOT), и обобщая теорию множеств n-го порядка сколь угодно большого n.
Пусть FOOT(n) обозначает наибольшее натуральное число, однозначно определяемое в языке FOOT не более чем в n символах. BIG FOOT определяется как FOOT 10 (10 100 ), где FOOT a (n) — это FOOT(n) (рекурсия).
BIG FOOT таким образом равен
Поиски конечного числа продолжаются. Будет ли оно когда-нибудь найдено?
Блез Паскаль так описал экзистенциальный ужас, охватывающий его при мысли о безграничности мира: «Вечная тишина этого бесконечного пространства пугает меня». Числа дают нам возможность установить рамки понимания и границы дозволенного, взять под контроль страх уробороса. Они — наше реликтовое излучение, возможность подойти к метафорическому краю мира. Но, как в космосе нельзя долететь до такого места, где будет висеть табличка «конец Вселенной», так и в математике невозможно достичь последнего рубежа. Впрочем, это нам еще предстоит проверить.
конечное число
Смотреть что такое «конечное число» в других словарях:
КОНЕЧНОЕ и БЕСКОНЕЧНОЕ — парные философские категории, обозначающие моменты определенного и неопределенного в вещах, явлениях, процессах. К. то, что имеет пространственный и (или) временной конец, границу (всякого) нечто, которая есть имманентное определение самого нечто … Современный философский словарь
Число Армстронга — Самовлюблённое число, или совершенный цифровой инвариант (англ. pluperfect digital invariant, PPDI или число Армстронга натуральное число, которое в данной системе счисления равно сумме своих цифр, возведённых в степень, равную количеству его… … Википедия
Конечное множество — Конечное множество множество, количество элементов которого конечно, то есть, существует неотрицательное целое число k, равное количеству элементов этого множества. В противном случае множество называется бесконечным. Содержание 1… … Википедия
конечное флегмовое число — — [http://slovarionline.ru/anglo russkiy slovar neftegazovoy promyishlennosti/] Тематики нефтегазовая промышленность EN finite reflux … Справочник технического переводчика
Число Линделёфа — один из кардиналов, характеризующий топологическое пространство. Определяется как наименьший кардинал m, такой, что из каждого открытого покрытия пространства X можно выбрать подпокрытие мощности не больше m[1]. Обозначается как l(X). Так как в… … Википедия
КОНЕЧНОЕ — филос. категория, характеризующая всякий определ., огранич. объект (вещь, процесс, явление, состояние, свойство и т. д.). Каждый познаваемый объект действительности выступает в некотором отношении как К. Определённость К. придаёт его… … Философская энциклопедия
∞ (число) — ∞ Термин бесконечность соответствует нескольким различным понятиям, в зависимости от области применения, будь то математика, физика, философия, теология или повседневная жизнь. Финитизм отрицает понятие Бесконечность. Бесконечность в большинстве… … Википедия
Вещественное число — Вещественное, или действительное число [1] математическая абстракция, возникшая из потребности измерения геометрических и физических величин окружающего мира, а также проведения таких операций как извлечение корня, вычисление логарифмов, решение… … Википедия
Иррациональное число — так называются в математике числа, которые не могут быть точно выражены ни целыми числами, ни арифметическими дробями, а представляются бесконечными и непериодическими десятичными дробями; означаются особыми знаками (радикалами) или буквами (е,… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона
Самовлюбленное число — Самовлюблённое число, или совершенный цифровой инвариант (англ. pluperfect digital invariant, PPDI или число Армстронга натуральное число, которое в данной системе счисления равно сумме своих цифр, возведённых в степень, равную количеству его… … Википедия
конечное число
Смотреть что такое «конечное число» в других словарях:
КОНЕЧНОЕ и БЕСКОНЕЧНОЕ — парные философские категории, обозначающие моменты определенного и неопределенного в вещах, явлениях, процессах. К. то, что имеет пространственный и (или) временной конец, границу (всякого) нечто, которая есть имманентное определение самого нечто … Современный философский словарь
Число Армстронга — Самовлюблённое число, или совершенный цифровой инвариант (англ. pluperfect digital invariant, PPDI или число Армстронга натуральное число, которое в данной системе счисления равно сумме своих цифр, возведённых в степень, равную количеству его… … Википедия
Конечное множество — Конечное множество множество, количество элементов которого конечно, то есть, существует неотрицательное целое число k, равное количеству элементов этого множества. В противном случае множество называется бесконечным. Содержание 1… … Википедия
конечное флегмовое число — — [http://slovarionline.ru/anglo russkiy slovar neftegazovoy promyishlennosti/] Тематики нефтегазовая промышленность EN finite reflux … Справочник технического переводчика
Число Линделёфа — один из кардиналов, характеризующий топологическое пространство. Определяется как наименьший кардинал m, такой, что из каждого открытого покрытия пространства X можно выбрать подпокрытие мощности не больше m[1]. Обозначается как l(X). Так как в… … Википедия
КОНЕЧНОЕ — филос. категория, характеризующая всякий определ., огранич. объект (вещь, процесс, явление, состояние, свойство и т. д.). Каждый познаваемый объект действительности выступает в некотором отношении как К. Определённость К. придаёт его… … Философская энциклопедия
∞ (число) — ∞ Термин бесконечность соответствует нескольким различным понятиям, в зависимости от области применения, будь то математика, физика, философия, теология или повседневная жизнь. Финитизм отрицает понятие Бесконечность. Бесконечность в большинстве… … Википедия
Вещественное число — Вещественное, или действительное число [1] математическая абстракция, возникшая из потребности измерения геометрических и физических величин окружающего мира, а также проведения таких операций как извлечение корня, вычисление логарифмов, решение… … Википедия
Иррациональное число — так называются в математике числа, которые не могут быть точно выражены ни целыми числами, ни арифметическими дробями, а представляются бесконечными и непериодическими десятичными дробями; означаются особыми знаками (радикалами) или буквами (е,… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона
Самовлюбленное число — Самовлюблённое число, или совершенный цифровой инвариант (англ. pluperfect digital invariant, PPDI или число Армстронга натуральное число, которое в данной системе счисления равно сумме своих цифр, возведённых в степень, равную количеству его… … Википедия
конечное число
Смотреть что такое «конечное число» в других словарях:
КОНЕЧНОЕ и БЕСКОНЕЧНОЕ — парные философские категории, обозначающие моменты определенного и неопределенного в вещах, явлениях, процессах. К. то, что имеет пространственный и (или) временной конец, границу (всякого) нечто, которая есть имманентное определение самого нечто … Современный философский словарь
Число Армстронга — Самовлюблённое число, или совершенный цифровой инвариант (англ. pluperfect digital invariant, PPDI или число Армстронга натуральное число, которое в данной системе счисления равно сумме своих цифр, возведённых в степень, равную количеству его… … Википедия
Конечное множество — Конечное множество множество, количество элементов которого конечно, то есть, существует неотрицательное целое число k, равное количеству элементов этого множества. В противном случае множество называется бесконечным. Содержание 1… … Википедия
конечное флегмовое число — — [http://slovarionline.ru/anglo russkiy slovar neftegazovoy promyishlennosti/] Тематики нефтегазовая промышленность EN finite reflux … Справочник технического переводчика
Число Линделёфа — один из кардиналов, характеризующий топологическое пространство. Определяется как наименьший кардинал m, такой, что из каждого открытого покрытия пространства X можно выбрать подпокрытие мощности не больше m[1]. Обозначается как l(X). Так как в… … Википедия
КОНЕЧНОЕ — филос. категория, характеризующая всякий определ., огранич. объект (вещь, процесс, явление, состояние, свойство и т. д.). Каждый познаваемый объект действительности выступает в некотором отношении как К. Определённость К. придаёт его… … Философская энциклопедия
∞ (число) — ∞ Термин бесконечность соответствует нескольким различным понятиям, в зависимости от области применения, будь то математика, физика, философия, теология или повседневная жизнь. Финитизм отрицает понятие Бесконечность. Бесконечность в большинстве… … Википедия
Вещественное число — Вещественное, или действительное число [1] математическая абстракция, возникшая из потребности измерения геометрических и физических величин окружающего мира, а также проведения таких операций как извлечение корня, вычисление логарифмов, решение… … Википедия
Иррациональное число — так называются в математике числа, которые не могут быть точно выражены ни целыми числами, ни арифметическими дробями, а представляются бесконечными и непериодическими десятичными дробями; означаются особыми знаками (радикалами) или буквами (е,… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона
Самовлюбленное число — Самовлюблённое число, или совершенный цифровой инвариант (англ. pluperfect digital invariant, PPDI или число Армстронга натуральное число, которое в данной системе счисления равно сумме своих цифр, возведённых в степень, равную количеству его… … Википедия
Числа Какота
Числа Какота — кардинальные числа, используются при рассмотрении счетности/несчетности элементов множеств. Так натуральные числа — начальный класс, он же — счетное множество N=0,1,2,…,N-1 всех конечных чисел. Его кардинал N называется конечным числом Какота. Кагот — герой повествования чукотского писателя Юрия Рытхэу. (Кагот искал числа, которые уже не конечные, но еще и не бесконечные, и считал, что тот, кто найдет их, будет счастлив и все узнает). Числа Какота позволяют в примитивной теории множеств сопоставить бесконечному ряду W всех порядковых чисел бесконечный числовой рядо Ω.
Бесконечный ряд W порядковых чисел имеет вид:
W=<0,1,2,3,…,n,…; ω,ω+1,ω+2,ω+3,…,ω+n,…; …; ω×n,ω×n+1,ω×n+2,ω×n+3,…,ω×n+n,…; … …; ω1,ω1+1,…; ω2,ω2+1,…; …; ωω,ωω+1,…; …>. Его началом является канторовский бесконечный ряд порядковых чисел со свойствами: за всеми конечными числами n следует наименьшее трансфинитное число ω, которое указывает также количество предшествующих ему конечных чисел. Само же число ω не имеет предшественника, то есть левого соседнего с ним числа ω-1. Любое бесконечное число вида ω, ω×n,ωn, ωω и т. д. является предельным и не имеет предшественника. Не имеют предшественников и все числа, кратные начальной бесконечности ω. Это значит, что перед всеми этими числами есть «дырки». Говорят, что ряд W не имеет наибольшего бесконечного числа. Логически это то же самое, что говорить, что множество конечных натуральных чисел не имеет наибольшего конечного числа.
См. также
Мощность множества или кардинальное число множества