Compactness Theorem (logic) application.

compactnessfirst-order-logiclogicmodel-theory

I met a question which says: if we have $A, B$, both are nonempty theories such that every model of $A$ satisfies at least one formula (sentence if they are in the first-order language, the question indicates that there is no difference whether it's propositional or first-order) in $B$. Then it asks me to show there are some formulas/sentences, $a_1….a_k$ from $A$ and $b_1…b_l$ from $B$ such that $(a_1…\land…a_k)\to(b_1…\lor…b_l)$ is a tautology.

The question specifically says I should use the compactness theorem, but I don't see how to apply the theorem here. Any hints?

Best Answer

Hint: Notice that the hypothesis says exactly that $\{\varphi,\neg \psi\mid \varphi\in A,\psi\in B\}$ is inconsistent. By compactness, there is a finite inconsistent subset.

Related Question