# Properties of Restriction of Relation

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

 $\ds \left({x, y}\right)$ $\in$ $\ds \mathcal R {\restriction_T}$ $\ds \implies \ \$ $\ds \left({x, y}\right)$ $\in$ $\ds \left({T \times T}\right) \cap \mathcal R$ Definition of Restriction of Relation $\ds \implies \ \$ $\ds \left({x, y}\right)$ $\in$ $\ds T \times T$ $\, \ds \land \,$ $\ds \left({x, y}\right)$ $\in$ $\ds \mathcal R$ Definition of Set Intersection $\ds \implies \ \$ $\ds \left({y, x}\right)$ $\in$ $\ds T \times T$ $\, \ds \land \,$ $\ds \left({y, x}\right)$ $\in$ $\ds \mathcal R$ $\mathcal R$ is symmetric on $S$ $\ds \implies \ \$ $\ds \left({y, x}\right)$ $\in$ $\ds \left({T \times T}\right) \cap \mathcal R$ Definition of Set Intersection $\ds \implies \ \$ $\ds \left({y, x}\right)$ $\in$ $\ds \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:

 $\ds \left({x, y}\right)$ $\in$ $\ds \mathcal R \restriction_T$ $\ds \implies \ \$ $\ds \left({x, y}\right)$ $\in$ $\ds \left({T \times T}\right) \cap \mathcal R$ Definition of Restriction of Relation $\ds \implies \ \$ $\ds \left({x, y}\right)$ $\in$ $\ds \mathcal R$ Intersection is Subset $\ds \implies \ \$ $\ds \left({y, x}\right)$ $\notin$ $\ds \mathcal R$ $\mathcal R$ is asymmetric on $S$ $\ds \implies \ \$ $\ds \left({y, x}\right)$ $\notin$ $\ds \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 $\RR$ is antisymmetric on $S$.

Then:

 $\ds \set {\tuple {x, y}, \tuple {y, x} }$ $\subseteq$ $\ds \RR {\restriction_T}$ $\ds \leadsto \ \$ $\ds \set {\tuple {x, y}, \tuple {y, x} }$ $\subseteq$ $\ds \paren {T \times T} \cap \RR$ Definition of Restriction of Relation $\ds \leadsto \ \$ $\ds \set {\tuple {x, y}, \tuple {y, x} }$ $\subseteq$ $\ds \RR$ Intersection is Subset $\ds \leadsto \ \$ $\ds x$ $=$ $\ds y$ $\RR$ is Antisymmetric on $S$

Thus $\RR {\restriction_T}$ is antisymmetric on $T$.

$\blacksquare$

### Transitivity

#### Restriction of Transitive Relation is Transitive

Suppose $\RR$ is transitive on $S$.

Then by definition:

$\set {\tuple {x, y}, \tuple {y, z} } \subseteq \RR \implies \tuple {x, z} \in \RR$

So:

 $\ds \set {\tuple {x, y}, \tuple {y, z} }$ $\subseteq$ $\ds \RR {\restriction_T}$ $\ds \leadsto \ \$ $\ds \set {\tuple {x, y}, \tuple {y, z} }$ $\subseteq$ $\ds \paren {T \times T} \cap \RR$ Definition of Restriction of Relation $\ds \leadsto \ \$ $\ds \tuple {x, z}$ $\in$ $\ds \paren {T \times T} \cap \RR$ $\RR$ is transitive on $S$ $\ds \leadsto \ \$ $\ds \tuple {x, z}$ $\in$ $\ds \RR {\restriction_T}$ Definition of Restriction of Relation

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

$\set {\tuple {x, y}, \tuple {y, z} } \subseteq \RR {\restriction_T} \implies \tuple {x, z} \in \RR {\restriction_T}$

and so by definition $\RR {\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:

 $\ds \left\{ {\left({x, y}\right), \left({y, z}\right)}\right\}$ $\subseteq$ $\ds \mathcal R \restriction_T$ $\ds \implies \ \$ $\ds \left\{ {\left({x, y}\right), \left({y, z}\right)}\right\}$ $\subseteq$ $\ds \left({T \times T}\right) \cap \mathcal R$ by definition of restriction of relation $\ds \implies \ \$ $\ds \left({x, z}\right)$ $\notin$ $\ds \left({T \times T}\right) \cap \mathcal R$ as $\mathcal R$ is antitransitive on $S$ $\ds \implies \ \$ $\ds \left({x, z}\right)$ $\in$ $\ds \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 $\RR$ is connected on $S$.

That is:

$\forall a, b \in S: a \ne b \implies \tuple {a, b} \in \RR \lor \tuple {b, a} \in \RR$

So:

 $\ds a, b$ $\in$ $\ds T$ $\ds \leadsto \ \$ $\ds \tuple {a, b}$ $\in$ $\ds T \times T$ $\, \ds \land \,$ $\ds \tuple {b, a}$ $\in$ $\ds T \times T$ Definition of Ordered Pair and Definition of Cartesian Product $\ds \leadsto \ \$ $\ds \tuple {a, b}$ $\in$ $\ds \paren {T \times T} \cap \RR$ $\, \ds \lor \,$ $\ds \tuple {b, a}$ $\in$ $\ds \paren {T \times T} \cap \RR$ as $\RR$ is connected on $S$ $\ds \leadsto \ \$ $\ds \tuple {a, b}$ $\in$ $\ds R \restriction_T$ $\, \ds \lor \,$ $\ds \tuple {b, a}$ $\in$ $\ds R \restriction_T$ Definition of Restriction of Relation

and so $\RR \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.