A Mathematical Introduction to Logic -- Section 2.2 -- Problem 2 Solution
\(\def\PROOF{\sf{P\scriptsize ROOF}.\quad}\)
Problem 2
Show that no one of the following sentences is logically implied by the other two. (This is done by giving a structure in which the sentence in question is false, while the other two are true.)
- \(\forall{x}\forall{y}\forall{z}(Pxy\rightarrow Pyz\rightarrow Pxz).\) Recall that by our convention \(\alpha\rightarrow\beta\rightarrow\gamma\) is \(\alpha\rightarrow(\beta\rightarrow\gamma).\)
- \(\forall{x}\forall{y}(Pxy\rightarrow Pyx\rightarrow x=y).\)
- \(\forall{x}\exists{y}Pxy\rightarrow\exists{y}\forall{x}Pxy.\)
\(\PROOF\)
Let above wff in a,b and c be \(\alpha\), \(\beta\) and \(\gamma\).
- \(\alpha\) is a transitive relation
- \(\beta\) is a anti-symmetric relation
- \(\gamma\) describe a relation in which if for every element, there is a greater one then there is a maximal element.
Three different structures will be constructed below in which one sentence in question is false, while the other two are true.
\({\frak A} = ({\Bbb N};\forall,=,\le)\), in which
- \(|{\frak A}| = {\Bbb N}\)
- \(P_{\frak A} = \le\)
Then obviously \(\vDash_{\frak A}\alpha\), \(\vDash_{\frak A}\beta\), but \(\nvDash_{\frak A}\gamma\). So \(\{\alpha,\beta\}\nvDash\gamma\)
Say that \({\frak B}\) is defined as below:
- \(|{\frak B}| = \{a,b\}\)
- \(P_{\frak B} = \{\langle a,a\rangle,\langle a,b\rangle,\langle b,a\rangle,\langle b,b\rangle\}\)
Then obviously \(\vDash_{\frak B}\alpha\), \(\vDash_{\frak B}\gamma\). But \(\nvDash_{\frak B}\beta\) because \(Pab\), \(Pba\) exists, but \(a\neq b\). So \(\{\alpha,\gamma\}\nvDash\beta\).
Say that \({\frak C}\) is defined as below:
- \(|{\frak C}| = \{a,b,c\}\)
- \(P_{\frak C} = \{\langle a,b\rangle,\langle b,c\rangle\}\)
Then \(\vDash_{\frak C}\beta\), because there is no \(x\) and \(y\) such that \(Pxy\) and \(Pyx\). \(\vDash_{\frak B}\gamma\) because not for every \(x\) there is \(y\) such that \(Pxy\). But \(\nvDash_{\frak B}\alpha\) because there is no \(Pac\). \(\{\beta,\gamma\}\nvDash\alpha\)
In summary, no one of the three sentences in question is logically implied by the other two.\(\dashv\)