Relation algebra
Encyclopedia
In mathematics
and abstract algebra
, a relation algebra is a residuated Boolean algebra
expanded
with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2X² of all binary relation
s on a set X, that is, subsets of the cartesian square X2, with R•S interpreted as the usual composition of binary relations
R and S, and with the converse of R interpreted as the inverse relation
.
Relation algebra emerged in the 19th century work of Augustus De Morgan
and Charles Peirce, which culminated in the algebraic logic
of Ernst Schröder
. The equational form of relation algebra treated here was developed by Alfred Tarski
and his students, starting in the 1940s. Tarski and Givant (1987) applied relation algebra to a variable-free treatment of axiomatic set theory, with the implication that mathematics founded on set theory could itself be conducted without variables.
) is an algebraic structure equipped with the Boolean operations of conjunction x∧y, disjunction x∨y, and negation x−, the Boolean constants 0 and 1, the relational operations of composition x•y and converse x
, and the relational constant I, such that these operations and constants satisfy certain equations constituting an axiomatization of relation algebra. A relation algebra is to a system of binary relations on a set containing the empty (0), complete (1), and identity (I) relations and closed under these five operations as a group
is to a system of permutation
s of a set containing the identity permutation and closed under composition and inverse.
Following Jónsson and Tsinakis (1993) it is convenient to define additional operations x◁y = x•y, and, dually, x▷y = x
•y . Jónsson and Tsinakis showed that I◁x = x▷I, and that both were equal to x
. Hence a relation algebra can equally well be defined as an algebraic structure (L, ∧, ∨, −, 0, 1, •, I, ◁, ▷). The advantage of this signature
over the usual one that a relation algebra can then be defined in full simply as a residuated Boolean algebra
for which I◁x is an involution, that is, I◁(I◁x) = x . The latter condition can be thought of as the relational counterpart of the equation 1/(1/x) = x for ordinary arithmetic reciprocal
, and some authors use reciprocal as a synonym for converse.
Since residuated Boolean algebras are axiomatized with finitely many identities, so are relation algebras. Hence the latter form a variety
, the variety RA of relation algebras. Expanding the above definition as equations yields the following finite axiomatization.
in 1948.
L is a Boolean algebra under binary disjunction, ∨, and unary complementation –:
This axiomatization of Boolean algebra is due to Huntington
(1933). Note that the meet of the implied Boolean algebra is not the • operator (even though it distributes over
like a meet does), nor is the 1 of the Boolean algebra the I constant.
L is a monoid
under binary composition
(•) and nullary identity I:
Unary converse
is an involution with respect to composition:
Converse and composition distribute over disjunction:
B10 is Tarski's equational form of the fact, discovered by Augustus De Morgan
, that A•B ≤ C– A
•C ≤ B– C•B
≤ A–.
These axioms are ZFC theorems; for the purely Boolean B1-B3, this fact is trivial. After each of the following axioms is shown the number of the corresponding theorem in chpt. 3 of Suppes (1960), an exposition of ZFC: B4 27, B5 45, B6 14, B7 26, B8 16, B9 23.
s can be expressed as succinct RA equalities or inequalities. Below, an inequality of the form A≤B is shorthand for the Boolean equation A∨B = B.
The most complete set of results of this nature is chpt. C of Carnap (1958), where the notation is rather distant from that of this entry. Chpt. 3.2 of Suppes (1960) contains fewer results, presented as ZFC theorems and using a notation that more resembles that of this entry. Neither Carnap nor Suppes formulated their results using the RA of this entry, or in an equational manner.
of RA are discussed at length in Tarski and Givant (1987), and more briefly in Givant (2006).
RA consists entirely of equations manipulated using nothing more than uniform replacement and the substitution of equals for equals. Both rules are wholly familiar from school mathematics and from abstract algebra
generally. Hence RA proofs are carried out in a manner familiar to all mathematicians, unlike the case in mathematical logic
generally.
RA can express any (and up to logical equivalence
, exactly the) first-order logic
(FOL) formulas containing no more than three variables. (A given variable can be quantified multiple times and hence quantifiers can be nested arbitrarily deeply by "reusing" variables.) Surprisingly, this fragment of FOL suffices to express Peano arithmetic and almost all axiomatic set theories ever proposed. Hence RA is, in effect, a way of algebraizing nearly all mathematics, while dispensing with FOL and its connectives
, quantifiers, turnstiles
, and modus ponens
. Because RA can express Peano arithmetic and set theory, Gödel's incompleteness theorems
apply to it; RA is incomplete
, incompletable, and undecidable
. (N.B. The Boolean algebra fragment of RA is complete and decidable.)
The representable relation algebras, forming the class RRA, are those relation algebras isomorphic to some relation algebra consisting of binary relations on some set, and closed under the intended interpretation of the RA operations. It is easily shown, e.g. using the method of pseudoelementary class
es, that RRA is a quasivariety
, that is, axiomatizable by a universal Horn theory. In 1950, Roger Lyndon
proved the existence of equations holding in RRA that did not hold in RA. Hence the variety generated by RRA is a proper subvariety of the variety RA. In 1955, Alfred Tarski
showed that RRA is itself a variety. In 1964, Donald Monk showed that RRA has no finite axiomatization, unlike RA which is finitely axiomatized by definition.
Essentially these axioms imply that the universe has a (non-surjective) pairing relation whose projections are A and B. It is a theorem that every QRA is a RRA (Tarski & Givant 1987: 8.4(iii) ).
Every QRA is representable (Tarski and Givant 1987). That not every relation algebra is representable is a fundamental way RA differs from QRA and Boolean algebras which, by Stone's representation theorem for Boolean algebras
, are always representable as sets of subsets of some set, closed under union, intersection, and complement.
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.
gave it in Vol. 3 of his Vorlesungen (1890–1905). Principia Mathematica
drew strongly on Schröder's RA, but acknowledged him only as the inventor of the notation. In 1912, Alwin Korselt
proved that a particular formula in which the quantifiers were nested 4 deep had no RA equivalent. This fact led to a loss of interest in RA until Tarski (1941) began writing about it. His students have continued to develop RA down to the present day. Tarski returned to RA in the 1970s with the help of Steven Givant; this collaboration resulted in the monograph by Tarski and Givant (1987), the definitive reference for this subject. For more on the history of RA, see Maddux (1991, 2006).
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
, a relation algebra is a residuated Boolean algebra
Residuated Boolean algebra
In mathematics, a residuated Boolean algebra is a residuated lattice whose lattice structure is that of a Boolean algebra. Examples include Boolean algebras with the monoid taken to be conjunction, the set of all formal languages over a given alphabet Σ under concatenation, the set of all binary...
expanded
Reduct
In universal algebra and in model theory, a reduct of an algebraic structure is obtained by omitting some of the operations and relations of that structure...
with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2X² of all binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
s on a set X, that is, subsets of the cartesian square X2, with R•S interpreted as the usual composition of binary relations
Composition of relations
In mathematics, the composition of binary relations is a concept of forming a new relation from two given relations R and S, having as its most well-known special case the composition of functions.- Definition :...
R and S, and with the converse of R interpreted as the inverse relation
Inverse relation
In mathematics, the inverse relation of a binary relation is the relation that occurs when you switch the order of the elements in the relation. For example, the inverse of the relation 'child of' is the relation 'parent of'...
.
Relation algebra emerged in the 19th century work of Augustus De Morgan
Augustus De Morgan
Augustus De Morgan was a British mathematician and logician. He formulated De Morgan's laws and introduced the term mathematical induction, making its idea rigorous. The crater De Morgan on the Moon is named after him....
and Charles Peirce, which culminated in the algebraic logic
Algebraic logic
In mathematical logic, algebraic logic is the study of logic presented in an algebraic style.What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for the study of various logics and connected problems...
of Ernst Schröder
Ernst Schröder
Ernst Schröder was a German mathematician mainly known for his work on algebraic logic. He is a major figure in the history of mathematical logic , by virtue of summarizing and extending the work of George Boole, Augustus De Morgan, Hugh MacColl, and especially Charles Peirce...
. The equational form of relation algebra treated here was developed by Alfred Tarski
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
and his students, starting in the 1940s. Tarski and Givant (1987) applied relation algebra to a variable-free treatment of axiomatic set theory, with the implication that mathematics founded on set theory could itself be conducted without variables.
Definition
A relation algebra (L, ∧, ∨, −, 0, 1, •, I,) is an algebraic structure equipped with the Boolean operations of conjunction x∧y, disjunction x∨y, and negation x−, the Boolean constants 0 and 1, the relational operations of composition x•y and converse x, and the relational constant I, such that these operations and constants satisfy certain equations constituting an axiomatization of relation algebra. A relation algebra is to a system of binary relations on a set containing the empty (0), complete (1), and identity (I) relations and closed under these five operations as a groupGroup (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
is to a system of permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s of a set containing the identity permutation and closed under composition and inverse.
Following Jónsson and Tsinakis (1993) it is convenient to define additional operations x◁y = x•y, and, dually, x▷y = x
•y . Jónsson and Tsinakis showed that I◁x = x▷I, and that both were equal to x. Hence a relation algebra can equally well be defined as an algebraic structure (L, ∧, ∨, −, 0, 1, •, I, ◁, ▷). The advantage of this signatureSignature (logic)
In logic, especially mathematical logic, a signature lists and describes the non-logical symbols of a formal language. In universal algebra, a signature lists the operations that characterize an algebraic structure. In model theory, signatures are used for both purposes.Signatures play the same...
over the usual one that a relation algebra can then be defined in full simply as a residuated Boolean algebra
Residuated Boolean algebra
In mathematics, a residuated Boolean algebra is a residuated lattice whose lattice structure is that of a Boolean algebra. Examples include Boolean algebras with the monoid taken to be conjunction, the set of all formal languages over a given alphabet Σ under concatenation, the set of all binary...
for which I◁x is an involution, that is, I◁(I◁x) = x . The latter condition can be thought of as the relational counterpart of the equation 1/(1/x) = x for ordinary arithmetic reciprocal
Multiplicative inverse
In mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the multiplicative identity, 1. The multiplicative inverse of a fraction a/b is b/a. For the multiplicative inverse of a real number, divide 1 by the...
, and some authors use reciprocal as a synonym for converse.
Since residuated Boolean algebras are axiomatized with finitely many identities, so are relation algebras. Hence the latter form a variety
Variety (universal algebra)
In mathematics, specifically universal algebra, a variety of algebras is the class of all algebraic structures of a given signature satisfying a given set of identities. Equivalently, a variety is a class of algebraic structures of the same signature which is closed under the taking of homomorphic...
, the variety RA of relation algebras. Expanding the above definition as equations yields the following finite axiomatization.
Axioms
The axioms B1-B10 below are adapted from Givant (2006: 283), and were first set out by TarskiAlfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
in 1948.
L is a Boolean algebra under binary disjunction, ∨, and unary complementation –:
- B1: A ∨ B = B ∨ A
- B2: A ∨ (B ∨ C) = (A ∨ B) ∨ C
- B3: (A– ∨ B)– ∨ (A– ∨ B–)– = A
This axiomatization of Boolean algebra is due to Huntington
Edward Vermilye Huntington
Edward Vermilye Huntington was an American mathematician....
(1933). Note that the meet of the implied Boolean algebra is not the • operator (even though it distributes over
like a meet does), nor is the 1 of the Boolean algebra the I constant.L is a monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
under binary composition
Composition of relations
In mathematics, the composition of binary relations is a concept of forming a new relation from two given relations R and S, having as its most well-known special case the composition of functions.- Definition :...
(•) and nullary identity I:
- B4: A•(B•C) = (A•B)•C
- B5: A•I = A
Unary converse
Inverse relation
In mathematics, the inverse relation of a binary relation is the relation that occurs when you switch the order of the elements in the relation. For example, the inverse of the relation 'child of' is the relation 'parent of'...
is an involution with respect to composition:
- B6: A
= A - B7: (A•B)
= B
•A
Converse and composition distribute over disjunction:
- B8: (A∨B)
= A
∨B
- B9: (A∨B)•C = (A•C)∨(B•C)
B10 is Tarski's equational form of the fact, discovered by Augustus De Morgan
Augustus De Morgan
Augustus De Morgan was a British mathematician and logician. He formulated De Morgan's laws and introduced the term mathematical induction, making its idea rigorous. The crater De Morgan on the Moon is named after him....
, that A•B ≤ C– A
•C ≤ B– C•B ≤ A–.
- B10: (A
•(A•B)–)∨B– = B–
These axioms are ZFC theorems; for the purely Boolean B1-B3, this fact is trivial. After each of the following axioms is shown the number of the corresponding theorem in chpt. 3 of Suppes (1960), an exposition of ZFC: B4 27, B5 45, B6 14, B7 26, B8 16, B9 23.
Expressing properties of binary relations in RA
The following table shows how many of the usual properties of binary relationBinary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
s can be expressed as succinct RA equalities or inequalities. Below, an inequality of the form A≤B is shorthand for the Boolean equation A∨B = B.
The most complete set of results of this nature is chpt. C of Carnap (1958), where the notation is rather distant from that of this entry. Chpt. 3.2 of Suppes (1960) contains fewer results, presented as ZFC theorems and using a notation that more resembles that of this entry. Neither Carnap nor Suppes formulated their results using the RA of this entry, or in an equational manner.
| R is | If and only if If and only if In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements.... : |
|---|---|
| Functional | R •R ≤ I |
| Total Total relation In mathematics, a binary relation R over a set X is total if for all a and b in X, a is related to b or b is related to a .In mathematical notation, this is\forall a, b \in X,\ a R b \or b R a.... or Connected |
I ≤ R•R (R is surjective) |
| Function Function (mathematics) In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can... |
functional and total. |
| Injective | R•R ≤ I (R is functional) |
| Surjective | I ≤ R •R (R is total) |
| Bijection Bijection A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements... |
R •R = R•R = I (Injective surjective function) |
| Reflexive Reflexive relation In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:... |
I ≤ R |
| Irreflexive | R ∧ I = 0 |
| Transitive Transitive relation In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c.... |
R•R ≤ R |
| Preorder Preorder In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders... |
R is reflexive and transitive. |
| Antisymmetric Antisymmetric relation In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:\forall a, b \in X,\ R \and R \; \Rightarrow \; a = bor, equivalently,... |
R ∧ R ≤ I |
| Partial order | R is an antisymmetric preorder. |
| Total order Total order In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total... |
R is a total partial order. |
| Strict partial order | R is transitive and irreflexive. |
| Strict total order Total order In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total... |
R is a total strict partial order. |
| Symmetric Symmetric relation In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:... |
R = R |
| Equivalence Equivalence relation In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell... |
R•R = R. R is a symmetric preorder. |
| Asymmetric Asymmetric relation Asymmetric often means, simply: not symmetric. In this sense an asymmetric relation is a binary relation which is not a symmetric relation.That is,\lnot.... |
R ≠ R |
| Dense Dense order In mathematics, a partial order ≤ on a set X is said to be dense if, for all x and y in X for which x In mathematics, a partial order ≤ on a set X is said to be dense if, for all x and y in X for which x... |
R ∧ I– ≤ (R ∧ I–)•(R ∧ I–). |
Expressive power
The metamathematicsMetamathematics
Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories...
of RA are discussed at length in Tarski and Givant (1987), and more briefly in Givant (2006).
RA consists entirely of equations manipulated using nothing more than uniform replacement and the substitution of equals for equals. Both rules are wholly familiar from school mathematics and from abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
generally. Hence RA proofs are carried out in a manner familiar to all mathematicians, unlike the case in mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
generally.
RA can express any (and up to logical equivalence
Logical equivalence
In logic, statements p and q are logically equivalent if they have the same logical content.Syntactically, p and q are equivalent if each can be proved from the other...
, exactly the) first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
(FOL) formulas containing no more than three variables. (A given variable can be quantified multiple times and hence quantifiers can be nested arbitrarily deeply by "reusing" variables.) Surprisingly, this fragment of FOL suffices to express Peano arithmetic and almost all axiomatic set theories ever proposed. Hence RA is, in effect, a way of algebraizing nearly all mathematics, while dispensing with FOL and its connectives
Logical connective
In logic, a logical connective is a symbol or word used to connect two or more sentences in a grammatically valid way, such that the compound sentence produced has a truth value dependent on the respective truth values of the original sentences.Each logical connective can be expressed as a...
, quantifiers, turnstiles
Turnstile (symbol)
In mathematical logic and computer science the symbol \vdash has taken the name turnstile because of its resemblance to a typical turnstile if viewed from above. It is also referred to as tee and is often read as "yields", "proves", "satisfies" or "entails"...
, and modus ponens
Modus ponens
In classical logic, modus ponendo ponens or implication elimination is a valid, simple argument form. It is related to another valid form of argument, modus tollens. Both Modus Ponens and Modus Tollens can be mistakenly used when proving arguments...
. Because RA can express Peano arithmetic and set theory, Gödel's incompleteness theorems
Gödel's incompleteness theorems
Gödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic. The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of...
apply to it; RA is incomplete
Incomplete
Incomplete may refer to:* A piece of work that is not finished* Gödel's incompleteness theorems, a specification of logic* Incomplete * "Incomplete" , a track from the album Stranger Than Fiction by Bad Religion...
, incompletable, and undecidable
Undecidable
Undecidable may refer to:In mathematics and logic* Undecidable problem - a decision problem which no algorithm can decide* "Undecidable" is sometimes used as a synonym of "independent", where a formula in mathematical logic is independent of a logical theory if neither that formula nor its negation...
. (N.B. The Boolean algebra fragment of RA is complete and decidable.)
The representable relation algebras, forming the class RRA, are those relation algebras isomorphic to some relation algebra consisting of binary relations on some set, and closed under the intended interpretation of the RA operations. It is easily shown, e.g. using the method of pseudoelementary class
Pseudoelementary class
In logic, a pseudoelementary class is a class of structures derived from an elementary class by omitting some of its sorts and relations. It is the mathematical logic counterpart of the notion in category theory of a forgetful functor, and in physics of hidden variable theories purporting to...
es, that RRA is a quasivariety
Quasivariety
In mathematics, a quasivariety is a class of algebraic structures generalizing the notion of variety by allowing equational conditions on the axioms defining the class.-Definition:...
, that is, axiomatizable by a universal Horn theory. In 1950, Roger Lyndon
Roger Lyndon
Roger Conant Lyndon was an American mathematician, for many years a professor at the University of Michigan. He is known for Lyndon words, the Curtis–Hedlund–Lyndon theorem, Craig–Lyndon interpolation and the Lyndon–Hochschild–Serre spectral sequence.-Biography:Lyndon was born on December 18, 1917...
proved the existence of equations holding in RRA that did not hold in RA. Hence the variety generated by RRA is a proper subvariety of the variety RA. In 1955, Alfred Tarski
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
showed that RRA is itself a variety. In 1964, Donald Monk showed that RRA has no finite axiomatization, unlike RA which is finitely axiomatized by definition.
Q-Relation Algebras
An RA is a Q-Relation Algebra (QRA) if, in addition to B1-B10, there exist some A and B such that (Tarski and Givant 1987: §8.4):- Q0: A
•A ≤ I - Q1: B
•B ≤ I - Q2: A
•B = 1
Essentially these axioms imply that the universe has a (non-surjective) pairing relation whose projections are A and B. It is a theorem that every QRA is a RRA (Tarski & Givant 1987: 8.4(iii) ).
Every QRA is representable (Tarski and Givant 1987). That not every relation algebra is representable is a fundamental way RA differs from QRA and Boolean algebras which, by Stone's representation theorem for Boolean algebras
Stone's representation theorem for Boolean algebras
In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Stone...
, are always representable as sets of subsets of some set, closed under union, intersection, and complement.
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
Ordered pair
In mathematics, an ordered pair is a pair of mathematical objects. In the ordered pair , the object a is called the first entry, and the object b the second entry of the 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
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
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 groupGroup (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
as well as a monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
. B4-B7 become well-known theorems of group theory
Group theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
, so that RA becomes a proper extension of group theory
Group theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
as well as of Boolean algebra.
Historical remarks
DeMorgan founded RA in 1860, but C. S. Peirce took it much further and became fascinated with its philosophical power. The work of DeMorgan and Peirce came to be known mainly in the extended and definitive form Ernst SchröderErnst Schröder
Ernst Schröder was a German mathematician mainly known for his work on algebraic logic. He is a major figure in the history of mathematical logic , by virtue of summarizing and extending the work of George Boole, Augustus De Morgan, Hugh MacColl, and especially Charles Peirce...
gave it in Vol. 3 of his Vorlesungen (1890–1905). Principia Mathematica
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913...
drew strongly on Schröder's RA, but acknowledged him only as the inventor of the notation. In 1912, Alwin Korselt
Alwin Korselt
Alwin Reinhold Korselt was a German mathematician. He discovered Korselt's Criterion which provides a definition for Carmichael numbers and also contributed an early result in relational algebra.-Personal life:The Korselts are a huge, widespread family that has been resident in the village of...
proved that a particular formula in which the quantifiers were nested 4 deep had no RA equivalent. This fact led to a loss of interest in RA until Tarski (1941) began writing about it. His students have continued to develop RA down to the present day. Tarski returned to RA in the 1970s with the help of Steven Givant; this collaboration resulted in the monograph by Tarski and Givant (1987), the definitive reference for this subject. For more on the history of RA, see Maddux (1991, 2006).
Software
- RelMICS / Relational Methods in Computer Science maintained by Wolfram Kahl
- Carsten Sinz: ARA / An Automatic Theorem Prover for Relation Algebras
See also
- Algebraic logicAlgebraic logicIn mathematical logic, algebraic logic is the study of logic presented in an algebraic style.What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for the study of various logics and connected problems...
- Allegory (category theory)Allegory (category theory)In mathematical category theory, an allegory is a category that has some of the structure of the category of sets and binary relations between them. Allegories can be used as an abstraction of categories of relations, and in this sense the theory of allegories is a generalization of relation...
- Binary relationBinary relationIn mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
- Cartesian productCartesian productIn mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
- Cartesian square
- Composition of relationsComposition of relationsIn mathematics, the composition of binary relations is a concept of forming a new relation from two given relations R and S, having as its most well-known special case the composition of functions.- Definition :...
- Converse of a relationInverse relationIn mathematics, the inverse relation of a binary relation is the relation that occurs when you switch the order of the elements in the relation. For example, the inverse of the relation 'child of' is the relation 'parent of'...
- Cylindric algebraCylindric algebraThe notion of cylindric algebra, invented by Alfred Tarski, arises naturally in the algebraization of first-order logic with equality. This is comparable to the role Boolean algebras play for propositional logic. Indeed, cylindric algebras are Boolean algebras equipped with additional...
s - Extension in logicExtension (predicate logic)The extension of a predicatea truth-valued functionis the set of tuples of values that, used as arguments, satisfy the predicate. Such a set of tuples is a relation.For example the statement "d2 is the weekday following d1"...
- Involution
- Logic of relatives
- RelationRelation (mathematics)In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
- Relation constructionRelation constructionIn logic and mathematics, relation construction and relational constructibility have to do with the ways that one relation is determined by an indexed family or a sequence of other relations, called the relation dataset. The relation in the focus of consideration is called the faciendum...
- Relation reduction
- Relational calculusRelational calculusRelational calculus consists of two calculi, the tuple relational calculus and the domain relational calculus, that are part of the relational model for databases and provide a declarative way to specify database queries...
- Relational algebraRelational algebraRelational algebra, an offshoot of first-order logic , deals with a set of finitary relations that is closed under certain operators. These operators operate on one or more relations to yield a relation...
- Relative product of relations
- Residuated Boolean algebraResiduated Boolean algebraIn mathematics, a residuated Boolean algebra is a residuated lattice whose lattice structure is that of a Boolean algebra. Examples include Boolean algebras with the monoid taken to be conjunction, the set of all formal languages over a given alphabet Σ under concatenation, the set of all binary...
- Spatial-temporal reasoningSpatial-temporal reasoningSpatial–temporal reasoning is used in both the fields of psychology and computer science.-Spatial–temporal reasoning in psychology:Spatial-temporal reasoning is the ability to visualize spatial patterns and mentally manipulate them over a time-ordered sequence of spatial transformations.This...
- Theory of relationsTheory of relationsThe theory of relations treats the subject matter of relations in its combinatorial aspect, as distinguished from, though related to, its more properly logical study on one side and its more generally mathematical study on another....
- Triadic relationTriadic relationIn mathematics, a ternary relation or triadic relation is a finitary relation in which the number of places in the relation is three. Ternary relations may also be referred to as 3-adic, 3-ary, 3-dimensional, or 3-place....
External links
- Yohji AKAMA, Yasuo Kawahara, and Hitoshi Furusawa, "Constructing Allegory from Relation Algebra and Representation Theorems."
- Richard Bird, Oege de Moor, Paul Hoogendijk, "Generic Programming with Relations and Functors."
- R.P. de Freitas and Viana, "A Completeness Result for Relation Algebra with Binders."
- Peter Jipsen:
- Relation algebras. In Mathematical structures. If there are problems with LaTeX, see an old HTML version here.
- "Foundations of Relations and Kleene Algebra."
- "Computer Aided Investigations of Relation Algebras."
- "A Gentzen System And Decidability For Residuated Lattices."
- Vaughan Pratt:
- "Origins of the Calculus of Binary Relations." A historical treatment.
- "The Second Calculus of Binary Relations."
- Priss, Uta:
- "An FCA interpretation of Relation Algebra."
- "Relation Algebra and FCA" Links to publications and software
- Kahl, Wolfram, and Schmidt, Gunther, "Exploring (Finite) Relation Algebras Using Tools Written in Haskell." See homepage of the whole project.