1

We have the following variation of the Ackermann function: $$A(0,m) = m+1$$ $$A(n,0) = \begin{cases}1, & \text{if } n=0 \\ 2, & \text{if } n=1 \\ 0, & \text{if }n=2 \\ 1, & \text{if }n\gt 2\end{cases}$$ $$A(n+1,m+1) = A(n, A(n+1,m))$$

The question asks, "Explain why the previous equations do indeed define a function $A: \mathbb N \times \mathbb N \rightarrow \mathbb N$."

I understand how the function works - that is, I can describe what happens to an arbitrary input. But I don't fully understand what this question is asking. Am I meant to explain why a single input will never produce more than one output, and that the function is closed under the natural numbers? If so, how do I argue this without simply describing what the function is doing?

lisyarus
  • 15,517
J.R.CD
  • 57
  • It looks like the question is simply asking whether $A$ is well defined... – Riccardo Orlando Apr 29 '16 at 18:08
  • 1
    I would guess that you are expected to show that the function is defined for all valid inputs $(n,m)$ in such a way that the calculation terminates after finitely many recursive steps. A suitable induction seems to be called for (based on the lexicographical ordering of inputs). – Jyrki Lahtonen Apr 29 '16 at 18:17

1 Answers1

0

It is sufficient to prove $A(m,n)$ is well-defined through two layers of induction (for each argument).

Base case: $A(0,n)$ is well-defined for all $n$.

Induction case: Assume $A(m,n)$ is well-defined for all $n$. We will prove $A(m+1,n)$ is well-defined for all $n$.

Base case: $A(m+1,0)$ is well-defined.

Induction case: Assume $A(m+1,k)$ is well-defined for some $k$. Then $A(m+1,k+1)=A(m,A(m+1,k))$ is well-defined.

Q.E.D.

Simply Beautiful Art
  • 74,685