## You are here

Homeproperties of Ackermann function

## Primary tabs

# properties of Ackermann function

In this entry, we derive some basic properties of the Ackermann function $A(x,y)$, defined by double recursion, as follows:

$A(0,y)=y+1,\quad A(x+1,0)=A(x,1),\quad A(x+1,y+1)=A(x,A(x+1,y)).$ |

These properties will be useful in proving that $A$ is not primitive recursive.

1. $A$ is total ($\operatorname{dom}(A)=\mathbb{N}^{2}$).

2. $A(1,y)=y+2$.

3. $A(2,y)=2y+3$.

4. $y<A(x,y)$.

5. $A(x,y)<A(x,y+1)$.

6. $A(x,y+1)\leq A(x+1,y)$.

7. $A(x,y)<A(x+1,y)$.

8. $A(r,A(s,y))<A(r+s+2,y)$

9. For any $r,s$, $A(r,y)+A(s,y)<A(t,y)$ for some $t$ not depending on $y$.

Most of the proofs are done by induction.

###### Proof.

1. Induct on $x$. First, $A(0,y)=y+1$ is well-defined, so $(0,y)\in\operatorname{dom}(A)$ for all $y$. Next, suppose that for a given $x$, $(x,y)\in\operatorname{dom}(A)$ for all $y$. We want to show that $(x+1,y)\in\operatorname{dom}(A)$ for all $y$. To do this, induct on $y$. First, $(x+1,0)\in\operatorname{dom}(A)$, since $A(x+1,0)=A(x,1)$ is well-defined. Next, assume that $(x+1,y)\in\operatorname{dom}(A)$. Then $A(x,A(x+1,y))=A(x+1,y+1)$ is well-defined. so $(x+1,y+1)\in\operatorname{dom}(A)$ as well.

2. Induct on $y$. First, $A(1,0)=A(0,1)=2$. Next, assume $A(1,y)=y+2$. Then $A(1,y+1)=A(0,y+2)=y+3=(y+1)+2$.

3. Induct on $y$. First, $A(2,0)=A(1,1)=1+2=3$. Next, assume $A(2,y)=2y+3$. Then $A(2,y+1)=A(1,A(2,y))=A(2,y)+2=(2y+3)+2=2(y+1)+3$.

4. Induct on $x$. First, $y<y+1=A(0,y)$. Next, assume $y<A(x,y)$, where $x>0$. Then $y+1\leq A(x,y)<A(x-1,A(x,y))=A(x,y+1)$.

5. Induct on $x$. First, $A(0,y)=y+1<y+2=A(0,y+1)$. Next, assume that $A(x,y)<A(x,y+1)$. Then $A(x+1,y)<A(x,A(x+1,y))=A(x+1,y+1)$.

6. Induct on $y$. First, $A(x,1)=A(x+1,0)$. Next, assume that $A(x,y+1)\leq A(x+1,y)$. Then $A(x,y+2)\leq A(x,A(x,y+1))\leq A(x,A(x+1,y))=A(x+1,y+1)$.

7. Induct on $x$. First, $A(0,y)=y+1<y+2=A(1,y)$. Next, assume that $A(x,y)<A(x+1,y)$. There are two cases: $y=0$. Then $A(x+1,0)=A(x,1)<A(x+1,1)$. Otherwise, $y=z+1$, so that $A(x+1,y)=A(x+1,z+1)=A(x,A(x+1,z))\leq A(x,A(x,z+1))=A(x,A(x,y))<A(x,A(x+1,y))=% A(x+1,y+1)$.

8. $A(r,A(s,y))<A(r+s,A(s,y))<A(r+s,A(r+s+1,y))=A(r+s+1,y+1)\leq A(r+s+2,y)$.

9. Let $z=\max\{r,s\}$. Then $A(r,y)+A(s,y)\leq 2A(z,y)<2A(z,y)+3=A(2,A(z,y))<A(4+z,y)$. The proof is completed by setting $t=4+z$.

∎

With respect to the recursive property of $A$, we see that $A$ is recursive, since, by Church’s Thesis, $A$ can be effectively computed (in fact, a program can be easily written to compute $A(x,y)$). We also have the following:

###### Proposition 1.

Define $A_{n}:\mathbb{N}\to\mathbb{N}$ by $A_{n}(m)=A(n,m)$. Then $A_{n}$ is primitive recursive for each $n$.

###### Proof.

$A_{0}(m)=m+1=s(m)$, so is primitive recursive. Now, assume $A_{n}$ is primitive recursive, then $A_{{n+1}}(0)=A(n+1,0)=A(n,1)=A_{n}(1)=k$, and $A_{{n+1}}(m+1)=A(n+1,m+1)=A(n,A(n+1,m))=A_{n}(A(n+1,m))=A_{n}(A_{{n+1}}(m))$, so that $A_{{n+1}}$ is defined by primitive recursion via the constant function $\operatorname{const}_{k}$, and $A_{n}$, which is primitive recursive by the induction hypothesis. Therefore $A_{{n+1}}$ is primitive recursive also. ∎

The most important fact about $A$ concerning recursiveness is that $A$ is not primitive recursive. Due to the length of its proof, it is demonstrated in this entry.

## Mathematics Subject Classification

03D75*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## error

The proof 4 $A(x,y)<A(x-1,A(x,y))$ use as assumption

^{}the property 5The proof of property 5 on $A(x+1,y)<A(x,A(x+1,))$ uses as assumption the property 7.

The proof of property 7 is wrong in the inductive step if $y>0$ you should prove that $A(x+1,y)<A(x+2,y)$ instead it prove that $A(x+1,y)<A(x+1,y+1)$.

here a valid proof http://logic.amu.edu.pl/images/c/cd/Ackermanntaylor.pdf