Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

up vote 5 down vote accepted

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

share|improve this answer
add comment

You can use the Compactness Theorem to show that a countable graph $G$ is $k$-colorable if and only if every finite subgraph of $G$ is $k$-colorable. A proof is explained here, but the general idea is clear, and it's almost easier to realize the solution than write it up.

You can also use the Compactness Theorem to introduce the notion of non-standard models of arithmetic, or the hyperreals. That is, you take the theory of $\mathbb{N}$ or $\mathbb{R}$ and adjoin the infinite family of sentences

$$ x > n$$

as $n$ ranges over $\mathbb{N}$ (here, $x$ is a new constant symbol). These sentences assert the existence of some value $x$ larger than every natural number. Since any finite subset of this theory is satisfiable (by interpreting $x$ as some sufficiently large number), the whole theory is satisfiable, and hence you get models with infinitesimal and/or unlimited elements. You can read more about nonstandard models of arithmetic here, and more on the hyperreals here, which naturally extends itself to studying non-standard analysis.

share|improve this answer
2  
The first example is very nice. The second one is a nice as well, but it's in first-order logic, not propositional calculus... –  Gadi A Mar 28 '12 at 7:28
    
Ah, you're right. I just couldn't help myself. =) –  Isaac Solomon Mar 28 '12 at 7:32
add comment

There is a very nice construction showing that every partial order can be extended to a total order using the propositional compactness theorem, see http://www.math.caltech.edu/~2010-11/3term/ma006c/Notes46c.pdf (Thanks to Brian M. Scott for an English version).

The proof works by assuming a given set $S$, and for each pair $a,b \in S$ of values, having a variable $L_{a,b}$ that stands for $a < b$. It is then easy to formalize the axioms of a total order and the existing partial order as a set of propositional formulas. Using compactness, one shows that the formula set is satisfiable, i.e., there is a total order.

share|improve this answer
    
Prove the finite case by induction, then use the compactness theorem to get the general case? These notes do it in Section 1.8.C. –  Brian M. Scott Mar 28 '12 at 8:04
    
Thanks, this is the same proof in more detail and in English. –  Johannes Kloos Mar 28 '12 at 8:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.