大數學 维基
Advertisement

鸟数阵记号(英语:Bird's array notation,缩写BAN,另称鸟之记号)是由克里斯·鸟所发明的大数记号。这是乔纳森·鲍尔斯所创之扩展数阵记号的扩展,并在历史和定义上与BEAF类似。

“简单”数阵

线性和多维数阵

在线性和多维数阵上,BAN和BEAF相同。

  • 规则1. 如果只有1或2项,则\(\{a\} = a\), \(\{a,b\} = a^b\)(另外,\(\lbrace a \rbrace = a\)可从\(\{a,b\} = a^b\)推出,因为\(\{a\} = \{a,1\} = a^1 = a\))(规则2的逆推)。
  • 规则2. 如果尾项是1,可以将它去掉:\(\{\# 1\} = \{\#\}\)。(“#”表示数阵不变的部分)
  • 规则3. 如果第2项是1,则数阵的值等于首项:\(\{a,1 \#\} = a\)。
  • 规则4. 如果第3项是1:
    \(\{a,b,1,1,\cdots,1,1,c \#\} = \{a,a,a,a,\cdots,a,\{a,b-1,1,1,\cdots,1,1,c \#\},c-1 \#\}\)
  • 规则5. 否则:
    \(\{a,b,c \#\} = \{a,\{a,b-1,c \#\},c-1 \#\}\)

在多维数阵中,鸟使用\(a \langle c \rangle b\)这个记号,相当于鲍尔斯的\(b^c \& a\),它的规则为:

  • 规则A1. 如果\(c = 0\),\(\textrm` a \langle 0 \rangle b = a \textrm'\)。
  • 规则A2. 如果\(b = 1\),\(\textrm` a \langle c \rangle 1 = a \textrm'\)。
  • 规则A3. 否则,\(\textrm` a \langle c \rangle b \textrm' = \textrm` a \langle c - 1 \rangle b [c] a \langle c \rangle (b - 1) \textrm'\)。

主规则为:

  • 规则M1. 如果只有2项,\(\{a, b\} = a^b\)。
  • 规则M2. 如果\([m] < [n]\),\(\{\# [m] 1 [n] \#\} = \{\# [n] \#\}\)。(包含上面的规则2)
  • 规则M3. 如果第2项是1,\(\{a,1 \#\} = a\)。
  • 规则M4. 如果第2项后有未填充分隔符,后面接着非1项:
    \(\{a,b [m_1] 1 [m_2] \cdots 1 [m_x] c \#\}\)
    \(= \{a \langle m_1-1 \rangle b [m_1] a \langle m_2-1 \rangle b [m_2] \cdots a \langle m_x-1 \rangle b [m_x] (c-1) \#\}\)
  • 规则M5. 如果第2项后有未填充分隔符跟一串1,后面接着非1项:
    \(\{a,b [m_1] 1 [m_2] \cdots 1 [m_x] 1,1,\cdots,1,1,c \#\}\)
    \(= \{a \langle m_1-1 \rangle b [m_1] a \langle m_2-1 \rangle b [m_2] \cdots a \langle m_x-1 \rangle b [m_x] a,a,\cdots,a,R,c-1 \#\}\)
    其中\(R = \{a,b-1 [m_1] 1 [m_2] \cdots 1 [m_x] 1,1,\cdots,1,1,c \#\}\)
  • 规则M6. 如果第2项后有一串1:
    \(\{a,b,1,1,\cdots,1,1,c \#\} = \{a,a,a,a,\cdots,a,\{a,b-1,1,1,\cdots,1,1,c-1 \#\},c-1 \#\}\)
  • 规则M7. 上述规则不适用:
    \(\{a,b,c \#\} = \{a,\{a,b-1,c \#\},c-1 \#\}\)

例如,{3,3 [3] 1 [2] 1,1,1,4} = {3 <2> 3 [3] 3 <1> 3 [2] 3,3,{3,2 [3] 1 [2] 1,1,1,4},3}。

鸟使用\([m]\)作为维度分隔符,相当于BEAF的\((m - 1)\)分隔符。在BEAF中,数阵的默认值为1,分隔符默认值为0,而鸟的方法解决了这个问题。

在快速增长阶层,线性和多维数阵分别对应极限序数\(\omega^\omega\)和\(\omega^{\omega^\omega}\)。

超维和嵌套数阵

接下来,可以允许分隔符变为数阵(如\([1, 1, 2]\))。在规则M1至M7上,只要把\([m_n]\)改为\([m_n \#]\)即可,其他不变。

尖括号规则需要修改。规则A3变为A4,然后订定新的规则A3:

  • 规则A3. 如果尖括号的首项是0,且后面有非1项:
    \(a \langle 0,1,1,\cdots,1,1,c \# \rangle b = a \langle b,b,b,\cdots,b,b,c-1 \# \rangle b\)

这条规则与规则M4类似。

下一步是容许分隔符内含有分隔符,由此制定嵌套数阵记号。规则A3、A4分别替换为A4、A5,然后订定新的规则A3、A4:

  • 规则A3. 如果\([A] < [B]\),\(a <\# [A] 1 [B] \#> b = a <\# [B] \#> b\)。
  • 规则A4. 如果尖括号的首项是0,且后面有非1项:
    \(a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_n] c \# \rangle b\)
    \(= a \langle b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_n-1 \rangle b [A_n] c-1 \# \rangle b\)

An和B是数阵,而Ai-1跟Ai的差别,只在于首项减去1。

分隔符的层级比较

在规则A3和M2中,需要确定分隔符的层级。首先,制定数阵的嵌套层级,我们可以记为Lev(A)。例如,假设A = \(\{3,3 [1 [1 [2] 2] 2] 2\}\),则Lev(A) = 3,因为最内层数阵[2]嵌套在[1 [2] 2]里,它又嵌套在[1 [1 [2] 2] 2]里,然后就是嵌套在主数阵里了。非正式的说,Lev(A)就是从最内层嵌套到主数阵所需的次数。另外还有其他函数,Num(H,A)代表数阵A中,分隔符[H]的个数,如A = \(\{3,3 [1 [2] 1 [2] 1 [2] 2] 2] 2\}\),则Num(2,A) = 3。

假设我们要确定分隔符[A]和[B]哪个具有较高层级,则可以通过下列步骤:

  1. 设[A1]=[A], [A2]=[A1]和[B1]=[B], [B2]=[B1]。
  2. 如果Lev(A)>Lev(B),则[A]>[B],如果Lev(A)<Lev(B),则[A]<[B]。如果Lev(A)=Lev(B)>0,则前往步骤3,否则跳到步骤6。
  3. 设[A*]和[B*]是A2和B2中等级最高的分隔符。如果[A*]>[B*]则[A]>[B],如果[A*]<[B*]则[A]<[B],否则设[H]=[A*]=[B*],然后前往步骤4。
  4. 如果Num(H,A2)>Num(H,B2),则[A]>[B],如果Num(H,A2)<Num(H,B2),则[A]<[B],否则前往步骤5。
  5. 在A2和B2中,删除最后的[H]分隔符及前面的所有项,然后回到步骤2。
  6. 现在,A2和B2变为[a]和[b],其中a和b是简单的数。所以,如果[a]<[b],则[A]<[B],如果[a]>[b],则[A]>[B],否则前往步骤7。
  7. 在A1和B1中,除去最后一项和它前面的分隔符。如果A1和B1是空的,那么[A]=[B],否则回到步骤2。

超嵌套数阵

反斜杠数阵

为了超越嵌套数阵记号,鸟定义了特殊的分隔符,[1 \ c],具体定义如下:

  • \(\{a,b [1 \backslash c] 2\} = \{a \langle 0 \backslash c \rangle b\} = \{a \langle b \langle b \langle b \langle \cdots b \langle b \rangle b \cdots \rangle b \backslash c-1 \rangle b \backslash c-1 \rangle b \backslash c-1 \rangle b\}\)(从中间到右边有b个b)
  • \(\{a,b [A \backslash 1] 2\} = \{a,b [A] 2\}\)(A是任意数阵)

这个记号允许我们在反斜杠前套用一般数阵,如[1 [2] 2 \ 2]或[1 [1 \ 2] 2 \ 2]。反斜杠不能放在底层(外围无方括号的层级),例如{3, 3 \ 2}是不合法的。

鸟进一步将其扩展,除了单个反斜杠外,也可使用多个反斜杠,甚至是反斜杠阵。他用[A]\代表反斜杠阵A。有新的3个规则用来处理反斜杠阵:

  • 规则B1. 如果反斜杠维度是0或1:
    • \(a \langle 0 \rangle\backslash b = a\)
    • \(a \langle 1 \rangle\backslash b = a \backslash a \backslash \cdots \backslash a \backslash a\)(b个a)
  • 规则B2. 第一个非1项(首项不计入)前是反斜杠:
    • \(a \langle 0 [A_1]\backslash 1 [A_2]\backslash \cdots 1 [A_n]\backslash 1 \backslash c \# \rangle b\)
      \(= a \langle b \langle A_1' \rangle\backslash b [A_1]\backslash b \langle A_2' \rangle\backslash b [A_2]\backslash \cdots b \langle A_n' \rangle\backslash b [A_n]\backslash R_{b-1} \backslash c-1 \# \rangle b\)
    • \(R_n = b \langle b \langle A_1' \rangle b [A_1]\backslash b \langle A_2' \rangle b [A_2]\backslash \cdots b \langle A_n' \rangle\backslash b [A_n]\backslash R_{n-1} \backslash c-1 \# \rangle b\)
    • \(R_1 = b\)
  • 规则B3. 否则:
    • \(a \langle 0 [A_1]\backslash 1 [A_2]\backslash \cdots 1 [A_n]\backslash 1 [B_1] 1 [B_2] \cdots 1 [B_n] c \# \rangle b\)
      \(= a \langle b \langle A_1' \rangle\backslash b [A_1]\backslash b \langle A_2' \rangle\backslash b [A_2]\backslash \cdots b \langle A_n' \rangle\backslash b [A_n]\backslash\)
      \(b \langle B_1' \rangle b [B_1] b \langle B_2' \rangle b [B_2] \cdots b \langle B_n' \rangle b [B_n] c-1 \# \rangle b\)

这个符号的限制是费佛曼-舒特序

嵌套超嵌套数阵

2级超分隔符

现在,我们需要一个分隔符,用来表示任何级别的反斜杠嵌套。在鸟的文件“Beyond Bird's Nested Arrays I”中,他使用正斜杠来表示反斜杠的嵌套:

\(\{a,b [1 / 2] 2\} = \{a \langle 0 / 2 \rangle b\} = \{a \langle b \langle b \langle b \cdots b \langle b \rangle\backslash b \cdots b \rangle\backslash b \rangle\backslash b \rangle b\}\)(从中间到右边有b个b,而反斜杠有b-2个)

接下来,鸟指出分隔符[A]\(反斜杠阵A)可改写为\([A \neg 2]\),因此我们能够把正斜杠写为\([1 \neg 3]\)。然而,为了更便于推广,\([1 \neg 3]\)的定义跟正斜杠有点不同,即:

\(\{a,b [1 [1 \neg 3] 2] 2\} = \{a \langle 0 [1 \neg 3] 2 \rangle b\} = \{a \langle b \langle b \langle b \cdots b \langle b \rangle\backslash b \cdots b \rangle\backslash b \rangle\backslash b \rangle b\}\)(从中间到右边有b+1个b,而反斜杠有b-1个)

然后,我们可以延伸\([1 \neg 3]\)到\([A \neg 3]\),就像从反斜杠延伸到\([A \neg 2]\)。注意,反斜杠相当于\([1 \neg 2]\)分隔符。

因此,我们可以嵌套\(\neg 3\),它的限制可以写为\([1 \neg 4]\)。不难看出这里的模式,可以由此定义\([1 \neg n]\)分隔符:

\(\{a,b [1 [1 \neg n] 2] 2\} = \{a \langle 0 [1 \neg n] \rangle b\} = \{a \langle b \langle b \langle b \cdots b \langle b \neg n-1\rangle b \neg n-1\rangle b \cdots b \neg n-1\rangle b \neg n-1\rangle b \rangle b\}\)(从中间到右边有b+1个b,而\(\neg n-1\)有b-1个)

一般来说,我们需要定义一套规则,使我们能够处理\([A \neg n]\)。我们不需要重写主规则,它们和嵌套数阵记号一样。只有尖括号规则需要改变。

  • 规则A1. 尖括号的数字为0:
    \(a \langle 0 \rangle b = a\)
  • 规则A2. b = 1:
    \(a \langle A \rangle 1 = a\)
  • 规则A3. [A] < [B]:
    \(a \langle\# [A] 1 [B] \#\rangle b = a \langle\# [B] \#\rangle b\)
  • 规则A4. 第一项是0,c前为正常分隔符(非\([1 \neg n]\)的分隔符,其中n > 1):
    \(a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_m] c \# \rangle b\)
    \(= a \langle b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] c-1 \# \rangle b\)
  • 规则A5. 第一项是0,c前为反斜杠:
    \(a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_m] 1 \backslash c \# \rangle b\)
    \(= a \langle b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] b \langle R_b \rangle b \backslash c-1 \# \rangle b\)
    • \(R_n = b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] b \langle R_{n-1} \rangle b \backslash c-1 \# \rangle b\) (n > 1)
    • \(R_1 = 0\)
  • 规则A6. 第一项是0,c前为\([1 \neg n]\) (n > 2):
    \(a \langle 0 [A_1] 1 [A_2] \cdots 1 [A_m] 1 [1 \neg n] c \# \rangle b\)
    \(= a \langle b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] b \langle R \rangle b [1 \neg n] c-1 \# \rangle b\)
    • \(R = b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] R_b [1 \neg n] c-1 \# \rangle b\)
    • \(R_n = b \langle A_1-1 \rangle b [A_1] b \langle A_2-1 \rangle b [A_2] \cdots b \langle A_m-1 \rangle b [A_m] b \langle R_{b-1} \rangle b [1 \neg n] c-1 \# \neg n-1 \rangle b\) (n > 1)
    • \(R_1 = 0\)
  • 规则A7. 规则A1-A6不适用:
    \(a \langle c \# \rangle b = a \langle c-1 \# \rangle b [c] a \langle c \# \rangle b-1\).

这个符号的增长率达到\(\vartheta(\Omega^\omega)\),即小凡勃伦序

2级超分隔符数阵

我们定义\(\{a \langle 0 [1 \neg 1,2] 2 \rangle b\} = \{a \langle b [b \neg b] b \rangle b\}\)。它和\(\{a,b [1 \backslash 1, 2] 2\} = \{a \langle b \backslash b \rangle b\}\)非常相似。它的增长率为\(\vartheta(\Omega^\omega)\)。为了推广它,我们重新定义规则A2:

  • 规则A2. 方括号中,如果分隔符后有1:
    • 情况1. 1是最后一项,在分隔符后:
      \(a \langle \# [ A ] 1 \rangle b = a \langle \# \rangle b\)
    • 情况2 1被夹在分隔符与\(\neg\)中:
      \(a \langle \# [ A ] 1 \neg n \rangle b = a \langle \# \neg n \rangle b\)
    • 情况3 1在\(\neg\)后:
      \(a \langle \# \neg 1 \rangle b = a \langle \# \rangle b\)
    • 接下来,如果[A]比[B]小,或者只有[B]是超分隔符:
    • 情况4 1夹在A和B中,并且最后不是\(\neg n\):
      \(a \langle \# [ A ] 1 [ B ] \# \rangle b = a \langle \# [B] \# \rangle b\)
    • 情况5 否则:
      \(a \langle \# [ A ] 1 [ B ] \# \neg n \rangle b = a \langle \# [B] \# \neg n \rangle b\)

其中,两个#不一定相同。这个记号的极限是大凡勃伦序

参见

  • H函数
  • S函数
  • U函数
  • BEAF
  • 鸟数阵记号入门

外部链接

Advertisement