Minimal WRT Restriction

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $A$ be a set or class.

Let $\mathcal R$ be a relation on $A$.

Let $B$ be a subset or subclass of $A$.

Let $\mathcal R'$ be the restriction of $\mathcal R$ to $B$.

Let $m \in B$.


Then:

$m$ is $\mathcal R$-minimal in $B$

if and only if:

$m$ is $\mathcal R'$-minimal in $B$.


Proof

Sufficient Condition

Let $m$ be $\mathcal R$-minimal in $B$.

Let $x$ be any element of $B$.

Suppose for the sake of contradiction that $x \mathrel {\mathcal R'} m$.

Then since $\mathcal R' \subseteq \mathcal R$:

$x \mathrel{\mathcal R} m$

contradicting the fact that $m$ is $\mathcal R$-minimal in $B$.

Thus:

$\lnot \left({x \mathrel{\mathcal R'} m}\right)$

As this holds for all $x \in B$, $m$ is $\mathcal R'$-minimal in $B$.

$\Box$


Necessary Condition

Let $m$ be $\mathcal R'$-minimal in $B$.

Let $x \in B$.

Suppose for the sake of contradiction that $x \mathrel{\mathcal R} m$.

Then $x, m \in B$.

Therefore:

$\left({x, m}\right) \in B \times B$

Thus:

$\left({x, m}\right) \in \mathcal R \cap \left({B \times B}\right) = \mathcal R'$

so $x \mathrel{\mathcal R'} m$

This contradicts the fact that $m$ is $\mathcal R'$-minimal in $B$.

Thus:

$\lnot \left({x \mathrel{\mathcal R} m}\right)$

As this holds for all $x \in B$, it follows that $m$ is $\mathcal R$-minimal in $B$.

$\blacksquare$