Show that if $G$ is an equivalence relation in $A$, then $G \circ G=G$

Question

This is my attempt of proving this proposition, but it is probably incorrect.

$G$ is an equivalence relation if it is:

1. Reflexive $$(x,x)\in G$$
2. Symmetric $$(x,y)\in G \Rightarrow (y,x)\in G$$
3. Transitive $$(x,y)\in G \wedge (y,z)\in G \Rightarrow(x,z)\in G$$

In order to prove the proposition we should prove that $G \subseteq G\circ G$ and $G\circ G \subseteq G$. The second on seems easy enough to prove:

$$(x,y)\in G\circ G \Rightarrow \exists z\in A \ni (x,z)\in G \wedge(z,y)\in G$$ Since $G$ is transitive, $$(x,y)\in G\circ G \Rightarrow (x,y)\in G$$ Therefore, $$G\circ G\subseteq G$$

For the converse,

$$(x,y)\in G \Rightarrow (x,x)\in G \wedge (x,y)\in G$$ Because $G$ is reflexive. So, $$(x,y)\in G \Rightarrow \exists z=x\in G \ni (x,z)\in G \wedge (z,y)\in G \Rightarrow (x,y)\in G\circ G$$ Therefore, $$G\subseteq G\circ G$$ QED.

However, I haven't utilised the Symmetry of $G$, so I suspect that the proof is not correct. Could anyone fix it?

Answer 1

Most of your proof is right except some informal use of symbols. I fix the proof as follows which may be a reference for you. But before that let me give the proposition to be proved.

Proposition 1. If $G$ is an equivalent relation, then $G\circ G=G$.

Proof. We show $G\circ G=G$ by two directions.

• $(\subseteq)$ This is because $$ \begin{array}{rcll} (x,y)\in G\circ G&\Longleftrightarrow&(x,z)\in G\text{ and }(z,y)\in G\text{ for some }z&\text{by the definition of }G\circ G\\ &\Longrightarrow&(x,y)\in G\text{ for some }z&\text{by transitivity of }G \\ &\Longleftrightarrow& (x,y)\in G&\text{by }\exists z\varphi(x,y)\leftrightarrow\varphi(x,y)\\ &&&\text{where }z\text{ is not free in }\varphi(x,y). \end{array} $$
• $(\supseteq)$ This is becuase $$ \begin{array}{rcll} (x,y)\in G&\Longleftrightarrow&(x,x)\in G\text{ and }(x,y)\in G&\text{by reflexivity of }G \\ &\Longrightarrow&(x,z)\in G\text{ and }(z,y)\in G\text{ for some }z&\text{by }\varphi(x,y,x)\to\exists z\varphi(x,y,z) \\ &\Longleftrightarrow&(x,y)\in G\circ G&\text{by the definition of }G\circ G. \end{array} $$

This completes the proof.

Remark 2. For the two formulas as the inference rules, if you learn little about first order logic, then you could regard them as valid rules in the natural language, and write nothing at the end of those two lines.

At last just as what @Rob Arthan and @Greg Martin observed, this proof can be through for reflexive and transitive relations. So Proposition 1 could be reformulated as Proposition 4 as follows.

Definition 3. Suppose $G$ is a binary relation. $G$ is a quasiorder or preorder if $G$ is reflexive and transitive.

Proposition 4. If $G$ is a quasiorder or preorder, then $G\circ G=G$.