Robinson's joint consistency theorem

Template:Short description Robinson's joint consistency theorem is an important theorem of mathematical logic. It is related to Craig interpolation and Beth definability.

The classical formulation of Robinson's joint consistency theorem is as follows:

Let $T_1$ and $T_2$ be first-order theories. If $T_1$ and $T_2$ are consistent and the intersection $T_1\cap T_2$ is complete (in the common language of $T_1$ and $T_2$), then the union $T_1\cup T_2$ is consistent. A theory $T$ is called complete if it decides every formula, meaning that for every sentence $\phi ,$ the theory contains the sentence or its negation but not both (that is, either $T⊢\phi$ or $T⊢\mathrm{\neg }\phi$).

Since the completeness assumption is quite hard to fulfill, there is a variant of the theorem:

Let $T_1$ and $T_2$ be first-order theories. If $T_1$ and $T_2$ are consistent and if there is no formula $\phi$ in the common language of $T_1$ and $T_2$ such that $T_1⊢\phi$ and $T_2⊢\mathrm{\neg }\phi ,$ then the union $T_1\cup T_2$ is consistent.

Proof

For a first-order language $L$ and a set $S$, let $L_S$ denote the language obtained from $L$ by adding 0-ary operations bijectively corresponding to the set $S$. For a first-order language $L$, an $L$-structure $M$ and a subset $S\subseteq M$, let $M_S$ denote the $L_S$-structure obtained from $M$ by interpreting each 0-ary operation $s\in S$ as $s$ itself. For a first-order language $L$, its expansion $L^{\prime }$ and an $L^{\prime }$-structure $M$, let $M\upharpoonright L$ denote the reduct of $M$ in $L$.

Let $L$ be a first-order language and $L_1$ and $L_2$ its expansions such that $L_1\cap L_2=L$. Let $T_1$ be a consistent theory in $L_1$ and $T_2$ a consistent theory in $L_2$. Suppose that $T_1\cap T_2$ is a complete theory in $L$. We shall show that $T_1\cup T_2$ is a consistent theory.

Using the compactness theorem, it is not hard to show that, for every $L_1$-structure $M$ and an $L_2$-structure $N$, if $M\upharpoonright L$ is elementarily equivalent to $N\upharpoonright L$, then the theory

$\mathrm{Th}(M_M)\cup \mathrm{Th}((N\upharpoonright L{)}_N)$

is satisfiable.

For an $L_1$-structure $M$ and an $L_2$-structure $N$, if $M\upharpoonright L$ is elementarily equivalent to $N\upharpoonright L$, then for some $L_1$-structure $M^{\prime }$, there exist an $L_1$-elementary embedding $M\hookrightarrow M^{\prime }$ and an $L$-elementary embedding $N\upharpoonright L\hookrightarrow M^{\prime }\upharpoonright L$. Indeed, take an $(L_1{)}_{M,N}$-model

$M^{″}\models \mathrm{Th}(M_M)\cup \mathrm{Th}((N\upharpoonright L{)}_N)$

and put $M^{\prime }=M^{″}\upharpoonright L_1$.

Now take a model $M_0\models T_1$ and a model $N_0\models T_2$. Since $T_1\cap T_2$ is an $L$-complete theory, we have $T_1\cap T_2=\mathrm{Th}(M_0\upharpoonright L)=\mathrm{Th}(N_0\upharpoonright L)$. Therefore, there exist an $L_2$-structure $N_1$, an $L_2$-elementary embedding $N_0\hookrightarrow N_1$ and an $L$-elementary embedding $M_0\upharpoonright L\hookrightarrow N_1\upharpoonright L$. Again, since $(L_1{)}_{M_0}\cap (L_2{)}_{M_0}=L_{M_0}$ and $(M_0\upharpoonright L{)}_{M_0}$ is elementarily equivalent to $(N_1\upharpoonright L{)}_{M_0}$, there exist an $(L_1{)}_{M_0}$-structure $(M_1{)}_{M_0}$, $(L_1{)}_{M_0}$-elementary embedding $(M_0{)}_{M_0}\hookrightarrow (M_1{)}_{M_0}$ and an $L_{M_0}$-elementary embedding $(N_1\upharpoonright L{)}_{M_0}\hookrightarrow (M_1\upharpoonright L{)}_{M_0}$. In particular, there exist an $L_2$-structure $M_1$, an $L_1$-elementary embedding $M_0\hookrightarrow M_1$ and an $L$-elementary embedding $N_1\upharpoonright L\hookrightarrow M_1\upharpoonright L$.

By induction, there exist $L_1$-structures $M_0,M_1,\dots$, $L_2$-structures $N_0,N_1,\dots$ and elementary embeddings

$M_i\hookrightarrow M_{i+1}$

$N_i\hookrightarrow N_{i+1}$

$M_i\upharpoonright L\hookrightarrow N_{i+1}\upharpoonright L$

$N_{i+1}\upharpoonright L\hookrightarrow M_{i+1}\upharpoonright L$

which make the following diagram commute.

$\begin{array}{ccccccc}{M}_0& \to & M_1& \to & M_2& \to & \cdots \\ & \searrow & \uparrow & \searrow & \uparrow & \searrow & \cdots \\ N_0& \to & N_1& \to & N_2& \to & \cdots \end{array}$

(In the above diagram, the horizontal arrows are elementary embeddings in $L_1$ or $L_2$, and the vertical and diagonal arrows are elementary embeddings in $L$.) Finally, the colimit of the above diagram is easily seen to be a model of $T_1\cup T_2$.

See also

• Template:Annotated link

References

• Template:Cite book
• Robinson, Abraham, 'A result on consistency and its application to the theory of definition', Proc. Royal Academy of Sciences, Amsterdam, series A, vol 59, pp 47-58.

Template:Logic-stub Template:Mathlogic-stub