Let $T$ be an effectively generated (recursively enumerable) theory written in a first order language that has infinitely many extra-logical primitives. 


Is it always the case that there is a theory $T^\*$ that is:


* effectively generated
* bi-interpretable with $T$
* written in a first order language that has finitely many extra-logical primitives?



Can we re-write every effective first order theory using finitely many primitives?
The theory of the (full) random hypergraph is a counterexample. (Full meaning we are allowing any arity.)


The language consists of a relation symbol $E\_n$ for each $n \geq 1$ (sometimes people start at $2$ but it doesn't really matter). For each $n$, $E\_n$ is an $n$-ary relation symbol. The structure is a hypergraph, meaning that $E\_n(\bar{a})$ can only hold if the tuple $\bar{a}$ is pairwise distinct and if $E\_n(\bar{a})$ holds then if $\bar{b}$ is any permutation of the tuple $\bar{a}$, then $E\_n(\bar{b})$ holds as well.


The random hypergraph is easiest to describe in terms of random generation. Let the elements be labeled $a\_n$. We decide the edge relations randomly. For each finite set $A \subset \omega$, with $A$ enumerated by the tuple $\bar{a}=a\_{n\_0}a\_{n\_1}\dots a\_{n\_{|A|-1}}$, we flip a fair and independent coin to decide whether $E\_{|A|}(\bar{a})$ holds or not. Any two hypergraphs constructed this way are isomorphic with probability $1$. The theory in question is the theory of this almost sure structure.


The random hypergraph can also be described as the Fraïssé limit of the class of finite hypergraphs.


The theory of the random hypergraph is relatively straightforward to axiomatize. The axioms are clearly c.e., so, since the theory is complete, it is decidable.


* For each $n$, we have $\forall \bar{x} E\_n(\bar{x})\rightarrow \bigwedge\_{i<j<n} x\_i \neq x\_j$.
* For each $n$ and each permutation $\sigma$ of $\{0,\dots,n-1\}$, we have $\forall \bar{x} E\_n(\bar{x}) \leftrightarrow E\_n(x\_{\sigma(0)}x\_{\sigma(1)}\dots x\_{\sigma(n-1)})$.
* For each $n$ and each $Z \subseteq \mathcal{P}(\{0,\dots,n-1\})$, we have $\forall \bar{x} \exists y \bigwedge\_{W \subseteq \{0,\dots,n-1\}} \pm\_{W \in Z} E\_{|W|+1}(\bar{x}\_W,y)$, where $\pm\_{W \in Z}$ means the empty string if $W \in Z$ and $\neg$ if $W \notin Z$, and $\bar{x}\_W$ is the $|W|$-tuple consisting of $x\_i$ for each $i\in W$ in ascending order.


The first two schema are just the definition of a hypergraph. The last one is obviously more difficult to parse. What it's saying is that given any $n$-tuple and any possible way of relating the elements of that $n$-tuple to a new element in a hypergraph, there is an element that relates in that way to that $n$-tuple.


I don't know what the best way to explicitly prove that this is a complete theory is. It is $\omega$-categorical (since it's a Fraïssé limit). It also has quantifier elimination.


The way to show that it is not bi-interpretable with any theory in a finite language is to show that it is not inter-definable with any finite reduct of itself. This is actually really easy. None of the relations $E\_n$ is definable in terms of the others and you can prove this by showing that for any model $\mathfrak{M}$ of this theory, if you take some $n$ and invert the edge relation $E\_n$ on all $n$-tuples you get another model of this theory. This alone shows that $E\_n$ is not definable in terms of $E\_m$ for $m\neq n$.




---


You actually don't even need arbitrarily large arities. A much simpler example (although in some sense less nice because it isn't $\omega$-categorical) is this theory that doesn't have a standard name but frequently occurs as an example in model theory textbooks. The language is just a countable sequence of unary predicates, $P\_n$. The theory just consists of the axioms: For each $\sigma \in 2^{<\omega}$, you have an axiom saying that $\exists x \bigwedge\_{i<|\sigma|} \pm\_{\sigma(i)}P\_i(x)$, where $\pm\_{\sigma(i)}$ is the empty string if $\sigma(i) = 0$ and $\neg$ if $\sigma(i)=1$.


You can show that this theory is complete by showing that each finite reduct of it is $\omega$-categorical. It also has quantifier elimination. You can show that it's not inter-definable with a finite reduct of itself by basically the same argument as with the random hypergraph.


