Число Райо

Число Райо
Темпы роста	>* все функции, определяемые в сегменте первого порядка теории множеств второго порядка, предполагаемые в определении функции Райо
Автор(ы)	Августин Райо
Год	2007

Число Райо — одно из самых больших именованных чисел, придуманное в битве больших чисел Агустином Райо против Адама Эльги 26 января 2007 года. Число Райо, по собственным словам Райо, "наименьшее положительное целое число, большее любого конечного положительного целого числа, названного выражением на языке теории множеств первого порядка с использованием гугола символов или меньше".

Позволяя количеству символов превышать натуральные числа, мы получаем очень быстро растущую функцию Rayo. Число Райо - $Rayo(10^{100})$. Функция Райо является невычислимой, что означает, что для Машины Тьюринга (и, согласно тезису Черча–Тьюринга, любого современного компьютера) невозможно вычислить $Rayo(n)$.

Хотя теория множеств второго порядка не была указана в первоначальном определении и уточняется как философский (но математически плохо определенный) набор формул, которым философски "удовлетворяет" реальный мир, разумно предположить, что ТМЦФ - это сегмент первого порядка неопределенной теории множеств, потому что большинство математиков и гугологов интересуются ТМЦФ. В предположении, функция Райо перерастает все функции, определяемые в ТМЦФ. На протяжении всей этой статьи мы всегда используем одно и то же предположение, за исключением раздела аксиомы, который более глубоко объясняет проблему отсутствия разъяснения теории множеств второго порядка.

Функция Райо — одна из самых быстрорастущих функций, когда-либо возникавших в профессиональной математике; лишь несколько функций, особенно её расширение седьмое рыбье число, превосходят её. Поскольку функция Райо использует сложную математику, существует несколько попыток её обобщения, которые приводят к неудаче. Например, функция FOOT (теория Удла первого порядка) также считалась превосходящей её, но она плохо определена.

Функция Райо когда не сможет опередить функцию в быстрорастущей иерархии $f_\alpha(n)$ для счётного порядкового числа $\alpha$ и фиксированной системой фундаментальной последовательности s для ординалов ⩽$\alpha$, если иерархия определена в ТМЦВ по определению $Rayo$.

Описание

Пусть ϕ и ψ быть формулами в кодировке Гёделя и s и t быть переменными назначениями. Определить Sat([ϕ], s) следующим образом:

∀R {
  {
    ∀[ψ], s: R([ψ],t) ↔ ([ψ] = "xi ∈ xj" ∧ t(xi) ∈ t(xj))
                      ∨ ([ψ] = "xi = xj" ∧ t(xi) = t(xj))
                      ∨ ([ψ] = "(¬θ)"    ∧ ¬R([θ], t))
                      ∨ ([ψ] = "(θ∧ξ)" ∧ R([θ], t) ∧ R([ξ], t))
                      ∨ ([ψ] = "∃xi(θ)"  ∧ ∃t′: R([θ], t′))
                      (где t' - копия t с изменённым xi)
  } ⇒ R([ϕ],s)
}

Назвав натуральное число $m$ "Райо-именуемым в $n$ символах", если существует формула ϕ(x₁) с меньшим количеством $n$ символов и x₁ в качестве единственной свободной переменной, которая удовлетворяет следующим свойствам:

1. Существует присвоение переменной $s$, присваивающее x₁ := m, такое, что Sat([ϕ(x₁) ], s).
2. Для любого присвоения переменной $t$, если Sat([ϕ(x₁) ], t), $t$ должно быть x₁ = m.

$Rayo(n)$, тогда является наименьшим числом, большим, чем все числа, которые Райо-именуемы в $n$ символах.

Обратите внимание, что x_i' в t(x_i) ∈ t(x_j) и t(x_i) = t(x_j) в определении из ${Sat}$ выше были x_1 в исходном определении. Хотя x_1 является единственной свободной переменной, которой разрешено встречаться в Райо-именуемых, присвоение переменной для x_i фактически упоминается в удовлетворении ∃-формуле. Следовательно, первоначальное определение сработало не так, как на самом деле предполагал Райо, и было обновлено самим Райо.

Объяснение

Объяснение 1

Существует множество терминологий формальной логики, зависящих от авторов. Мы объясним одну из таких терминологий. "Формальный язык" - это набор постоянных символов терминов, переменных символов терминов, индексируемых натуральными числами, символов функций и символов отношений. "Формула" на формальном языке $L$ - это формальные строки, построенные из символов постоянных терминов в $L$, символов переменных терминов в $L$, символов функций в $L$, символов отношений в $L$, кванторов, и логические связки, следующие определённому синтаксису.

Формально добавляя каждый набор в качестве символа постоянного термина, мы можем канонически расширить $L$ до формального языка $L'$ с параметрами в $V$. Интерпретация формул в $L$ канонически распространяется на интерпретацию формул в $L'$. Присвоение переменной - это некоторая счётно бесконечная последовательность математических объектов, таких как $A = (3, 2, 6, 1/2, {4, \pi}, \omega, 65, ...)$. Учитывая присвоение переменной, мы можем преобразовать формулу в $L'$, и в замкнутую формулу в $L'$, заменив свободные вхождения символов термина переменной параметром, заданным соответствующей записью в присвоении переменной.

Например, формула "третья переменная относительно проста по отношению ко второй переменной" в $L$ интерпретируется $A$ как замкнутая формула "$6$ относительно проста по отношению к $2$" в $L'$, и формула "вторая переменная - это множество всех действительных чисел, за исключением $3.2$" в $L'$ интерпретируется $a$ как замкнутая формула "$2$ - это множество всех действительных чисел, за исключением $3.2$" в $L'$.

Интерпретация формул в $L$ - это отображение, которое присваивает константу каждому символу постоянного термина, функцию каждому символу функции и отношение к каждому символу отношения. Учитывая интерпретацию формул в $L$, каждая замкнутая формула в $L'$ будет оцениваться как действительная или ложная до тех пор, пока предикат истинности формализуем, поскольку он соответствует формуле для параметров в $V$. В частности, учитывая присвоение переменной и интерпретацию, мы можем спросить, является ли данная формула в $L$ истинной или ложной до тех пор, пока формализуемый предикат истинности. Чтобы формализовать предикат истинности, нам нужна достаточно сильная теория множеств. Например, ТМЦФ не подходит для этой цели.

Райо определил очень конкретный и абстрактный формальный язык вместе с каноническим выбором интерпретации:

• Атомарная формула "x_a∈x_b" означает, что переменная a является элементом переменной b.
• Атомарная формула "x_a=x_b" означает, что переменная a равна переменной b.
• Формула "(¬e)" для формулы e означает отрицание e.
• Формула "(e∧f)" для формул e и f означает соединение (логическое и) e и f.
• Формула "∃x_a(e)" означает, что мы можем изменить свободное вхождение a-й переменной, т.е. заменить x_a другим членом класса $V$ всех множеств в e, так что формула e верна.

Атомарная формула - это особый вид формулы.

Например, возьмём формулу "(x₁∈x₂)". Это говорит о том, что "первая переменная является элементом второй переменной", поэтому мы можем подключить присвоение переменной $(\emptyset, \{\emptyset\}, ...)$ и результат будет истинным, поскольку $\emptyset$ является элементом $\{\emptyset\}$. Если вместо этого мы подключим $(\{\emptyset\}, \emptyset, ...)$, результат будет неверным, потому что $\{\emptyset\}$ не является элементом $\emptyset$ (Если вы знакомы с логикой высказываний, вам может быть интересно отсутствие универсального квантора ∀. Это потому, что ∀x(e) совпадает с (¬(∃x((¬e)))), и это не нужно.)

Более сложный пример: "(¬(∃x₁(x₁∈x₂)))". Это говорит: "неверно, что существует $x$ такое, что "первая переменная является элементом второй переменной" неверно, когда мы заменяем "первую переменную" на $x$. Другими словами, мы не можем выбрать $x$ таким образом, чтобы $x$ был элементом второй переменной. Учитывая присвоение переменной, это верно, когда вторая запись является пустым набором. Например, это верно для присвоения переменной $(3, \{\}, ...)$, но имеет ложное значение для присвоения переменной $(3, {1}, ...)$.

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

Теперь мы подходим к основной концепции способности Райо-именуемых, игнорируя ограничение по длине:

Существует формула $\phi$ такая, что все удовлетворительные присвоения переменных должны иметь $m$ в качестве первого аргумента, и существует по крайней мере одно такое присвоение.

Сначала мы покажем, что 0 является Райо-именуемым. В порядковой системе, $0 = \{\}$. Нам нужно создать формулу $\phi$, которая использует $\{\}$ в качестве своего первого аргумента. Одной из таких строк является "(¬(∃x₂(x₂∈x₁)))" = "мы не можем выбрать $x$ такой, что $x$ является элемент первой переменной" = "мы не можем выбрать элемент первой переменной" = "первая переменная не имеет элементов" = "первая переменная - это пустой набор".

Теперь нам нужно найти способ получить Rayo-name x₁ = $\{\{\}\}$. Первой переменной нужен элемент: "∃x₂(x₂∈x₁)". Затем, чтобы убедиться, что элемент является пустым набором, мы используем "(￢(∃x₂((x₂∈x₁∧∃x₃(x₃∈x₂)))))" = "мы не можем выбрать $x$ таким образом, чтобы $x$ был элементом первой переменной, а третья переменная была элементом $x$" = "мы не можем выбрать $x$ такой, что $x$ является элементом первой переменной и имеет элемент" = "мы не можем выбрать $x$ такой, что $x$ является элементом первой переменной и не является пустым набором" = "если первая переменная содержит элемент, это должно быть пустое множество". Мы "и" все эти утверждения вместе, мы получаем "(∃x₂(x₂∈x₁)∧(￢(∃x₂((x₂∈x₁∧∃x₃(x₃∈x₂))))))".

Мы можем продолжить с этим шаблоном, определяя каждое натуральное число с помощью этого метода. Это позволяет нам назвать число $n$ в символах $O(n^2)$. При больших значениях можно определить рекурсивные операции, что позволило нам присваивать радиообозначения всё большим и большим числам, используя компактную нотацию. Учитывая достаточно большое число, строкам массива, определяющим возведение в степень, потребовалось бы меньше символов, чем нашему наивному методу.

Обратите внимание, что символ x_n считается как единый символ - его не следует разбивать на отдельные символы x и n.

У нас есть всё необходимое для определения функции Rayo:

Функция Rayo $Rayo(n)$ определяется как наименьшее неотрицательное целое число, большее всех неотрицательных целых чисел Rayo, которые могут быть названы не более чем в $n$ символах.

Почему функция Райо не поддаётся вычислению? Используя микроязык Rayo, можно построить множество, элементами которого являются так называемые мгновенные описания машины Тьюринга, и, исходя из этого, это всего лишь небольшой шаг для определения функции занятого бобра (см. ниже). Приложив больше усилий, можно даже сконструировать машину-предсказатель машины Тьюринга и определить их аналоги функции занятого бобра.

Известные значения функции Райо

В настоящее время известны лучшие строки Rayo для 0, 1 и 2:
$0 = \{\} = (\neg\exists x_2(x_2 \in x_1))$ (10 символов)
$1 = \{\{\}\} = (\exists x_2(x_2 \in x_1) \land (\neg\exists x_2((x_2 \in x_1 \land \exists x_3(x_3 \in x_2)))))$ (30 символов)
$2 = \{\{\},\{\{\}\}\} = (\exists x_2 (\exists x_3 ((x_3 \in x_2 \land (x_2 \in x_1 \land x_3 \in x_1)))) \land (\neg \exists x_4 (\exists x_2 (\exists x_3 ((x_4 \in x_3 \land (x_3 \in x_2 \land x_2 \in x_1)))))))$ (56 символов)

Наконец, благодаря различным усилиям Plain'N'Simple, P進大好きBot и Ytosk позже было показано, что $Rayo(260+20n) > 2\uparrow\uparrow n$, что является значительно лучшей оценкой.
Следовательно:
$Rayo(320) > 16$
$Rayo(340) > 65536$
$Rayo(360) > 2^{65536}$
$Rayo(380) > 2^{2^{65536}}$

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

Пользователь англоязычной гугология вики Emk показал, что $Rayo(7901)>S(2^{65536}-1)$, где $S$ - это функция максимального сдвига. Однако, поскольку в его сообщении в блоге используется устаревшая строка Rayo для представления $2^{65536}$, граница не так высока, как могла бы быть. Используя последние границы, можно определить, что $Rayo(7339)>S(2^{65536}-1)$.

Объяснение 2

Мы начнём с парадокса Берри:

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

Дискуссии

Аксиома

Чтобы определить натуральное число с помощью теории множеств, нам нужно зафиксировать, в соответствии с какими аксиомами мы его определяем. Проблема в определении числа Райо заключается в том, что мы не разъяснили аксиомы. В математике мы традиционно опускаем объявление аксиом, в которых мы работаем, до тех пор, пока мы не работаем в ТМЦФ. По традиции несколько гугологов считают, что число Райо определено в ТМЦФ или не имеет отношения к аксиомам, но это неверно.

По крайней мере, поскольку ТМЦФ не способна формализовать предикат истинности во вселенной фон Неймана, число Райо плохо определено в ТМЦФ, если мы не интерпретируем определение числа Райо в терминах доказуемости. Даже если мы интерпретируем определение таким образом, результирующее большое число не будет значительно больше, чем, например, Σ(10¹⁰⁰) где Σ - функция занятого бобра, поскольку доказуемость в рекурсивно перечислимой теории с ограничением длины разрешимо с помощью машины Тьюринга. Чтобы значительно выйти за рамки функции занятого бобра, мы должны отказаться от доказуемости и говорить об истинности в конкретной модели, существование которой не доказуемо в рамках ТМЦФ до тех пор, пока она непротиворечива.

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

Поскольку Райо писал, что он использует теорию множеств второго порядка для того, чтобы формализовать словарь примитивной семантики в исходном описании, число Райо определяется в соответствии с определёнными аксиомами теории множеств второго порядка, которые не уточняются. Важно прояснить аксиомы в невычислимой гугологии, потому что невычислимые большие числа можно сравнивать друг с другом только тогда, когда они разделяют аксиомы, используемые в их определениях. К счастью, существует множество вариантов аксиом теории множеств второго порядка, которые позволяют нам определить число Райо. В качестве вывода: "Число Райо хорошо определено для гугологов, которые не заботятся об уточнении аксиом, и плохо определено для гугологов, которые заботятся об уточнении аксиом".

В 2020 году Райо добавил следующее новое описание того, как обращаться с его числом:

Примечание: Философы иногда придерживаются реалистической интерпретации теории множеств. Согласно этой интерпретации, теоретико-множественные выражения имеют "стандартные" значения, которые определяют определённое значение истинности для каждого предложения языка, независимо от того, возможно ли в принципе узнать, каковы эти значения истинности. (Смотрите, например, эту статью Ванна Макги.) Во время конкурса мы с Адамом считали само собой разумеющимся, что язык теории множеств (второго порядка) интерпретировался стандартно, что гарантирует, что итоговая заявка соответствует определённому числу. Если бы вместо этого язык интерпретировался на основе системы аксиом, окончательная запись была бы недействительной. Это связано с тем, что каждая (непротиворечивая) аксиоматизация языка имеет неизоморфные модели, и нет никакой гарантии, что конечная запись будет соответствовать одному и тому числу относительно разных моделей.

Это означает, что Райо рассматривает философскую "интерпретацию" теоретико-множественных формул по отношению к "истине" в реальном мире, которая неформализуема в математике, и не предполагает конкретного выбора аксиом. Это одно из разумных направлений гугологии за пределами математики. С другой стороны, проблема в последнем предложении выглядит как оправдание того, почему они принимают неформализуемую "истину" как должное, но это не имеет смысла, потому что зависимость значения данного числа от модели не имеет отношения к "недействительности". В математике существует много чётко определённых понятий, которые не являются абсолютными, т.е. зависят от модели, например, уникальное натуральное число $n$, удовлетворяющее $(\text{CH} \to n=0) \land (\neg\text{CH} \to n=1)$. В гугологии есть много больших чисел, которые зависят от модели, например, значения функции занятого бобра и особенно $S(1919)$, где $S$ обозначает функцию максимального сдвига. В дуэли больших чисел нет правила, запрещающего число, которое зависит от модели, и действительно, оно даже позволяет пропускать, чтобы исправить аксиомы.

История

Когда было определено число Райо

Дуэль Райо и Эльги по большим числам была вдохновлена дуэлью по большим числам, описанной в статье "Кто может назвать большее число?" автор: Скотт Ааронсон.

После того, как было определено число Райо

• В январе 2013 года Адам П. Гоучер заявил, что $\text{Rayo}(n)$ растёт медленнее, чем его функция Кси. Однако утверждение оказалось неверным.

• В октябре 2013 года пользователь англоязычной гугология вики Кёдайсуу определил седьмое рыбье число как расширение номера Райо. седьмого рыбьего числа такая же проблема с числом Райо, которая описана в разделе аксиом.

• В октябре 2014 года Wojowu определил BIG FOOT, используя не наивное расширение теории множеств n-го порядка, теорию Удла первого порядка, и оно было признано самым большим именованным числом. Однако, в 2018 выяснилось, что BIG FOOT нечётко определён.

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

Автор

Это число было изобретено доктором Агустином Райо, адъюнкт-профессор (в то время, когда он создал своё число) лингвистики и философии Массачусетского технологического института, где он получил степень доктора философии в 2001 году.

Смотрите также

• Число Райо в википедии
• Функция занятого бобра
• BIG FOOT
• Маленький Бигеддон
• Снежный человек/Большой Бигеддон
• Большое количество числа сада
• Невычислимая функция