# cantors-attic

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

# Ackermann function

The Ackermann function, expressed as $$A(a,b)$$, is a function for expressing extremely large numbers.

## Defination

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}

## Example

\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*}

## Explicit formula

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.