1
$\begingroup$

What does the notation $\Gamma \vDash \phi$ mean (in Mathematical Logic)?

I understand that $\Gamma$ represents a system of formulas, and that $\phi$ represents an individual formula.

I also know that $\Gamma \vDash \phi$ means " $\phi$ is a semantic consequence of $\Gamma$" - but I do not understand what this actually means. Can someone explain this idea to me in layman's terms?

Furthermore, suppose I had the following question:

Let $\Gamma \cup \{ \phi \}$. Does $\Gamma \vDash \phi$ hold for the set of formulae $$ \Gamma = \{ p \rightarrow q, q \rightarrow r, r \rightarrow s \} \hspace{10 mm} \text{ where } \phi \text{ is } p \rightarrow s $$

Would I attempt this question by trying to prove that, for every formula $\psi \in \Gamma$, the valuation $v(\psi) = T$, based on the assumption that $v(\phi) = T$?

$\endgroup$
1
  • $\begingroup$ Regarding the second part, the answer is yes; with the said $\Gamma$ and $\phi$ it is true that $\Gamma \vDash \phi$. They are propositional calculus formukae; thus, to chek it it is enough to use valuations. Simple check: assume $v$ such that $v(\psi)=T$ for every $\psi \in \Gamma$ and see what happens to $\phi$: is it possible that $v(\phi)=F$? $\endgroup$ – Mauro ALLEGRANZA Feb 7 '17 at 12:19
4
$\begingroup$

Are you familiar with the notation $\mathfrak A\vDash \phi$, meaning that the structure $\mathfrak A$ satisfies $\phi$, or (in other words) $\phi$ is true in $\mathfrak A$?

$\Gamma\vDash \phi$ is then shorthand for:

$$ \forall \mathfrak A \bigl[ (\forall \psi\in\Gamma: \mathfrak A\vDash \psi) \;\to\; \mathfrak A\vDash\phi \bigr ] $$

Or, in words, $\phi$ is satisfied by every structure that satisfies all of $\Gamma$.

In yet other words, $\phi$ is true in every model of $\Gamma$.


If we're not speaking about ordinary first-order logic, something else may take the place of "structure" above -- for example, for propositional calculus, instead of $\forall\mathfrak A$ we would quantify over all truth assignments for the propositional variables in $\Gamma$ and $\phi$.

$\endgroup$

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.