Logic and Proof MT24, Compactness theorems

Created: October 31, 2024 | Updated: June 16, 2025 | About these notes | View in context | Study these flashcards

Flashcards

Propositional logic

@Define a partial assignment.

A function

\[v : D \to \\{0, 1\\}\]

where $D$ is either the infinite set $\{p _ 1, p _ 2, \ldots\}$ or a finite initial segment $\{p _ 1, \ldots, p _ n\}$.

Suppose:

  • $v$, $v’$ are partial assignments

@Define what it means for $v’$ to extend $v$.
\[\text{dom}(v) \subseteq \text{dom}(v')\]

and

\[v[p_i] = v'[p_i]\]

for all $p _ i \in \text{dom}(v)$.

@State the compactness theorem.

Suppose:

  • $S$ is a set of formulas (possibly infinite)

Then:

  • $S$ is satisfiable if and only if every finite subset of $S$ is satisfiable

@Prove the compactness theorem, i.e. that if:

  • $S$ is a set of formulas

then:

  • $S$ is satisfiable if and only if every finite subset of $S$ is satisfiable.

Overall idea: The only tricky direction is finding a satisfying assignment for all of $F$ given that every finite subset is satisfiable. First you show that for every $n$, there is a satisfying assignment for all formulas on propositional variables $p _ 1, \ldots, p _ n$. Then you show that you can build up a sequence of assignments $v _ 0, v _ 1, \ldots, v _ n$ where each assignment agrees with all the previous ones. Then you define a “global” assignment $v^\ast$ by $v^\ast(p _ n) = v _ n(p _ n)$.

Forward direction: If $S$ is satisfiable then every finite subset has to be satisfiable.

Backward direction: Let $S$ be a set of formulas such that every finite subset of $S$ is satisfiable.

Say a partial assignment $v$ is “good” if it satisfies any formula $F \in S$ that only mentions propositional variables in the domain of $v$.

Note that for each $n \in \mathbb N$, there is a good partial assignment with formulas that mention only propositional variables $p _ 1, p _ 2, \ldots, p _ n$.

To see this, consider a subset $S’ \subseteq S$ that only mentions formulas on propositional variables $p _ 1, \ldots, p _ n$. $S’$ might be infinite, but it can only contain finitely many formulas up to logical equivalence. Since all finite subsets of $S$ are satisfiable, it follows $S’$ is satisfiable by a partial assignment $v$, and by construction this assignment is good.

Now we construct a sequence of good partial assignments $v _ 0, v _ 1, \ldots$ with $\text{dom}(v _ n) = \{p _ 1, \ldots, p _ n\}$ where $v _ {n+1}$ extends $v _ n$ for each $n$ and maintain the invariant that there are infinitely many good partial assignments that extend $v _ n$.

Take $v _ 0$ to be the assignment with an empty domain. Since there is a good assignment with domain $\{p _ 1, \ldots, p _ n\}$ for every $n$, there are infinitely many good assignments that extend $v _ 0$. So the inductive hypothesis is satisfied.

Now suppose we have constructed assignments $v _ 0, \ldots, v _ n$ all satisfying the invariant. Consider the two assignments extending $v _ n$ given by $v _ n^0, v _ n^1$ that extend $v _ n$ by either setting $p _ {n+1}$ to $0$ or $1$. Since any proper extension of $v _ n$ is an extension of either $v _ n^0$ or $v _ n^1$, it follows that at least one of them has infinitely many good extensions. Let $v _ {n+1}$ be $v _ n^0$ or $v _ n^1$ depending on which satisfies this property, and therefore the inductive hypothesis is satisfied.

Now define a total assignment $v[p _ n] := v _ n[p _ n]$ for each $n \in \mathbb N$. Then $v$ satisfies all formulas in $S$, since for any formula in $S$ that contains $n$ propositional variables $\{p _ 1, \ldots, p _ n\}$, $v _ n$ satisfies $F$. Since $v$ extends $v _ n$, it follows $v$ satisfies $F$ also.

Alternative proof using completeness of resolution:

Here is an alternative shorter proof (although it relies on the result that resolution is complete, which sweeps a lot of complexity under the rug).

  • Forward direction: If $S$ is satisfiable then every finite subset has to be satisfiable.
  • Backward direction: Suppose $S$ is unsatisfiable. Then by the completeness of resolution, there is a resolution refutation of $S$. But this refutation must only mention a finite number of formulas of $S$, and so there must be an unsatisfiable subset of $S$.
Applications

Suppose $F _ 1$ and $F _ 2$ are two sets of formulas such that for all assignments $\mathcal A$, $\mathcal A \models F _ 1$ implies $\mathcal A \not\models F _ 2$.

Use the compactness theorem to show that there exists a formula $G$ such that $F _ 1 \models G$ and $F _ 2 \models \lnot G$.

We know $F = F _ 1 \cup F _ 2$ is unsatisfiable, so by the compactness theorem there is a finite set $S \subseteq F$ such that $S$ is unsatisfiable.

Let $G$ be the conjunction of the formulas in $S \cap F _ 1$.

If $\mathcal A \models F _ 1$, then $\mathcal A \models F _ 1 \cap S$ and so $\mathcal A \models G$.

If $\mathcal A \models F _ 2$, then $\mathcal A \models F _ 2 \cap G$. Suppose also that $\mathcal A \models G$, then as $S = (F _ 1 \cap S) \cup (F _ 2 \cap S)$, it follows $\mathcal A \models S$, a contradiction to $S$ being unsatisfiable.

@exam~ @example~

Suppose:

  • $G = (V, E)$ is an undirected, potentially infinite graph
  • $H = (W, F)$ is an undirected but finite graph

Say that $G$ is homomorphic to $H$ if there is some function $h : V \to W$ such that for all $(v, w) \in E$, $(f(v), f(w)) \in F$.

Use the compactness theorem to show that if every finite subgraph $G’$ is homomorphic to $H$, then $G$ is homomorphic to $H$.

For each $v \in V$ and $w \in W$, introduce a propositional variable $f _ {v, w}$ which an assignment should set to true iff $h(v) = w$.

For each vertex $v$, introduce the formula $F _ v$ which guarantees that each $v$ has precisely one image:

\[F_v := \left( \bigvee_{w \in W} p_{v, w} \right) \land \left( \bigwedge_{w \ne w' \in W} \lnot (p_{v, w} \land p_{v, w'})\right)\]

For each edge $(v, v’) \in E$, introduce the formula $G _ {v, v’}$ which guarantees that the homomorphisms are met for that edge:

\[G_{v, v'} := \bigwedge_{w, w' \in F} (p_{v, w} \land p_{v', w'}) \to [ [ (w, w') \in F ] ]\]

where $[ [ (w, w’) \in F ] ]$ is $1$ iff $(w, w’) \in F$.

Let $S = \lbrace F _ v \mid v \in V\rbrace \cup \lbrace G _ {v, v’} \mid (v, v’) \in E \rbrace$. Then $S$ is satisfiable iff there is a homomorphism $h : V \to W$; this follows from the compactness theorem.

@exam~ @example~

First-order logic

@State the compactness theorem for first-order logic.

Suppose:

  • $\sigma$ is a countable signature
  • $\pmb S$ is a set of $\sigma$-formulas

Then:

  • Every finite subset of $\pmb S$ has a model iff $\pmb S$ has a countable model.

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

  • $\sigma$ is a countable signature
  • $\pmb S$ is a set of $\sigma$-formulas

then:

  • Every finite subset of $\pmb S$ has a model iff $\pmb S$ has a countable model.

Clearly if $\pmb S$ has a countable model, then every finite subset of $\pmb S$ has a model.

For the other direction, by replacing the free variables in the formulas in $\pmb S$ by constant symbols, we may assume without loss of generality that $\pmb S$ consists entirely of sentences.

For each sentence $F \in \pmb S$, let $F’$ be its skolemization, and write $\pmb S’ := \{F’ : F \in \pmb S\}$. Then every finite subset of $\pmb S’$ is satisfiable.

It follows that each finite subset of

\[\bigcup_{F' \in \pmb S'} E(F')\]

is also satisfiable by Herbrand’s theorem (given a finite subset of this set, pick the satisfying assignment that works for all the sentences that the Herbrand expansion comes from).

But by the compactness theorem for propositional logic, we have that $\bigcup _ {F’ \in \pmb S’} E(F’)$ is satisfiable. Therefore $\pmb S’$ has a (countable) Herbrand model, and we are done.

Alternative proof using completeness of resolution:

Here is an alternative shorter proof (although it relies on the result that resolution is complete, which sweeps a lot of complexity under the rug).

  • Forward direction: If $S$ is satisfiable then every finite subset has to be satisfiable.
  • Backward direction: Suppose $S$ is unsatisfiable. Then by the completeness of resolution, there is a resolution refutation of $S$. But this refutation must only mention a finite number of formulas of $S$, and so there must be an unsatisfiable subset of $S$.
Applications

@Prove that there is no first-order formula $\phi(x, y)$ expressing the reachability relation in the language of graphs via the compactness theorem.

Suppose such a formula exists.

For all $n \in \mathbb N$, let $\psi _ n(x, y)$ be a formula expressing that there is a path from $x$ to $y$ of length $n$.

Now define

\[\pmb S := \\{ \phi(x, y) \\} \cup \\{\lnot \psi_n(x, y) \mid n \in \mathbb N\\}\]

Then every finite subset of $\pmb S$ is satisfiable whereas $\pmb S$ is not satisfiable (in other words, there are graphs where two vertices are separated by an arbitrary distance path, but there are no graphs where two vertices are connected despite not being connected by a path of arbitrary distance).

This contradicts compactness, hence no such $\phi(x, y)$ can exist.

Examples / When to use which?

Some of these examples come from the course [[Course - Logic MT24]]U, specifically [[Notes - Logic MT24, Compactness theorems]]U.

Propositional logic

The compactness theorem for propositional logic can be used to:

Showing some local property extends to a global property

Some examples:

  • Every finite subgraph of a graph is $k$-colourable, then the whole graph is $k$-colourable.
  • Every finite subgraph of a graph is connected, then that graph is connected.
First-order logic

The compactness theorem for first-order logic is often used for:

Showing that there is no first-order formula expressing some property

This is often done when there is an infinite set of “finite approximations” to that property which are expressible as first-order formulas.

Some examples:

  • Reachability / connectivity in graphs: If there did exist some formula $\text{reach}(v, w)$, consider $\lbrace \text{reach}(v, w) \rbrace \cup \lbrace \lnot \text{reach} _ n(v, w) \rbrace$ where $n$ encodes that there is a path of length $n$ between $v$ and $w$. Then every finite subset is satisfiable, since there are graphs where vertices are separated by an arbitrary distance, but the whole set is not satisfiable, a contradiction.
  • Rationality in fields: If there did exist some formula $\text{rational}(x)$ over $\lbrace+, \times, 0, 1\rbrace$, then consider $\lbrace \text{rational}(x) \rbrace \cup \lbrace ax \ne b : a, b \in \mathbb Z \rbrace \cup \lbrace ax + b \ne 0 : a, b \in \mathbb Z \rbrace$. Then every finite subset of this is satisfiable by e.g. $\mathbb Q$, since we can just take $x$ small enough. But the whole set is not satisfiable, a contradiction.
  • Torsion-freeness abelian groups: Take it for granted that there exists a finite set of sentences $\Sigma^\text{ag}$ over $\langle +, 0\rangle$ which axiomatises the property of being an abelian group, and call an abelian group torsion-free if for every nonzero $x$, $n \cdot x \ne 0$ for any $n \ge 1$ where “$\cdot$” represents repeated additions). If there did exist some sentence $\tau$ expressing the property of being a torsion-free abelian group, we could consider $\lnot \tau \cup \Sigma^\text{ag} \cup \lbrace \forall x \text{ } n \cdot x \ne 0 \mid n \ge 1\rbrace$. Then every finite subset of this satisfiable by e.g. $C _ p$ for a sufficiently large prime $p$. But the whole set is not satisfiable, a contradiction.
Constructing non-standard models

Another way to view showing that there is no first-order formula expressing some property is that it gives you a way of finding non-standard models for your favourite theory.

  • Reachability / connectivity in graphs: Consider the theory $T$ of the “infinite line graph” $v _ 0 \leftrightarrow v _ 1 \leftrightarrow \cdots$. This graph is connected. But by the above, we may also construct a new model which adds a new vertex $w$, which is not connected to this line. But this model satisfies all the sentences true in the infinite line graph.
  • Non-isomorphic sets of constants: Consider $\mathcal L$ as the first-order language with equality that has no function symbols or predicates, but does have infinitely many constant symbols $c _ i$. Let $\Sigma$ be the set of sentences which asserts all these constant symbols are different, i.e. $\Sigma = \lbrace c _ i \ne c _ j \mid i, j \in \mathbb N, i \ne j \rbrace$. Then it’s possible to construct two countably infinite but non-isomorphic models: consider extending $\mathcal L$ to $\mathcal L’ = \mathcal L \cup \lbrace d \rbrace$ and define the set of sentences $\Sigma’ := \Sigma \cup \lbrace c _ i \ne d \mid i \in \mathbb N \rbrace$. Every finite subset of $\Sigma’$ is satisfiable (e.g. by the Herbrand model $\mathcal H$), thus there must be a countable model $\mathcal A’$ of $\Sigma’$. Dropping the constant symbol $d$ yields a new countable model $\mathcal A$ of $\Sigma$, but this time it contains an element which is not named by a constant symbol. This means that there can be no isomorphism from $\mathcal H$ to $\mathcal A$: if some $f : \mathcal H \to \mathcal A$ did exist, as it is an isomorphism the image of $f$ must be $\lbrace c^{\mathcal A} _ i \mid i \in \mathbb N \rbrace$, which necessarily misses out the element which used to correspond to $d$, a contradiction.
  • Non-isomorphic models in general: The above example can be generalised: if you’ve got infinitely many ground terms, you can always apply this trick to find a model which is not isomorphic.
  • Rationality in fields: As an example with the same flavour, consider $\mathbb Q$ with a new constant symbol $c$. Then as every finite subset of $\text{Th}(\mathbb Q) \cup \lbrace \text{rational}(c) \rbrace \cup \lbrace ac \ne b : a, b \in \mathbb Z \rbrace \cup \lbrace ac + b \ne 0 : a, b \in \mathbb Z \rbrace$ is satisfiable by setting $c$ to a small enough rational, this also has a model where $c$ is not rational, say $\mathbb Q’$. But then $\mathbb Q$ and $\mathbb Q’$ are not isomorphic, since any isomorphism must map $c$ onto a rational.
  • Archimedeanity in ordered fields: 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 \rbrace _ {\mathbb F}$ with $-n < x < n$. If there did exist some formula $\pmb A$ over $\lbrace +, \times, <, 0, 1, c\rbrace$ which expressed $\mathbb R$ was Archimedean, consider $\text{Th}(\mathbb R) \cup \lbrace \pmb A \rbrace \cup \lbrace 0 < c, c < 1, 2c < 1, 3c < 1, \ldots \rbrace$. Then every finite subset is satisfiable by $\mathbb R$ and taking $c$ small enough, so this must have a model, say $\mathcal M$. But $\mathcal M$ is not Archimedean, yet satisfies all the same first-order sentences as $\mathbb R$.
Using finiteness of proofs rather than compactness

One way to view compactness is that it’s really a consequence of the fact that proofs (using $L _ 0$ in [[Course - Logic MT24]]U or resolution in [[Course - Logic and Proof MT24]]U) are finite, and that these proof systems are complete. Sometimes this offers alternative ways of questions involving compactness.

For example, you can prove the following proposition:

Let $\mathcal L$ be a first-order language, and let $\Gamma$ be an infinite set of $\mathcal L$-sentences. Assume that $\Delta$ is a finite set of $\mathcal L$-sentences having the same models as $\Gamma$. Then $\Gamma$ contains a finite subset $\Gamma _ 0$ with the same models as $\Gamma$.

A quick proof is the following: as $\Delta$ is finite, we may form the $\mathcal L$ sentence

\[\varphi = \bigwedge_{\delta \in \Delta} \delta\]

which has the same models as $\Delta$. Hence $\Gamma \models \varphi$ and $\lbrace \varphi \rangle \models \gamma$ for each $\gamma \in \Gamma$. By the completeness theorem for first-order logic, it follows that $\Gamma \models \varphi$ and since any derivation of $\varphi$ from $\Gamma$ only uses a finite set $\Gamma _ 0 \subseteq \Gamma$ of assumptions, we get $\Gamma _ 0 \models \varphi$ and hence by soundness, $\Gamma _ 0 \models \varphi$, and still $\lbrace \varphi \rbrace \models \gamma$ for each $\gamma \in \Gamma _ 0$. Thus $\Gamma _ 0$ and $\Gamma$ have the same models.



Related posts