# Today I Learned

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

## 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)$

and

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

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$.