1
$\begingroup$

I'm taking a knowledge representation class and need more perspective on basic model theory. We're currently using Levesque and Brachman.

Specifically, a question on the midterm was something like, "Given $\alpha$ $\beta$ and $\gamma$ are formulas, does $\alpha \models \beta \wedge \gamma$ imply $\alpha \models \beta$ or $\alpha \models \gamma$." I thought this was the case as if we have an interpretation that entails the disjunctions of two formulas then there is an if and only if concerning whether the interpretation entails both separately: $\mathfrak{I} \models \alpha \wedge \beta \iff \mathfrak{I} \models \alpha$ or $\mathfrak{I} \models \beta$. After the midterm I came across this explanation which made clear that entailment for interpretations have a different meaning then those for logical forumlas (or perhaps I'm confused here as well and not using the correct vernacular to describe the difference). From what I've read the difference is semantic consequence vs logical entailment.

Is there a book, set of notes, or write up that elucidates distinctions like this? If the distinction above is incorrect, then even naming it correctly would help.

As an aside here are some related questions:

When do we use entailment vs implication?

Semantic vs syntactic consequence

Implies vs. Entails vs. Provable

Edit:

I think my real issue here was that I misunderstood how commonly this topic was covered. I was unaware of my very superficial understanding of logic/models (e.g. basic predicate and first order covered in discrete math). From what I can tell now, I don't actually own an undergraduate level logic book nor have I really spent time with one.

I guess that changes the question to what are good undergraduate logic books. As there are many lists of this type I won't ask that you post them unless they're absolutely spectacular. (Mauro has already provided more than enough for me to get started).

$\endgroup$
4
$\begingroup$

You have to see any good Math Log textbook, like :

There is a clear link between the relation of logical implication between formulae and the relation of "being a model" between a structure and a formula.

We have :

DEFINITION [Enderton, page 88] : Let $\Gamma$ be a set of wffs, $\varphi$ a wff. Then $\Gamma$ logically implies $\varphi$, written $\Gamma \vDash \varphi$, iff for every structure $\mathfrak A$ for the language and every function $s : Var \to dom(\mathfrak A)$ such that $\mathfrak A$ satisfies every member of $\Gamma$ with $s$, $\mathfrak A$ also satisfies $\varphi$ with $s$.

We have that [Enderton, page 87] :

For a sentence [i.e. a formula without free variables] $\sigma$, either :

(a) $\mathfrak A$ satisfies $\sigma$ with every function $s : Var \to dom(\mathfrak A)$, or

(b) $\mathfrak A$ does not satisfy $\sigma$ with any such function.

If alternative (a) holds, then we say that $\sigma$ is true in $\mathfrak A$ (written $\mathfrak A \vDash \sigma$) or that $\mathfrak A$ is a model of $\sigma$.

In conclusion, assuming for simplicity sentences $\alpha, \beta, \gamma$, we have that :

$α \vDash β∧γ$ iff for every structure $\mathfrak A$, if $\mathfrak A \vDash \alpha$, then $\mathfrak A \vDash β∧γ$.

$\endgroup$
  • $\begingroup$ I see that my mistake was in failing to remember that bold if and only if. These definitions are great. I didn't know these would be handled in intro to logic books... (I was thinking it would've been more involved like a model theory book). Even if I did, your emphasis would have definitely helped. $\endgroup$ – J C Oct 29 '14 at 18:54
  • 1
    $\begingroup$ @JC - of course you can find them also in the introductory chapter of most model theory books, like : David Marker, Model theory : An introduction (2002), Ch.1 : Structures and Theories ... 1/2 $\endgroup$ – Mauro ALLEGRANZA Oct 29 '14 at 19:36
  • 1
    $\begingroup$ ... or Alexander Prestel & Charles Delzell, Mathematical Logic and Model Theory : A Brief Introduction (2011), Ch.1 : First-Order Logic. 2/2 $\endgroup$ – Mauro ALLEGRANZA Oct 29 '14 at 19:38

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.