I am working through problems which ask you to apply the compactness theorem (from propositional logic) to problems. How would you go about solving this one?

Let $\mathbf{L}$ be an arbitrary infinite set of natural numbers, presented in binary notation (e.g., the set of prime numbers: $\mathbf{L} = \{10, 11, 101, ... \}$.) Prove there is an infinite sequence of different binary numbers $\omega_1, \omega_2, \omega_3, ... $ such that $\omega_i$ is a prefix of $\omega_{i+1}$ and also a prefix of some element $\mathbf{L}$.

I guess what you are meant to do is represent the numbers using propositional variables somehow and then show that every finite subset is satisfiable before invoking compactness to get the infinite result. Maybe we could consider the binary numbers to be sequences of assignments which extend each other.


1 Answer 1


Hint: take the set $L$, view it as a set of binary sequences, and make a tree out of that set of binary sequences. Then use compactness in the form of Konig's lemma.

  • $\begingroup$ Did you mean something like that: we build tree, each node has finite degree (<=2), tree must be infinite because sequences are infinite. From Konig lemma we know that there exists infinite branch. root, root and son, ... of this infinite branch creates expected $\omega_1, \omega_2...$. ??? $\endgroup$
    – user343207
    Commented Feb 19, 2017 at 14:04
  • 1
    $\begingroup$ Yes, that is the idea. $\endgroup$ Commented Feb 20, 2017 at 1:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .