# Antisymmetric Quotient of Preordered Set is Ordered Set

## Contents

## Theorem

Let $\struct {S, \precsim}$ be a preordered set.

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

Let $\struct {S / {\sim}, \preceq}$ be the antisymmetric quotient of $\struct {S, \precsim}$.

Then:

- $\struct {S / {\sim}, \preceq}$ is an ordered set.

- $\forall P, Q \in S / {\sim}: \paren {P \preceq Q} \land \paren {p \in P} \land \paren {q \in Q} \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 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, 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}: \paren {P \preceq Q} \land \paren {p \in P} \land \paren {q \in Q} \implies p \precsim q$

$\blacksquare$

## Sources

- 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: Further exercises: $5$