Robinson's joint consistency theorem

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 {\displaystyle T_{1}} and T 2 {\displaystyle T_{2}} be first-order theories. If T 1 {\displaystyle T_{1}} and T 2 {\displaystyle T_{2}} are consistent and the intersection T 1 ∩ T 2 {\displaystyle T_{1}\cap T_{2}} is complete (in the common language of T 1 {\displaystyle T_{1}} and T 2 {\displaystyle T_{2}} ), then the union T 1 ∪ T 2 {\displaystyle T_{1}\cup T_{2}} is consistent. A theory T {\displaystyle T} is called complete if it decides every formula, meaning that for every sentence φ , {\displaystyle \varphi ,} the theory contains the sentence or its negation but not both (that is, either T ⊢ φ {\displaystyle T\vdash \varphi } or T ⊢ ¬ φ {\displaystyle T\vdash \neg \varphi } ). Since the completeness assumption is quite hard to fulfill, there is a variant of the theorem: Let T 1 {\displaystyle T_{1}} and T 2 {\displaystyle T_{2}} be first-order theories. If T 1 {\displaystyle T_{1}} and T 2 {\displaystyle T_{2}} are consistent and if there is no formula φ {\displaystyle \varphi } in the common language of T 1 {\displaystyle T_{1}} and T 2 {\displaystyle T_{2}} such that T 1 ⊢ φ {\displaystyle T_{1}\vdash \varphi } and T 2 ⊢ ¬ φ , {\displaystyle T_{2}\vdash \neg \varphi ,} then the union T 1 ∪ T 2 {\displaystyle T_{1}\cup T_{2}} is consistent.

Proof For a first-order language L {\displaystyle L} and a set S {\displaystyle S} , let L S {\displaystyle L_{S}} denote the language obtained from L {\displaystyle L} by adding 0-ary operations bijectively corresponding to the set S {\displaystyle S} . For a first-order language L {\displaystyle L} , an L {\displaystyle L} -structure M {\displaystyle M} and a subset S ⊆ M {\displaystyle S\subseteq M} , let M S {\displaystyle M_{S}} denote the L S {\displaystyle L_{S}} -structure obtained from M {\displaystyle M} by interpreting each 0-ary operation s ∈ S {\displaystyle s\in S} as s {\displaystyle s} itself. For a first-order language L {\displaystyle L} , its expansion L ′ {\displaystyle L'} and an L ′ {\displaystyle L'} -structure M {\displaystyle M} , let M ↾ L {\displaystyle M\upharpoonright L} denote the reduct of M {\displaystyle M} in L {\displaystyle L} . Let L {\displaystyle L} be a first-order language and L 1 {\displaystyle L_{1}} and L 2 {\displaystyle L_{2}} its expansions such that L 1 ∩ L 2 = L {\displaystyle L_{1}\cap L_{2}=L} . Let T 1 {\displaystyle T_{1}} be a consistent theory in L 1 {\displaystyle L_{1}} and T 2 {\displaystyle T_{2}} a consistent theory in L 2 {\displaystyle L_{2}} . Suppose that T 1 ∩ T 2 {\displaystyle T_{1}\cap T_{2}} is a complete theory in L {\displaystyle L} . We shall show that T 1 ∪ T 2 {\displaystyle T_{1}\cup T_{2}} is a consistent theory. Using the compactness theorem, it is not hard to show that, for every L 1 {\displaystyle L_{1}} -structure M {\displaystyle M} and an L 2 {\displaystyle L_{2}} -structure N {\displaystyle N} , if M ↾ L {\displaystyle M\upharpoonright L} is elementarily equivalent to N ↾ L {\displaystyle N\upharpoonright L} , then the theory

Th ⁡ ( M M ) ∪ Th ⁡ ( ( N ↾ L ) N ) {\displaystyle \operatorname {Th} (M_{M})\cup \operatorname {Th} ((N\upharpoonright L)_{N})}

is satisfiable. For an L 1 {\displaystyle L_{1}} -structure M {\displaystyle M} and an L 2 {\displaystyle L_{2}} -structure N {\displaystyle N} , if M ↾ L {\displaystyle M\upharpoonright L} is elementarily equivalent to N ↾ L {\displaystyle N\upharpoonright L} , then for some L 1 {\displaystyle L_{1}} -structure M ′ {\displaystyle M'} , there exist an L 1 {\displaystyle L_{1}} -elementary embedding M ↪ M ′ {\displaystyle M\hookrightarrow M'} and an L {\displaystyle L} -elementary embedding N ↾ L ↪ M ′ ↾ L {\displaystyle N\upharpoonright L\hookrightarrow M'\upharpoonright L} . Indeed, take an ( L 1 ) M , N {\displaystyle (L_{1})_{M,N}} -model

M ″ ⊨ Th ⁡ ( M M ) ∪ Th ⁡ ( ( N ↾ L ) N ) {\displaystyle M''\models \operatorname {Th} (M_{M})\cup \operatorname {Th} ((N\upharpoonright L)_{N})}

and put M ′ = M ″ ↾ L 1 {\displaystyle M'=M''\upharpoonright L_{1}} . Now take a model M 0 ⊨ T 1 {\displaystyle M_{0}\models T_{1}} and a model N 0 ⊨ T 2 {\displaystyle N_{0}\models T_{2}} . Since T 1 ∩ T 2 {\displaystyle T_{1}\cap T_{2}} is an L {\displaystyle L} -complete theory, we have T 1 ∩ T 2 = Th ⁡ ( M 0 ↾ L ) = Th ⁡ ( N 0 ↾ L ) {\displaystyle T_{1}\cap T_{2}=\operatorname {Th} (M_{0}\upharpoonright L)=\operatorname {Th} (N_{0}\upharpoonright L)} . Therefore, there exist an L 2 {\displaystyle L_{2}} -structure N 1 {\displaystyle N_{1}} , an L 2 {\displaystyle L_{2}} -elementary embedding N 0 ↪ N 1 {\displaystyle N_{0}\hookrightarrow N_{1}} and an L {\displaystyle L} -elementary embedding M 0 ↾ L ↪ N 1 ↾ L {\displaystyle M_{0}\upharpoonright L\hookrightarrow N_{1}\upharpoonright L} . Again, since ( L 1 ) M 0 ∩ ( L 2 ) M 0 = L M 0 {\displaystyle (L_{1})_{M_{0}}\cap (L_{2})_{M_{0}}=L_{M_{0}}} and ( M 0 ↾ L ) M 0 {\displaystyle (M_{0}\upharpoonright L)_{M_{0}}} is elementarily equivalent to ( N 1 ↾ L ) M 0 {\displaystyle (N_{1}\upharpoonright L)_{M_{0}}} , there exist an ( L 1 ) M 0 {\displaystyle (L_{1})_{M_{0}}} -structure ( M 1 ) M 0 {\displaystyle (M_{1})_{M_{0}}} , ( L 1 ) M 0 {\displaystyle (L_{1})_{M_{0}}} -elementary embedding ( M 0 ) M 0 ↪ ( M 1 ) M 0 {\displaystyle (M_{0})_{M_{0}}\hookrightarrow (M_{1})_{M_{0}}} and an L M 0 {\displaystyle L_{M_{0}}} -elementary embedding ( N 1 ↾ L ) M 0 ↪ ( M 1 ↾ L ) M 0 {\displaystyle (N_{1}\upharpoonright L)_{M_{0}}\hookrightarrow (M_{1}\upharpoonright L)_{M_{0}}} . In particular, there exist an L 2 {\displaystyle L_{2}} -structure M 1 {\displaystyle M_{1}} , an L 1 {\displaystyle L_{1}} -elementary embedding M 0 ↪ M 1 {\displaystyle M_{0}\hookrightarrow M_{1}} and an L {\displaystyle L} -elementary embedding N 1 ↾ L ↪ M 1 ↾ L {\displaystyle N_{1}\upharpoonright L\hookrightarrow M_{1}\upharpoonright L} . By induction, there exist L 1 {\displaystyle L_{1}} -structures M 0 , M 1 , … {\displaystyle M_{0},M_{1},\dots } , L 2 {\displaystyle L_{2}} -structures N 0 , N 1 , … {\displaystyle N_{0},N_{1},\dots } and elementary embeddings

M i ↪ M i + 1 {\displaystyle M_{i}\hookrightarrow M_{i+1}}

N i ↪ N i + 1 {\displaystyle N_{i}\hookrightarrow N_{i+1}}

M i ↾ L ↪ N i + 1 ↾ L {\displaystyle M_{i}\upharpoonright L\hookrightarrow N_{i+1}\upharpoonright L}

N i + 1 ↾ L ↪ M i + 1 ↾ L {\displaystyle N_{i+1}\upharpoonright L\hookrightarrow M_{i+1}\upharpoonright L}

which make the following diagram commute.

M 0 → M 1 → M 2 → ⋯ ↘ ↑ ↘ ↑ ↘ ⋯ N 0 → N 1 → N 2 → ⋯ {\displaystyle {\begin{matrix}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{matrix}}}

(In the above diagram, the horizontal arrows are elementary embeddings in L 1 {\displaystyle L_{1}} or L 2 {\displaystyle L_{2}} , and the vertical and diagonal arrows are elementary embeddings in L {\displaystyle L} .) Finally, the colimit of the above diagram is easily seen to be a model of T 1 ∪ T 2 {\displaystyle T_{1}\cup T_{2}} .

Tags