« Section 2.5: Problem 5 Solution

Section 2.5: Problem 7 Solution »

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).