Logic MT24, Compactness theorems

Suppose:

• $\Gamma \subseteq \mathrm{Form}(\mathcal L _ 0)$

Then:

• $\Gamma$ is satisfiable iff every finite subset of $\Gamma$ is satisfiable.

Since consistency and satisfiability are equivalent in $\mathcal L _ 0$, this is equivalent to “$\Gamma$ is consistent iff every finite subset of $\Gamma$ is consistent”. But by finiteness of proofs, $\Gamma \vdash \chi$ and $\Gamma \vdash \lnot \chi$ iff already $\Gamma _ 0 \vdash \chi$ and $\Gamma _ 0 \vdash \lnot \chi$ for some finite $\Gamma _ 0 \subseteq _ {\mathrm{fin}} \Gamma$.

Suppose:

• $\mathcal L$ is a first-order language
• $\Sigma \subseteq \mathrm{Sent}(\mathcal L)$ is an $\mathcal L$-theory

Then:

• $\Sigma$ is satisfiable iff every finite subset $\Sigma _ 0 \subseteq _ {\mathrm{fin}} \Sigma$ is satisfiable.

Since consistency and satisfiability are equivalent in $K(\mathcal L)$, this is equivalent to “$\Sigma$ is consistent iff every finite subset of $\Sigma$ is consistent”. But by finiteness of proofs, $\Sigma \vdash \tau$ and $\Sigma \vdash \lnot \tau$ iff already $\Sigma _ 0 \vdash \tau$ and $\Sigma _ 0 \vdash \lnot \tau$ for some finite $\Sigma _ 0 \subseteq _ {\mathrm{fin}} \Sigma$.

Introduce a new constant symbol $c$ and consider the collection $\Phi$ of $\mathcal L \cup \lbrace c \rbrace$-sentences:

• $\lnot (c = 1 + \cdots + 1)$
• $\lnot (c + (1 + \cdots + 1) = 0)$
• $\lnot ((1 + \cdots + 1) \times c = (1 + \cdots + 1))$
• $\lnot ((1 + \cdots + 1) \times c + (1 + \cdots + 1) = 0)$

(one for each length of sum, so together they say that $c$ is not any of the rationals). Then $\mathrm{Th}(\mathcal Q) \cup \Phi$ is consistent, as every finite subset of $\Phi$ can be satisfied by interpreting $c$ as a suitable element of $\mathbb Q$, so by compactness (∆first-order-compactness) it has a model $\mathcal A$.

In $\mathcal A$, the element $c^{\mathcal A}$ must lie outside the prime subfield (the copy of $\mathbb Q$ sitting inside $\mathcal A$). But any field isomorphism $\mathcal A \to \mathcal Q$ must map the prime subfield of $\mathcal A$ onto all of $\mathbb Q$, and it’s injective, so there’s nowhere left for $c^{\mathcal A}$ to go, a contradiction.

Let $T$ be the set of all $\mathcal L$-sentences true in $\mathbb R$. We show that there is a model of $T$ which is non-Archimedean. Introduce a new constant $c$, let $\mathcal L' = \mathcal L \cup \lbrace c \rbrace$, and let

Every finite subset of $\Sigma$ is satisfiable in $\mathbb R$ by taking $c$ sufficiently small, so by compactness (∆first-order-compactness) $\Sigma$ has a model $\mathcal M$. But $\mathcal M$ (forgetting $c$) is non-Archimedean: we have $0 < c^{\mathcal M}$ and $n \cdot c^{\mathcal M} < 1$ for every $n$, so $(c^{\mathcal M})^{-1}$ is bigger than every $n \in \langle 1 \rangle _ {\mathcal M}$. Yet $\mathcal M$ satisfies all the same first-order sentences as $\mathbb R$, hence there is no collection of sentences defining Archimedeanity.

Let $\mathcal A$ be the Herbrand model of $\Sigma$, i.e. $A = \lbrace c _ 0, c _ 1, c _ 2, \ldots \rbrace$ with $c _ i^{\mathcal A} = c _ i$. Let $d$ be a new constant symbol and consider the set of $\mathcal L \cup \lbrace d \rbrace$-sentences

Every finite subset of $\Sigma _ d$ is satisfiable by $\mathcal A$ with $d$ interpreted as some $c _ j$ the subset doesn’t mention, so by compactness (∆first-order-compactness) $\Sigma _ d$ has a countable model $\mathcal B'$.

Let $\mathcal B$ be the model obtained from $\mathcal B'$ using the same domain but forgetting the interpretation of $d$; this is now a model over $\mathcal L$.

But then $\mathcal A \not\cong \mathcal B$, as $\mathcal B$ contains an element which is not named by a constant symbol: any potential isomorphism $f : A \to B$ has image $\lbrace c^\mathcal B _ i \mid i \in \mathbb N \rbrace$, which leaves out the element $d^{\mathcal B'}$ by construction.