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.

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|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
add comment

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.