« Section 1.7: Compactness and Effectiveness

Section 1.7: Problem 2 Solution »

Section 1.7: Problem 1 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
Assume that every finite subset of is satisfiable. Show that the same is true of at least one of the sets and . (This is part of the proof of the compactness theorem.) Suggestion: If not, then and are unsatisfiable for some finite and . Look at .
As suggested, if and are finite and not satisfiable (finite unsatisfiable subsets of must include as itself is finitely satisfiable), then we consider . is a finite subset of , hence, there is a truth assignment that satisfies it. Now, either and satisfies , and, hence, , or , and, hence, satisfies , and, hence, . Therefore, at least one of and is satisfiable. Contradiction.
Note, that this is not true that exactly one of and is finitely satisfiable. For example, or even , and .