HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The ter ...
, a relation algebra is a
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 alph ...
expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2''X''² of all
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
s on a set ''X'', that is, subsets of the
cartesian square In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A ...
''X''2, with ''R''•''S'' interpreted as the usual composition of binary relations ''R'' and ''S'', and with the converse of ''R'' as the converse relation. Relation algebra emerged in the 19th-century work of Augustus De Morgan and
Charles Peirce Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism". Educated as a chemist and employed as a scientist for ...
, which culminated in the
algebraic logic In mathematical logic, algebraic logic is the reasoning obtained by manipulating equations with free variables. What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for ...
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 Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
, with the implication that mathematics founded on set theory could itself be conducted without variables.


Definition

A relation algebra is an
algebraic structure In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set o ...
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 , such that these operations and constants satisfy certain equations constituting an axiomatization of a calculus of relations. Roughly, a relation algebra is to a system of binary relations on a set containing the
empty Empty may refer to: ‍ Music Albums * ''Empty'' (God Lives Underwater album) or the title song, 1995 * ''Empty'' (Nils Frahm album), 2020 * ''Empty'' (Tait album) or the title song, 2001 Songs * "Empty" (The Click Five song), 2007 * ...
(0),
universal Universal is the adjective for universe. Universal may also refer to: Companies * NBCUniversal, a media and entertainment company ** Universal Animation Studios, an American Animation studio, and a subsidiary of NBCUniversal ** Universal TV, a t ...
(1), and
identity Identity may refer to: * Identity document * Identity (philosophy) * Identity (social science) * Identity (mathematics) Arts and entertainment Film and television * ''Identity'' (1987 film), an Iranian film * ''Identity'' (2003 film), an ...
relations and closed under these five operations as a group is to a system of
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pro ...
s of a set containing the identity permutation and closed under composition and inverse. However, the
first order In mathematics and other formal sciences, first-order or first order most often means either: * "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of hi ...
theory A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may ...
of relation algebras is not
complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...
for such systems of binary relations. 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 , and that both were equal to ''x''˘. Hence a relation algebra can equally well be defined as an algebraic structure . The advantage of this
signature A signature (; from la, signare, "to sign") is a Handwriting, handwritten (and often Stylization, stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and ...
over the usual one is that a relation algebra can then be defined in full simply as a
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 alph ...
for which is an involution, that is, . The latter condition can be thought of as the relational counterpart of the equation 1/(1/''x'') = ''x'' for ordinary arithmetic
reciprocal Reciprocal may refer to: In mathematics * Multiplicative inverse, in mathematics, the number 1/''x'', which multiplied by ''x'' gives the product 1, also known as a ''reciprocal'' * Reciprocal polynomial, a polynomial obtained from another pol ...
, 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.


Axioms

The axioms B1-B10 below are adapted from Givant (2006: 283), and were first set out by Tarski in 1948. ''L'' is a
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
under binary
disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...
, ∨, 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 (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 constant. ''L'' is a
monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoid ...
under binary composition (•) and nullary identity : :B4: ''A''•(''B''•''C'') = (''A''•''B'')•''C'' :B5: ''A''•I = ''A'' Unary converse ()˘ is an involution with respect to composition: :B6: ''A''˘˘ = ''A'' :B7: (''A''•''B'')˘ = ''B''˘•''A''˘ Axiom B6 defines conversion as an involution, whereas B7 expresses the antidistributive property of conversion relative to composition. 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, 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 Chapter 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 relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
s can be expressed as succinct RA equalities or inequalities. Below, an inequality of the form ''A'' ≤ ''B'' is shorthand for the Boolean equation . The most complete set of results of this nature is Chapter C of Carnap (1958), where the notation is rather distant from that of this entry. Chapter 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.


Expressive power

The metamathematics 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 In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The ter ...
generally. Hence RA proofs are carried out in a manner familiar to all mathematicians, unlike the case in
mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of forma ...
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 A turnstile (also called a turnpike, gateline, baffle gate, automated gate, turn gate in some regions) is a form of gate which allows one person to pass at a time. A turnstile can be configured to enforce one-way human traffic. In addition, a ...
, and
modus ponens In propositional logic, ''modus ponens'' (; MP), also known as ''modus ponendo ponens'' (Latin for "method of putting by placing") or implication elimination or affirming the antecedent, is a deductive argument form and rule of inference ...
. Because RA can express Peano arithmetic and set theory,
Gödel's incompleteness theorems Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of in formal axiomatic theories. These results, published by Kurt Gödel in 1931, are important both in mathematical logic and in the phil ...
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 classes, that RRA is a quasivariety, that is, axiomatizable by a universal Horn theory. In 1950,
Roger Lyndon Roger Conant Lyndon (December 18, 1917 – June 8, 1988) 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 ...
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 In mathematical logic, an axiom schema (plural: axiom schemata or axiom schemas) generalizes the notion of axiom. Formal definition An axiom schema is a formula in the metalanguage of an axiomatic system, in which one or more schematic variables ap ...
, 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: :Q1: :Q2: 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 (Proof by Maddux, see 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 In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a certain field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first hal ...
, are always representable as sets of subsets of some set, closed under union, intersection, and complement.


Examples

# 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''). # The motivating example of a relation algebra depends on the definition of a binary relation ''R'' on a set ''X'' as any subset , where is the
Cartesian square In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A ...
of ''X''. The power set 2''X''² consisting of all binary relations on ''X'' is a Boolean algebra. While can be made a relation algebra by taking , as per example (1) above, the standard interpretation of • is instead . That is, the
ordered pair In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
(''x'',''z'') belongs to the relation ''R''•''S'' just when there exists such that and . This interpretation uniquely determines ''R''\''S'' as consisting of all pairs (''y'',''z'') such that for all , 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 then establishes the converse ''R''˘ of ''R'' as consisting of all pairs (''y'',''x'') such that (''x'',''y'') ∈ ''R''. # An important generalization of the previous example is the power set 2''E'' where is any
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
on the set ''X''. This is a generalization because is itself an equivalence relation, namely the complete relation consisting of all pairs. While 2''E'' is not a subalgebra of when (since in that case it does not contain the relation , the top element 1 being ''E'' instead of ), 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 2''E'' for some equivalence relation ''E'' on some set. The previous section says more about the relevant metamathematics. # Let be a group. Then the power set 2^G is a relation algebra with the obvious boolean algebra operations, composition given by the
product of group subsets In mathematics, one can define a product of group subsets in a natural way. If ''S'' and ''T'' are subsets of a group ''G'', then their product is the subset of ''G'' defined by :ST = \. The subsets ''S'' and ''T'' need not be subgroups for this pr ...
, the converse by the inverse subset (A^ = \), and the identity by the singleton subset \. There is a relation algebra homomorphism embedding 2^G in 2^ which sends each subset A\subset G to the relation R_A = \. The image of this homomorphism is the set of all right-invariant relations on . # If group sum or product interprets composition, group inverse interprets converse, group identity interprets , and if ''R'' is a one-to-one correspondence, so that , then ''L'' is a group as well as a
monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoid ...
. B4-B7 become well-known theorems of
group theory In 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 ...
, so that RA becomes a proper extension of
group theory In 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 well as of Boolean algebra.


Historical remarks

De Morgan founded RA in 1860, but
C. S. Peirce Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism". Educated as a chemist and employed as a scientist for t ...
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öder 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 four deep had no RA equivalent.Korselt did not publish his finding. It was first published in
Leopold Loewenheim Leopold may refer to: People * Leopold (given name) * Leopold (surname) Arts, entertainment, and media Fictional characters * Leopold (''The Simpsons''), Superintendent Chalmers' assistant on ''The Simpsons'' * Leopold Bloom, the protagonist o ...
(1915) "Über Möglichkeiten im Relativkalkül," '' Mathematische Annalen'' 76: 447–470. Translated as "On possibilities in the calculus of relatives" in Jean van Heijenoort, 1967. ''A Source Book in Mathematical Logic, 1879–1931''. Harvard Univ. Press: 228–251.
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 b
Wolfram Kahl
* Carsten Sinz
ARA / An Automatic Theorem Prover for Relation Algebras

Stef Joosten
Relation Algebra as programming language using the Ampersand compiler
Journal of Logical and Algebraic Methods in Programming
Volume 100, April 2018, Pages 113–129. (see also https://ampersandtarski.gitbook.io/documentation)


See also

*
Algebraic logic In mathematical logic, algebraic logic is the reasoning obtained by manipulating equations with free variables. What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for ...
* Allegory (category theory) *
Binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
*
Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\t ...
*
Cartesian square In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A ...
*
Cylindric algebra In mathematics, the 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. Cylindric algebr ...
s * Extension in logic * Involution *
Logic of relatives Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism". Educated as a chemist and employed as a scientist for t ...
*
Logical matrix A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix (mathematics), matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets. ...
* Predicate functor logic *
Quantale In mathematics, quantales are certain partially ordered algebraic structures that generalize locales ( point free topologies) as well as various multiplicative lattices of ideals from ring theory and functional analysis (C*-algebras, von Neumann ...
* Relation *
Relation construction In 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 ...
*
Relational calculus The relational 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. The raison d'être ...
* Relational 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 alph ...
* Spatial-temporal reasoning *
Theory of relations In mathematics, a finitary relation over sets is a subset of the Cartesian product ; that is, it is a set of ''n''-tuples consisting of elements ''x'i'' in ''X'i''. Typically, the relation describes a possible connection between the elemen ...
*
Triadic relation In 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. Just as a binary relati ...


Footnotes


References

* * * * * * * * * * Schein, Boris M. (1970) "Relation algebras and function semigroups",
Semigroup Forum Semigroup Forum (print , electronic ) is a mathematics research journal published by Springer. The journal serves as a platform for the speedy and efficient transmission of information on current research in semigroup theory. Coverage in the jou ...
1: 1–62 * * * * {{cite book, last1=Tarski , first1=Alfred , last2=Givant, first2=Steven, year=1987, title=A Formalization of Set Theory without Variables, location=Providence RI, publisher=American Mathematical Society, isbn=9780821810415 , url=https://books.google.com/books?id=BgviDgAAQBAJ&q=%22A+Formalization+of+Set+Theory+without+Variables%22&pg=PP1


External links

*Yohji AKAMA, Yasuo Kawahara, and Hitoshi Furusawa,
Constructing Allegory from Relation Algebra and Representation Theorems.
*Richard Bird, Oege de Moor, Paul Hoogendijk,

* R.P. de Freitas and Viana,
A Completeness Result for Relation Algebra with Binders.

Peter Jipsen

Relation algebras
!
Relation algebras
I
Mathematical structures.
If there are problems with LaTeX, see an old HTML versio
here.
broken links--> **
Foundations of Relations and Kleene Algebra.
**
Computer Aided Investigations of Relation Algebras.
**

*
Vaughan Pratt Vaughan Pratt (born April 12, 1944) is a Professor Emeritus at Stanford University, who was an early pioneer in the field of computer science. Since 1969, Pratt has made several contributions to foundational areas such as search algorithms, sorti ...
: **
Origins of the Calculus of Binary Relations.
A historical treatment. **
The Second Calculus of Binary Relations.
* Priss, Uta: **
An FCA interpretation of Relation Algebra.
**

Links to publications and software
Kahl, Wolfram
and Gunther Schmidt
Exploring (Finite) Relation Algebras Using Tools Written in Haskell.
an

from McMaster University. Boolean algebra Algebraic logic Mathematical axioms Mathematical logic Mathematical relations