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.
Read more about this topic: Relation Algebra
Famous quotes containing the word examples:
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)
“In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
—Michel de Montaigne (1533–1592)