Binary Relation: Difference between revisions

** In [[mathematics]], a '''binary relation''' on a [[set (mathematics)|set]] ''A'' is a collection of [[ordered pair]]s of elements of ''A''. In other words, it is a [[subset]] of the [[Cartesian product]] ''A''² = . More generally, a binary relation between two sets ''A'' and ''B'' is a subset of . The terms <B>correspondence''', '''dyadic relation</B> and '''2-place relation</B> are synonyms for binary relation. <P> An example is the "[[divides]]" relation between the set of [[prime number]]s '''P</B> and the set of [[integer]]s '''Z''', in which every prime ''p'' is associated with every integer ''z'' that is a [[divisibility|multiple]] of ''p'' (but with no integer that is not a multiple of ''p''). 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. <P> Binary relations are used in many branches of mathematics to model concepts like "[[inequality (mathematics)|is greater than]]", "[[Equality (mathematics)|is equal to]]", and "divides" in [[arithmetic]], "[[Congruence (geometry)|is congruent to]]" in [[geometry]], "is adjacent to" in [[graph theory]], "is [[orthogonal]] to" in [[linear algebra]] and many more. The concept of [[function (mathematics)|function]] is defined as a special kind of binary relation. Binary relations are also heavily used in [[computer science]]. <P> A binary relation is the special case of an [[finitary relation|''n''-ary relation]] ''R''&nbsp;⊆&nbsp;''A''₁&nbsp;×&nbsp;…&nbsp;×&nbsp;''A''_''n'', that is, a set of [[tuple|''n''-tuple]]s where the ''j''th component of each ''n''-tuple is taken from the ''j''th domain ''A''_''j'' of the relation. An example for a ternary relation on '''Z'''&times;'''Z'''&times;'''Z''' is "lies between ... and ...", containing e.g. the triples , , and . <P> In some systems of [[axiomatic set theory]], relations are extended to [[class (mathematics)|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]].