Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In my logic book they ask me to prove the following as a consequence of the compactness theorem for propositional logic.

Let $S \subseteq N$ be an infinite set. I have to show that there exists an infinite sequence of unequal binary numbers: $b_1,b_2,\ldots$ such that $b_i$ is a prefix of $b_{i+1}$ and also of the prefix of a number in $S$.

Can someone help me on the way to solving this as an application of the compactness theorem?

My guess is that I have to model this situation as a set of propositional formulas and show that every finite subset is satisfiable.

share|cite|improve this question
Are you sure this is a question about propositional logic? It sounds much more like a problem for predicate logic. – Alex Kocurek Sep 8 '13 at 23:04
I am very sure :). – user93828 Sep 8 '13 at 23:17
which book do you use? – Willemien Sep 9 '13 at 8:59
It's a dutch syllabus written by one of our professors, which I do not have digitaly unfortunatly. – user93828 Sep 9 '13 at 13:36

Your Answer


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

Browse other questions tagged or ask your own question.