The following problem is exercise 2.5.2 from "Mathematical Logic" by Ian Chiswell and Wilfrid Hodges (2007). I feel that the part about symmetry and transivity is a bit verbose and somewhat clumsy. How can I express that part more concisely?

2.5.2. Let $S$ be any set of statements, and let $\sim$ be the relation on S defined by: for all $\phi,\psi \in S$, $$ \phi\sim\psi\quad\text{if and only if}\quad\vdash(\phi\leftrightarrow\psi) $$ Show that $\sim$ is an equivalence relation on S. That is, it has the three properties:

  • (Reflexive) For all $\phi$ in $S$, $\phi\sim\phi$.
  • (Symmetric) For all $\phi$ and $\psi$ in $S$, if $\phi\sim\psi$ then $\psi\sim\phi$.
  • (Transitive) For all $\phi,\psi$, and $\chi$ in $X$, if $\phi\sim\psi$ and $\psi\sim\chi$ then $\phi\sim\chi$.

[For reflexivity use (b) of Exercise 2.5.1. With a little more work, (c) and Example 2.5.1 give transitivity and symmetry.]

(Reflexive) Let $\phi$ be a statement in $S$. Since $\phi\to\phi$ and $\phi\leftarrow\phi$, $\phi\leftrightarrow\phi$. Thus, $\vdash\phi\leftrightarrow\phi$. This means $\phi\sim\phi$ for all $\phi$ in $S$.

(Symmetric) Let $\phi$ and $\psi$ be statements in $S$. Assume $\phi\sim\psi$. By the definition of $\sim$, $\vdash(\phi\leftrightarrow\psi)$ holds. From $\vdash(\phi\leftrightarrow\psi)$, it follows that $\psi\to\phi$ and $\psi\leftarrow\phi$. Thus, if $\phi\sim\psi$, by ($\leftrightarrow$I), $\vdash\psi\leftrightarrow\phi$, and by the definition of $\sim$, $\psi\sim\phi$.

(Transitive) Let $\phi,\psi$, and $\chi$ be statements in $X$. Assume $\phi\sim\psi$ and $\psi\sim\chi$. By the definition of $\sim$, $\vdash\phi\leftrightarrow\psi$ and $\vdash\psi\leftrightarrow\chi$. By ($\leftrightarrow$E), $\phi\to\psi$, $\psi\to\chi$, $\chi\to\psi$, and $\psi\to\phi$. Since $\to$ is transitive, $\phi\to\chi$ and $\phi\leftarrow\chi$. By ($\leftrightarrow$I), $\phi\leftrightarrow\chi$. Therefore, if $\phi\sim\psi$ and $\psi\sim\chi$, then $\vdash\phi\leftrightarrow\chi$, and, by the definition of $\sim$, $\phi\sim\chi$.

  • 1
    $\begingroup$ Avoid "plain text" and write down the Natural Derivation proof trees needed... $\endgroup$ – Mauro ALLEGRANZA Dec 15 '15 at 11:24

In the transitive case, you might make the use of $\leftarrow$ more consistent. You could also avoid repeating the assumption and the definition of $\sim$ in the conclusion, so the last sentence would be simply "Therefore, $\vdash \phi\leftrightarrow\chi$, thus $\phi\sim\chi$." Oh, and it starts by saying, "Let ... be statements in $X$" — I'd correct $X$ to $S$ :) [It's not an error that you introduced when rendering into MSE markup: it's in the original LaTeX that you included in your question earlier.]

The reflexive case I'd leave alone.


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.