In
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
and
abstract algebraAbstract 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 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...
equipped with an involution called "converse". The motivating example of a relation algebra is the algebra 2
X² of all
binary 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...
s on a set
X, with
R•
S interpreted as the usual
composition of binary 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 :If and are two binary relations, then...
and the converse of
R as the
inverse 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'. In formal terms, if...
. Relation algebra emerged in the 19th century work of
Augustus De MorganAugustus De Morgan was a British mathematician and logician. He formulated De Morgan's laws and introduced the term mathematical induction, and made its idea rigorous. The crater De Morgan on the Moon is named after him....
and Charles Peirce, which culminated in the
algebraic logicIn mathematical logic, algebraic logic is the study of logic presented in an algebraic style.-Algebras as models of logics:Algebraic logic treats algebraic structures, often bounded lattices, as models of certain logics, making logic a branch of order theory.In algebraic logic:* Variables are...
of
Ernst SchröderErnst 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 present-day purely equational form or relation algebra was developed by
Alfred TarskiAlfred Tarski was a Polish logician and mathematician...
and his students, starting in the 1940s.
Definition
A
relation algebra (
L, ∧, ∨, ¬, 0, 1, •,
I, ▷, ◁,
) is an algebraic structure such that
(
L, ∧, ∨, •,
I, ▷, ◁) is a
residuated 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...
, and
the unary operation
x satisfies
x▷
I =
x =
I◁
x.
Since
x▷
y can be defined in terms of composition and converse as
x•
y, and dually
x◁
y as
x•
y, it is not necessary to include ▷ or ◁ in the signature, which can therefore be simplified to (
L, ∧, ∨, ¬, 0, 1, •,
I,
), the more usual form of the signature for relation algebras. On the other hand
x is definable as either
x▷
I or
I◁
x, in which case a relation algebra can have the same signature as a residuated Boolean algebra. With that definition the axioms become (
x▷
I)▷
I =
x =
I◁(
I◁
x). But this simply asserts that ▷
I and
I◁ are involutions. Jónsson and Tsinakis have shown that if either one is an involution then so is the other and they are then the same operation, namely converse. This leads to a particularly straightforward definition:
- A relation algebra is a residuated Boolean algebra (L, ∧, ∨, ¬, 0, 1, •, I, ▷, ◁) such that I◁ is an involution.
When
x◁
y is viewed as a form of quotient of
x by
y, with
I as the corresponding multiplicative unit,
x =
I◁
x can be understood as the
reciprocal of
x by syntactic analogy with 1/
x, a term some authors use synonymously with converse.
Since residuated Boolean algebras are axiomatized with finitely many equations, so are relation algebras, which therefore form a finitely axiomatized
varietyIn 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...
called
RA, the variety of relation algebras.
Axioms
The axioms
B1-B10 below are adapted from Givant (2006: 283), and were first set out by
TarskiAlfred Tarski was a Polish logician and mathematician...
in 1948. This axiomatization is predicated on a relation algebra being an
algebraic structureIn algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...
over some Cartesian square
L, having
signatureIn 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...
⟨
L,∨,•,
–,
,
I⟩ of
typeIn logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the number of domains in the corresponding Cartesian product. The term springs from such words as unary, binary, ternary,...
⟨2,2,1,1,0⟩.
L is a
Boolean algebraIn abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations...
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
HuntingtonEdward Vermilye Huntington was an American mathematician....
(1933).
L is a
monoidIn 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...
under binary
compositionIn 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 :If and are two binary relations, then...
(•) and nullary identity
I:
- B4: A•(B•C) = (A•B)•C
- B5: A•I = A
Unary
converseIn 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'. In formal terms, if...
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 MorganAugustus De Morgan was a British mathematician and logician. He formulated De Morgan's laws and introduced the term mathematical induction, and made 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 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...
s can be expressed as succinct inequalities or equalities using
RA operations. Below, an inequality of the form
A≤
B is shorthand for a Boolean equation of the form
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 those of this entry. Chpt. 3.2 of Suppes (1960) contains fewer results, but they are presented as ZFC theorems, using a notation that more resembles that of this entry. Neither Carnap nor Suppes formulate their results using the
RA of this entry, or in an equational manner.
| R is | 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. In that it is biconditional, the connective can be likened to the standard material conditional combined with its reverse ; hence the name...
: |
|---|
| Surjective |
R•R ≤ I |
| Injective(R surjective) |
R•R ≤ I |
| 1-to-1 |
R is surjective and injective. |
| Total 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 isNote that this implies reflexivity....
or Connected |
I ≤ R∨R |
| Functional |
|
FunctionIn mathematics, a function is a relation between a given set of elements and another set of elements , which associates each element in the domain with exactly one element in the codomain...
|
R is functional and total. |
1-1 FunctionIn mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f = y and no unmapped element remains in both X and Y.Alternatively, f is bijective if it is a one-to-one correspondence...
|
R•R = I and R•R = I.
R is total, functional, and injective. |
| Reflexive In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation R on S where xRx holds true for every x in S.-Related terms:...
|
I ≤ R |
| Irreflexive |
R ∧ I = 0. (0 = I–) |
| Transitive 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 In mathematics, especially in order theory, preorders are binary relations that satisfy certain conditions. For example, all partial orders and equivalence relations are preorders. The name quasiorder is also common for preorders. Other names are pre-order, quasi-order, and quasi order...
|
R is reflexive and transitive. |
AntisymmetricIn 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:or equally,An example of an antisymmetric relation is the subset relation:...
|
R ∧ R ≤ I |
| Partial order |
R is an antisymmetric preorder. |
| Total order In mathematics and 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 In mathematics and 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. |
SymmetricIn 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 |
EquivalenceIn mathematics, an equivalence relation is, loosely, a binary relation on a set that specifies how to split up the set into subsets such that every element of the larger set is in exactly one of the subsets...
|
R•R = R. R is a symmetric preorder. |
| Asymmetric Asymmetric often means, simply: not symmetric. In this sense an asymmetric relation is a binary relation which is not a symmetric relation.In some texts the word is given the following stronger definition...
|
R ≠ R |
| Dense 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 < y, there is a z in X such that x < z < y....
|
R∧0 ≤ (R∧0)•(R∧0). |
Expressive power
The
metamathematicsMetamathematics 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 algebraAbstract 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 logicMathematical logic is a subfield of mathematics with close connections to 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, exactly the)
first-order logicFirst-order logic is a formal logic used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, and predicate logic...
(FOL) formulas containing no more than three variables. (A given variable can be quantified multiple times as long as the quantifiers do not nest more than 3 deep.) 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
connectivesIn 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 dependant on the respective truth values of the original sentences.Each logical connective can be expressed as a...
, quantifiers,
turnstilesIn mathematical logic and computer science the symbol 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" or "proves"...
, and
modus ponensIn classical logic, modus ponendo ponens is a valid, simple argument form sometimes referred to as affirming the antecedent or the law of detachment...
. Because
RA can express Peano arithmetic and set theory,
Gödel's incompleteness theoremsIn mathematical logic, Gödel's incompleteness theorems, proved by Kurt Gödel in 1931, are two theorems stating inherent limitations of all but the most trivial formal systems for arithmetic of mathematical interest. The theorems are of considerable importance to the philosophy of mathematics...
apply to it;
RA is
incompleteIncomplete 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
undecidableUndecidable has more than one meaning:In mathematical logic:* A decision problem is called undecidable if no algorithm can decide it, such as for Turing's halting problem; see also under Decidable and Undecidable problem....
. (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 comprised of binary relations on some set, and closed under the standard interpretations of the
RA operations. It is easily shown, e.g. using the method of
pseudoelementary classIn 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, 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, that is, the variety generated by
RRA is a proper subvariety of the variety
RA. In 1955,
Alfred TarskiAlfred Tarski was a Polish logician and mathematician...
showed that
RRA is itself a variety, which however, as shown by Donald Monk in 1964, has no finite axiomatization, unlike
RA which is finitely axiomatized by definition. That not every relation algebra is representable is a fundamental way relation algebras differ from Boolean algebras, which are
always representableIn 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...
as sets of subsets of some set closed under union, intersection, and complement.
Examples
1. Any Boolean algebra can be turned into a relation algebra 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². The power set 2
X² consisting of all binary relations on
X is a Boolean algebra. While 2
X² can be made a relation algebra by taking
R•
S =
R∧
S as for the preceding example, the standard interpretation of • is instead given by
x(
R•
S)
z = ∃
y.
xRySz. That is, 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 to consist 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 2
E where
E ⊆
X² is any
equivalence relationIn mathematics, an equivalence relation is, loosely, a binary relation on a set that specifies how to split up the set into subsets such that every element of the larger set is in exactly one of the subsets...
on the set
X. This is a generalization because
X² is itself an equivalence relation, namely the complete relation consisting of all pairs. While 2
E is not a subalgebra of 2
X² 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 made 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. Refer to the previous section for more on 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
groupIn 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
monoidIn 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...
.
B4-
B7 become well-known theorems of
group theoryIn 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 relation algebra becomes a proper extension of
group theoryIn 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, a fact indicative of its great expressive power.
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 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 MathematicaThe Principia Mathematica is a 3-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912 & 1913...
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 Tarski and Givant (1987), the definitive reference for this subject. For more on the history of
RA, see Maddux (1991, 2006).
Software
See also
- Algebraic logic
In mathematical logic, algebraic logic is the study of logic presented in an algebraic style.-Algebras as models of logics:Algebraic logic treats algebraic structures, often bounded lattices, as models of certain logics, making logic a branch of order theory.In algebraic logic:* Variables are...
- Allegory (category theory)
In mathematics, in the subject of 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...
- 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...
- Cartesian product
In mathematics, a Cartesian product is the direct product of two sets. The Cartesian product is named after René Descartes, whose formulation of analytic geometry gave rise to this concept....
- Cartesian square
- 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 :If and are two binary relations, then...
- Converse of a 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'. In formal terms, if...
- Cylindric algebra
The notion of cylindric algebra, invented by Alfred Tarski, arises naturally in the algebraization of first-order logic. This is comparable to the role Boolean algebras play for propositional logic...
s
- Extension in 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
- Relation
In mathematics , a relation is a property that assigns truth values to combinations of k individuals. Typically, the property describes a possible connection between the components of a k-tuple...
- 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 the focus of consideration is called the faciendum...
- Relation reduction
In logic and mathematics, relation reduction and relational reducibility have to do with the extent to which a given relation is determined by an indexed family or a sequence of other relations, called the relation dataset. The relation under examination is called the reductandum...
- Relational calculus
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...
- Relational algebra
Relational algebra, an offshoot of first-order logic , deals with a set of finitary relations which is closed under certain operators. These operators operate on one or more relations to yield a relation...
- Relative product of relations
- 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...
- Spatial-temporal reasoning
Spatial-temporal reasoning is used in both the field 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.Academia has...
- Theory of relations
The 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 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....
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:
- Vaughan Pratt:
- Priss, Uta, "An FCA interpretation of Relation Algebra."
- Kahl, Wolfram, and Schmidt, Gunther, "Exploring (Finite) Relation Algebras Using Tools Written in Haskell." See homepage of the whole project.