# Using the compactness theorem

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.

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