Strict Ordering can be Expanded to Compare Additional Pair/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({S, \prec}\right)$ be an ordered set.

Let $a$ and $b$ be distinct, $\prec$-incomparable elements of $S$.

That is, let:

$a \not \prec b$ and $b \not \prec a$.

Let ${\prec'} = {\prec} \cup \left\{ {\left({a, b}\right)} \right\}$.

Define a relation $\prec'^+$ by letting $p \prec'^+ q$ if and only if:

$p \prec q$

or:

$p \preceq a$ and $b \preceq q$

where $\preceq$ is the reflexive closure of $\prec$.


Then:

$\prec'^+$ is a strict ordering
$\prec^+$ is the transitive closure of $\prec'$.


Proof

First, note that since $\prec$ is a strict ordering, $\preceq$ is an ordering by Reflexive Closure of Strict Ordering is Ordering.

$a$ and $b$ are $\preceq$-incomparable

Suppose that $a \preceq b$.

By the definition of reflexive closure, either $a \prec b$ or $a = b$.

Each possibility contradicts one of the premises, so $a \not \preceq b$.

For the same reasons, $b \not \preceq a$.

$\Box$


$\prec'^+$ is antireflexive

Let $p \in S$.

Then by the definition of strict ordering:

$p \not\prec p$.

Suppose that $p \preceq a$ and $b \preceq p$.

Then since $\preceq$ is transitive, $b \preceq a$, contradicting the fact that $a$ and $b$ are $\preceq$-incomparable.

Since neither $p \prec p$ nor $\paren {p \preceq a \land \paren {b \preceq p}$ holds:

$p \not \prec'^+ p$.

Since this is the case for all $p \in S$, $\prec'^+$ is antireflexive.

$\Box$


$\prec'^+$ is transitive

Let $p \prec'^+ q$ and $q \prec'^+ r$.

Then there are three possibilities:

$(1): \quad p \prec q$ and $p \prec r$

Because $\prec$ is transitive:

$p \prec r$

Thus:

$p \prec'^+ r$


$(2): \quad p \prec q$, $q \preceq a$, and $b \preceq r$

By Extended Transitivity, $p \prec a$.

Since $p \prec a$ and $b \prec r$:

$p \prec'^+ r$


$(3): \quad p \preceq a$, $b \preceq q$, and $q \prec r$

By Extended Transitivity:

$b \prec r$

Therefore:

$b \preceq r$

Since $p \preceq a$ and $b \preceq r$:

$p \prec'^+ r$


Note that it is impossible to have $p \preceq a$, $b \preceq q$, $q \preceq a$ and $b \preceq r$.

If that were so, $b \preceq q$ and $q \preceq a$ together would imply by transitivity that $b \preceq a$.

But this contradicts the fact that $a$ and $b$ are $\preceq$-incomparable.

Thus in all cases, $p \prec'^+ q$ and $q \prec'^+ r$ imply $p \prec'^+ r$, so $\prec'^+$ is transitive.

$\Box$

Since $\prec'^+$ is transitive and antireflexive, it is by definition a strict ordering.


$\prec'^+$ is the transitive closure of $\prec'$

First note that $\prec'$ is a subset of $\prec'^+$:

If $p \prec' q$ then either

$p \prec q$ or
$p = a$ and $q = b$

If $p \prec q$ then $p \prec'^+ q$ by definition.

If $p = a$ and $q = b$, then $p \preceq a$ and $q \preceq b$ by the definition of $\preceq$.

Thus $p \prec'^+ q$ by the definition of $\preceq'^+$.


Let $\mathcal R$ be a transitive relation containing $\prec'$.

Let $p, q \in S$ and let $p \prec'^+ q$.

Then either:

$p \prec q$ or
$p \preceq a$ and $b \preceq q$

If $p \prec q$, then by the definition of subset, $p \mathrel {\mathcal R} q$.

Suppose instead that $p \preceq a$ and $b \preceq q$. By the definition of $\preceq'$, $a \preceq' b$.

Since Reflexive Closure is Closure Operator, it is increasing, so $\preceq \subseteq \mathcal R^=$.

Thus $p \mathrel {\mathcal R}^= a$, $a \mathrel {\mathcal R}^= b$, and $b \mathrel {\mathcal R}^= q$.

Since $\mathcal R$ is transitive, $\mathcal R^=$ is as well, by Reflexive Closure of Transitive Relation is Transitive.

Thus $p \mathrel {\mathcal R}^= q$.

Since $\preceq'^+$ is antireflexive and we assumed $p \preceq'^+ q$, we conclude that $p \ne q$.

Thus by the definition of reflexive closure:

$p \mathrel {\mathcal R} q$

Thus we have shown that $\preceq'^+$ is a subset of $\mathcal R$.

Since this holds when $\mathcal R$ is any transitive superset of $\preceq'$, $\preceq'^+$ is the transitive closure of $\preceq'$.

$\blacksquare$