Preordering induces Equivalence Relation

From ProofWiki
Jump to: navigation, search

Theorem

Let $\left({S, \precsim}\right)$ be a preordered set.

Define a relation $\sim$ on $S$ by letting $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