Ordering is Strict Ordering Union Diagonal Relation

From ProofWiki
Jump to: navigation, search


Theorem

Let $S$ be a set, and let $\mathcal R$ be a strict ordering on $S$.


Then $\mathcal R \cup \Delta_S$, where $\Delta_S$ is the diagonal relation, is an ordering on $S$.

Also, $\mathcal R$ is a strict total ordering iff $\mathcal R \cup \Delta_S$ is a total ordering.


Conversely, let $\mathcal R'$ be an ordering on $S$.


Then $\mathcal R' \setminus \Delta_S$ is a strict ordering on $S$.

Also, $\mathcal R'$ is a total ordering iff $\mathcal R' \setminus \Delta_S$ is a strict total ordering.


Proof

Proof of Strict Ordering union Diagonal Relation

Checking in turn each of the criteria for an ordering:

Reflexivity

From Subset of Union we have that $\Delta_S \subseteq \mathcal R \cup \Delta_S$.

Hence from Relation Contains Diagonal Relation iff Reflexive $\mathcal R \cup \Delta_S$ is reflexive.

$\Box$

Transitivity

Let $\left({a, b}\right) \in \mathcal R \cup \Delta_S$ and $\left({b, c}\right) \in \mathcal R \cup \Delta_S$.

Let $a, b, c \in S$, and suppose that $a \ne b$, $b \ne c$, and $c \ne a$.

Then it follows that $\left({a, b}\right) \ne \Delta_S$ and $\left({b, c}\right) \ne \Delta_S$.

That is, that $\left({a, b}\right) \in \mathcal R$ and $\left({b, c}\right) \in \mathcal R$

Because of transitivity of $\mathcal R$ it follows that $\left({a, c}\right) \in \mathcal R$ and so $\left({a, c}\right) \in \mathcal R \cup \Delta_S$ from Subset of Union.


Now suppose $a = b, b \ne c$.

Then $\left({a, b}\right) \in \Delta_S, \left({b, c}\right) \in \mathcal R$.

So $\left({a, b}\right) \in \mathcal R \cup \Delta_S, \left({b, c}\right) \in \mathcal R \cup \Delta_S$.

But as $a = b$ it follows that as $\left({b, c}\right) \in \mathcal R$ then $\left({a, c}\right) \in \mathcal R$ and so $\left({a, c}\right) \in \mathcal R \cup \Delta_S$.

Similarly for $a \ne b, b = c$.


Now suppose $a \ne b, a = c$.

This combination can't happen, because that would mean $\left({a, b}\right) \in \mathcal R, \left({b, a}\right) \in \mathcal R$ which can't happen as $\mathcal R$ is asymmetric by dint of it being a strict ordering.


Finally, let $a = b = c$.

Then $\left({a, b}\right) \in \Delta_S, \left({b, c}\right) \in \Delta_S$ and so from Diagonal Relation is Equivalence, $\left({a, c}\right) \in \Delta_S$.


All cases are covered, and in all cases $\left({a, b}\right) \in \mathcal R \cup \Delta_S, \left({b, c}\right) \in \mathcal R \cup \Delta_S \implies \left({a, c}\right) \in \mathcal R \cup \Delta_S$.

So $\mathcal R \cup \Delta_S$ is transitive.

$\Box$

Antisymmetry

Suppose $\left({a, b}\right) \in \mathcal R \cup \Delta_S$ and $\left({b, a}\right) \in \mathcal R \cup \Delta_S$.

As $\mathcal R$ is asymmetric, by dint of it being a strict ordering either $\left({a, b}\right) \notin \mathcal R$ or $\left({b, a}\right) \notin \mathcal R$ (or both).

Therefore at least one of $\left({a, b}\right) \in \Delta_S$ and $\left({b, a}\right) \Delta_S$.

By definition of $\Delta_S$ that means $a = b$.

So $\mathcal R \cup \Delta_S$ is antisymmetric.

$\Box$


So $R \cup \Delta_S$ has been shown to be reflexive, transitive and antisymmetric.

Hence by definition it is an ordering.

$\blacksquare$


Proof of Total Ordering

Let $\mathcal R$ be a strict total ordering on $S$.

Then:

$\forall x, y \in S: x \ne y \implies \left({x, y}\right) \in \mathcal R \lor \left({y, x}\right) \in \mathcal R$

But from Subset of Union we have that $\mathcal R \subseteq \mathcal R \cup \Delta_S$.

So:

$\forall x, y \in S: x \ne y \implies \left({x, y}\right) \in \mathcal R \cup \Delta_S \lor \left({y, x}\right) \in \mathcal R \cup \Delta_S$

So $\mathcal R \cup \Delta_S$ is an ordering which is connected.

That is, $\mathcal R \cup \Delta_S$ is a total ordering.


Now suppose that $\mathcal R$ is not a strict total ordering on $S$.

That is, $\mathcal R$ is not connected.

So:

$\exists x, y \in S: \left({x, y}\right) \notin \mathcal R \land \left({y, x}\right) \notin \mathcal R$

But if $x \ne y$ it follows that $\left({x, y}\right) \notin \Delta_S$.

So:

$\exists x, y \in S: \left({x, y}\right) \notin \mathcal R \cup \Delta_S \land \left({y, x}\right) \notin \mathcal R \cup \Delta_S$

demonstrating that if $\mathcal R$ is not a strict total ordering on $S$, then $\mathcal R \cup \Delta_S$ is similarly not a total ordering.

$\blacksquare$


Proof of Ordering difference Diagonal Relation

Checking in turn each of the criteria for a strict ordering:

Antireflexivity

From Set Difference Intersection with Second Set is Empty Set we have that $\mathcal R' \setminus \Delta_S$ is disjoint from $\Delta_S$.

Hence from Relation is Antireflexive iff Disjoint from Diagonal Relation $\mathcal R' \setminus \Delta_S$ is antireflexive.

$\Box$


Transitivity

Let $\left({a, b}\right) \in \mathcal R' \setminus \Delta_S$ and $\left({b, c}\right) \in \mathcal R' \setminus \Delta_S$.

By definition of set difference, $\left({a, b}\right) \notin \Delta_S$ and $\left({b, c}\right) \notin \Delta_S$.

Therefore $a \ne b$ and $b \ne c$.

From Set Difference is Subset it follows that $\left({a, b}\right) \in \mathcal R'$ and $\left({b, c}\right) \in \mathcal R'$.

By transitivity of $\mathcal R'$ we have that $\left({a, c}\right) \in \mathcal R'$.

Suppose $a = c$.

Then that would mean that $\left({a, b}\right) \in \mathcal R'$ and $\left({b, a}\right) \in \mathcal R'$.

But this can not happen as $\mathcal R'$, being an ordering, is antisymmetric, and that would mean $a = b$ and it's not.

So $a \ne c$.

But that means $\left({a, c}\right) \notin \Delta_S$.

So $\left({a, c}\right) \in \mathcal R' \setminus \Delta_S$.


So $\mathcal R' \setminus \Delta_S$ has been shown to be transitive.

$\Box$


Asymmetry

Let $\left({a, b}\right) \in \mathcal R' \setminus \Delta_S$.

By definition of set difference, $\left({a, b}\right) \notin \Delta_S$.

That means $a \ne b$.


From Set Difference is Subset we have that $\left({a, b}\right) \in \mathcal R'$.

By definition of ordering, it follows that $\left({b, a}\right) \notin \mathcal R'$ as $\mathcal R'$ is antisymmetric.

Hence $\left({b, a}\right) \notin \mathcal R' \setminus \Delta_S$.

So $\mathcal R' \setminus \Delta_S$ has been shown to be asymmetric.

$\Box$


$\mathcal R' \setminus \Delta_S$ has been shown to be antireflexive, transitive and asymmetric.

Hence by definition it is a strict ordering.

$\blacksquare$


Proof of Total Ordering

Let $\mathcal R'$ be a total ordering on $S$.

Then:

$\forall x, y \in S: x \ne y \implies \left({x, y}\right) \in \mathcal R' \lor \left({y, x}\right) \in \mathcal R'$


But as $x \ne y$ it follows that $\left({x, y}\right) \notin \Delta_S$ and so $\left({x, y}\right) \in \mathcal R' \setminus \Delta_S$ .

So:

$\forall x, y \in S: x \ne y \implies \left({x, y}\right) \in \mathcal R' \setminus \Delta_S \lor \left({y, x}\right) \in \mathcal R' \setminus \Delta_S$

That is,

So $\mathcal R' \setminus \Delta_S$ is a strict ordering which is connected.

That is, $\mathcal R' \setminus \Delta_S$ is a strict total ordering.


Now suppose that $\mathcal R'$ is not a total ordering on $S$.

That is, $\mathcal R'$ is not connected.

So:

$\exists x, y \in S: \left({x, y}\right) \notin \mathcal R' \land \left({y, x}\right) \notin \mathcal R'$

But if $\left({x, y}\right) \notin \mathcal R'$ then $\left({x, y}\right) \notin \mathcal R' \setminus \Delta_S$ from Set Difference is Subset.

So it follows directly that:

$\exists x, y \in S: \left({x, y}\right) \notin \mathcal R' \setminus \Delta_S \land \left({y, x}\right) \notin \mathcal R' \setminus \Delta_S$

demonstrating that if $\mathcal R'$ is not a total ordering on $S$, then $\mathcal R \cup \Delta_S$ is similarly not a strict total ordering.

$\blacksquare$