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.