Properties of Restriction of Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\mathcal R \subseteq S \times S$ be a relation on $S$.


Let $T \subseteq S$ be a subset of $S$.

Let $\mathcal R \restriction_T \ \subseteq T \times T$ be the restriction of $\mathcal R$ to $T$.


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

... then $\mathcal R \restriction_T$ on $T$ has the same properties.


Proof

Reflexivity

Restriction of Reflexive Relation is Reflexive

Suppose $\mathcal R$ is reflexive on $S$.

Then:

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

So:

$\forall x \in T: \left({x, x}\right) \in \mathcal R {\restriction_T}$

Thus $\mathcal R {\restriction_T}$ is reflexive on $T$.

$\blacksquare$


Restriction of Antireflexive Relation is Antireflexive

Suppose $\mathcal R$ is antireflexive on $S$.

Then:

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

So:

$\forall x \in T: \left({x, x}\right) \notin \mathcal R \restriction_T$

Thus $\mathcal R \restriction_T$ is antireflexive on $T$.

$\blacksquare$


Symmetry

Restriction of Symmetric Relation is Symmetric

Suppose $\mathcal R$ is symmetric on $S$.


Then:

\(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \mathcal R {\restriction_T}\)
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \left({T \times T}\right) \cap \mathcal R\) Definition of Restriction of Relation
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle T \times T\)
\(\, \displaystyle \land \, \) \(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \mathcal R\) Definition of Set Intersection
\(\displaystyle \implies \ \ \) \(\displaystyle \left({y, x}\right)\) \(\in\) \(\displaystyle T \times T\)
\(\, \displaystyle \land \, \) \(\displaystyle \left({y, x}\right)\) \(\in\) \(\displaystyle \mathcal R\) $\mathcal R$ is symmetric on $S$
\(\displaystyle \implies \ \ \) \(\displaystyle \left({y, x}\right)\) \(\in\) \(\displaystyle \left({T \times T}\right) \cap \mathcal R\) Definition of Set Intersection
\(\displaystyle \implies \ \ \) \(\displaystyle \left({y, x}\right)\) \(\in\) \(\displaystyle \mathcal R {\restriction_T}\) Definition of Restriction of Relation


and so $\mathcal R {\restriction_T}$ is symmetric on $T$.

$\blacksquare$


Restriction of Asymmetric Relation is Asymmetric

Suppose $\mathcal R$ is asymmetric on $S$.


Then:

\(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \mathcal R \restriction_T\)
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \left({T \times T}\right) \cap \mathcal R\) Definition of Restriction of Relation
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \mathcal R\) Intersection is Subset
\(\displaystyle \implies \ \ \) \(\displaystyle \left({y, x}\right)\) \(\notin\) \(\displaystyle \mathcal R\) $\mathcal R$ is asymmetric on $S$
\(\displaystyle \implies \ \ \) \(\displaystyle \left({y, x}\right)\) \(\notin\) \(\displaystyle \mathcal R \restriction_T\) Definition of Restriction of Relation


and so $\mathcal R \restriction_T$ is asymmetric on $T$.

$\blacksquare$


Restriction of Antisymmetric Relation is Antisymmetric

Suppose $\mathcal R$ is antisymmetric on $S$.

Then:

\(\displaystyle \left\{ {\left({x, y}\right), \left({y, x}\right)}\right\}\) \(\subseteq\) \(\displaystyle \mathcal R {\restriction_T}\)
\(\displaystyle \implies \ \ \) \(\displaystyle \left\{ {\left({x, y}\right), \left({y, x}\right)}\right\}\) \(\subseteq\) \(\displaystyle \left({T \times T}\right) \cap \mathcal R\) Definition of Restriction of Relation
\(\displaystyle \implies \ \ \) \(\displaystyle \left\{ {\left({x, y}\right), \left({y, x}\right)}\right\}\) \(\subseteq\) \(\displaystyle \mathcal R\) Intersection is Subset
\(\displaystyle \implies \ \ \) \(\displaystyle x\) \(=\) \(\displaystyle y\) $\mathcal R$ is Antisymmetric on $S$

Thus $\mathcal R {\restriction_T}$ is antisymmetric on $T$.

$\blacksquare$


Transitivity

Restriction of Transitive Relation is Transitive

Suppose $\mathcal R$ is transitive on $S$.

Then by definition:

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


So:

\(\displaystyle \left\{ {\left({x, y}\right), \left({y, z}\right)}\right\}\) \(\subseteq\) \(\displaystyle \mathcal R {\restriction_T}\)
\(\displaystyle \implies \ \ \) \(\displaystyle \left\{ {\left({x, y}\right), \left({y, z}\right)}\right\}\) \(\subseteq\) \(\displaystyle \left({T \times T}\right) \cap \mathcal R\) Definition of Restriction of Relation
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, z}\right)\) \(\in\) \(\displaystyle \left({T \times T}\right) \cap \mathcal R\) $\mathcal R$ is transitive on $S$
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, z}\right)\) \(\in\) \(\displaystyle \mathcal R {\restriction_T}\) Definition of Restriction of Relation


Therefore, if $x, y, z \in T$, it follows that:

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

and so by definition $\mathcal R {\restriction_T}$ is a transitive relation on $T$.

$\blacksquare$


Restriction of Antitransitive Relation is Antitransitive

Suppose $\mathcal R$ is antitransitive on $S$.

Then by definition:

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


So:

\(\displaystyle \left\{ {\left({x, y}\right), \left({y, z}\right)}\right\}\) \(\subseteq\) \(\displaystyle \mathcal R \restriction_T\)
\(\displaystyle \implies \ \ \) \(\displaystyle \left\{ {\left({x, y}\right), \left({y, z}\right)}\right\}\) \(\subseteq\) \(\displaystyle \left({T \times T}\right) \cap \mathcal R\) by definition of restriction of relation
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, z}\right)\) \(\notin\) \(\displaystyle \left({T \times T}\right) \cap \mathcal R\) as $\mathcal R$ is antitransitive on $S$
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, z}\right)\) \(\in\) \(\displaystyle \mathcal R \restriction_T\) by definition of restriction of relation


Therefore, if $x, y, z \in T$, it follows that:

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

and so by definition $\mathcal R \restriction_T$ is an antitransitive relation on $T$.

$\blacksquare$


Connectedness

Restriction of Connected Relation is Connected

Suppose $\mathcal R$ is connected on $S$.

That is:

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


So:

\(\displaystyle a, b\) \(\in\) \(\displaystyle T\)
\(\displaystyle \implies \ \ \) \(\displaystyle \left({a, b}\right)\) \(\in\) \(\displaystyle T \times T\)
\(\, \displaystyle \land \, \) \(\displaystyle \left({b, a}\right)\) \(\in\) \(\displaystyle T \times T\) by definition of ordered pair and cartesian product
\(\displaystyle \implies \ \ \) \(\displaystyle \left({a, b}\right)\) \(\in\) \(\displaystyle \left({T \times T}\right) \cap \mathcal R\)
\(\, \displaystyle \lor \, \) \(\displaystyle \left({b, a}\right)\) \(\in\) \(\displaystyle \left({T \times T}\right) \cap \mathcal R\) as $\mathcal R$ is connected on $S$
\(\displaystyle \implies \ \ \) \(\displaystyle \left({a, b}\right)\) \(\in\) \(\displaystyle R \restriction_T\)
\(\, \displaystyle \lor \, \) \(\displaystyle \left({b, a}\right)\) \(\in\) \(\displaystyle R \restriction_T\) by definition of restriction of relation


and so $\mathcal R \restriction_T$ is connected on $T$.

$\blacksquare$


Also see

Properties of Relation Not Preserved by Restriction

If a relation is:

it is impossible to state without further information whether or not any restriction of that relation has the same properties.