0
$\begingroup$

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?

$\endgroup$
10
  • 3
    $\begingroup$ Hint: Using the condition "every model of A satisfies at least one sentence in B", try to come up with a set of sentences that is inconsistent. Then apply compactness theorem to that set. $\endgroup$
    – halrankard2
    Dec 7, 2020 at 17:36
  • $\begingroup$ @halrankard2, so you mean, we need to first separate if B is satisfiable or not? If B is not satisfiable, then we just pick some b and not b so that it will be a tautology. But if B is satisfible, how to use the condition to construct such a set? $\endgroup$
    – qwerty
    Dec 7, 2020 at 18:12
  • $\begingroup$ Analyzing whether or not B is satisfiable isn't fully leveraging the main connection between A and B. You know that every model of A is a model of some sentence in B. Therefore there is a certain collection of sentences (built using both A and B as ingredients) that is inconsistent. $\endgroup$
    – halrankard2
    Dec 7, 2020 at 18:29
  • 1
    $\begingroup$ Well it's hard to make an example that doesn't give away the answer. But suppose B consisted of just one sentence $\phi$. Then your assumption is that every model of A is a model of $\phi$. So $A\cup\{\neg\phi\}$ is an inconsistent set. $\endgroup$
    – halrankard2
    Dec 7, 2020 at 22:21
  • 1
    $\begingroup$ @qwerty You don't have that $A$ and $B$ are finite ... $\endgroup$
    – Ned
    Dec 7, 2020 at 23:46

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .