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


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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Sara May 19 '15 at 17:45
  • $\begingroup$ @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$. $\endgroup$ – hmakholm left over Monica May 19 '15 at 17:51
  • $\begingroup$ Thank you, I think I got that one. Do you have any advice for me for the second one? I am still a bit confused about what approach I can take for it. $\endgroup$ – Sara May 24 '15 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.