This problem is from CS-157: Introduction to Logic, Problem 8.2 – Logical Entailment, Part-c.
Let $\Gamma$ be a set of Relational Logic sentences, and let $\varphi$ be an individual Relational Logic sentence. Then, prove the following statement false:
If $\Gamma \vDash \lnot \varphi[\tau]$ for some ground-term $\tau$, then $\Gamma \nvDash \forall x.\varphi[x]$
My Reasoning: Let $\tau = \tau_{o}$ be the ground-term for which $\Gamma \vDash \lnot \varphi[\tau]$ holds; then, we have that every truth-assignment that satisfies $\Gamma$ falsifies $\varphi[\tau_{o}]$.
Since, $\Gamma \vDash \forall x.\varphi[x]$ is equivalent to $\Gamma \vDash \varphi[\tau_{o}] \land \varphi[\tau_{1}] \land …\land\varphi[\tau_{n}]$, where $\tau_{o}, \tau_{1}, …, \tau_{n}$ are ground-terms; (for the consequent of the above statement to hold) we must have that every truth-assignment that satisfies $\Gamma$ also satisfy $\varphi[\tau_{o}] \land \varphi[\tau_{1}] \land …\land\varphi[\tau_{n}]$. Which is not possible, because every truth-assignment that satisfies $\Gamma$ falsifies $\varphi[\tau_{o}]$, thereby falsifying $\varphi[\tau_{o}] \land \varphi[\tau_{1}] \land …\land\varphi[\tau_{n}]$!
PS: it seems that I have proved the statement to be true, but the solution says that the statement is false! So, what am I missing?
Best Answer
This is incorrect on one problem. But it's not the problem you mentioned. The error is actually on
Suppose we have a vocabulary with a zero-ary relation $P$ and no ground terms at all. Take the model where $P$ is false. Then in this model, $\forall x . P$ is true, but $P$ is false. So $\forall x . P \nvDash P$.
But the assignment is actually correct on the problem you stated. The reason? It could be that $\Gamma$ is inconsistent itself. Take a vocabulary with a single ground term $t$ and with a single 1-ary relation symbol $P$. Take $\Gamma = \{P(t), \neg P(t)\}$.
Then we see that $\Gamma \models Q$ for all sentences $Q$. For suppose that $W$ is a truth assignment which satisfies $\Gamma$. But this is contradictory, since $W$ must state both that $P(t)$ and $\neg P(t)$ hold, which is impossible. So $\Gamma \models Q$ holds vacuously, regardless of what $Q$ is.
So in particular, we have $\Gamma \models \neg P(t)$ and also $\Gamma \models \forall x . P(x)$.