I am trying to follow Logic Notes of Lou Van Dries and I am stuck at a particular question in propositional logic. Assuming $A$ is any set and Prop$(A)$ is the set of propositions on $A$. The question goes as follows:

Let $\Sigma \subset$ Prop$(A)$ such that for every truth assignment $t:A \to \lbrace 0,1\rbrace$ there exists $p\in \Sigma$ for which $t(p)=1$. I need to show that there exists $p_1,p_2,\ldots,p_n \in \Sigma$ such that $p_1\vee p_2\vee \ldots \vee p_n$ is a tautology (i.e it gives value 1 for all truth assignments).

I suspect this to be some application of compactness theorem.


Hint. Consider the theory $\{\neg p\mid p\in\Sigma\}$. Your assumption amounts to saying that this theory is inconsistent. By compactness, therefore, it has a finite inconsistent subset $\{\neg p_1,\neg p_2,\ldots,\neg p_n\}$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.