Relation Algebra - Examples

Examples

1. Any Boolean algebra can be turned into a RA by interpreting conjunction as composition (the monoid multiplication •), i.e. x•y is defined as x∧y. This interpretation requires that converse interpret identity (ў = y), and that both residuals y\x and x/y interpret the conditional y→x (i.e., ¬y∨x).

2. The motivating example of a relation algebra depends on the definition of a binary relation R on a set X as any subset R ⊆ X², where X² is the Cartesian square of X. The power set 2X² consisting of all binary relations on X is a Boolean algebra. While 2X² can be made a relation algebra by taking R•S = R∧S, as per example (1) above, the standard interpretation of • is instead x(R•S)z = ∃y.xRySz. That is, the ordered pair (x,z) belongs to the relation R•S just when there exists y ∈ X such that (x,y) ∈ R and (y,z) ∈ S. This interpretation uniquely determines R\S as consisting of all pairs (y,z) such that for all x ∈ X, if xRy then xSz. Dually, S/R consists of all pairs (x,y) such that for all z ∈ X, if yRz then xSz. The translation ў = ¬(y\¬I) then establishes the converse R of R as consisting of all pairs (y,x) such that (x,y) ∈ R.

3. An important generalization of the previous example is the power set 2E where E ⊆ X² is any equivalence relation on the set X. This is a generalization because X² is itself an equivalence relation, namely the complete relation consisting of all pairs. While 2E is not a subalgebra of 2X² when E ≠ X² (since in that case it does not contain the relation X², the top element 1 being E instead of X²), it is nevertheless turned into a relation algebra using the same definitions of the operations. Its importance resides in the definition of a representable relation algebra as any relation algebra isomorphic to a subalgebra of the relation algebra 2E for some equivalence relation E on some set. The previous section says more about the relevant metamathematics.

4. If group sum or product interprets composition, group inverse interprets converse, group identity interprets I, and if R is a one to one correspondence, so that R•R = R•R = I, then L is a group as well as a monoid. B4-B7 become well-known theorems of group theory, so that RA becomes a proper extension of group theory as well as of Boolean algebra.