# Schröder Rule/Proof 1

## Theorem

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

The following statements are equivalent:

$(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)$ 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: \paren {\tuple {y, z} \in A \land \tuple {x, y} \in B \implies \tuple {x, z} \in C}$

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

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

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: \paren {\tuple {y, z} \in A \land \tuple {x, z} \notin C) \implies \tuple {x, y} \notin B}$

We shall use the method of truth tables.

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

Statement 1:

$\begin{array}{ccccc} (\tuple {y, z} \in A & \land & \tuple {x, y} \in B) & \implies & \tuple {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} (\tuple {y, z} \in A & \land & \tuple {x, z} \notin C) & \implies & \tuple {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$

## Source of Name

This entry was named for Friedrich Wilhelm Karl Ernst Schröder.