Application of the compactness theorem

Asked Sep 08 '13 at 22:01

Active Sep 08 '13 at 22:01

Viewed 265 times

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.

asked Sep 08 '13 at 22:01

user93828

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

Application of the compactness theorem

0 Answers0