Properties of Restriction of Relation
in the process of being refactored, or:
has been identified as a candidate for refactoring.
Until this has been finished, please leave {{refactor}} in the code.
Contents |
Theorem
Let $\left({S, \mathcal R}\right)$ be a relational structure.
Let $T \subseteq S$ be a subset of $S$.
Let $\left({T, \mathcal R \restriction_T}\right)$ 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
- Suppose $\mathcal R$ is reflexive on $S$.
Then $\forall x \in S: \left({x, x}\right) \in \mathcal R$, and so $\forall x \in T: \left({x, x}\right) \in \mathcal R\restriction_T$.
Thus $\mathcal R\restriction_T$ is reflexive on $T$.
- Suppose $\mathcal R$ is antireflexive on $S$.
Then $\forall x \in S: \left({x, x}\right) \notin \mathcal R$, and so $\forall x \in T: \left({x, x}\right) \notin \mathcal R \restriction_T$.
Thus $\mathcal R \restriction_T$ is antireflexive on $T$.
Symmetry
- Suppose $\mathcal R$ is symmetric on $S$.
Then $\left({x, y}\right) \in \mathcal R \implies \left({y, x}\right) \in \mathcal R$.
So, if both $x$ and $y$ are in $T$, $\left({x, y}\right) \in \mathcal R \restriction_T$ and $\left({y, x}\right) \in \mathcal R \restriction_T$ and so $\mathcal R \restriction_T$ is symmetric.
- Similarly for asymmetry.
Let $\left({x, y}\right) \in \mathcal R \implies \left({y, x}\right) \notin \mathcal R$.
If both $x$ and $y$ are in $T$, $\left({x, y}\right) \in \mathcal R \restriction_T$ but $\left({y, x}\right) \notin \mathcal R \restriction_T$ still.
And so $\mathcal R \restriction_T$ is asymmetric.
- Now suppose $\mathcal R$ is antisymmetric.
Then $\left({x, y}\right) \in \mathcal R \land \left({y, x}\right) \in \mathcal R \implies x = y$.
By the above argument, the same applies to $\mathcal R \restriction_T$.
Transitivity
- Suppose $\mathcal R$ is transitive.
Then $\left({x, y}\right) \in \mathcal R \land \left({y, z}\right) \in \mathcal R \implies \left({x, z}\right) \in \mathcal R$
Therefore, if $x, y, z \in T$, it follows that $\left({x, y}\right) \in \mathcal R \restriction_T, \left({y, z}\right) \in \mathcal R \restriction_T \implies \left({x, z}\right) \in \mathcal R \restriction_T$.
- Suppose $\mathcal R$ is antitransitive.
Then there are no $\left({x, z}\right) \in \mathcal R$ such that $\left({x, y}\right) \in \mathcal R \land \left({y, z}\right) \in \mathcal R$.
If $x, y, z \in T$, then the same still applies, and $\mathcal R \restriction_T$ remains antitransitive.
$\blacksquare$
Connectedness
- Suppose $\mathcal R$ is connected.
Let $x, y \in T$.
As $T \subseteq S$, from the definition of subset, $x, y \in S$.
As $\mathcal R$ is by definition a connected relation, either $\left({x, y}\right) \in \mathcal R$ or $\left({y, x}\right) \in \mathcal R$.
As $x$ and $y$ are arbitrary elements of $T$ it follows that $\left({T, \preceq}\right)$ is also connected.
$\blacksquare$
If you are fairly certain that there are none, please remove {{proofread}} from the code.
Note
If a relation is:
it is impossible to state without further information whether or not any restriction of that relation has the same properties.
