Finitely satisfiable sets of formulas

467 Views Asked by At

The following problem is from the book "A Beginner's Guide to Mathematical Logic" by Raymond M. Smullyan in the context of preparing a (second) proof of the compactness theorem for propositional logic (slightly reworded to use unsigned instead of signed formulas):

For any set $S$ of formulas and any formula $X$, if some finite subset of $S \cup \{X\}$ is unsatisfiable, and if some finite subset of $S \cup \{\neg X\}$ is unsatisfiable, then some finite subset of $S$ is unsatisfiable.

My proof goes like this:

Proof. Let $I$ be an arbitrary interpretation and $S_1 \subseteq S \cup \{X\}$ and $S_2 \subseteq S \cup \{\neg X\}$ some unsatisfiable finite subsets. Then either $I$ satisfies $X$ or $I$ satisfies $\neg X$. If $I$ satisfies $X$, then $I$ cannot satisfy $S_1 \setminus \{X\}$, for $S_1$ is unsatisfiable. If $I$ satisfies $\neg X$, then $I$ cannot satisfy $S_2 \setminus \{\neg X\}$, for $S_2$ is unsatisfiable. Thus $(S_1 \setminus \{X\}) \cup (S_2 \setminus \{\neg X\})$ is an unsatisfiable finite subset of $S$. $\blacksquare$

Now I have tried an alternative proof of the contrapositive, i.e.:

For any set $S$ of formulas and any formula $X$, if all finite subsets of $S$ are satisfiable, then either all finite subsets of $S \cup \{X\}$ are satisfiable, or all finite subsets of $S \cup \{\neg X\}$ are satisfiable.

I began as follows:

Proof. Let $S_1 \subseteq S \cup \{X\}$ and $S_2 \subseteq S \cup \{\neg X\}$ be finite subsets. If $X$ is unsatisfiable, then $\neg X$ is valid and since all finite subsets of $S$ are satisfiable, $S_2$ is satisfiable as well, hence all finite subsets of $S \cup \{\neg X\}$ are satisfiable. If $X$ is satisfiable, ...

At this point I don't know how to continue, i.e. how to show that if both $X$ and $S_1 \setminus \{X\}$ are satisfiable, then they necessarily have at least one interpretation in common that satisfies both, such that $S_1$ is satisfiable and hence I could conclude that all finite subsets of $S \cup \{X\}$ are satisfiable. Any hints on how the proof could proceed, if it can?