Is Ackermann's Function Bijective?

Question

I have been trying to understand the more rigorous side of mathematics and especially functions, and I came across Ackermann's Function recently. I was wondering if A(x,y) is bijective among the natural numbers for any pair (x,y). If it isn't, is it injective or surjective? Any proofs would be greatly appreciated :)

Looking at this wikipedia page, it seems $A(0,y) = y+1$ for $y \in \mathbb{W}$ is bijective with $\mathbb{N}$. So $A(x,y)$ for general $(x,y)$ is surjective on $\mathbb{N}$. But since $A(x,y)$ maps to natural numbers for $x>0$ as well, $A(x,y)$ is not injective. So not bijective. I'm writing this as a comment since this is the first I'm reading of the function, so could very well be mistaken. https://en.wikipedia.org/wiki/Ackermann_function — Tony Mathew, Jul 20 '23 at 06:42
Following Tony's comment, it would be useful to state in the question whether you include $0$ in your "natural numbers" — leslie townes, Jul 20 '23 at 06:46
Also state what you mean by "bijective" for a function of two variables. — GEdgar, Jul 20 '23 at 07:13

Henrik supports the community · Answer 1 · 2023-07-20T08:22:14.463

1

According to wikipedia's table of values: $A(1,3)=5=A(2,1)$.

That disproves injectivity.

For surjectivity just convince yourself that $1$ can't be reached ($2$ can't be either). (As $A(1,n)=n+2$ the function is surjective onto $\mathbb N\setminus\{1,2\}$).

edited Jul 20 '23 at 08:22

answered Jul 20 '23 at 08:16

Henrik supports the community

6,831

Is Ackermann's Function Bijective?

1 Answers1