Schröder Rule

From ProofWiki
Jump to: navigation, search

Theorem

Let $A$, $B$ and $C$ be relations on a set $S$.


Then the following are equivalent statements:

$(1): \quad A \circ B \subseteq C$
$(2): \quad A^{-1} \circ \overline C \subseteq \overline B$
$(3): \quad \overline C \circ B^{-1} \subseteq \overline A$

where:

$\circ$ denotes relation composition
$A^{-1}$ denotes the inverse of $A$
$\overline A$ denotes the complement of $A$.


Proof 1

$(1)$ iff $(2)$

By the definition of relation composition and subset we have that statement $(1)$ may be written as:

$(1'):\quad \forall x, y, z \in S: \left({ (y, z) \in A \land (x, y) \in B \implies (x, z) \in C }\right)$

Using a different arrangement of variable names, statement $(2)$ can be written:

$(2'):\quad \forall x, y, z \in S: \left({ (z, y) \in A^{-1} \land (x, z) \in \overline C \implies (x, y) \in \overline B }\right)$

By the definition of inverse relation and the complement of a relation we can rewrite this as:

$(2''):\quad \forall x, y, z \in S: \left({ (y, z) \in A \land (x, z) \notin C) \implies (x, y) \notin B }\right)$


We shall use the method of truth tables.

The two statements will be equivalent iff the columns under the main connectives, which is $\implies$ in each case, are identical.

Statement 1:

$\begin{array}{ccccc} ((y, z) \in A & \land & (x, y) \in B) & \implies & (x, z) \in C \\ \hline T & T & T & T & T \\ T & T & T & F & F \\ T & F & F & T & T \\ T & F & F & T & F \\ F & F & T & T & T \\ F & F & T & T & F \\ F & F & F & T & T \\ F & F & F & T & F \\ \end{array}$

Statement 2:

$\begin{array}{ccccc} ((y, z) \in A & \land & (x, z) \notin C) & \implies & (x, y) \notin B \\ \hline T & F & F & T & F \\ T & T & T & F & F \\ T & F & F & T & T \\ T & T & T & T & T \\ F & F & F & T & F \\ F & F & T & T & F \\ F & F & F & T & T \\ F & F & T & T & T \\ \end{array}$

$\Box$

$(2)$ iff $(3)$


Proof 2

By the definition of relation composition and subset we have that statement $(1)$ may be written as:

$(1')\quad \forall x, y, z \in S: \left({ (y, z) \in A \land (x, y) \in B \implies (x, z) \in C }\right)$


Using a different arrangement of variable names, statement $(2)$ can be written:

$(2')\quad \forall x, y, z \in S: \left({ (z, y) \in A^{-1} \land (x, z) \in \overline C \implies (x, y) \in \overline B }\right)$

By the definition of the inverse and the complement of a relation we can rewrite this as:

$(2'')\quad \forall x, y, z \in S: \left({ (y, z) \in A \land (x, z) \notin C) \implies (x, y) \notin B }\right)$

Similarly, statement $(3)$ can be written:

$(3')\quad \forall x, y, z \in S: \left({ (x, z) \in \overline C \land (y, x) \in B^{-1} \implies (y, z) \in \overline A }\right)$

By the definition of the inverse and the complement of a relation we can rewrite this as:

$(3'')\quad \forall x, y, z \in S: \left({ (x, z) \notin C \land (x, y) \in B \implies (y, z) \notin A }\right)$

So in all we have:

$(1')\quad \forall x, y, z \in S: \left({ (y, z) \in A \land (x, y) \in B \implies (x, z) \in C }\right)$
$(2'')\quad \forall x, y, z \in S: \left({ (y, z) \in A \land (x, z) \notin C) \implies (x, y) \notin B }\right)$
$(3'')\quad \forall x, y, z \in S: \left({ (x, z) \notin C \land (x, y) \in B \implies (y, z) \notin A }\right)$



Source of Name

This entry was named for Ernst Schröder.


Also known as

  • This result is usually seen with "The" before it: The Schröder Rule.


Sources