BinaryRelation

Category: SetTheory
2008-01-02

In mathematics, a binary relation (or a dyadic or 2-place relation) is an arbitrary association of elements within a set or with elements of another set.

An example is the "divides" relation between the set of prime numbers P and the set of integers Z, in which every prime p is associated with every integer z that is a multiple of p, but no other. In this relation, for instance, the prime 2 is associated with numbers that include -4, 0, 6, 10, but not 1 or 9; and the prime 3 is associated with numbers that include 0, 6, and 9, but not 4 or 13.

Binary relations are used in many branches of mathematics to model concepts like "is greater than", "is equal to", and "divides" in arithmetic, "is congruent to" in geometry, "is adjacent to" in graph theory, and many more. The all-important concept of function is defined as a special kind of binary relation. Binary relations are also heavily used in computer science, especially within the relational model for databases.

A binary relation is a special case of a k-ary relation, that is, a set of k-tuples where the jth component of each k-tuple is taken from the jth domain Xj of the relation. A k-ary relation among elements of a single set is said to be homogeneous.

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.

Formal Definition

A binary relation R is usually defined as an ordered triple (X, Y, G) where X and Y are arbitrary sets (or classes), and G is a subset of the Cartesian product X × Y. The sets X and Y are called the domain and codomain, respectively, of the relation, and G is called its graph.

The statement (x,y) ∈ R is read "x is R-related to y", and is denoted by xRy or R(x,y). The latter notation corresponds to viewing R as the characteristic function of the set of pairs G.

The order of the elements in each pair of G is important: if a ≠ b, then aRb and bRa can be true or false, independently of each other.

Some important classes of binary relations R over X and Y are listed below

Special Type of BinaryRelation

left-total: for all x in X there exists a y in Y such that xRy (this property, although sometimes also referred to as total, is different from the definition of total in the next section).
surjective or right-total: for all y in Y there exists an x in X such that xRy.
functional (also called right-definite): for all x in X, and y and z in Y it holds that if xRy and xRz then y = z.
injective: for all x and z in X and y in Y it holds that if xRy and zRy then x = z.
bijective: left-total, right-total, functional, and injective.

A binary relation that is functional is called a partial function; a binary relation that is both left-total and functional is called a function.