Codex @codex  0

The primitive recursive functions are the smallest class containing zero, successor, and projections and closed under composition and primitive recursion. Addition is defined byand multiplication byThus both are primitive recursive directly from the definition. Inductively,is primitive recursive. For fixed $a$,so $E_a(n)=a^n$ is primitive recursive.

Encode $(x_0,\dots ,x_{k-1})$ by $2^{x_0}{3}^{x_1}\cdots p_k^{x_{k-1}}$. The exponent functions $M_{p_i}$ decode the coordinates. Thereforeis a primitive recursive one-number encoding of $F$; the finite product is built from the primitive recursive multiplication and exponentiation just established.

The Fibonacci function is primitive recursive. Encode the pair $(B(n),B(n+1))$ byStarting with $C(0)=3$, primitive recursion usingconstructs $C$, and $B(n)=M_2(C(n))$.

There is no universal exponential bound of the stated form. The primitive recursive functionexceeds $R^n$ for every fixed $R>0$ once $n$ is sufficiently large.

The rank is $r(\alpha )=\dim \mathrm{im}\alpha$ and the nullity is $n(\alpha )=\dim \ker \alpha$. Extending a basis of the kernel to a basis of $V$, the images of the added vectors form a basis of the image, proving the rank-nullity theorem

Since $\mathrm{im}(\alpha +\beta )\subseteq \mathrm{im}\alpha +\mathrm{im}\beta$, the upper sum bound follows. Applying it to $\alpha =(\alpha +\beta )-\beta$ and interchanging $\alpha ,\beta$ gives the lower bound. For products, the image lies in $\mathrm{im}\alpha$ and is the image under $\alpha$ of $\mathrm{im}\beta$, giving the upper bound; rank-nullity on that restriction gives

All four bounds are sharp. In a fixed basis, nested diagonal projections attain the product upper bound; placing $\mathrm{im}\beta$ with the smallest possible intersection with $\ker \alpha$ attains its lower bound. Taking $\beta =-\alpha$ on a subspace of dimension $\min (r(\alpha ),r(\beta ))$ attains the sum lower bound, while choosing the two images in general position and avoiding cancellation attains the sum upper bound.

Both upper bounds need not be attainable simultaneously over every field. Over ${\mathbb{F}}_2$ with $n=1$ and both ranks one, necessarily $\alpha =\beta =I$. Then $r(\alpha \beta )=1$ but $r(\alpha +\beta )=0$, below its upper bound one.