Relation algebra

Relation algebra (RA), a proper extension of the two-element Boolean algebra 2, consists of two binary operations, juxtaposition and relative product, two unary operations, complementation and converse, and the distinguished constant 1.

Definition

For an introduction to RA, see Maddux (2006); for a more advanced treatement; see Tarski and Givant (1987). In what follows, Greek letters denote syntactical metavariables ranging over formulae.

Given any nonempty set A, Boolean algebra is the algebra of its power set, and RA is the algebra of its Cartesian product set B. B is the Cartesian product of A with itself, and thus the set of all possible ordered pairs constructible from the members of A. Hence B={x: x⊆A×A}. A may, of course, be coextensive with the universe in first order logic.

Syntax: The notation described here for the binary and unary operations of RA is not the conventional one. The syntax of 2 is:

• () and single Latin letters are atoms;
• If φ and δ are formulae, so are (φ) and φδ. The latter binary operation is called juxtaposition.

To this Boolean syntax added syntax peculiar to RA:

• 1 is primitive, and the other constants are derived from 1 as follows: ()=(1)1, an instance of BA2 below, and 0=(1);
• If φ and δ are formulae, so are ⟨φ⟩ and [φδ].

In the terminology of universal algebra], RA is a <B,--,[--],(-),⟨-⟩,1> algebra of type <2,2,1,1,0>, with all members of B being ordered pairs.

Boolean Semantics: The intended interpretation of (-) is Boolean complementation; that of juxtaposition is one of Boolean meet or join. If φδ denotes the meet of φ and δ, ((φ)(δ)) denotes their join, and vice versa. Complementation with nothing in its scope denotes one of the two lattice bounds Boolean algebra requires. On the Boolean syntax and semantics employed here, see laws of form.

RA Semantics: 1 denotes the identity relation, consisting of all ordered pairs whose left and right members are identical. 0 denotes the diversity relation, namely all ordered pairs whose left and right members are not identical. If the ordered pair (φ,δ) satisfies some relation R, then (δ,φ) satisfies ⟨R⟩. Given that (δ,γ) satisfies the relation S, (φ,γ) satisfies [RS]. Hence the intended interpretations of ⟨-⟩ and [--] are converse and relative product. Hence the customary notations for ⟨R⟩ and [RS] are R and R|S, respectively.

Axioms

Tarski (1941) proposed the following axiomatization of RA.

Label	Axiom	Remarks
	Axioms for the Boolean algebra 2
A1	()()=()
A2	φ(())=φ	The blank page is a lattice bound.
BA1	φδγ=δγφ	Concatenation commutes and associates.
BA2	(φ)φ=()
BA3	φ(φδ)=φ(δ)
	Axioms Peculiar to RA.
RA1	⟨⟨φ⟩⟩=φ	((φ))=φ is a theorem.
RA2	⟨φδ⟩=⟨φ⟩⟨δ⟩	See RA5 below.
		Relative Product:
RA3	[[φδ]γ]=[φ[δγ]]	Associates.
RA4	[φ1]=[1φ]=φ	Has 1 as identity element.
RA5	⟨[φδ]⟩=[⟨δ⟩⟨φ⟩]	Note order of φ and δ.
RA6	[((φγ))δ]=[φδ][γδ]	Distributes over Concatenation.
RA7	[⟨φ⟩([φδ])]⟨δ⟩=⟨δ⟩	Interacts with other 3 operations via cyclic law.

BA1-BA3 define a Boolean lattice, and () and (()) are the associated lattice bounds. BA1-BA3 may be replaced by any basis for Boolean algebra. Note that φ and δ in RA2 may be freely interchanged on either side of '=', while the order of φ and δ in RA5 cannot be altered. RA7 is a concise version of the cyclic law: ([φγ])(δ) = ([⟨φ⟩δ])(γ) = ([δ⟨γ⟩])(φ).

RA6 assures that RA is a ringoid. Moreover, B, [--], ⟨-⟩, and 1 form a monoid. A monoid does not require a unary operation such as ⟨-⟩, but this is immaterial because ⟨-⟩ is easily defined in terms of 1 and [--], as follows. Redefine [φδ] so as to have the same meaning as one of [φ⟨δ⟩] or [δ⟨φ⟩]. Hence [1δ] ⇔ ⟨δ⟩ and [φ[1δ]] ⇔ [φδ]. Now let E be the set membership relation, so that E∈R. If at least one of the following two axioms applies to E:

• Given any set x, the unit set {x} exists;
• Given any two sets, their union and Cartesian product exist,

1 and () can then be defined in terms of E, [--], and (-) as follows: 1=([E(E)]) and ()=(E)E. On these and other reductions in the primitives of RA, see Tarski and Givant (1987: §§5.2-3).

Expressive power

RA can express any formula of first order logic (FOL) formula having no part lying within the scope of more than three quantifiers. This proviso is commonly but perhaps misleadingly expressed as "RA can express any FOL formula having no more than three quantified variables." Surprisingly, this fragment of FOL suffices to express Peano arithmetic and all axiomatic set theories having any following. Because RA has the expressive power of Peano arithmetic and set theory, the classic theorems of Gödel apply to it. However, just as the ZFC axioms of set theory and the Peano axioms are adequate for the entire mathematical mainstream, likewise there is no proposition of RA known to be true by semantic methods but which cannot be proved from the axioms above.

The definition of B limits the scope of RA to binary relations, but this is not a serious limitation, simply because set theory, whose enormous expressive power is beyond question, requires but a single binary relation, set membership. The definitive treatment of the metamathematics of RA is Tarski and Givant (1987).

Historical Remarks

DeMorgan founded RA in 1860, but Charles Peirce took it much further. In his Vorlesungen (1890-1905), Ernst Schröder, who admired Peirce's work, codified and extended RA, giving it its definitive form. Principia Mathematica drew strongly on Schröder's theory of relations, but cited him but once, for his notation. Tarski (1941) is the founding paper for contemporary work in RA; he and his students have written on the subject down to the present day. Much of the content of Tarski and Givant (1987) was worked out by Tarski alone in the 1940s, who returned to the subject in the 1970s with the help of Steven Givant. For more information on the evolution of RA, see Maddux (2006)

References

• Maddux, Roger D., 2006. Relation Algebras, vol. 150 in Studies in Logic and the Foundations of Mathematics. Elsevier Science.
• Alfred Tarski,1941, "On the calculus of relations," Journal of Symbolic Logic 6: 73-89.
• ------, and Givant, Steven, 1987. A Formalization of Set Theory without Variables. Providence RI: American Mathematical Society.