Today I Learned

Some of the things I've learned every day since Oct 10, 2016

Category Archives: logic

187: Craig Interpolation Theorem

Where \Gamma is a set of first-order formulas, let \mathcal{A}_\Gamma be the set of function, relation, and constant symbols which occur in \Gamma. That is, the smallest set \mathcal{A} such that each formula of \Gamma is an \mathcal{L}_{\mathcal{A}}-formula.

Suppose that \Gamma is any set of formulas, \varphi_1, \varphi_2 are formulas, \Gamma \vdash (\varphi_1 \rightarrow \varphi_2), and that \mathcal{A}_{\{\varphi_1\}} \cap \mathcal{A}_{\{\varphi_2\}} \subseteq \mathcal{A}_\Gamma. Then the Craig Interpolation Theorem states that there is an \mathcal{L}_{\mathcal{A}_\Gamma}-formula \psi, the interpolant, such that

\Gamma \vdash (\varphi_1 \rightarrow \psi)


\Gamma \vdash (\psi \rightarrow \varphi_2).


186: Proof by Contradiction

Suppose \Gamma is a set of first-order formulas, \varphi is a first-order formula, and that \Gamma \cup \{\neg \varphi \} is inconsistent. Then \Gamma \vdash \varphi. This can be seen as a formal statement of the legitimacy of proof by contradiction.

Sketch of proof: If \Gamma itself is inconsistent, then it’s trivial that \Gamma \vdash \varphi. Otherwise if \Gamma is consistent, it’s clear that the problem with consistency is the addition of \neg \varphi to \Gamma, implying that \Gamma \vdash \varphi.

185: The Deduction Theorem

Let \Gamma be a set of first-order \mathcal{L}-formulas. Then for \mathcal{L}-formulas \varphi_1, \varphi_2,

\Gamma \cup \{\varphi_1\} \vdash \varphi_2 \Leftrightarrow \Gamma \vdash (\varphi_1 \rightarrow \varphi_2).

The implication from right to left is obvious, and the converse can be proven by induction on formulas.

179: Universal Axiomatization and Substructures

Definition universal sentence is a first-order sentence of the form \forall \bar{v} \phi (\bar{v}), where \phi has no quantifiers.

Definition We say an \mathcal{L}-theory T has a universal axiomatization if there’s a set \Gamma of universal \mathcal{L}-sentences such that \mathcal{M} \vDash T if and only if \mathcal{M} \vDash \Gamma.

With the above definitions, an \mathcal{L}-theory  T has a universal axiomatization if and only if wherever \mathcal{M} \vDash T and \mathcal{N \subseteq M} we have that \mathcal{N} \vDash T. In the words of Marker’s Model Theory, “a theory is preserved under substructure if and only if it has a universal axiomatization.”

177: Elementary Embeddings, Elementary Substructures

In logic and model theory, an embedding \gamma : \mathcal{M} \rightarrow \mathcal{N} between \mathcal{L}-structures \mathcal{M, N} is called an elementary embedding if

\mathcal{M} \vDash \phi(a_1, \dots, a_n) \Leftrightarrow \mathcal{N} \vDash \phi(\gamma(a_1), \dots, \gamma(a_n))

for any \mathcal{L}-sentence \phi and a_1, \dots, a_n \in M. A substructure \mathcal{M} \subseteq \mathcal{N} is called an elementary substructure, denoted \mathcal{M} \preceq \mathcal{N}, if the inclusion map is an elementary embedding.

175: Tarski’s Theorem

In first-order logic, Tarski’s Theorem states that where \mathcal{M, N} are structures and \mathcal{M} \subseteq \mathcal{N}, the following are equivalent:

  1. \mathcal{M} \preceq \mathcal{N}
  2. For all Y \subseteq N definable over M, if Y \neq \varnothing then Y \cap M \neq \varnothing.


174: Decidability of Recursive, Complete, Satisfiable Theories

It’s pretty much in the title. If T is an \mathcal{L}-theory which is recursive, complete, and satisfiable, then T is decidable. That is, there’s an algorithm which takes an \mathcal{L}-sentence \phi and outputs whether or not T \vDash \phi.

(T being recursive means that there’s an algorithm which similarly takes \phi as input but outputs whether \phi \in T.)

173: Vaught’s Test

In model theory, Vaught’s Test (also known as the Łoś–Vaught test) determines whether certain \mathcal{L}-theories T are complete. It states that if T is satisfiable, has no finite models, and is \kappa-categorical for some \kappa \geq |\mathcal{L}|, then T is complete.

Proof outline Assume T isn’t complete. Then there’s a sentence \phi such that T \nvDash \phi, T \nvDash \neg \phi, meaning T \cup \{\phi\}, T \cup \{\neg \phi \} are satisfiable, meaning both have infinite models (since T has no finite models), so by [172] we can find models \mathcal{M}, \mathcal{N} of cardinality \kappa which respectively satisfy these theories. But since \mathcal{M}, \mathcal{N} disagree on \phi, they are not elementarily equivalent and hence not isomorphic, contradicting the assumption that T is \kappa-categorical. Thus T must be complete.

172: Infinite Models of L-Theories (Variation of Lowenheim-Skolem)

Suppose \mathcal{L} is a first-order language and T is an \mathcal{L}-theory with an infinite model. Then for every infinite cardinal \kappa \geq |\mathcal{L}|, T has a model of cardinality \kappa.

This result — a variation of the Löwenheim–Skolem theorem — implies that theories with infinite models can’t have unique models up to isomorphism.

169: Finiteness of Logical Implication

Suppose T is an \mathcal{L}-theory and T \vDash \phi. Then \Delta \vDash \phi for some finite \Delta \subseteq T.

Proof Let \Delta \subseteq T be finite and suppose \Delta \nvDash \phi. Then \Delta \cup \{\neg \phi\} is satisfiable, so T \cup \{ \neg \phi \} is finitely satisfiable and by the compactness theorem T \nvDash \phi.