# Universal languages are primitive recursive.

First of all, this are the definitions I am working with.

Definitions:

A language $L$ is $universal$ if it is countable, has infinitely many constants, and for each $n$, $1 \leq n$ has infinitely many $n$-ary function symbols and infinitely many $n$-ary relation symbols.

A language $L$ is (primitive) recursive, if there is a (primitive) recursive arithmetisation of $L$. A recursive arithmetisation of $L$ is a one-to-one mapping $\pi$, $\pi: L \rightarrow \mathbb{N}$

{$\pi (c) | c \in L$ is a constant}

{$\pi (F) | F \in L$ is a function symbol}

{$\pi (R) | R \in L$ is a relation symbol}

{$\langle \pi(s),n\rangle | s \in L$ is a an $n$-ary function symbol or relation symbol}

I need to prove that:

1. Universal languages are primitive recursive.

2. $L$ is recursive $\Leftrightarrow$ there is a universal language $L' \supseteq L$ admitting a recursive arithmetization $\pi$ such that ${\pi(s) \ | \ s \in L}$ is recursive.

So, for the first one, if I understand things right, I need to find a primitive recursive map that arithmetises the language. I think that for the constants I can use the constant function, but I still need to find a way to also map all the function symbols and relation symbols. I think i can do something like this: instead of sending each constant to itself, i send it to 3*C, leaving space for function and relation symbols, but I have infinitely many of each arity, so... even if its countable, the cardinality of that is so huge that I am getting lost on how to handle it. I would very much appreciate any help you can give me about how to tackle this problem.

For the second one, I think that what I need to prove is that I am able to add anything that is missing on $L$ in order to make it recursive, but I am not entirely sure about how to do that in a formal level. I would like to hear your input about this problems, and also know if you have suggestions of sources where I can find more information about it. Most of what I find is about Turing machines, and I need an entirely different approach.

There's an important caveat to the definition, namely that the map $\pi$ does not need to be (primitive) recursive. (Indeed it would be pointless to require this, because nobody says that the symbols of $L$ are even numbers).
The only thing that is required is that you can find a $\pi$ which is any odd function $L\to\mathbb N$ that you can produce by free-wheeling set-theoretic methods such that the predicates defined are primitive recursive.
For example, you can choose to map the constants of to numbers of the form $3n$, the function symbols to numbers of the form $3n+1$ and the relations to numbers of the form $3n+2$, such that $n$ somehow encodes the arity of a function or relation symbol.
• You are right, I fixed the definition, I had missed a sentence while typing it, I think this solves, at least, the issue about the symbols of $L$ being numbers. What you say about $3n$, $3n+1$ and $3n+2$ is exactly what I have in mind, but I am not sure what to do with it. I understand what you say about $n$ encoding the arity, but now I need infinitely many of that specific arity, which is something I don't know how to handle. – Sara May 19 '15 at 17:45
• @Sara: For example you could encode all $k$-ary functions as $3(2j+1)2^k+1$ for $j\in\mathbb N$. Or perhaps as $3(j^2+k)+1$ where $j\ge k$. – hmakholm left over Monica May 19 '15 at 17:51