Otherwise, there is a $b$ such that for any $x,y$, $h(x,y)<h(a,b)$ where $a=\max\{x,y\}>1$. Let $c=\max\{a,b\}>1$. Then $h(c,b)<h(\max\{b,c\},b)=h(c,b)$, a contradiction. ∎

We simply show that $\mathcal{A}$ contains the addition, multiplication, difference, quotient, and the projection functions, and that $\mathcal{A}$ is closed under composition, bounded sum, and bounded product. And since $\mathcal{ER}$ is the smallest such set, the proof completes.

• For addition, multiplication, and difference: suppose $t=\max\{x,y\}>1$. Then $x+y\leq 2t=2f(t,0)\leq f(t,1)<f(t,2)$, and $xy\leq t^{2}=f(t,0)^{2}\leq f(t,1)<f(t,2)$. Moreover, $|x-y|\leq t=f(t,0)<f(t,1)$, and $\operatorname{quo}(x,y)\leq t=f(t,0)<f(t,1)$.

• For projection functions $p_{m}^{k}$, suppose $t=\max\{x_{1},\ldots,x_{k}\}>1$. Then $p_{m}^{k}(\boldsymbol{x})=x_{m}\leq t=f(t,0)<f(t,1)$.

• Suppose $g_{1},\ldots,g_{m}\in A$ are $n$-ary, and $h\in A$ is $m$-ary. Let $u=h(g_{1},\ldots,g_{m})$ and suppose $x=\{x_{1},\ldots,x_{n}\}>1$. Given $u(\boldsymbol{x})=h(g_{1}(\boldsymbol{x}),\ldots,g_{m}(\boldsymbol{x}))$, let $z=\max\{g_{1}(\boldsymbol{x}),\ldots,g_{m}(\boldsymbol{x})\}$. We have two cases:

  1. (a)

     $z\leq 1$. Let $y=\max\{h(y_{1},\ldots,y_{m})\mid y_{i}\in\{0,1\}\}$. Then $u(\boldsymbol{x})\leq y<f(x,y)$.

  2. (b)

     $z>1$. Then, for some $i$, $z=g_{i}(\boldsymbol{x})<f(x,s)$ for some $s$, since $g_{i}\in A$. Then $u(\boldsymbol{x})=h(g_{1}(\boldsymbol{x}),\ldots,g_{m}(\boldsymbol{x}))\leq f(z,t)$ for some $t$ since $h\in\mathcal{A}$. Now, $f(z,t)=f(g_{i}(\boldsymbol{x}),t)<f(f(x,s),t)\leq f(x,s+2t)$. As a result, $u(\boldsymbol{x})<f(x,s+2t)$.

  In either case, let $r=\max\{y,s+2t\}$. We see that $u(\boldsymbol{x})<f(x,r)$.

• For the next two parts, suppose $g\in A$ is $(n+1)$-ary. For any $\boldsymbol{x}=(x_{1},\ldots,x_{n})$, let $x=\max\{x_{1},\ldots,x_{n}\}$, and for any $y$, assume $z=\max\{x,y\}>1$. Since $g\in A$, let $t\in\mathbb{N}$ be such that $g(\boldsymbol{x},y)\leq f(z,t)$, where $z$ is as described above.

  Let $g_{s}(\boldsymbol{x},y):=\sum_{{i=0}}^{y}g(\boldsymbol{x},i)$. We break this down into cases:

  1. (a)

     $x>1$. Then $g(\boldsymbol{x},i)<f(z_{i},t)$ where $z_{i}=\max\{x,i\}>1$ for each $i$. Let $f(z_{j},t)$ be the maximum among the $f(z_{i},t)$. Then $g_{s}(\boldsymbol{x},y)\leq(y+1)f(z_{j},t)\leq(y+1)f(z,t)$, as $j\leq y$. Since $y+1\leq z+1<2z=2f(z,0)\leq f(z,1)$, we see that $g_{s}(\boldsymbol{x},y)<f(z,1)f(z,t)\leq f(z,t_{1})$, where $t_{1}=1+\max\{1,t\}$.

  2. (b)

     $x=1$. Then $y>1$. So $g_{s}(\boldsymbol{x},y)=h(\boldsymbol{x})+\sum_{{i=2}}^{y}g(\boldsymbol{x},i)$, where $h(\boldsymbol{x})=g(\boldsymbol{x},0)+g(\boldsymbol{x},1)$. Let $v=\max\{h(v_{1},\ldots,v_{n})\mid v_{i}\in\{0,1\}\}$. Then $g_{s}(\boldsymbol{x},y)\leq v+\sum_{{i=2}}^{y}g(\boldsymbol{x},i)$. As before, $g(\boldsymbol{x},i)\leq f(z_{i},t)$ for each $i\leq 2$, so pick the largest $f(z_{j},t)$ among the $f(z_{i},t)$. Then $\sum_{{i=2}}^{y}g(\boldsymbol{x},i)\leq(y-1)f(z_{j},t)\leq(y-1)f(z,t)<zf(z,t)=f(z,0)f(z,t)\leq f(z,t+1)$. Therefore, $g_{s}(\boldsymbol{x},y)<v+f(z,t+1)<f(z,v)+f(z,t+1)\leq f(z,t_{2})$, where $t_{2}=1+\max\{v,t+1\}$.

  In each case, pick $t_{3}=\max\{t_{1},t_{2}\}$, so that $g_{s}(\boldsymbol{x},y)<f(z,t_{3})$.

• Let $g_{p}(\boldsymbol{x},y):=\prod_{{i=0}}^{y}g(\boldsymbol{x},i)$. We again break down the proof into cases:

  1. (a)

     $x>1$. Then each $g(\boldsymbol{x},i)<f(z_{i},t)$ where $z_{i}=\max\{x,i\}>1$. Let $f(z_{j},t)$ be the maximum among the $f(z_{i},t)$. Then $g_{s}(\boldsymbol{x},y)\leq f(z_{j},t)^{{(y+1)}}\leq f(z,t)^{{(y+1)}}$. Since $y+1\leq z+1<2z=2f(z,0)\leq f(z,1)$, we see that $g_{s}(\boldsymbol{x},y)<f(z,t)^{{f(z,1)}}\leq f(z,t_{1})$, where $t_{1}=2+\max\{1,t\}$.

  2. (b)

     $x=1$. Then $y>1$. So $g_{p}(\boldsymbol{x},y)=h(\boldsymbol{x})\prod_{{i=2}}^{y}g(\boldsymbol{x},i)$, where $h(\boldsymbol{x})=g(\boldsymbol{x},0)g(\boldsymbol{x},1)$. Let $v=\max\{h(v_{1},\ldots,v_{n})\mid v_{i}\in\{0,1\}\}$. Then $g_{p}(\boldsymbol{x},y)\leq v\prod_{{i=2}}^{y}g(\boldsymbol{x},i)$. As before, each $g(\boldsymbol{x},i)\leq f(z_{i},t)$, so pick the largest $f(z_{j},t)$ among the $f(x_{i},t)$. Then $\prod_{{i=2}}^{y}g(\boldsymbol{x},i)\leq f(z_{j},t)^{{(y-1)}}\leq f(z,t)^{{(y-1)}}<f(z,t)^{z}=f(z,t)^{{f(z,0)}}\leq f(z,t+2)$. Therefore, $g_{p}(\boldsymbol{x},y)<vf(z,t+2)<f(z,v)f(z,t+2)\leq f(z,t_{2})$, where $t_{2}=1+\max\{v,t+2\}$.

  In each case, pick $t_{3}=\max\{t_{1},t_{2}\}$, so that $g_{p}(\boldsymbol{x},y)<f(z,t_{3})$.

As a result, $\mathcal{ER}\subseteq\mathcal{A}$. In other words, every elementary function is majorized by $f$. ∎

If it were, it would majorize itself, which is impossible. ∎