# Ordering is Strict Ordering Union Diagonal Relation

 It has been suggested that this page or section be merged into Reflexive Reduction of Ordering is Strict Ordering. (Discuss)
 It has been suggested that this page or section be merged into Reflexive Closure of Strict Ordering is Ordering. (Discuss)

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