To prove the statements about the composition of a binary relation, we need to clarify some concepts first.

Definitions

1. Binary Relation: A binary relation $R$ from set $A$ to set $B$ is a subset of $A \times B$.
2. Composition of Relations: Given two binary relations $R \subseteq A \times B$ and $S \subseteq B \times C$, the composition $S \circ R$ is defined as: $S \circ R = \{ (a, c) \in A \times C \mid \exists b \in B \text{ such that } (a, b) \in R \text{ and } (b, c) \in S \}$

Proving the Statements

1. Cardinality Greater than 2:

   • Example: Let $A = \{x, y\}$, $B = \{a, b\}$, and $C = \{1, 2\}$.
   • Define relations:
     • $R = \{(x, a), (y, b)\}$
     • $S = \{(a, 1), (b, 2)\}$
   • The composition $S \circ R$:
     • From $R$, we can map $x$ to $a$ and $y$ to $b$.
     • From $S$, we can map $a$ to $1$ and $b$ to $2$.
     • Thus, $S \circ R = \{(x, 1), (y, 2)\}$.
   • The cardinality of $S \circ R$ is 2, but this is a specific case.
   • In general, for larger sets or different configurations, the cardinality can easily exceed 2. For instance, if there are multiple elements in $B$ leading to multiple mappings in $C$, the cardinality will grow.

2. Associativity:

   • We need to show that $(T \circ S) \circ R = T \circ (S \circ R)$.
   • Let $R \subseteq A \times B$, $S \subseteq B \times C$, and $T \subseteq C \times D$.
   • For $(T \circ S) \circ R$:
     • Take an element $(a, d)$ such that $\exists b \in B, c \in C$ such that $(a, b) \in R$, $(b, c) \in S$, $(c, d) \in T$.
   • For $T \circ (S \circ R)$:
     • Take an element $(a, d)$ such that $\exists c \in C$ such that $(a, b) \in R$, $(b, c) \in S$, $(c, d) \in T$.
   • Both compositions lead to the same pairs $(a, d)$, thus showing that composition is associative.

3. Non-commutativity:

   • To demonstrate that composition is not commutative, we can find a counterexample.
   • Let $A = \{x\}$, $B = \{a, b\}$, $C = \{1\}$.
   • Define relations:
     • $R = \{(x, a)\}$
     • $S = \{(a, 1), (b, 1)\}$
   • Compute $S \circ R$:
     • $S \circ R = \{(x, 1)\}$
   • Compute $R \circ S$:
     • $R \circ S = \emptyset$ (since there’s no $(b, x)$ in $R$).
   • Since $S \circ R \neq R \circ S$, we conclude that relation composition is not commutative.

Summary

• Cardinality: Can be greater than 2 depending on the sets involved.
• Associativity: Verified through a structural argument.
• Non-commutativity: Proven via counterexamples.

Further Questions

1. How does the cardinality of the relations impact their composition?
2. Can you give examples of binary relations that are both associative and commutative?
3. What are the implications of non-commutativity in practical applications?
4. How does the concept of inverse relations fit into this discussion?
5. What happens when relations are not defined over distinct sets?

Tip

Always visualize the relations with Venn diagrams or directed graphs for better understanding of compositions and cardinalities.