Preordering induces Equivalence Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \RR}$ be a relational structure such that $\RR$ is a preordering.

Let $\sim$ be the relation induced by $\RR$:

$x \sim y$ if and only if $x \precsim y$ and $y \precsim x$.


Then $\sim$ is an equivalence relation.


Proof

To show that $\sim$ is an equivalence relation, we must show that it is reflexive, transitive, and symmetric.

By the definition of preordering, $\precsim$ is transitive and reflexive.


Transitive

Let $p, q, r \in S$.

Suppose that $p \sim q$ and $q \sim r$.

Then $p \precsim q$, $q \precsim r$, $r \precsim q$, and $q \precsim p$.

Since $\precsim$ is transitive:

$p \precsim r$ and $r \precsim p$.

Thus by the definition of $\sim$, $p \sim r$.

Since this holds for all $p$, $q$, and $r$, $\sim$ is transitive.

$\Box$


Reflexive

Let $p \in S$.

Since $\precsim$ is reflexive:

$p \precsim p$

Thus by the definition of $\sim$:

$p \sim p$

As this holds for all $p$, $\sim$ is reflexive.

$\Box$


Symmetric

Let $p, q \in S$ with $p \sim q$.

Then $p \precsim q$ and $q \precsim p$.

Thus $q \sim p$.

Since this holds for all $p$ and $q$, $\sim$ is symmetric.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Preordering_induces_Equivalence_Relation&oldid=523029"