Logic: Equivalence Relation

407 Views Asked by At

Let $\Gamma$ be a maximally consistent set of formulas of $\mathcal{L}$. For any two terms $\tau_1$ and $\tau_2$ of $\mathcal{L}$, define that $\tau_1 \cong_\Gamma \tau_2$ if and only if $(\tau_1=\tau_2)\in\Gamma$. Show that $\cong_\Gamma$ is an equivalence relation of terms of the language $\mathcal{L}$.


Can I check if what I am doing is right? Please point out any mistakes or lapses in syntax or notation! Sincere thanks!

Reflexive: Suppose to the contrary $(\tau_1=\tau_1)\notin\Gamma$. Then $\neg (\tau_1=\tau_1)\in \Gamma$. So, $\Gamma \vdash \neg(\tau_1=\tau_1)$.

But $\Gamma \vdash (\tau_1=\tau_1)$. $\therefore \Gamma$ is inconsistent.

Symmetric: Assume $\tau_1\cong\tau_2$. Then, ($\tau_1\cong\tau_2 )\in\Gamma$. So $(\tau_2 =\tau_1)\in\Gamma$.$\therefore\tau_2 \cong_\Gamma \tau_1$.

Transitive: Assume $\tau_1\cong_\Gamma \tau_2$, $\tau_2\cong_\Gamma \tau_3$.

Then $(\tau_1 =\tau_2) \in\Gamma$, $(\tau_2 = \tau_3)\in\Gamma$.

So, $\Gamma \vdash (\tau_1 = \tau_2)$ and $\Gamma \vdash (\tau_2 = \tau_3)$. So $\Gamma \vdash (\tau_1 = \tau_3)$.

Suppose to the contrary $(\tau_1\ncong \tau_3$. Then ($\tau_1 = \tau_3)\notin \Gamma$.

So, $\neg (\tau_1 = \tau_3)\in\Gamma$. $\Gamma \vdash \neg (\tau_1 = \tau_3)$.

$\Gamma$ is inconsistent. Contradiction.

1

There are 1 best solutions below

0
On BEST ANSWER

Why not first show (if it isn't already given) that if $\Gamma$ is max consistent, then if $\Gamma \vdash \varphi$ then $\varphi \in \Gamma$?

Then, Reflexive: $\Gamma \vdash \tau_1=\tau_1$ implies $\tau_1=\tau_1 \in \Gamma$ implies $\tau_1 \cong_\Gamma \tau_1$.

Transitive: You prove $\Gamma \vdash \tau_1 = \tau_3$, which implies $\tau_1 = \tau_3 \in \Gamma$ implies $\tau_1 \cong_\Gamma \tau_3$.

[Style point: the use of brackets round identity propositions is unnecessary.]