Composite of Antisymmetric Relations is not necessarily Antisymmetric

From ProofWiki
Jump to navigation Jump to search


Let $A$ be a set.

Let $\RR$ and $\SS$ be antisymmetric relations on $A$.

Then their composite $\RR \circ \SS$ is not necessarily also antisymmetric.


Proof by Counterexample

Consider the ordering $\le$ on the natural numbers $\N$.

Consider its dual ordering $\ge$ also on $\N$.

Note that Dual Ordering is Ordering.

Both $\le$ and $\ge$ are a fortiori antisymmetric relations.

We have:

$1 \le 3$
$3 \ge 2$

and similarly:

$2 \le 3$
$3 \ge 1$

Hence it follows that:

$1 \le \circ \ge 2$

while at the same time:

$2 \le \circ \ge 1$

and so while both $\le$ and $\ge$ are antisymmetric, their composite $\le \circ \ge$ is not.

Hence the result.