Inverse Relation Properties

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathcal R$ be a relation on a set $S$.

If $\mathcal R$ has any of the properties:

... then its inverse $\mathcal R^{-1}$ has the same properties.


Proof

Reflexivity

\(\displaystyle x\) \(\in\) \(\displaystyle S\)
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, x}\right)\) \(\in\) \(\displaystyle \mathcal R\) Definition of Reflexive Relation
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, x}\right)\) \(\in\) \(\displaystyle \mathcal R^{-1}\) Definition of Inverse Relation

Hence the result by definition of reflexive relation.

$\blacksquare$


Antireflexivity

\(\displaystyle x\) \(\in\) \(\displaystyle S\)
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, x}\right)\) \(\notin\) \(\displaystyle \mathcal R\) by definition of antireflexive relation
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, x}\right)\) \(\notin\) \(\displaystyle \mathcal R^{-1}\) by definition of inverse relation

Hence the result by definition of antireflexive relation.

$\blacksquare$


Non-Reflexivity

Let $\mathcal R$ be non-reflexive.


Then:

\(\displaystyle \exists x \in S: \left({x, x}\right)\) \(\in\) \(\displaystyle \mathcal R\) as $\mathcal R$ is not antireflexive
\(\displaystyle \implies \ \ \) \(\displaystyle \exists x \in S: \left({x, x}\right)\) \(\in\) \(\displaystyle \mathcal R^{-1}\) by definition of inverse relation

Thus $\mathcal R^{-1}$ is not antireflexive.


Also:

\(\displaystyle \exists x \in S: \left({x, x}\right)\) \(\notin\) \(\displaystyle \mathcal R\) as $\mathcal R$ is not reflexive
\(\displaystyle \implies \ \ \) \(\displaystyle \exists x \in S: \left({x, x}\right)\) \(\notin\) \(\displaystyle \mathcal R^{-1}\) by definition of inverse relation

Thus $\mathcal R^{-1}$ is not reflexive.


Hence the result, by definition of non-reflexive relation.

$\blacksquare$


Symmetry

Let $\mathcal R$ be symmetric.

Then from Relation equals Inverse iff Symmetric it follows that $\mathcal R^{-1}$ is also symmetric.

$\blacksquare$


Asymmetry

Let $\mathcal R$ be asymmetric.

Then:

$\left({x, y}\right) \in \mathcal R \implies \left({y, x}\right) \notin \mathcal R$

Thus if $\left({x, y}\right) \in \mathcal R$ then:

$\left({y, x}\right) \in \mathcal R^{-1}$ and $\left({x, y}\right) \notin \mathcal R^{-1}$

Thus it follows that $\mathcal R^{-1}$ is also asymmetric.

$\blacksquare$


Antisymmetry

Let $\mathcal R$ be antisymmetric.

Then:

$\left({x, y}\right) \land \left({y, x}\right) \in \mathcal R \implies x = y$

It follows that:

$\left({y, x}\right) \land \left({x, y}\right)\in \mathcal R^{-1} \implies x = y$

Thus it follows that $\mathcal R^{-1}$ is also antisymmetric.

$\blacksquare$


Non-Symmetry

Let $\mathcal R$ be non-symmetric.

Then:

$\exists \left({x_1, y_1}\right) \in \mathcal R \implies \left({y_1, x_1}\right) \in \mathcal R$

and also:

$\exists \left({x_2, y_2}\right) \in \mathcal R \implies \left({y_2, x_2}\right) \notin \mathcal R$

Thus:

$\exists \left({y_1, x_1}\right) \in \mathcal R^{-1} \implies \left({x_1, y_1}\right) \in \mathcal R^{-1}$

and also:

$\exists \left({y_2, x_2}\right) \in \mathcal R^{-1} \implies \left({x_2, y_2}\right) \notin \mathcal R^{-1}$

and so $\mathcal R^{-1}$ is non-symmetric.

$\blacksquare$


Transitivity

Let $\mathcal R$ be a relation on a set $S$.

Let $\mathcal R$ be transitive.


Then its inverse $\mathcal R^{-1}$ is also transitive.


Antitransitivity

Let $\mathcal R$ be antitransitive.

Then:

$\left({x, y}\right), \left({y, z}\right) \in \mathcal R \implies \left({x, z}\right) \notin \mathcal R$

Thus:

$\left({y, x}\right), \left({z, y}\right) \in \mathcal R^{-1} \implies \left({z, x}\right) \notin \mathcal R^{-1}$

and so $\mathcal R^{-1}$ is antitransitive.

$\blacksquare$


Non-Transitivity

Let $\mathcal R$ be non-transitive.

Then:

$\exists x_1, y_1, z_1 \in S: \left({x_1, y_1}\right), \left({y_1, z_1}\right) \in \mathcal R, \left({x_1, z_1}\right) \in \mathcal R$
$\exists x_2, y_2, z_2 \in S: \left({x_2, y_2}\right), \left({y_2, z_2}\right) \in \mathcal R, \left({x_2, z_2}\right) \notin \mathcal R$


So:

$\exists x_1, y_1, z_1 \in S: \left({y_1, x_1}\right), \left({z_1, y_1}\right) \in \mathcal R^{-1}, \left({z_1, x_1}\right) \in \mathcal R^{-1}$
$\exists x_2, y_2, z_2 \in S: \left({y_2, x_2}\right), \left({z_2, y_2}\right) \in \mathcal R^{-1}, \left({z_2, x_2}\right) \notin \mathcal R^{-1}$

So $\mathcal R^{-1}$ is non-transitive.

$\blacksquare$