Prove φ is a contradiction or ψ is a tautology if φ ⊨ ψ and φ and ψ have no sentence letters in common.

Question

Show that if φ ⊨ ψ but φ and ψ have no sentence letters in common, then either φ is unsatisfiable or ψ is tautologous.

Use the lemma: if $\cal{A}$(Ρ) = $\cal{B}$(P), for every sentence letter P in φ, then |φ|_$\cal{A}$ = |φ|_$\cal{B}$.

I see that we can reformulate the question as follows: If φ ⊨ ψ but φ and ψ have no sentence letters in common, then either |φ|_$\cal{A}$ = F or |ψ|_$\cal{A}$ = T in all $\cal{L}$₁-structures.

I figure the proof will look something like this:

Let's say it's not the case that either |φ|_$\cal{A}$ = F or |ψ|_$\cal{A}$ = T in all $\cal{L}$₁-structures.

That leaves two possibilities:

(1) |φ|_$\cal{A}$ = T, |ψ|_$\cal{A}$ = T. Can this happen if φ and ψ have no sentence letters in common?

(2) |φ|_$\cal{A}$ = F, |ψ|_$\cal{A}$ = F. Again, I don't know what the implications of φ and ψ having no sentence letters in common does here.

I am new to proofs, and perhaps I am going completely the wrong direction here. Any help would be greatly appreciated.

Answer 1

We prove that $\phi$ not unsatisfiable implies that $\psi$ is a tautology, provided that $\phi\models\psi$ and they have disjoint sentence letters.

Assume $\phi$ contains sentence letters $x_1,\dots, x_n$, and $\psi$ contains sentence letters $y_1,\dots,y_m$.
Assume further that $\phi$ is satisfied in a model $A$, i.e. $|\phi|_A=\top$.
Let $x_i$ evaluate to $a_i\in\{\bot,\top\}$ in $A$.
By the given hint, the evaluation of $\phi$ remains the same if we change the model at any other sentence letters (different from all $x_i$'s).

Now take an arbitrary model $B$, and change each value of $x_i$ to $a_i$, yielding a model $B'$.
Note that we didn't touch $y_j$'s, that is, $|y_j|_{B'}=|y_j|_B$ because they differ from the $x_i$'s.
Consequently, $|\psi|_{B'}=|\psi|_B$.

Finally, in the model $B'$, we have $|\phi|_{B'}=|\phi|_A=\top$, hence $\phi\models\psi$ implies $|\psi|_{B'} =\top$.
We got $|\psi|_B=|\psi|_{B'}=\top$ for any model $B$, so $\psi$ is a tautology.

Answer 2

It might be easier (and it's definitely more symmetrical) to proceed by contradiction. Suppose $\phi$ isn't a contradiction and $\psi$ isn't a tautology. So we have an assignment $A$ (assigning truth values to the sentence letters) that makes $\phi$ true, and we have an assignment $B$ that makes $\psi$ false. Now define a third assignment $C$ giving all the sentence letters in $\phi$ the same truth values that $A$ gave them, and giving all the sentence letters in $\psi$ the same truth values that $B$ gave them. Such a $C$ exists, because of the assumption that $\phi$ and $\psi$ have no sentence letters in common --- so my definition of $C$ is not trying to give the same sentence letter two possibly different values. Thanks to the lemma you quoted, $C$ gives $\phi$ the same truth value that $A$ gave $\phi$, namely true, and similarly $C$ gives $\psi$ the same truth value that $B$ gave it, namely false. But these facts about $C$ --- making $\phi$ true and $\psi$ false --- contradict the assumption that $\phi\models\psi$.