Ampersand Notation

Ampersand Notation (&N) is a notation for large numbers made by Wikia user CompactStar. The notation is currently composed of 3 parts, which are as follows:
* Basic Ampersand Notation (B&N)
* Extended Ampersand Notation (X&N) 
* Nested Ampersand Notation (N&N) 
Ampersand Notation up to Extended Ampersand Notation is well-defined, but unfortunately, several versions of Nested Ampersand Notation are ill-defined, as is explained in #Issues section and #Issues_2 section. Even if the creator will update the definition, this does not automatically mean that it is known to be well-defined, but it would be considered uncertain unless a proof of well-definedness or ill-definedness was found. The creator plans to create the following part in the future:
* Hyper-Nested Ampersand Notation (HN&N)
== Basic Ampersand Notation ==
Basic Ampersand Notation (B&N) is the first part of Ampersand Notation.
=== Definition ===
Let @ represent any sequence of ampersand symbols (&).
A valid expression in B&N is of the form a[@b], where a and b are non-negative integers. b is optional and may be removed.
B&N outputs a non-negative integer for every valid expression, determined using this set of rules:
* a[] = aa
* a[@0]= a[@]
* b > 0: a[@b]= a[@b - 1][@b - 1]...[@b - 1][@b - 1], with a copies of "[@b - 1]"
* a[@&]= a[@a]
=== Examples ===
2[1]
= 2[0][0]
= 2[][]
= 2[]2[]
= (22)(22)
= 44
= 256
2[&1]
= 2[&0][&0]
= 2[&][&]
= 2[2][&]
= 2[1][1][&]
= 2[0][0][1][&]
= 2[][][1][&]
= (22)(22)[1][&]
= 44[1][&]
= 256[1][&]
= ...
=== Comparison with fast-growing hierarchy ===
Here, a is a non-negative integer. All inequalities presented only hold true for sufficiently large a, rather than any a.
*a[] ≥ f2(a)
*a[1] ≥ f3(a)
*a[2] ≥ f4(a)
*a[3] ≥ f5(a)
*a[4] ≥ f6(a)
*a[&] ≥ fω(a)
*a[&1] ≥ fω+1(a)
*a[&2] ≥ fω+2(a)
*a[&3] ≥ fω+3(a)
*a[&&] ≥ fω×2(a)
*a[&&1] ≥ fω×2+1(a)
*a[&&&] ≥ fω×3(a)
*a[&&&&] ≥ fω×4(a)
This notation has a limit ordinal of \(\omega^{2}\) in the fast-growing hierarchy.
== Extended Ampersand Notation ==
Extended Ampersand Notation (X&N) is the second part of Ampersand Notation.
=== Definition ===
Define an ampersand-structure as an expression of the form &x, where x is a non-negative integer. x is optional and may be removed.
Let @ represent any sequence of ampersand-structures.
A valid expression in X&N is of the form a[@b], where a and b are non-negative integers. b is optional and may be removed. X&N outputs a non-negative integer for every valid expression, determined using this set of rules:
* a[] = aa
* a[@0]= a[@]
* b > 0: a[@b]= a[@b - 1][@b - 1]...[@b - 1][@b - 1], with a copies of "[@b - 1]"
* a[@&] = a[@a]
* a[@&0]= a[@&]
* x > 0: a[@&x]= a[@&x - 1&x - 1...&x - 1&x - 1] with a copies of "&x - 1"
=== Examples ===
2[&10]
= 2[&1]
= 2[&0&0]
= 2[&&]
= 2[&2]
= 2[&1][&1]
= 2[&0][&0][&1]
= 2[&][&][&1]
= ...
2[&2&1]
= 2[&2&0][&2&0]
= 2[&2&][&2&]
= 2[&22][&2&]
= 2[&21][&21][&2&]
= 2[&20][&20][&21][&2&]
= 2[&2][&2][&21][&2&]
= 2[&1&1][&2][&21][&2&]
= ...
=== Comparison with fast-growing hierarchy ===
Here, a is a non-negative integer. All inequalities presented only hold true for sufficiently large a, rather than any a.
*a[&1] ≥ fω2(a)
*a[&11] ≥ fω2+1(a)
*a[&1&] ≥ fω2+ω(a)
*a[&1&1] ≥ fω2×2(a)
*a[&2] ≥ fω3(a)
*a[&2&2] ≥ fω3×2(a)
*a[&3] ≥ fω4(a)
*a[&4] ≥ fω5(a)
== Nested Ampersand Notation ==
Nested Ampersand Notation (N&N) is the third part of Ampersand Notation.
Although the creator states that it is comparable to \(\varepsilon_0\) with respect to the Wainer hierarchy without a source or a proof, the notation is ill-defined as is explained in #Issues section and #Issues_2 section. The reader should be careful that analysis without a proof might be incorrect, even when the one who writes it regard the result as an obvious fact which does not require a proof.
==== Old definition ====
This is the original version. Define an ampersand-structure as an expression of the form &@x, where @ is any sequence of ampersand-structures, and x is a non-negative integer. x is optional and may be removed.
The number of layers in an ampersand-structure is the number of nested subscripts, e.g. & has 0 layers, &5 has 1 layer, and &&7</sub> has 2 layers.
A valid expression in N&N is of the form a[@b], where @ is any sequence of ampersand structures, and a and b are non-negative integers. b is optional and
may be removed.
N&N is intended to output a non-negative integer for every valid expression,
determined using this set of rules:
* a[] = aa
* a[@0] = a[@]
* b > 0: a[@b]= a[@b - 1][@b - 1]...[@b - 1][@b - 1], with a copies of "[@b - 1]"
* # is another ampersand-structure sequence: a[@&&...�] with x layers in the ampersand-structure after @ = a[@&&...&#] with x layers in the ampersand-structure after @ (x - 1 if # is empty and x > 0)
* # is another ampersand-structure sequence: a[@&&...&#&] with x layers in the ampersand-structure after @ = a[@&&...&#a] with x layers in the ampersand-structure after @
* # is another ampersand structure sequence, y > 0: a[@&&...&#x] with y layers in the ampersand-structure after @ = a[@&&...&#x - 1&#x - 1...&#x - 1&#x - 1] with y layers in the ampersand-structure after @ and a copies of "#x - 1"
===== Issues =====
The notion of "layer" is just described in this ambiguous way using the unformalised word "number of nested subscripts" with finitely many examples, and hence is not formalised. For example, the layer of \(\&_{\& \&}\) and \(\&_{\&_{\&} \&}\) are quite ambiguous.
Moreover, seriously ambiguos ellipses occur in the set of rules. Say, can \(\&_{\&_{\cdots \&}}\) stand for \(\&\) or \(\&_{\& \&}\)? Maybe no, because they are not obtained as \(\&_{\&_{\alpha \&}}\) for some string \(\alpha\).
Further, the set of rules is incomplete, because there is no rule applicable to valid expressions like \(2[\&]\) and \(2[\&_{\& \&}])\).
In addition, there are multiple rules applicable to a single expression. Say, both of the fourth and sixth rules are applicable to \(2[\&_{\&_{\&_{0}}}]\).
* The fourth rule returns the ambiguous expression "\(2[\&_{\cdots_{\&_{\#}}}]\) with \(3\) layers in the ampersand-structure after the empty string (\(2\) if \(\#\) is empty)" applicable to the case where \(\#\) is actually empty. What does "\(2\) if \(\#\) is empty" mean here? Is it an exceptional definition of the return value of the \(3\)-layered expression \(2[\&_{\&_{\&_{\&}}}]\)? Or is it an exceptional redefinition of the layer of the expression in \(2[\&_{\&_{\&_{\&}}}]\), which is originally \(3\)-layered? Or is it an exceptional definition of the layer of the expression in the expansion, i.e. \(2[\&_{\&_{\&}}]\) instead of \(2[\&_{\&_{\&_{\&}}}]\)? Although such a confusion could be easily removed if one defined rules in a recursive way, but since the original definition is defined in terms of natural language instead of recursion, such a serious ambiguity occurs.
* The sixth rule returns the ill-formed expression \(2[\&_{\&_{\&_{-1} \&_{-1}}}]\).
The creator stated that the growth rate was comparable to \(\varepsilon_0\) in Wainer hierarchy without a proof. However, since the notation is unformalised, the creator's statement on the growth rate does not mathematically make sense.
==== New definition ====
Later the creator updated the definition of the notation to fix issues present in the old definition.
Define an ampersand-structure as an expression of the form &@x, where @ is any sequence of ampersand-structures, and x is a non-negative
integer. x is optional and may be removed.
A valid expression in N&N is of the form a[@b], where @ is any sequence of ampersand structures, and a and b are non-negative integers. b is optional and
may be removed.
N&N outputs a non-negative integer for every valid expression,
determined using this set of rules:
* a[] = aa
* a[@0]= a[@]
* b > 0: a[@b]= a[@b - 1][@b - 1]...[@b - 1][@b - 1], with a copies of "[@b - 1]"
* # is another ampersand-structure sequence: a[@S(x)#0] = a[@S(x)#]
* # is another ampersand-structure sequence: a[@S(x)#&] = a[@S(x)#a]
* # is another ampersand structure sequence, y > 0: a[@S(x)&#y] = a[@S(x)&#y - 1&#y - 1...&#y - 1&#y - 1] with a copies of "&#y - 1"
In the above definition, the string S(x) for a non-negative integer x is defined as follows:
* S(0) = ø (empty string)
* x > 0: S(x) = &S(x - 1)
For example, S(1) = &, S(2) = &&, and S(3) = &&&.
Note: ø@ where @ is an ampersand-structure sequence is simply @.
===== Issues =====
Since expressions in this notation is not a simply inlined string, i.e. a string possibly admitting a subscript, the concatenation of two strings in a subscript is ambiguous. Namely, \(S(2)_1\) might be either \(\&_{\& 1}\) or \(\&_{\&_1}\).
Similar to the first definition, \(y\) is undefined and unquantified.
Further, the new set of rules is again incomplete. For example, there is no rule applicable to \(\&_{\& \&_{\& \&}}\). Of course, this is not the unique example to which there is no rule applicable to.
The creator again states that the growth rate is comparable to \(\epsilon_0\) in Wainer hierarchy without a proof. However, since the notation is incomplete, the creator's statement on the growth rate does not mathematically make sense.
=== Examples ===
Since versions of the notation are ill-defined, these results are just expectations by the creator. The reader should be careful that even if the creator will update the definition and will not clarify that results are just expectations, examples without a proof might be incorrect.
2[&&1]
= 2[&&][&&]
= 2[&2][&&]
= 2[&1][&1][&&]
= 2[&0][&0][&1][&&]
= 2[&][&][&1][&&]
= 2[2][&][&1][&&]
= 2[1][1][&][&1][&&]
= 2[][][1][&][&1][&&]
= 4[][1][&][&1][&&]
= 256[1][&][&1][&&]
= ...
== Relation to another notation ==
A Japanese Googology Wiki user Nayuta Ito proved that for any non-negative integers a and b, a[b] in this notation is in fact equal to a in the (b+3)-agon in Steinhaus-Moser Notation under the assumption that these two notations are based on the same formulation of \(0^0\). This is easily proven by the mathematical induction on b:
* When b=0, both a[0] and a in the triangle are equal to a^a.
* Suppose a[k] is equal to a in the (k+3)-agon. Then, when b=k+1:
** a[k+1] = a[k][k]...[k] with a copies of [k] = a in a copies of (k+3)-agons = a in the (k+4)-agon
The last equation holds from the definition of Steinhaus-Moser Notation.
This property shows that Mega is equal to 2[2]=256[1].
== Sources ==
== See also ==
Category:Notations
Category:Functions
Category:Numbers and functions by CompactStar