[Math] Compactness theorem for propositional calculus – nice uses

combinatoricslogic

The compactness theorem for propositional calculus states that a set of propositional sentences has a model (satisfying assignment) if and only if every finite subset of it has a model. I'm looking for uses of the theorem for something outside of logic that are simple enough to present without additional background.

An example is tiling, e.g. tiling of $\mathbb{Z}^2$ using Wang tiles. Given a set of Wang tiles one can introduce variables $X_{i,j}^k$ that means "Tile no. $k$ was placed in $(i,j)$". We now construct an infinite set of sentences saying that the assignment to the variables defines a legal tiling (i.e. for every $(i,j)$ exactly one $X_{i,j}^k$ is true, and we also check edge compatability). Now the compactness theorem can be used to prove that a set of tiles tiles the entire plane if and only if it tiles any finite zone in the plane.

Are there more uses in the same spirit?

Best Answer

Suppose that you have a set $S$ of students and a set $C$ of classes. Each student will be assigned to just one class. Each student $s\in S$ has a finite list $C(s)\subseteq C$ of classes that he or she is willing to take, and each class $c\in C$ has a finite enrolment capacity $n_c$. For $T\subseteq S$, an acceptable course assignment is a function $f:T\to C$ such that

  • $f(t)\in C(t)$ for each $t\in T$, and
  • $\left|f^{-1}\left[\{c\}\right]\right|\le n_c$ for each $c\in C$.

(In other words, each student gets an acceptable class, and no class is oversubscribed.)

The compactness theorem now easily implies that if each finite subset of $S$ admits an acceptable course assignment, then so does $S$. Probably the easiest way to model it is as a bipartite graph with parts $S$ and $C$, where each vertex in $S$ is to have degree $1$, each vertex $c\in C$ has degree no more than $n_c$ and for each $s\in S$ the unique edge adjacent to $s$ must terminate at one of the vertices in $C(s)$.