Ordering on Partition Determines Preordering

Theorem

Let $S$ be a set.

Let $\PP$ be a partition of $S$.

Let $\phi: S \to \PP$ be the quotient mapping.

Let $\preceq$ be a ordering of $\PP$.

Define a relation $\precsim$ on $S$ by letting $p \precsim q$ if and only if:

$\map \phi p \preceq \map \phi q$

Then:

$\precsim$ is a preordering on $S$.

$\precsim$ is the only preordering on $S$ that induces the $\preceq$ ordering on $\PP$.

Proof

To show that $\precsim$ is a preordering we must show that it is reflexive and transitive.

Reflexive

Let $p \in S$.

Then $\map \phi p = \map \phi p$.

Since $\preceq$ is an ordering it is reflexive.

Thus $\map \phi p \preceq \map \phi p$.

By the definition of $\precsim$, $p \precsim p$.

As this holds for all $p \in S$, $\precsim$ is reflexive.

$\Box$

Transitive

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

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

By the definition of $\precsim$:

$\map \phi p \preceq \map \phi q$

$\map \phi q \preceq \map \phi r$

Since $\preceq$ is an ordering, it is transitive, so:

$\map \phi p \preceq \map \phi r$

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

As this holds for all such $p$, $q$, and $r$, $\precsim$ is transitive.

$\Box$

$\precsim$ induces the $\preceq$ ordering on $\PP$

Let $P, Q \in P$.

First suppose that $P \preceq Q$.

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

By the definition of quotient mapping:

$\map \phi p = P$ and $\map \phi q = Q$.

Thus $\map \phi p \preceq \map \phi q$.

So by the definition of $\precsim$:

$p \precsim q$

Suppose instead that for some $p \in P$ and $q \in Q$, $p \precsim q$.

Then by the definition of $\precsim$:

$\map \phi p \preceq \map \phi q$

By the definition of quotient mapping:

$\map \phi p = P$ and $\map \phi q = Q$.

Thus $P \preceq Q$.

$\Box$

$\struct {\PP, \preceq}$ is the Antisymmetric Quotient of $\struct {S, \precsim}$

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

First we show that $\PP = S / {\sim}$.

As both $\PP$ and $S/ {\sim}$ are partitions of $S$, we need only show that for $p, q \in S$:

$\map \phi p = \map \phi q \iff p \sim q$

First suppose that $p \sim q$.

By the definition of $\sim$:

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

Then by the definition of $\precsim$:

$\map \phi p \preceq \map \phi q$

$\map \phi q \preceq \map \phi p$

Since $\preceq$ is an ordering, and hence antisymmetric:

$\map \phi p = \map \phi q$

Suppose instead that $\map \phi p = \map \phi q$.

Since $\preceq$ is reflexive:

$\map \phi p \preceq \map \phi q$

$\map \phi q \preceq \map \phi p$

By the definition of $\precsim$:

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

By the definition of $\sim$:

$p \sim q$

Now we must show that for $P, Q \in \PP$:

$P \preceq Q \iff \exists p \in P: \exists q \in Q: p \precsim q$

Suppose that $P \preceq Q$.

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

Then $\map \phi p = P$ and $\map \phi q = Q$, so $p \precsim q$ by the definition of $\precsim$.

Suppose instead that $\exists p \in P: \exists q \in Q: p \precsim q$.

Then by the definition of $\precsim$, $P \preceq Q$.

$\Box$

$\precsim$ is Unique

Let $\precsim'$ be a preordering such that the antisymmetric quotient of $\struct {S, \precsim'}$ is $\struct {P, \preceq}$.

Let $p, q \in S$.

First suppose that $p \precsim' q$.

Then $\map \phi p \preceq \map \phi q$ by the definition of antisymmetric quotient.

Thus $p \precsim q$ by the definition of $\precsim$.

Suppose instead that $p \precsim q$.

Then $\map \phi p \preceq \map \phi q$ by the definition of $\precsim$.

Thus $p \precsim' q$ by the definition of antisymmetric quotient.

$\blacksquare$