Binary Relations in Set Theory and Binary Matrices

This article explores the mathematical definition of binary relations in formal set theory and explains their direct structural correspondence to binary matrices (matrices consisting entirely of 0s and 1s). It details how subsets of Cartesian products map directly to two-dimensional grids of bits, and demonstrates how fundamental relational operations—such as composition, union, intersection, and transposition—align seamlessly with Boolean matrix algebra.

Formal Definition of a Binary Relation

In formal set theory, a binary relation \(R\) between two sets \(A\) and \(B\) is defined as a subset of their Cartesian product, \(A \times B\). The Cartesian product represents the set of all ordered pairs \((a, b)\) such that \(a \in A\) and \(b \in B\):

\[R \subseteq A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}\]

If \((a, b) \in R\), we say that \(a\) is related to \(b\) by \(R\), often written as \(aRb\). When \(A = B\), \(R\) is referred to as a homogeneous binary relation on \(A\).

The Binary Matrix Representation

When sets \(A\) and \(B\) are finite, a binary relation can be represented as a logical or binary matrix, often called an adjacency or relation matrix.

Let \(A = \{a_1, a_2, \dots, a_m\}\) and \(B = \{b_1, b_2, \dots, b_n\}\) be finite sets with fixed orderings. The relation \(R \subseteq A \times B\) corresponds to an \(m \times n\) matrix \(M_R\), whose entries are elements of the binary domain \(\{0, 1\}\):

\[M_R(i, j) = \begin{cases} 1 & \text{if } (a_i, b_j) \in R \\ 0 & \text{if } (a_i, b_j) \notin R \end{cases}\]

Here, the row index \(i\) corresponds to the element \(a_i \in A\), the column index \(j\) corresponds to the element \(b_j \in B\), and the value indicates the presence (\(1\)) or absence (\(0\)) of the relation.

Operational Correspondence

The algebraic operations performed on relations correspond directly to operations on binary matrices using Boolean arithmetic (where addition corresponds to logical OR \(\lor\), and multiplication corresponds to logical AND \(\land\)):

• Union (\(R \cup S\)): The union of two relations corresponds to the entrywise Boolean sum (OR) of their matrices: \[M_{R \cup S} = M_R \lor M_S\]

• Intersection (\(R \cap S\)): The intersection corresponds to the entrywise Boolean product (AND) of their matrices: \[M_{R \cap S} = M_R \land M_S\]

• Converse/Inverse (\(R^{-1}\)): The inverse relation, defined by \((b, a) \in R^{-1} \iff (a, b) \in R\), corresponds to the matrix transpose: \[M_{R^{-1}} = (M_R)^T\]

• Composition (\(S \circ R\)): Given \(R \subseteq A \times B\) and \(S \subseteq B \times C\), the composition \((a, c) \in S \circ R \iff \exists b \in B \text{ such that } (a, b) \in R \text{ and } (b, c) \in S\) corresponds to the Boolean matrix multiplication: \[M_{S \circ R} = M_R \odot M_S\] where the entry \((i, k)\) is computed as \(\bigvee_{j=1}^{n} (M_R(i, j) \land M_S(j, k))\).

Mapping Relation Properties to Matrix Properties

For homogeneous relations on a single set \(A\) (represented by an \(n \times n\) square binary matrix \(M\)), fundamental properties are easily verified through matrix structure:

• Reflexivity: \(\forall a \in A, (a, a) \in R\). The main diagonal of \(M\) contains only \(1\)s (\(M(i, i) = 1\) for all \(i\)).
• Symmetry: \((a, b) \in R \implies (b, a) \in R\). The matrix is equal to its transpose (\(M = M^T\)).
• Antisymmetry: \((a, b) \in R \land (b, a) \in R \implies a = b\). If \(i \neq j\) and \(M(i, j) = 1\), then \(M(j, i) = 0\).
• Transitivity: \((a, b) \in R \land (b, c) \in R \implies (a, c) \in R\). Under Boolean matrix multiplication, \(M \odot M \le M\) (meaning if \((M \odot M)_{ij} = 1\), then \(M_{ij} = 1\)).

This isomorphism allows computer systems to store, manipulate, and query abstract mathematical relations efficiently using compact bit arrays and standard matrix operations.