Section 2.5: Problem 6 Solution
Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
Let
and
be sets of sentences such that nothing is a model of both
and
. Show that there is a sentence
such that
and
. (This can be stated: Disjoint
classes can be separated by an
class.) Suggestion:
is unsatisfiable; apply compactness.
As suggested,
is unsatisfiable. According to the compactness theorem, there is a finite unsatisfiable subset
. Let
, and
be the conjunction of sentences in
(which is finite), or any valid sentence (an axiom of the language) if
is empty. Then,
is logically equivalent to
, and
, hence,
and
(well, if
is empty we can either assume that every structure is a model of
, so all relations hold, or simply argue that the latter relation holds in this case as
is valid). Now,
is not satisfiable (again, even if one of them is valid), and, hence, it is not consistent,
, and
. In particular,
.
Note. In the above proof we could have considered the case when one of
is inconsistent separately, and set
to be either a valid sentence or the negation of a valid sentence, and then repeat the proof for the case when both
and
are satisfiable to avoid the necessity to mention the case when one of the
’s is empty (if both
and
are satisfiable, then the unsatisfiable
cannot be a subset of either one).