Covariant and countervariant interpretations of SEQ in AR

Question

Let a covariant interpretation of model $\mathscr{M}$ in model $\mathscr{M}'$ be defined as a couple of functions $(f,g)$, with $f$ injective, such that $$f:D\hookrightarrow\text{Seq}(\mathscr{M}')$$$$g:\text{Rel}(\mathscr{M})\to\text{Rel}(\mathscr{M}')$$ $$\text{for any }\alpha\in\text{Seq}(\mathscr{M}) , R\in\text{Rel}(\mathscr{M})\quad\alpha\in R\iff f^\ast(\alpha)\in g(R)$$where $\text{Seq}(\mathscr{M}')$ is the set of the tuples of elements of the universe $D'$ of $\mathscr{M}'$ and where $\text{Rel}(\mathscr{M})$ is the set of the relations defined in model $\mathscr{M}$, whose universe is $D$. $f^\ast$ is defined as the function such that $f$ -my book says- naturally extends to function $f^\ast:\text{Seq}(\mathscr{M})\to\text{Seq}(\mathscr{M}')$, which I would say to mean that we can get an $n$-ary function $D^n\to\text{Seq}(\mathscr{M}'),$ $(d_1,\ldots,d_n)\mapsto f(d_1)\ldots f(d_n)$ (the concatenation of $f(d_1),\ldots ,f(d_n)$) and then get $f^\ast$ by "gluing" all the $n$-ary functions obtained in such a way.

Let a countervariant interpretation of model $\mathscr{M}$ in model $\mathscr{M}'$ be defined as a couple of functions $(f,g)$, with $f$ surjective, such that $$f:D'\twoheadrightarrow\text{Seq}(\mathscr{M})$$$$g:\text{Rel}(\mathscr{M})\to\text{Rel}(\mathscr{M}')$$$$\text{for any }\alpha\in\text{Seq}(\mathscr{M}') , R\in\text{Rel}(\mathscr{M})\quad\alpha\in g(R)\iff f^\ast(\alpha)\in R$$with the same notation as above. $f^\ast$ is defined as the function such that $f$ -my book says, again- naturally extends to a function $f^\ast:\text{Seq}(\mathscr{M}')\to\text{Seq}(\mathscr{M})$.

I read -in V. Manca's Logica matematica- that both a covariant interpretation and a countervariant interpretation of the model $\text{SEQ}=(\omega^\ast,--,||,0,\lambda)$ (where $--$ represents concatenation, $||$ the length of sequences and $\lambda$ is the empty sequence) of finite sequences of natural numbers in the model $\text{AR}=(\omega,+,\cdot,0,1)$ of standard arithmetic exist but I cannot see how to explicitly express them.

How can a covariant interpretation and a countervariant interpretations of $\text{SEQ}$ in $\text{AR}$ be built? I must add that the book gives no example of covariant or countervariant interpretations and I have found nothing on the Internet. I heartily thank you for any answer!

---

Some unfruitful trials: I do know that, if we call $x(i)$ the $i$-th element of sequence $x$, then $$\forall x\in \omega^\ast\quad\exists c,d\in\mathbb{N}:(\forall i\in\{1,\ldots,|x|\}\quad\beta(a,b,i)=x(i)\land\beta(a,b,0)=|x|)$$where $\beta(a,b,i)$ -Gödel's $\beta$ function- is the remainder of the division of $a$ by $(i+1)b+1$, but I have not been able to use that fact to build the interpretations.

Answer 1

It seems to me that is a very "formal" (and convoluted) way to express the "standard" Gödel numbering technique (see also : Gödel numbering for sequences), i.e. :

using Gödel numbering to encode unique sequences of symbols into unique natural numbers (i.e. place numbers into mutually exclusive or one-to-one correspondence with the sequences).

The key-features of the Gödel numbering encoding are : "effectivity", i.e. the encoding is computable or recursive, and "invertibility" :

• given a sequence we can effectively caculate its Gödel number

• given a Gödel number, we can effectively "unpack" it to recover the lenght of the encoded sequence and its $i$-th term.

---

You can see more "traditional" Gödel numberering descriptions in :

• Joseph Shoenfield, Mathematical Logic (1967), CH.6.4 Sequnce numbers, page 115-on,

or :

• George Tourlakis, Lectures in Logic and Set Theory. Volume 1 : Mathematical Logic (2003), Ch.I.9. Arithmetic, Definability, Undefinability, and Incompletableness, page 155-on.

---

See Covariance and contravariance of functors.

---

---

In Exercise 5.6 [page 158] we have the two models : $\mathscr{M} = \mathsf{SEQ}$ and $\mathscr{M}' = \mathsf{AR}$ with domains respectively $D=\omega^\ast$ : the set of finite sequences of natural numbers and $D'=\omega$.

We are searching for a couple of functions $f,g$ such that :

$$f:\omega^\ast \to \text{Seq}(\mathsf{AR})$$$$g:\text{Rel}(\mathsf{SEQ}) \to \text{Rel}(\mathsf{AR})$$ $$\text{for any }\alpha\in\text{Seq}(\mathsf{SEQ}) , R\in\text{Rel}(\mathsf{SEQ})\quad\alpha\in R\iff f^\ast(\alpha)\in g(R)$$

where $\text{Seq}(\mathsf{AR})$ is the set of the tuples of elements of the universe $D'=\omega$, i.e. tuples of natural numbers and where $\text{Rel}(\mathsf{SEQ})$ is the set of the relations defined in $\mathsf{SEQ}$, whose universe is $D=\omega^\ast$, i.e. finite sequences of natural numbers.

The hint points at Gödel's $\beta$-function [see Exercise 4.6, page 128]; the idea, as per your comment, is to use the encoding :

$(a_0,\ldots,a_n) \to (\Pi^n_{i=0}p^{ai+1}_i)$.

If we call this mapping $\mu$, we have that it maps $s \in \omega^\ast$ into $n \in \omega$, i.e. we have : $\mu : \omega^\ast \to \omega$. Thus, for any finite sequence $s$, $\mu(s)=n$ is its Gödel number.

In the Exerxises page 127-28 are described the "operations" with elements of $\mathsf{SEQ}$; we have to verify that e.g. the relation $x \in \alpha$, defined by :

$\exists i(1 \le i \land i \le |\alpha| \land x=\alpha(i))$

can be "mapped" to a corresponding relation between numbers, and we have the $\beta$ function with the property that :

for any $n$ and any $\alpha=(a_0,\ldots,a_n)$ there are numbers $c,d$ such that : $\beta(c,d,i)=\alpha(i)$ for all $i \le n$.