Ordering on Partition Determines Preordering

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\mathcal P$ be a partition of $S$.

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

Let $\preceq$ be a ordering of $\mathcal P$.

Define a relation $\precsim$ on $S$ by letting $p \precsim q$ iff:

$\phi \left({p}\right) \preceq \phi \left({q}\right)$


Then:

$\precsim$ is a preordering on $S$.
$\precsim$ is the only preordering on $S$ that induces the $\preceq$ ordering on $\mathcal P$.


Proof

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

Reflexive

Let $p \in S$.

Then $\phi \left({p}\right) = \phi \left({p}\right)$.

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

Thus $\phi \left({p}\right) \preceq \phi \left({p}\right)$.

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$:

$\phi \left({p}\right) \preceq \phi \left({q}\right)$
$\phi \left({q}\right) \preceq \phi \left({r}\right)$

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

$\phi \left({p}\right) \preceq \phi \left({r}\right)$

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 $\mathcal P$

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:

$\phi \left({p}\right) = P$ and $\phi \left({q}\right) = Q$.

Thus $\phi \left({p}\right) \preceq \phi \left({q}\right)$.

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$:

$\phi \left({p}\right) \preceq \phi \left({q}\right)$

By the definition of quotient mapping:

$\phi \left({p}\right) = P$ and $\phi \left({q}\right) = Q$.

Thus $P \preceq Q$.

$\Box$


$\left({\mathcal P, \preceq}\right)$ is the Antisymmetric Quotient of $\left({S, \precsim}\right)$

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

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

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

$\phi \left({p}\right) = \phi \left({q}\right) \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$:

$\phi \left({p}\right) \preceq \phi \left({q}\right)$
$\phi \left({q}\right) \preceq \phi \left({p}\right)$

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

$\phi \left({p}\right) = \phi \left({q}\right)$


Suppose instead that $\phi \left({p}\right) = \left({q}\right)$.

Since $\preceq$ is reflexive:

$\phi \left({p}\right) \preceq \phi \left({q}\right)$
$\phi \left({q}\right) \preceq \phi \left({p}\right)$

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 \mathcal P$:

$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 $\phi \left({p}\right) = P$ and $\left({q}\right) = 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 $\left({S, \precsim'}\right)$ is $\left({P, \preceq}\right)$.

Let $p, q \in S$.

First suppose that $p \precsim' q$.

Then $\phi \left({p}\right) \preceq \left({q}\right)$ by the definition of antisymmetric quotient.

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

Suppose instead that $p \precsim q$.

Then $\phi \left({p}\right) \preceq \left({q}\right)$ by the definition of $\precsim$.

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

$\blacksquare$