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?

  • $\begingroup$ I'm not sure you're missing anything; this proof seems like something of a triviality to me. In "plain english," we're proving that if $\Gamma$ says that $\phi$ does not hold for some $\tau$, then $\Gamma$ can't also say that $\phi$ holds for all $\tau$. $\endgroup$ Oct 1 at 16:01
  • $\begingroup$ The proof must work: if there is an Odd (i.e. not-Even) number, then it is not true that every number is Even. $\endgroup$ Oct 1 at 16:05
  • 1
    $\begingroup$ @MauroALLEGRANZA - If you go to this link and solve part-c. The solution there says that, the statement is false! However, I just proved that the statement is true! $\endgroup$ Oct 1 at 16:09
  • $\begingroup$ @MauroALLEGRANZA - I think this staetment "if $\vDash \varphi(\tau)$ for every ground term, then $\vDash \forall x.\varphi$" is True! $\endgroup$ Oct 1 at 16:14
  • 1
    $\begingroup$ @MauroALLEGRANZA In relational logic as defined by this course, quantifiers only range over ground terms. $\endgroup$ Oct 1 at 16:46

This is incorrect on one problem. But it's not the problem you mentioned. The error is actually on

$\forall x . \phi \models \phi$

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

  • $\begingroup$ I feel like "this is false, because $\Gamma$ could be inconsistent" is a bit pedantic (it's totally reasonable to assume $\Gamma$ is consistent, because unless we're working in a contradiction-tolerant logic, inconsistent systems are profoundly uninteresting). $\endgroup$ Oct 1 at 16:59
  • $\begingroup$ @user3716267 This is a class on logic. Being pedantic is the entire point. (I'm only partly joking). $\endgroup$ Oct 1 at 17:00
  • 1
    $\begingroup$ I disagree that pedantry is the "entire point" of formal logic. Were that the case, it would be quite useless. $\endgroup$ Oct 1 at 17:00
  • 1
    $\begingroup$ @user3716267 Or perhaps I should have said that it's a fundamental part of how this logic works. I agree that the problems are not ideal, but in my view the issue is that the answer key has no explanations at all. So it's very difficult to understand why the answer is "No" (unless you use MSE). $\endgroup$ Oct 1 at 17:18
  • 2
    $\begingroup$ @MarkSaving - since we are on the topic of being pedantic - it is not $\Gamma$ being "inconsistent", its $\Gamma$ being "unsatisfiable" - meaning there is no truth assignment that satisfies it. And in such a case (you are right!), $\Gamma$ will trivially entail every sentence (This point didn't even cross my mind!). $\endgroup$ Oct 1 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.