# Let $S$ be any set of statements. How do I concisely show that $\sim$ is reflexive, symmetric, and transitive on $S$?

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$.

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

## 1 Answer

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.