How to prove $\phi \models \psi$ iff $\phi \cup \{\neg \psi\}$?

Question

I want to prove $\phi \models \psi$ iff $\phi \cup \{\neg \psi\}$ unsatisfiable.

What's the meaning of the union operator w.r.t. satisfiability in FOL?

Does it mean that all such interpretations $\mathcal{I}$ of the LHS also have to model $\phi$ and $\{\neg \psi\}$?

So $\phi \cup \{\neg \psi\} \Leftrightarrow \phi \wedge \neg \psi$ ?

I read a few other related posts.

First one which I changed w.r.t. my proof:

Let $\phi$ be a set of propositional formulas and $\psi$ a propositional formula.

$\Rightarrow:$

Assume $\phi\models \psi$ and $\phi \cup \{\neg \psi\}$ satisfiable

Then there is a variable assignment s.t. $\forall \varphi:(\beta \models \varphi) \wedge (\beta \models \neg\psi)$

It follows that $\beta \nvDash \psi$. Therefore $\psi$ not a consequence of $\phi$.

$\Leftarrow$:

Assume $\psi \cup \{\neg \psi\}$ not satisfiable and $\beta$ any variable assignment s.t. $\beta \models \phi$.

To be shown $\beta \models \psi$.

For contradiction assume $\beta \nvDash \psi$.

Then $\beta \models \neg \psi$, whch implies $\beta \models \phi \cup \{\neg \psi\}$. So $\phi \cup \{ \neg \psi\}$ satisfiable, which is a contradiction.

Is this correct?

Source of first proof

Another proof with natural deduction.

$\frac{\psi \cup \{\phi\} \models \bot}{\phi \models \neg \psi}$

And

$\frac{\phi \models \psi}{\phi \cup \{ \neg \psi\}\models \bot}$

$\Rightarrow:$

If $\phi \models \psi$ then $\phi \cup \{\neg \psi\} \models \psi$.

But $\phi \cup \{\neg \psi\} \models \{ \neg \psi\}$.

Can't be satisfied, because it proves contradiction.

$\Leftarrow:$

If $\phi \cup \{ \neg \psi\} \models \phi$ can't be satisfied, then it has no models and so $\phi \cup \{ \neg \psi\} \models \bot$

By usage of semantic completeness theorem we get $\phi \cup \{ \neg \psi \} \models \bot$.

Which by usage of natural deduction results in $\phi \models \psi$.

In the deductions I changed $\vdash$ to $\models$, is this still correct?

Source of second proof

Answer 1

I want to prove $\phi \models \psi$ iff $\phi \cup \{\neg \psi\}$ unsatisfiable.

What's the meaning of the union operator w.r.t. satisfiability in FOL?

We have to be careful with symbols. $a\models b$ could mean one of two things:

• $a$ is a model, and the formula $b$ is true for $a$.
• $a$ is a set of formulas, and for every model $\mathcal M$ that satisfies $a$, it must satisfy $b$.

In your case, it seems you mean $\phi$ is either a formula or a set of formulas. If $\phi$ is a set of (well-formed) formulas that are understood as axioms, then $\cup$ is literally the union of the two sets, that is to add $\neg\psi$ as a new axiom.

Now the statement is almost trivial: if $\phi\models \psi$, i.e. for any model $\mathcal M$ that satisfies $\phi$, it must satisfy $\psi$, hence it cannot satisfy $\neg\psi$, so $\phi\cup\{\neg\psi\}$ cannot be satisfied. If $\mathcal M$ satisfies $\phi\cup\{\neg\psi\}$, it satifies $\phi$ but not $\psi$, which contradicts the meaning of $\phi\models\psi$.

This is trivial precisely because $\vDash$ is about semantics. Only "$\phi\vdash\psi$ iff $\phi\cup\{\neg\psi\}$ cannot be satisfied" needs the Godel completeness theorem. See the difference between $\vdash$ and $\vDash$.

There seem to be many notational problems. Just to name a few, but you probably should read entire sections of your study materials more carefully.

So $\phi \cup \{\neg \psi\} \Leftrightarrow \phi \wedge \neg \psi$ ?

$\phi\wedge\neg\psi$ makese no sense, unless $\phi$ is a single formula instead of a (potentially infinite) set of formulas.

$\forall \varphi:(\beta\models \varphi) \wedge (\beta \models \neg\psi)$.

"$\forall, \wedge$" are reserved symbols in the FOL, so better to avoid using them on the meta-level. If $\beta$ is actually a model/interpretation (together with assignment for free variables if necessary), it's correct to use $\vDash$ here, but this $\vDash$ has a different meaning from the one in $\phi\vDash\psi$. Also, are you suggesting $\varphi\in\phi$?

If $\phi \cup \{ \neg \psi\} \models \phi$ can't be satisfied, then it has no models and so $\phi \cup \{ \neg \psi\} \models \bot$

It makes no sense to say whether "$a\vDash b$" can be satisfied, which is either true or false objectively. Only a set of sentences can be satisfied or not.