Binary relation

Binary relations are used in many branches of mathematics to model a wide variety of concepts. These include, among others:

A function may be defined as a special kind of binary relation.[3] Binary relations are also heavily used in computer science.

Since relations are sets, they can be manipulated using set operations, including union, intersection, and complementation, and satisfying the laws of an algebra of sets. Beyond that, operations like the converse of a relation and the composition of relations are available, satisfying the laws of a calculus of relations, for which there are textbooks by Ernst Schröder,[4] Clarence Lewis,[5] and Gunther Schmidt.[6] A deeper analysis of relations involves decomposing them into subsets called concepts, and placing them in a complete lattice.

In some systems of axiomatic set theory, relations are extended to classes, which are generalizations of sets. This extension is needed for, among other things, modeling the concepts of "is an element of" or "is a subset of" in set theory, without running into logical inconsistencies such as Russell's paradox.

3) Visualization of relations leans on graph theory: For relations on a set (homogeneous relations), a directed graph illustrates a relation and a graph a symmetric relation. For heterogeneous relations a hypergraph has edges possibly with more than two nodes, and can be illustrated by a bipartite graph.

Just as the clique is integral to relations on a set, so bicliques are used to describe heterogeneous relations; indeed, they are the "concepts" that generate a lattice associated with a relation.

4) Hyperbolic orthogonality: Time and space are different categories, and temporal properties are separate from spatial properties. The idea of simultaneous events is simple in absolute time and space since each time t determines a simultaneous hyperplane in that cosmology. Herman Minkowski changed that when he articulated the notion of relative simultaneity, which exists when spatial events are "normal" to a time characterized by a velocity. He used an indefinite inner product, and specified that a time vector is normal to a space vector when that product is zero. The indefinite inner product in a composition algebra is given by

As a relation between some temporal events and some spatial events, hyperbolic orthogonality (as found in split-complex numbers) is a heterogeneous relation.[16]

Examples of four types of binary relations over the real numbers: one-to-one (in green), one-to-many (in blue), many-to-one (in red), many-to-many (in black).

Some important types of binary relations R over sets X and Y are listed below.

Totality properties (only definable if the domain X and codomain Y are specified):

Uniqueness and totality properties (only definable if the domain X and codomain Y are specified):

The identity element is the universal relation. For example, the relation "is divisible by 6" is the intersection of the relations "is divisible by 3" and "is divisible by 2".

If a relation is reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive, total, trichotomous, a partial order, total order, strict weak order, total preorder (weak order), or an equivalence relation, then so too are its restrictions.

However, the transitive closure of a restriction is a subset of the restriction of the transitive closure, i.e., in general not equal. For example, restricting the relation "x is parent of y" to females yields the relation "x is mother of the woman y"; its transitive closure doesn't relate a woman with her paternal grandmother. On the other hand, the transitive closure of "is parent of" is "is ancestor of"; its restriction to females does relate a woman with her paternal grandmother.

Binary relations over sets X and Y can be represented algebraically by logical matrices indexed by X and Y with entries in the Boolean semiring (addition corresponds to OR and multiplication to AND) where matrix addition corresponds to union of relations, matrix multiplication corresponds to composition of relations (of a relation over X and Y and a relation over Y and Z),[21] the Hadamard product corresponds to intersection of relations, the zero matrix corresponds to the empty relation, and the matrix of ones corresponds to the universal relation. Homogeneous relations (when X = Y) form a matrix semiring (indeed, a matrix semialgebra over the Boolean semiring) where the identity matrix corresponds to the identity relation.[22]

Another solution to this problem is to use a set theory with proper classes, such as NBG or Morse–Kelley set theory, and allow the domain and codomain (and so the graph) to be proper classes: in such a theory, equality, membership, and subset are binary relations without special comment. (A minor modification needs to be made to the concept of the ordered triple (X, Y, G), as normally a proper class cannot be a member of an ordered tuple; or of course one can identify the binary relation with its graph in this context.)[23] With this definition one can for instance define a binary relation over every set and its power set.

Some important properties that a homogeneous relation R over a set X may have are:

All operations defined in the section Operations on binary relations also apply to homogeneous relations. Beyond that, a homogeneous relation over a set X may be subjected to closure operations like:

In contrast to homogeneous relations, the composition of relations operation is only a partial function. The necessity of matching range to domain of composed relations has led to the suggestion that the study of heterogeneous relations is a chapter of category theory as in the category of sets, except that the morphisms of this category are relations. The objects of the category Rel are sets, and the relation-morphisms compose as required in a category.[citation needed]

Binary relations have been described through their induced concept lattices: A concept CR satisfies two properties: (1) The logical matrix of C is the outer product of logical vectors

The MacNeille completion theorem (1937) (that any partial order may be embedded in a complete lattice) is cited in a 2013 survey article "Decomposition of relations on concept lattices".[32] The decomposition is

Particular cases are considered below: E total order corresponds to Ferrers type, and E identity corresponds to difunctional, a generalization of equivalence relation on a set.

Relations may be ranked by the Schein rank which counts the number of concepts necessary to cover a relation.[33] Structural analysis of relations with concepts provides an approach for data mining.[34]

The logical matrix of such a relation R can be re-arranged as a block matrix with blocks of ones along the diagonal. In terms of the calculus of relations, in 1950 Jacques Riguet showed that such relations satisfy the inclusion

He named these relations difunctional since the composition F GT involves univalent relations, commonly called functions.

In 1997 researchers found "utility of binary decomposition based on difunctional dependencies in database management."[37] Furthermore, difunctional relations are fundamental in the study of bisimulations.[38]

In the context of homogeneous relations, a partial equivalence relation is difunctional.

In automata theory, the term rectangular relation has also been used to denote a difunctional relation. This terminology recalls the fact that, when represented as a logical matrix, the columns and rows of a difunctional relation can be arranged as a block diagonal matrix with rectangular blocks of true on the (asymmetric) main diagonal.[39]

A strict order on a set is a homogeneous relation arising in order theory. In 1951 Jacques Riguet adopted the ordering of a partition of an integer, called a Ferrers diagram, to extend ordering to binary relations in general.[40]

The corresponding logical matrix of a general binary relation has rows which finish with a sequence of ones. Thus the dots of a Ferrer's diagram are changed to ones and aligned on the right in the matrix.

Suppose B is the power set of A, the set of all subsets of A. Then a relation g is a contact relation if it satisfies three properties:

The set membership relation, ε = "is an element of", satisfies these properties so ε is a contact relation. The notion of a general contact relation was introduced by Georg Aumann in 1970.[41][42]

In terms of the calculus of relations, sufficient conditions for a contact relation include

On the other hand, Fringe(R) = ∅ when R is a dense, linear, strict order.[43]

There is a pleasant symmetry in Wagner's work between heaps, semiheaps, and generalised heaps on the one hand, and groups, semigroups, and generalised groups on the other. Essentially, the various types of semiheaps appear whenever we consider binary relations (and partial one-one mappings) between different sets A and B, while the various types of semigroups appear in the case where A = B.