primitive recursive encoding
Recall that an encoding of a set $L$ of words over some alphabet^{} $\mathrm{\Sigma}$ is defined as an injective function $E:L\to \mathbb{N}$, the set of natural numbers (including $0$ here).
Finite sequences^{} over $\mathbb{N}$ can be thought of as words over the “infinite^{}” alphabet $\mathbb{N}$. So the notion of word encoding directly carries over to encoding of finite sequences of natural numbers^{}. Let ${\mathbb{N}}^{*}$ be the set of all finite sequences over $\mathbb{N}$.
Definition. Let $E$ be an encoding for ${\mathbb{N}}^{*}$. A number is called a sequence number if it is in the range of $E$. Since $E$ is injective, we say that $E(a)$ is the sequence number of the sequence $a$.
Once $E$ is fixed, we also use the notation $\u27e8{a}_{1},\mathrm{\dots},{a}_{k}\u27e9$ to mean the sequence number of the sequence ${a}_{1},\mathrm{\dots},{a}_{k}$.
Define the following operations^{} on $\mathbb{N}$ associated with a given $E$:

1.
${E}_{n}:=E{\mathbb{N}}_{n}^{*}$, the restriction^{} of $E$ to the set ${\mathbb{N}}_{n}^{*}$ of all sequences of length $n$, and ${E}_{0}$ is defined as the number $\u27e8\u27e9$.

2.
the length function: $\mathrm{lh}:\mathbb{N}\to \mathbb{N}$:
$$\mathrm{lh}(x):=\{\begin{array}{cc}z,\hfill & \text{if}{E}^{1}(x)\text{exists, and has length}z,\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$ 
3.
${(\cdot )}_{\cdot}:{\mathbb{N}}^{2}\to \mathbb{N}$, such that
$${(x)}_{y}:=\{\begin{array}{cc}z,\hfill & \text{if}{E}^{1}(x)\text{exists, has length}\ge y\text{, with}z\text{its}y\text{th number},\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$ 
4.
$*:{\mathbb{N}}^{2}\to \mathbb{N}$, such that
$$x*y:=\{\begin{array}{cc}E(ab),\hfill & \text{where}E(a)=x\text{and}E(b)=y,\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$ The notation $ab$ stands for the concatenation^{} of the sequences $a$ and $b$.

5.
$\mathrm{ext}:{\mathbb{N}}^{2}\to \mathbb{N}$, such that
$$\mathrm{ext}(x,y):=\{\begin{array}{cc}E(ay),\hfill & \text{where}E(a)=x,\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$ The notation $ay$ stands for the sequence $a$, extended by appending $y$ to the right of $a$.

6.
$\mathrm{red}:\mathbb{N}\to \mathbb{N}$, such that
$$\mathrm{red}(x):=\{\begin{array}{cc}z,\hfill & \text{where}E(a)=x\text{and}E(b)=z\text{such that}a=bc\text{and}c\in \mathbb{N},\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$ In other words, $z$ is the sequence number of the sequence obtained by removing the last (rightmost) number (if any) in the sequence whose sequence number is $x$, provided that $x$ is a sequence number.
Definition. An encoding $E$ for ${\mathbb{N}}^{*}$ is said to be primitive recursive if

•
$E({\mathbb{N}}^{*})$ is a primitive recursive set, and

•
the first three types of functions defined above are primitive recursive.
Proposition 1.
If $E$ is primitive recursive, so are the functions $\mathrm{*}\mathrm{,}\mathrm{ext}$, and $\mathrm{red}$.
Proof.
Let $\chi (x)$ be the characteristic function^{} of the predicate “$x$ is a sequence number” (via $E$). It is primitive recursive by assumption^{}.

1.
Let $n=\mathrm{lh}(x)+\mathrm{lh}(y)$. Then $x*y={E}_{n}({(x)}_{1},\mathrm{\dots},{(x)}_{\mathrm{lh}(x)},{(y)}_{1},\mathrm{\dots},{(y)}_{\mathrm{lh}(y)})\cdot \chi (x)\chi (y)$, which is primitive recursive.

2.
Let $n=\mathrm{lh}(x)+1$. Then $\mathrm{ext}(x,y)={E}_{n}({(x)}_{1},\mathrm{\dots},{(x)}_{\mathrm{lh}(x)},y)\chi (x)$, which is primitive recursive.

3.
Let $n=\mathrm{lh}(x)\dot{}1$. Then
$$\mathrm{red}(x)=\{\begin{array}{cc}{E}_{n}({(x)}_{1},\mathrm{\dots},{(x)}_{\mathrm{lh}(x)\dot{}1}),\hfill & \text{if}\mathrm{lh}(x)1\text{, and}\chi (x)=1\hfill \\ \u27e8\u27e9,\hfill & \text{if}\mathrm{lh}(x)=1\text{, and}\chi (x)=1\hfill \\ 0,\hfill & \text{otherwise},\hfill \end{array}$$ which is primitive recursive.
∎
Examples of primitive recursive encoding can be found in the parent entry (methods 2, 3, and 7).
Title  primitive recursive encoding 

Canonical name  PrimitiveRecursiveEncoding 
Date of creation  20130322 19:06:20 
Last modified on  20130322 19:06:20 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  7 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q05 
Classification  msc 68Q45 
Classification  msc 03D20 
Classification  msc 94A60 
Defines  sequence number 