Constructing a tautology given a set $\Sigma \subset $Prop(A) with special properties.

76 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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\}$.