Notes - Logic MT24, Compactness theorems

Created: January 01, 2025
Updated: January 26, 2025

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



Related posts