Why $\models (F \rightarrow G)$ when $F$ and $G$ share no atomic formulas implies that either $F$ is unsatisfiable or $G$ is a tautology?

Question

I encountered this problem when studying Uwe Schoning's Logic for Computer Scientists. At the moment, I simply don't seem to think the statement makes sense. What I've tried is to suppose that it is not the case that "either $F$ is unsatisfiable or that $G$ is a tautology (or both)", and see what happens. Well, this means that $F$ is satisfiable and $G$ is not a tautology. But this doesn't seem to give the contradiction that $\models (F \rightarrow G)$ doesn't hold. For instance, because $F \rightarrow G \equiv \neg{F} \lor G$, can't I just find $F$ and $G$ such that whenever $F$ is true, $G$ is true, and whenever $F$ is false, $G$ is false? This doesn't seem to require $F$ to be unsatisfiable or $G$ to be a tautology.

Or perhaps there is something I've missed. Many thanks to anyone who could offer a proof for the problem.

By the way, the follow-up question to this problem is to explain why the assumption that $F$ and $G$ share no common atomic formulas is necessary. I also don't really know how to explain this, seeing that I haven't made any headways in solving the previous problem. Appreciate any answer to this follow-up question as well.

Answer 1

Assume, that $\models (F \to G)$ s.t. both $F$ and $G$ share no atomic formulas. Let $A(F)$ be the set of atoms in $F$, and $A(G)$ the set of atoms in $G$.

Now, to do a proof by contradiction we must assume the opposite of the conclusion we want to derive. So assume (bwoc), that both $F$ is satisfiable and $G$ not a tautology. Then, by definition, there is a valuation $v_1$ under which $F$ is true and a valuation $v_2$ under which $G$ is false. Define the valuation $v$ by

$$v(p) = \begin{cases} v_1(p) & \text{if } p \in A(F), \\ v_2(p) & \text{if } p \in A(G), \\ 0 & \text{else.} \end{cases}$$

$v$ is well-defined, since $A(F)$ and $A(G)$ are disjoint. Notice, that $F$ and $G$ have the same truth-value under $v$ as they have under $v_1$ and $v_2$. But then $F \to G$ is false under $v$, which contradicts our assumption that $\models (F \to G)$. ↯

The follow-up can be showed using an example. Here is a possible solution, but you should try it yourself first 😉

$F = G = p$ for some atom $p$.