2

I was given this excercise and find myself unable to tackle it (beginner here):

Prove that $\models$ is transitive, i.e. prove that if $\varphi\models\psi$ and $\psi\models\chi$, then $\varphi\models\chi$.

Similarily, prove that $\vdash$ is transitive, i.e. prove that if $\varphi\vdash\psi$ and $\psi\vdash\chi$, then $\varphi\vdash\chi$.

Thank you for any suggestions on how to approach this!

Alzbeta
  • 39
  • what does |= and |- mean? – Asinomás Jun 04 '14 at 15:10
  • Are $|=$ and $|-$ intended to be $\Rightarrow$ and $\rightarrow$? – Pockets Jun 04 '14 at 15:14
  • no, I am sorry I am using the notation we were given in class, where we use |= to indicate semantic validity and |− to indicate syntactic validity. – Alzbeta Jun 04 '14 at 15:17
  • 1
    @Bananarama : In standard usage $\alpha\models\beta$ means $\beta$ is true in every structure in which $\alpha$ is true, and $\alpha\vdash\beta$ means $\beta$ can be deduced from $\alpha$. Certainly neither of those is the same as $\alpha\to\beta$. ${}\qquad{}$ – Michael Hardy Jun 04 '14 at 16:13
  • @SamuelLijin : See my comment above. – Michael Hardy Jun 04 '14 at 16:13

1 Answers1

6

The definition of "$\vDash$" (the relation of entailment or logical consequence) is :

$\varphi \vDash \psi$ iff for every interpretation $\mathcal M$, if $\varphi$ is true in $\mathcal M$, then also $\psi$ is true in $\mathcal M$.

Thus, if we have :

$\varphi \vDash \psi$ and $\psi \vDash \chi$,

clearly in every interpretation $\mathcal M$ in which $\varphi$ is true, having that also $\psi$ is, and because in every interpretation in which $\psi$ is true also $\chi$ is, we may conlcude that in every interpretation $\mathcal M$ in which $\varphi$ is true, also $\chi$ is true, i.e. :

$\varphi \vDash \chi$.

Regarding the derivation relation : $\varphi \vdash \psi$, again by definition :

$\psi$ is derivable form $\varphi$ iff there is a finite sequence of formulae $\psi_1, ..., \psi_n$ such that : $\psi_n$ is $\psi$ and each $\psi_i$, $1 \le i \le n$ can be :

(i) $\varphi$, or

(ii) a logical axiom, or

(iii) derived by previous formulae in the sequence through an inference rule, i.e. assuming that modus ponens is the only inference rule, we have $1 \le j,k < i$ such that $\psi_k$ is $\psi_j \rightarrow \psi_i$.

Having said that, starting form the derivations $\varphi \vdash \psi$ and $\psi \vdash \chi$, it is enough to "concatenate" them; the resulting sequence of formulae will satisfy the above definition and it will end with $\chi$.

Thus, it will be a derivation of $\chi$ from $\varphi$, i.e. :

$\varphi \vdash \chi$.

Community
  • 1
Mauro ALLEGRANZA
  • 94,169
  • thank you, this is perfect, very helpful! – Alzbeta Jun 04 '14 at 15:25
  • thanks for the second one as well,again, extremely helpful and I see where was my mistake now – Alzbeta Jun 04 '14 at 15:41
  • 1
    @Alzbeta - you are welcome ! If you want to be "perfect" you have to add to the "concatenation" of the two derivations an additional "clean up", i.e. when you copy paste the second one, you have to delete the unnecessary occurrences of $\psi$ in it, because the corresponding step are already "covered" by the first part of the new derivation which terminates with $\psi$. – Mauro ALLEGRANZA Jun 04 '14 at 15:44
  • @MauroALLEGRANZA I think you can avoid the cleanup if an you have an inference rule $\phi\vdash\phi$ in your toolbox. – Hagen von Eitzen Jun 04 '14 at 15:47
  • 1
    @HagenvonEitzen - of course, you are right ! But, according to the "rough" definition of derivation I've used above, I have to "justify" each step writing it in the sequence. The first derivation ends with $\psi$; thus, when in the second one I "call" the assumption $\psi$, I have to copy it in the sequence. Merging the two, the second occurrence of $\psi$ is not really necessary, because each step in the second part which uses it e.g. as a premise in modus ponens can directly use the first occurrence (the last formula in the "old" first derivation) ... – Mauro ALLEGRANZA Jun 04 '14 at 15:54
  • Actually, no clean-up is needed for the raw concatenated sequence to be a valid proof sequence: each occurrence of $\psi$ in the second half can be justified in the same way as the final line in the first half. – hmakholm left over Monica Jun 08 '15 at 21:38