Logic MT24, Compactness theorems

Created: January 01, 2025 | Updated: May 05, 2025 | About these notes | View in context | Study these flashcards

Flashcards

Propositional logic

@State the compactness theorem for $\mathcal L _ 0$.

Suppose:

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

Then:

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

@Prove the compactness theorem for $\mathcal L _ 0$, i.e. that if:

  • $\Gamma \subseteq \text{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 $\Gamma _ 0 \subseteq \Gamma$.

First-order logic

@State the compactness theorem for first-order logic.

Suppose:

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

Then:

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

@Prove the compactness theorem for first-order logic, i.e. that if:

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

then:

  • Every finite subset $\Sigma _ 0 \subseteq _ \text{fin} \Sigma$ is satisfiable iff $\Sigma$ is satisfiable.
  • (And in fact, $\Sigma$ must be satisfiable by a countable model)

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 $\Sigma _ 0 \subseteq \Sigma$.

Examples

Suppose:

  • $\mathcal L = \lbrace +, \times, 0, 1\rbrace$ be the language of fields
  • $\mathcal Q = (\mathbb Q, +, \times, 0, 1)$

Show that there exists an $\mathcal L$-structure $\mathcal A$ such that $\mathcal A \models \text{Th}(\mathcal Q)$ but $A$ and $\mathbb Q$ are not isomorphic as fields.

Consider the collection of sentences $\Phi$:

  • $\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)$

Then $\text{Th}(\mathcal Q) \cup \phi$ is consistent as every finite subset of $\Phi$ can be satisfied by some $c$ in $\mathbb Q$, and so has a model $\mathcal A$.

In $\mathcal A$, $c$ must be non-rational but any isomorphism must map $\mathbb Q \cup \lbrace c\rbrace$ onto $\mathbb Q$, a contradiction.

@example~ @exam~

Suppose:

  • $\mathcal L = \lbrace +, \times, <, 0, 1\rbrace$ be the language of ordered fields

and recall:

  • An ordering on an ordered field $\mathbb F$ is called Archimedean if for every $x \in \mathbb F$, there is some $n \in \langle 1 \rangle _ {\mathbb F}$ with $-n < x < n$.

Show that Archimedeanity is not a first-order property.

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

\[\Sigma = T \cup \lbrace 0 < c, c < 1, 2 \cdot c < 1, 3 \cdot c< 1, \ldots\rbrace\]

Then every finite subset of $\Sigma$ is satisfiable by taking $c$ sufficiently small. Hence $\Sigma$ has a model $\mathcal M$. But $\mathcal M$ is non-Archimedean yet satisfies all the same first-order sentences as $\mathbb R$, hence there is no collection of sentences defining Archimedeanity.

Suppose:

  • $\mathcal L$ is a first-order language with no function symbols, no predicates, but infinitely many constant symbols $c _ 0, c _ 1, \ldots$
  • $\Sigma = {\lnot (c _ i = c _ j) \mid i, j \in \mathbb N, i \ne j}$

Show that there are two countable models $\mathcal A$ and $\mathcal B$ with $\mathcal A \not\cong \mathcal B$.

Let $\mathcal A$ be the Herbrand model of $\Sigma$, i.e. $A = {c _ 0, c _ 1, c _ 2, \ldots}$ 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

\[\Sigma_d := \Sigma \cup \lbrace \lnot d \doteq c_i \mid i \in \mathbb N \rbrace\]

This set of sentences is finitely satisfiable by $\mathcal A$, so by 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 $d$ by assumption.



Related posts