FACTOID # 19: Cheap sloppy joes: Looking for reduced-price lunches for schoolchildren? Head for Oklahoma!
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Binary relation

In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. Euclid, Greek mathematician, 3rd century BC, known today as the father of geometry; shown here in a detail of The School of Athens by Raphael. ... This article is about sets in mathematics. ...


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 to every integer z that is a multiple of p. In this relation, for instance, the prime 2 is associated to -4, 0, 6, 10, but not with 1 or 9; and the prime 3 is associated with 0, 6, and 9, but not with 4 or 13. In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ...


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 case of binary relation. Binary relations are also heavily used in computer science, especially within the relational model for databases. Arithmetic or arithmetics (from the Greek word αριθμός = number) is the oldest and simplest branch of mathematics, used by almost everyone, for tasks ranging from simple daily counting to advanced science and business calculations. ... Table of Geometry, from the 1728 Cyclopaedia. ... A labeled graph with 6 vertices and 7 edges. ... Partial plot of a function f. ... The relational model for database management is a data model based on predicate logic and set theory. ... The relational model was proposed by E. F. Codd in 1970. ...


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. In mathematics, a finitary relation is defined by one of the formal definitions given below. ...


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. This article or section is in need of attention from an expert on the subject. ... In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... Russells paradox (also known as Russells antinomy) is a paradox discovered by Bertrand Russell in 1901 which shows that the naive set theory of Frege is contradictory. ...

Contents

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. A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ... In mathematics, the Cartesian product (or direct product) of two sets X and Y, denoted X × Y, is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y: The Cartesian product is named after René Descartes... In mathematics, the domain of a function is the set of all input values to the function. ... A codomain in mathematics is the set of output values associated with (or mapped to) the domain of inputs in a function. ...


The statement (x,y) ∈ G 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. Some mathematicians use the phrase characteristic function synonymously with indicator function. ...


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


Is a relation more than its graph?

According to the definition above, two relations with the same graph may be different, if they differ in the sets X and Y. For example, if G = {(1,2),(1,3),(2,7)}, then (Z,Z, G), (R, N, G), and (N, R, G) are three distinct relations.


Some mathematicians do not consider the sets X and Y to be part of the relation, and therefore define a binary relation as being a subset of X×Y, i.e. just the graph G. According to this view, the set of pairs {(1,2),(1,3),(2,7)} is a relation from any set that contains {1,2} to any set that contains {2,3,7}.


Either approach is adequate for most uses, provided that one attends to the necessary changes in language, notation, and the definitions of concepts like restrictions, composition, inverse relation, and so on. The choice between the two definitions usually matters only in very formal contexts, like category theory. In mathematics, the notion of restriction finds a general definition in the context of sheaves. ... In mathematics, the composition of binary relations is a concept of forming a new relation S o R from two given relations R and S, having as its most well-know special case the composition of functions. ... In logic and mathematics, the inverse relation of a binary relation is the binary relation defined by . ... In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ...


Example

Example: Suppose there are four objects: {ball, car, doll, gun} and four persons: {John, Mary, So, Venus}. Suppose that John owns the ball, Mary owns the doll, and Venus owns the car. No one owns the gun and So owns nothing. Then the binary relation "is owned by" is given as

R=({ball, car, doll, gun}, {John, Mary, So, Venus}, {(ball, John), (doll, Mary), (car, Venus)}).

Thus the first element of R is the set of objects, the second is the set of people, and the last element is a set of ordered pairs of the form ( object, owner ).


The pair (ball, John), denoted by ballRJohn means that the ball is owned by John.


Two different relations could have the same graph. For example: the relation

({ball, car, doll, gun}, {John, Mary, Venus}, {(ball,John), (doll, Mary), (car, Venus)})

is different from the previous one as everyone is an owner. But the graphs of the two relations are the same.


Nevertheless, R is usually identified or even defined as G(R) and "an ordered pair (x, y) ∈ G(R)" is usually denoted as "(x, y) ∈ R".


Special types of binary relations

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


Total or partial

  • 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).
  • right-total or surjective: for all y in Y there exists an x in X such that xRy.

Functional, injective, surjective, bijective

  • functional: for all x in X, and y and z in Y it holds that if xRy and xRz then y = z.
  • surjective: for all y in Y there exists an x in X such that xRy.
  • 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 and functional.

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. In mathematics, a partial function is a relation that associates each element of a set (sometimes called its domain) with at most one element of another (possibly the same) set, called the codomain. ... Partial plot of a function f. ...


Relations over a set

If X = Y then we simply say that the binary relation is over X. Or it is an endorelation over X.


Some important classes of binary relations over a set X are:

  • reflexive: for all x in X it holds that xRx. For example, "greater than or equal to" is a reflexive relation but "greater than" is not.
  • irreflexive: for all x in X it holds that not xRx. "Greater than" is an example of an irreflexive relation.
  • coreflexive: for all x and y in X it holds that if xRy then x = y.
  • symmetric: for all x and y in X it holds that if xRy then yRx. "Is a blood relative of" is a symmetric relation, because x is a blood relative of y if and only if y is a blood relative of x.
  • antisymmetric: for all x and y in X it holds that if xRy and yRx then x = y. "Greater than or equal to" is an antisymmetric relation, because if xy and yx, then x=y.
  • asymmetric: for all x and y in X it holds that if xRy then not yRx. "Greater than" is an asymmetric relation, because of x>y then not y>x.
  • transitive: for all x, y and z in X it holds that if xRy and yRz then xRz. "Is an ancestor of" is a transitive relation, because if x is an ancestor of y and y is an ancestor of z, then x is an ancestor of z.
  • total (or linear): for all x and y in X it holds that xRy or yRx (or both). "Is greater than or equal to" is an example of a total relation (this definition for total is different from the one in the previous section).
  • trichotomous: for all x and y in X exactly one of xRy, yRx or x = y holds. "Is greater than" is an example of a trichotomous relation.
  • Euclidean: for all x, y and z in X it holds that if xRy and xRz, then yRz.
  • extendable (or serial): for all x in X, there exists y in X such that xRy. "Is greater than" is an extendable relation on the integers. But it is not an extendable relation on the positive integers, because there is no y in the positive integers such that 1>y.
  • set-like: for every x in X, the class of all y such that yRx is a set. (This makes sense only if we allow relations on proper classes.) The usual ordering < on the class of ordinal numbers is set-like, while its inverse <-1 is not.

A relation which is reflexive, symmetric and transitive is called an equivalence relation. A relation which is reflexive, antisymmetric and transitive is called a partial order. A partial order which is total is called a total order or a linear order or a chain. A linear order in which every nonempty set has the least element is called a well-order. In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity. ... In mathematics, the concept of binary relation is exemplified by such ideas as is greater than and is equal to in arithmetic, or is congruent to in geometry, or is an element of or is a subset of in set theory. ... In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a. ... In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X, if a is related to b and b is related to a, then a = b. ... In mathematics, a binary relation R on a set X is antisymmetric if it holds for all a and b in X that if a is related to b and b is related to a then a = b. ... In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ... In mathematics, a binary relation R over a set X is total if it holds for all a and b in X that a is related to b or b is related to a (or both). ... In mathematics, an equivalence relation, denoted by an infix ~, is a binary relation on a set X that is reflexive, symmetric, and transitive. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... In mathematics, a total order or linear order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually. ... In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ...


A relation which is symmetric, transitive, and extendable is also reflexive.


Operations on binary relations

If R is a binary relation over X and Y, then the following is a binary relation over Y and X:

  • Inverse or converse: R -1, defined as R -1 = { (y, x) | (x, y) ∈ R }. A binary relation over a set is equal to its inverse if and only if it is symmetric.

If R is a binary relation over X, then each of the following are binary relations over X: In logic and mathematics, the inverse relation of a binary relation is the binary relation defined by . ...

  • Reflexive closure: R =, defined as R = = {(x, x) | xX} ∪ R or the smallest reflexive relation over X containing R. This can be seen to be equal to the intersection of all reflexive relations containing R.
  • Transitive closure: R +, defined as the smallest transitive relation over X containing R. This can be seen to be equal to the intersection of all transitive relations containing R.
  • Transitive-reflexive closure: R *, defined as R * = (R +=.

If R, S are binary relations over X and Y, then each of the following are binary relations: In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. For any relation R the transitive closure of R always exists. ...

  • Union: RSX × Y, defined as RS = {(x, y) | (x, y) ∈ R or (x, y) ∈ S}.
  • Intersection: RSX × Y, defined as RS = { (x, y) | (x, y) ∈ R and (x, y) ∈ S }.

If R is a binary relation over X and Y, and S is a binary relation over Y and Z, then the following is a binary relation over X and Z: (see main article composition of relations) In mathematics, the composition of binary relations is a concept of forming a new relation S o R from two given relations R and S, having as its most well-know special case the composition of functions. ...

  • Composition: S o R (also denoted R o S), defined as S o R = { (x, z) | there exists yY, such that (x, y) ∈ R and (y, z) ∈ S }. The order of R and S in the notation S o R, used here agrees with the standard notational order for composition of functions.

In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ...

Sets versus classes

Certain mathematical "relations", such as "equal to", "member of", and "subset of", cannot be understood to be binary relations as defined above, because their domains and codomains cannot be taken to be sets in the usual systems of axiomatic set theory. This article or section is in need of attention from an expert on the subject. ...


For example, if we try to model the general concept of "equality" as a binary relation = , we must take the domain and codomain to be the "set of all sets", which is not a set in the usual set theory. The usual work-around to this problem is to select a "large enough" set A, that contains all the objects of interest, and work with the restriction = A instead of = .


Similarly, the "subset of" relation subseteq needs to be restricted to have domain and codomain P(A) (the power set of a specific set A): the resulting set relation can be denoted subseteq_A. Also, the "member of" relation needs to be restricted to have domain A and codomain P(A) to obtain a binary relation in_A which is a set.


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 function with its graph in this context.) In foundations of mathematics, Von Neumann-Bernays-Gödel set theory (NBG) is an axiom system for set theory designed to yield the same results as Zermelo-Fraenkel set theory, together with the axiom of choice (ZFC), but with only a finite number of axioms, that is without axiom schemas. ... Morse-Keylley set theory (MK) is another axiomatization of set theory. ... In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share. ...


In most mathematical contexts, references to the relations of equality, membership and subset are harmless because they can be understood implicitly to be restricted to some set in the context.


Examples of common binary relations

Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... A strict weak ordering is a binary relation that defines an equivalence relation and has the properties stated below. ... The feasible regions of linear programming are defined by a set of inequalities. ... For the socioeconomic meaning, see social inequality. ... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ... In mathematics, an equivalence relation, denoted by an infix ~, is a binary relation on a set X that is reflexive, symmetric, and transitive. ... In mathematics, two mathematical objects are considered equal if they are precisely the same in every way. ... The term Parallel has a number of important meanings: Parallel (geometry) occurs in geometry. ... In mathematics, an affine space is an abstract structure that generalises the affine-geometric properties of Euclidean space. ... A bijective function. ... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of mapping between objects, devised by Eilhard Mitscherlich, which shows a relation between two properties or operations. ...

See also


  Results from FactBites:
 
NationMaster - Encyclopedia: Binary relation (3803 words)
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.
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.
In mathematics, the concept of binary relation is exemplified by such ideas as "is greater than" and "is equal to" in arithmetic, or "is congruent to" in geometry, or "is an element of" or "is a subset of" in set theory.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m