Relation algebra on arvau

Wikipedia / Relation algebra

In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation of all binary relations, that is, subsets of the cartesian square interpreted as the usual composition of binary relations as the converse 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.

Definition

A relation algebra is an algebraic structure equipped with the Boolean operations, the relational operations of composition and converse, 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), universal), and identity relations and closed under these five operations as a group is to a system of permutations of a set containing the identity permutation and closed under composition and inverse. However, the first-order theory of relation algebras is not complete for such systems of binary relations.

. The advantage of this signature over the usual one is that a relation algebra can then be defined in full simply as a residuated Boolean algebra 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.

Axioms

The axioms B1-B10 below are adapted from Givant (2006: 283), and were first set out by Tarski in 1948.

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 constant.

is a monoid under binary composition) and nullary:

Unary converse is an involution with respect to composition:

Axiom B6 defines conversion as an involution, whereas B7 expresses the antidistributive property of conversion relative to composition.

Converse and composition distribute over disjunction:

B10 is Tarski's equational form of the fact, discovered by Augustus De Morgan

B10

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 relations can be expressed as succinct RA.

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 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, quantifierss, 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 classes, 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.

Q-relation algebras

An RA is a Q-relation algebra (QRA) if, in addition to B1-B10 such that (Tarski and Givant 1987: §8.4):

. 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, 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).
is the cartesian square. The power set. That is, the ordered pair.
is any equivalence relation), 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 on some set. The previous section says more about the relevant metamathematics.
be a group is a relation algebra with the obvious Boolean algebra operations, composition given by the product of group subsets), and the identity by the singleton subset.
If group sum or product interprets composition, group inverse is a one-to-one correspondence, is a group. 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.

Historical remarks

De Morgan 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ö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. 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).