Rayo函数：修订间差异

下一编辑→

可视化wikitext

2025年8月22日 (五) 16:44的版本

Rayo函数，是目前被命名的增长速度最快速的函数之一。它是Agustín Rayo在2007年1月26日，在麻省理工大学的“大数比赛”Big Number Duel中提出的^[1]。

定义

通俗定义

在集合论中我们知道，每个自然数 n 都可以用一个集合来表示，而一个一阶逻辑语句的自由变元所能够取为的值同样能够构成一个集合。因此，如果这个一阶逻辑语句所描述的集合恰好对应于一个自然数，那么我们就用这个一阶逻辑语句成功地描述了一个自然数。

通俗地说，Rayo 函数 Rayo(n) 的定义为：不能够用包含字符数为 n 的一阶逻辑语句定义的最小的自然数。

Rayo数定义为 $R a y o (1 0^{100})$

关于 Rayo 函数，有几点值得说明一下。首先，它不是用自然语言表述出的“不能用 n个字确定的最小自然数”。例如，我们可以考虑“不能用二十个字确定的最小自然数”，这句话确定了一个自然数。但是这句话本身又少于 20 个字，因此这个数也能够用小于 20 个字来确定。因此这句话产生了悖论，我们称之为 Perry 悖论。究其原因，这种悖论是由于自然语言的模糊性导致的。相比之下，Rayo 数的规则是明确的，因此不会产生这一问题。

另外，它也与“用 n 个字符所不能得到的最小自然数”不同。因为计算机程序总是递归的，而一阶逻辑不是递归的，它的描述能力要比计算机语言强得多。尽管初看起来，一阶逻辑的语言十分低效，但是一旦字符数量增加，我们就可以利用它定义一些非常高效的函数，它们的表示能力将大得惊人。

正式定义

令 $[ϕ]$ 和 $[ψ]$ 为 Gödel 编码公式，s 和 t 为变量。定义 $S a t ([ϕ], s)$ 如下:

  $\forall R {$ 
 {
    $\forall [ψ], t : R ([ψ], t) \leftrightarrow ([ψ] =^{″} x_{i} \in {x_{j}}^{″} \land t (x_{i}) \in t (x_{j}))$ 
                    $\lor ([ψ] =^{″} x_{i} = {x_{j}}^{″} \land t (x_{i}) = t (x_{j}))$ 
                    $\lor ([ψ] =^{″} (\neg θ)^{″} \land \neg R ([θ], t))$ 
                    $\lor ([ψ] =^{″} (θ \land ξ)^{″} \land R ([θ], t) \land R ([ξ], t))$ 
                    $\lor ([ψ] =^{'} \exists x_{i} (θ)^{″} \land \exists t^{'} : R ([θ], t^{'}))$ 
                   (where t′ is a copy of t with  $x_{i}$  changed)
    $} \Rightarrow R ([ϕ], s)$ 
 }

我们称自然数 m 为 Rayo 可命名的，如果存在一个公式 $ϕ (x_{1})$ 小于 n 个符号且 $x_{1}$ 作为其唯一的自由变量满足以下性质：

存在一个变量赋值 s，赋值 x1 := m，使得 $S a t ([ϕ (x_{1})], s)$ 。
对于任何变量赋值 t，如果 $S a t ([ϕ (x_{1})], t)$ ，则 t 必须有 $x_{1} = m$ 。

Rayo(n) 是大于使用 n 个符号的 Rayo 可命名的所有数的最小数。

对 Rayo 函数定义的阐述如下：

原子公式“ $x_{a} \in x_{b}$ ”表示第 a 变量是第 b 变量的元素。
原子公式 $x_{a} = x_{b}$ ”表示第 a 变量等于第 b 变量。
公式 e 的公式“( $\neg e$ ) ”表示 e 的否定。
公式 e 和 f 的公式“( $e \land f$ ) ”表示 e 和 f 的合取（逻辑与）。
公式 e 的公式“ $\exists x_{a} (e)$ ”意味着我们可以修改 a 变量的自由出现，即用 e 中所有集合的 V 类的另一个成员替换 $x_{a}$ 使得公式 e 为真。

以上五条定义只是更加精确地给出了 ∈, =, ¬, ∧, ∃ 这五个逻辑的含义。这样我们就给出了用公式定义自然数的方法。若一个自然数是不能够以上述方式从长度为 n 的语句中定义的最小数，那么它就是 Rayo(n)。

取值

\begin{eqnarray*}

0 & = & \{\} = (\neg\exists x_2(x_2 \in x_1)) \ \textrm{(10 symbols)} \\

1 & = & \{\{\}\} = (\exists x_2(x_2 \in x_1) \land (\neg\exists x_3((x_3 \in x_1 \land \exists x_4(x_4 \in x_3))))) \ \textrm{(30 symbols)} \\

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))))))) \ \textrm{(56 symbols)}

\end{eqnarray*}

↑ A. Rayo, "Big Number Duel", 2007

[1] A. Rayo, "Big Number Duel", 2007

[1]

@@ 第1行： / 第1行： @@
 Rayo函数，是目前被命名的增长速度最快速的函数之一。它是Agustín Rayo在2007年1月26日，在麻省理工大学的“大数比赛”[[Big Number Duel]]中提出的<ref>[https://web.mit.edu/arayo/www/bignums.html A. Rayo, "Big Number Duel", 2007]</ref>。
-{{默认排序:相关问题}}
+== 定义 ==
+=== 通俗定义 ===
+在集合论中我们知道，每个自然数 n 都可以用一个集合来表示，而一个一阶逻辑语句的自由变元所能够取为的值同样能够构成一个集合。因此，如果这个一阶逻辑语句所描述的集合恰好对应于一个自然数，那么我们就用这个一阶逻辑语句成功地描述了一个自然数。
+通俗地说，Rayo 函数 Rayo(n) 的定义为：不能够用包含字符数为 n 的[[一阶逻辑]]语句定义的最小的自然数。
+Rayo数定义为<math>Rayo(10^{100})</math>
+关于 Rayo 函数，有几点值得说明一下。首先，它不是用自然语言表述出的“不能用 n个字确定的最小自然数”。例如，我们可以考虑“不能用二十个字确定的最小自然数”，这句话确定了一个自然数。但是这句话本身又少于 20 个字，因此这个数也能够用小于 20 个字来确定。因此这句话产生了悖论，我们称之为 Perry 悖论。究其原因，这种悖论是由于自然语言的模糊性导致的。相比之下，Rayo 数的规则是明确的，因此不会产生这一问题。
+另外，它也与“用 n 个字符所不能得到的最小自然数”不同。因为计算机程序总是递归的，而一阶逻辑不是递归的，它的描述能力要比计算机语言强得多。尽管初看起来，一阶逻辑的语言十分低效，但是一旦字符数量增加，我们就可以利用它定义一些非常高效的函数，它们的表示能力将大得惊人。
+=== 正式定义 ===
+令<math>[\phi]</math>和<math>[\psi]</math>为 Gödel 编码公式，s 和 t 为变量。定义<math>Sat([\phi], s)</math>如下:
+  <math>\forall R \{</math>
+  {
+    <math>\forall[\psi],t:R([\psi],t)\leftrightarrow([\psi]=''x_i\in x_j''\land t(x_i)\in t(x_j))</math>
+                    <math>\lor([\psi]=''x_i=x_j''\land t(x_i)=t(x_j))</math>
+                    <math>\lor([\psi]=''(\neg\theta)''\land\neg R([\theta],t))</math>
+                    <math>\lor([\psi]=''(\theta\land\xi)''\land R([\theta],t)\land R([\xi],t))</math>
+                    <math>\lor([\psi]='\exists x_i(\theta)''\land\exists t':R([\theta],t'))</math>
+                    (where t′ is a copy of t with <math>x_i</math> changed)
+    <math>\} \Rightarrow R([\phi],s)</math>
+  }
+我们称自然数 m 为 Rayo 可命名的，如果存在一个公式 <math>\phi(x_1)</math> 小于 n 个符号且<math>x_1</math>作为其唯一的自由变量满足以下性质：
+# 存在一个变量赋值 s，赋值 x1 := m，使得<math>Sat ([\phi (x_1)] , s)</math>。
+# 对于任何变量赋值 t，如果 <math>Sat ([\phi (x_1)] , t)</math>，则 t 必须有 <math>x_1 = m</math>。
+Rayo(n) 是大于使用 n 个符号的 Rayo 可命名的所有数的最小数。
+对 Rayo 函数定义的阐述如下：
+# 原子公式“<math>x_a \in x_b</math>”表示第 a 变量是第 b 变量的元素。
+# 原子公式<math>x_a=x_b</math>”表示第 a 变量等于第 b 变量。
+# 公式 e 的公式“(<math>\neg e</math>) ”表示 e 的否定。
+# 公式 e 和 f 的公式“(<math>e \land f</math>) ”表示 e 和 f 的合取（逻辑与）。
+# 公式 e 的公式“<math>\exist x_a(e)</math>”意味着我们可以修改 a 变量的自由出现，即用 e 中所有集合的 V 类的另一个成员替换<math>x_a</math>使得公式 e 为真。
+以上五条定义只是更加精确地给出了 ∈, =, ¬, ∧, ∃ 这五个逻辑的含义。这样我们就给出了用公式定义自然数的方法。若一个自然数是不能够以上述方式从长度为 n 的语句中定义的最小数，那么它就是 Rayo(n)。
+== 取值 ==
+\begin{eqnarray*}
+& = & \{\} = (\neg\exists x_2(x_2 \in x_1)) \ \textrm{(10 symbols)} \\
+& = & \{\{\}\} = (\exists x_2(x_2 \in x_1) \land (\neg\exists x_3((x_3 \in x_1 \land \exists x_4(x_4 \in x_3))))) \ \textrm{(30 symbols)} \\
+& = & \{\{\},\{\{\}\}\} \\
+& = & (\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))))))) \ \textrm{(56 symbols)}
+\end{eqnarray*}{{默认排序:相关问题}}
 [[分类:记号]]