2

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}$1-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}$1-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.

vundabar
  • 41

2 Answers2

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.

Berci
  • 90,745
  • Why does $\psi$ hold at $B'$ by the hypothesis? Have you just arbitrarily chosen that model? And even if you show that it holds in $B'$, how can we then say it holds in $every$ model? – vundabar Jun 01 '18 at 18:49
  • Please reread my answer. Is it clear how we construct $B'$ by $A$ and $B$? Note that sentence letters of $\phi$ and $\psi$ are disjoint by hypothesis. – Berci Jun 01 '18 at 18:56
  • So, $\psi$ and $\phi$ have no element in common. Got it. So we can assume that the elements of $\phi$ (which are not elements of $\psi$) are satisfied by model $A$. Then you've taken another model, $B$, and changed its values to those of $A$, creating $B'$. That $|\phi|{B'}=|\phi|_A=\top$ follows is clear to me. I don't understand the next step, $|\psi|_B=|\psi|{B'} =\top$. – vundabar Jun 01 '18 at 19:05
  • You're almost there. What does $\phi\models\psi$ mean? Apply it to $B'$. – Berci Jun 01 '18 at 19:07
  • Thank you. It means that in any model where $\phi$ is true, $\psi$ must also be true. Which means that $\psi$ is true in $B'$. But isn't model $B$ different than model $B'$? After all, we changed the values of $B$ to create $B'$. Why is $|\psi|_{B} =\top$? – vundabar Jun 01 '18 at 19:11
  • It's the same reason as $|\phi|A=|\phi|{B'} $. We didn't touch any variables appearing in $\psi$ when creating $B'$. – Berci Jun 01 '18 at 19:14
  • I guess I'm confused because we never established that $|\psi|_{B} =\top$ in the first place. Unless all that is meant to show is that $\psi$ is true in a model that is not $A$, since $\psi$ and $\phi$ do not share elements. – vundabar Jun 01 '18 at 19:27
  • No. We aim to prove $\psi$ at $B$. – Berci Jun 01 '18 at 19:28
  • When we say $\psi$ is a tautology, though, we mean that it is true in $all$ models, correct? That is, $\psi$ must be true in $A$, $B$, $B'$, etc.? – vundabar Jun 01 '18 at 19:36
  • Yes. But $B$ was taken as arbitrary. – Berci Jun 01 '18 at 20:10
  • Apologies for my incompetence here. So $\phi$ ⊨ $\psi$, which means that it $could$ be the case that $\phi = \bot$ and $\psi = \top or \bot$. Why haven't we accounted for that, but instead we have assumed that $\phi = \top$, in which case there must be an $A$ model in which all its sentence letters are true. – vundabar Jun 01 '18 at 22:36
  • It's not $A$'s sentence letters that are evaluated to true, but it's $\phi$ at $A$. Let me detail my answer.. – Berci Jun 01 '18 at 23:48
  • Thanks for clarifying. I understand this: it is clear that if $|\phi| = \bot$ in all models--ie, if $\phi$ is a contradiction--then $\phi\models\psi$ is trivially true. If this isn't the case, then it must be true that $|\phi| = \top$ in $at$ $least$ $one$ model. We'll call that model $A$. It sounds like what you then go on to say is that for any arbitrary model $B$, despite it containing no sentences found in $A$ (or any model that makes $|\phi| = \top$), there is nothing stopping us from constructing a model $B$ such that $|\psi|_B$ = $\top$. Is this correct? – vundabar Jun 02 '18 at 01:14
  • $B$ is the arbitrarily given model. We change it on $x_i$'s, that's another model $B'$, but $\psi$ evaluates the same. – Berci Jun 02 '18 at 07:30
1

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

Andreas Blass
  • 71,833
  • I follow this mostly. If $\phi$ is false under any assignment -- ie, if $\phi$ is a contradiction -- then it is trivially true that $\phi\models\psi$. Under another case, though, $|\phi| = \top$ for at least one assignment, we'll call that $A$. Clearly, then, if it is to remain true that $\phi\models\psi$, then under the assignment $A$ where $|\phi| = \top$, it must be the case that $|\psi|_A = \top$. Here is the step I don't get. Why, then, must we conclude that $|\psi| = \top$ for $any$ assignment -- ie, why must it be true that $\psi$ is a $tautology$ -- and not just be true under $A$? – vundabar Jun 02 '18 at 20:01
  • To put this another way: where $|\phi| = \top$, it is clear that it $must$ be the case that $\psi$ is true under $some$ assignment -- namely, the assignment under which $\phi$ is true. But how do when then deduce that $|\psi| = \top$ under $all$ assignments? – vundabar Jun 02 '18 at 21:04
  • Let me repeat: take an arbitrary assignment $B$, and modify it on $\phi$'s letters according to $A$, yielding a new assignment $B'$. Since $\psi$'s letters are disjoint to $\phi$'s letters, we have $|\psi|B=|\psi|{B'}$. Use $\phi\models\psi$ for assignment $B'$ to obtain $|\psi|_{B'} =\top$. – Berci Jun 02 '18 at 21:39
  • Let's see if I can rephrase this: We know that if $\phi = \top$ under an assignment, call it $A$, then, since $\phi\models\psi$, it must be the case that $\psi = \top$. In order to make $\psi = \top$, we cannot use the same assignment $A$ under which $\phi = \top$, since $\phi$ and $\psi$ are disjoint. So instead we take a new assignment $B$, and modify it such that it produces the same evaluations as $A$. Under this modification, model $B'$, $\psi = \top$. – vundabar Jun 02 '18 at 21:58
  • I hope I got that right. Now, my question remains: you have clearly demonstrated that we $can$ produce a model -- namely $B'$ -- under which $\psi = \top$. But I'm meant to prove that $\psi$ $must$ be a tautology. That is, that we couldn't possibly produce a model $C$ under which $\psi = \bot$. I still don't quite see how we have proven that. – vundabar Jun 02 '18 at 21:58
  • 1
    @vundabar You seem to be commenting on a version of the proof closer to Berci's answer than to mine. Perhaps you should read one of the proofs slowly and carefully and not try to guess what we (Berci or I) should be doing --- instead, think about what we actually wrote. – Andreas Blass Jun 02 '18 at 22:19
  • We are first given an arbitrary model $B$. Then we modify it to make $\phi$ true but not touching $\psi$ (we can do it because of the disjointness hypothesis). Using the other hypothesis, $\phi\models\psi$, we have $\psi$ is true in $B'$. Since at modification we didn't touch $\psi$'s letters, $\psi$ must have been true in the original arbitrary model $B$. – Berci Jun 02 '18 at 22:21
  • @Berci It makes a lot more sense thinking about it this way! So if $\phi$ and $\psi$ do not share sentence letters, then necessarily they are evaluated under different models. And if we start with any model where $\psi$ is true (we know it must be true under at least one model if $\phi$ is satisfiable) and modify that model to make sure $\phi$ is true, we will never tamper with the fact that $\psi$ was true under the original model. – vundabar Jun 02 '18 at 22:48
  • Well, a model assigns a truth value to all sentence letters, including all $x_i$'s and all $y_j$'s. Now the point is that $\phi$ only cares the $x_i$'s and $\psi$ only cares the $y_j$'s. In that circumstance $\phi\models\psi$ is a quite strong criterium, that's what this exercise is about. – Berci Jun 02 '18 at 22:52