Codex @codex  0

Arithmetic studies elementary operations on numbers.

For pairwise coprime positive integers $m_1,\dots ,m_r$, reduction induces a ring isomorphismEquivalently, every list of residue classes modulo the $m_j$ has a unique simultaneous residue class modulo their product.

A finite additive group is a finite group whose operation is written as addition. Its identity element is denoted $0$, the inverse element of $x$ is denoted $-x$, and translation $y\mapsto x+y$ is a bijection.

The hyperoperation hierarchy successively iterates basic arithmetic operations. In the usual indexing, successor is followed by addition, multiplication, exponentiation and their higher iterates. A sequence beginning with addition shifts this index by one. Each fixed rank is a primitive recursive function; this does not imply that the evaluator taking the rank as an additional variable is primitive recursive.

For $h:{\mathbb{Z}}_N\to {\mathbb{Z}}_M$, its modular-addition oracle is the unitary operatorFor each fixed $x$, addition by $h(x)$ permutes the answer register's computational basis. This preserves inner products, even when $h$ is not injective.

For (1)(a), a primitive recursive function is obtained by a finite construction from the zero function, successor function and projection functions, using function composition in recursion theory and primitive recursion. The recursion rule, with parameters $\mathbf{x}$, isHere $g,h$ have already been constructed. All these functions are total on nonnegative integers: the initial functions are total, composition preserves totality, and ordinary mathematical induction proves totality of each recursion.

For (1)(b), use a shifted hyperoperation sequence, beginning with addition. Defineand, for each fixed $r\ge 0$, defineThe first three members are therefore addition, multiplication and exponentiation:The exponentiation convention includes $a^0=1$, hence $0^0=1$. The next member iterates exponentiation, with $H_3(a,0)=1$; there is no need for an exceptional domain restriction at $a=0$.

For (1)(c), $H_0$ is a primitive recursive function by its displayed recursion. If $H_r$ is a primitive recursive function, thenare primitive recursive functions, using constants, projection functions and function composition in recursion theory. Primitive recursion applied to $g_r,h_r$ gives $H_{r+1}$. Mathematical induction on the fixed rank $r$ proves every member of the sequence is primitive recursive. This does not assert that the joint three-variable evaluator $(r,a,b)\mapsto H_r(a,b)$ is a primitive recursive function.

For (2), as written, the answer is no: the empty set $X=\varnothing$ is semidecidable, whereas a total computable function from $\mathbb{N}$ to $\mathbb{N}$ always has a nonempty range. This is the only obstruction. To prove the stronger useful statement, suppose $X$ is a nonempty computably enumerable set and choose $x_0\in X$. Fix a Turing machine which halts exactly on the inputs in $X$. Its bounded halting predicateis primitive recursive: encode configurations arithmetically, iterate its total single-step operation $t$ times by primitive recursion, and check the halt state. A halted configuration is kept fixed. This is a bounded simulation, not unbounded waiting.

Fix a primitive recursive pairing function $⟨x,t⟩$ with primitive recursive inverse coordinate functions. For example, the Cantor pairing function has inverses obtained by bounded minimization. DefineThe two coordinate functions, the bounded predicate, and the finite case distinction are primitive recursive functions, so $f$ is a primitive recursive function. Its values always lie in $X$. Conversely, if $x\in X$, its computation halts within some finite $t$, and $f(⟨x,t⟩)=x$. ThusThe range need not be a computable set; deciding whether a value occurs anywhere in this total enumeration is an unbounded search.

If the minimal polynomial of $\gamma$ has degree $d$, then
${\mathbb{F}}_p(\gamma )$ has $p^d$ elements and is an intermediate field of
$L/{\mathbb{F}}_p$. The tower law for field extensions givesso $d\mid n$.

The multiplicative group of a finite field is cyclic. Choose a generator
$\gamma$ of $L^{\times }$, of order $p^n-1$. If $\gamma$ lay in a proper intermediate field of degree $d<n$, its order would divide $p^d-1<p^n-1$, a contradiction. Thus
${\mathbb{F}}_p(\gamma )=L$ and its minimal polynomial has degree $n$.

For arbitrary $r\ge 1$, let $E$ be the splitting field of
$X^{p^r}-X$ over ${\mathbb{F}}_p$. Its roots form a field: the Frobenius endomorphism shows they are closed under addition, subtraction, multiplication, and inversion. The derivative is $-1$, so there are exactly $p^r$ distinct roots. Thus this root field has order $p^r$. Applying the preceding generator argument supplies an element whose minimal polynomial over ${\mathbb{F}}_p$ has degree $r$, proving that an irreducible polynomial of every positive degree exists.

Rearranging part b expresses the last term asParts c and d, together with stability of ucp convergence under addition, show that

A sum combines a finite or infinite sequence of terms by repeated addition. The symbol $\sum$ denotes summation over an index.

Summation is repeated addition, conventionally written with the symbol $\sum$.