Antisymmetric Quotient of Preordered Set is Ordered Set

From ProofWiki
Jump to: navigation, search

Theorem

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

Let $\sim$ be the equivalence relation on $S$ induced by $\precsim$.

Let $\left({S / {\sim}, \preceq}\right)$ be the antisymmetric quotient of $\left({S, \precsim}\right)$.


Then:

$\left({S / {\sim}, \preceq}\right)$ is an ordered set.
$\forall P, Q \in S / {\sim}: \left({P \preceq Q}\right) \land \left({p \in P}\right) \land \left({q \in Q}\right) \implies p \precsim q$


This second statement means that we could just as well have defined $\preceq$ by letting $P \preceq Q$ iff:

$\forall p \in P: \forall q \in Q: p \precsim q$


Proof

By the definition of equivalence relation, $\sim$ is transitive, reflexive, and symmetric.

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

To show that $\preceq$ is an Definition:ordering, we must show that it is transitive, reflexive, and antisymmetric.


Transitive

Let $P, Q, R \in S / {\sim}$.

Suppose that $P \preceq Q$ and $Q \preceq R$.

Then for some $p \in P$, $q_1, q2 \in Q$, and $r \in R$:

$p \precsim q_1$ and $q_2 \precsim r$.

By the definition of quotient set, $q_1 \sim q_2$.

By the definition of $\sim$:

$q_1 \precsim q_2$

Since $p \precsim q_1$, $q_1 \precsim q_2$, $q_2 \precsim r$, and $\precsim$ is transitive, Transitive Chaining shows that:

$p \precsim r$

Thus by the definition of $\preceq$:

$P \preceq R$.

Since this holds for all such $P$, $Q$, and $R$, $\preceq$ is transitive.

$\Box$


Reflexive

Let $P \in S / {\sim}$.

By the definition of quotient set, $P$ is non-empty.

Thus there exists a $p \in P$.

Since $\precsim$ is a preordering, it is reflexive, so $p \precsim p$.

By definition of the equivalence relation do we have that $q\sim p$ for any other $q\in P$

This gives that $q\sim p \precsim p$ which is equivalent to $q \precsim p \precsim p$ by definition of the equivalence relation.

It also gives that $p \precsim p \precsim q$ by similar reasoning.

Both by transitivity gives $p\precsim q$ and $q\precsim p$

This gives us that $P\preceq P$

As this holds for all $P \in S / {\sim}$, $\preceq$ is reflexive.

$\Box$


Antisymmetric

Let $P, Q \in S / {\sim}$ such that:

$P \preceq Q$
$Q \preceq P$

By the definition of $\preceq$, there are elements $p_1, p_2 \in P$ and $q_1, q_2 \in Q$ such that:

$(1)\quad p_1 \precsim q_1$
$(2)\quad q_2 \precsim p_2$

Let $p \in P$.

Then by the definition of quotient set:

$p \sim p_1$
$p_2 \sim p$

By the definition of $\sim$:

$p \precsim p_1$
$p_2 \precsim p$

Thus by $(1)$ and $(2)$ and the fact that $\precsim$ is transitive:

$p \precsim q_1$
$q_2 \precsim p$

By the definition of quotient set:

$q_1 \sim q_2$

Thus by the definition of $\sim$:

$q_1 \precsim q_2$

Since $\precsim$ is transitive:

$p \precsim q_2$

We already know that:

$q_2 \precsim p$

Thus $p \sim q_2$.

By the definition of quotient set, $p \in Q$.

The same argument shows that each element of $Q$ is also in $P$.

Thus by the Axiom of Extension, $P = Q$.

As this holds for all such $P, Q \in S / {\sim}$, $\preceq$ is antisymmetric.

$\Box$


Relation between Sets implies all their Elements are Related

Let $P, Q \in S / {\sim}$ with $P \preceq Q$.

Then by the definition of $\preceq$, there are $p \in P$ and $q \in Q$ such that $p \precsim q$.

Let $p' \in P$ and $q' \in Q$.

By the definition of quotient set:

$p' \sim p$
$q \sim q'$

Thus by the definition of $\sim$:

$p' \precsim p$
$q \precsim q'$

Since $p \precsim q$ and $\precsim$ is transitive:

$p' \precsim q'$

We have shown that:

$\forall P, Q \in S / {\sim}: \left({P \preceq Q}\right) \land \left({p \in P}\right) \land \left({q \in Q}\right) \implies p \precsim q$

$\blacksquare$


Sources