Climb into Cantor’s Attic, where you will find infinities large and small. We aim to provide a comprehensive resource of information about all notions of mathematical infinity.
View the Project on GitHub neugierde/cantors-attic
Quick navigation
The upper attic
The middle attic
The lower attic
The parlour
The playroom
The library
The cellar
Sources
Cantor's Attic (original site)
Joel David Hamkins blog post about the Attic
Latest working snapshot at the wayback machine
The Ackermann function, expressed as \(A(a,b)\), is a function for expressing extremely large numbers.
The Ackermann function is defined as follows:
\begin{array}{l} A(0,b)=b+1 \\ A(a,0)=A(a-1,1) \\ A(a,b)=A(a-1,A(a,b-1)) \end{array}
\begin{eqnarray*} A(4,3) &=& A(3, A(4, 2)) \\ &=& A(3, A(3, A(4, 1))) \\ &=& A(3, A(3, A(3, A(4, 0)))) \\ &=& A(3, A(3, A(3, A(3, 1)))) \\ &=& A(3, A(3, A(3, A(2, A(3, 0))))) \\ &=& A(3, A(3, A(3, A(2, A(2, 1))))) \\ &=& A(3, A(3, A(3, A(2, A(1, A(2, 0)))))) \\ &=& A(3, A(3, A(3, A(2, A(1, A(1, 1)))))) \\ &=& A(3, A(3, A(3, A(2, A(1, A(0, A(1, 0))))))) \\ &=& A(3, A(3, A(3, A(2, A(1, A(0, A(0, 1))))))) \\ &=& A(3, A(3, A(3, A(2, A(1, A(0, 2)))))) \\ &=& A(3, A(3, A(3, A(2, A(1, 3))))) \\ &=& A(3, A(3, A(3, A(2, A(0, A(1, 2)))))) \\ &=& A(3, A(3, A(3, A(2, A(0, A(0, A(1, 1))))))) \\ &=& A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(1, 0)))))))) \\ &=& A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(0, 1)))))))) \\ &=& A(3, A(3, A(3, A(2, A(0, A(0, A(0, 2))))))) \\ &=& A(3, A(3, A(3, A(2, A(0, A(0, 3)))))) \\ &=& A(3, A(3, A(3, A(2, A(0, 4))))) \\ &=& A(3, A(3, A(3, A(2, 5)))) \end{eqnarray*}
We now prove that \(A(a, b) = 2 \uparrow^{a - 2} (b + 3) - 3\) for \(a>2\).
\begin{eqnarray*} A(0, b) &=& b + 1 \\ A(1, b) &=& A(0, A(1, b - 1)) \\ &=& A(1, b - 1) + 1 \\ &=& A(1, b - 2) + 2 \\ &=& \cdots \\ &=& A(1, b - b) + b \\ &=& b + 2 \\ A(2, b) &=& A(1, A(2, b - 1)) \\ &=& A(2, b - 1) + 2\times 1 \\ &=& A(2, b - 2) + 2\times 2 \\ &=& \cdots \\ &=& A(2, b - b) + 2b \\ &=& 2b + 3 \\ &=& 2(b + 3) - 3 \\ A(3, b) &=& A(2, A(3, b - 1)) \\ &=& 2(A(3, b - 1) + 3) - 3 \\ &=& 2^2(A(3, b - 2) + 3) - 3 \\ &=& \cdots \\ &=& 2^b(A(3, 0) + 3) - 3 \\ &=& 2^{b + 3} - 3 \end{eqnarray*}
Assuming that this holds true for \(a=k\), for \(a=k+1\):
\begin{eqnarray*} A(k + 1, b) &=& A(k, A(k + 1, b - 1)) \\ &=& 2 \uparrow^{k - 2} (A(k, A(k + 1, b - 2) + 3) - 3 \\ &=& \cdots \\ &=& \underbrace{2 \uparrow^{k - 2} 2 \uparrow^{k - 2} \cdots}_\text{b 2’s} \uparrow^{k - 2} (A(k + 1, 0) + 3) - 3 \\ &=& \underbrace{2 \uparrow^{k - 2} 2 \uparrow^{k - 2} \cdots \uparrow^{k - 2} 2 \uparrow^{k - 2} 2}_\text{b+3 2’s} - 3 \\ &=& 2 \uparrow^{k - 1} (b + 3) - 3 \end{eqnarray*}
QED.