HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a relation on a set may, or may not, hold between two given set members. For example, ''"is less than"'' is a relation on the set of
natural number In mathematics, the natural numbers are those number A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in lang ...
s; it holds e.g. between 1 and 3 (denoted as 1<3) , and likewise between 3 and 4 (denoted as 3<4), but neither between 3 and 1 nor between 4 and 4. As another example, ''"is sister of"'' is a relation on the set of all people, it holds e.g. between
Marie Curie Marie Salomea Skłodowska–Curie ( , , ; born Maria Salomea Skłodowska, ; 7 November 1867 – 4 July 1934) was a Polish and naturalized-French physicist and chemist A chemist (from Greek ''chēm(ía)'' alchemy; replacing ''chymist ...
and Bronisława Dłuska, and likewise vice versa. Set members may not be in relation "to a certain degree", hence e.g. ''"has some resemblance to"'' cannot be a relation. Formally, a relation over a set can be seen as a set of
ordered pair In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mo ...
s of members of . The relation holds between and if is a member of . For example, the relation ''"is less than"'' on the natural numbers is an infinite set of pairs of natural numbers that contains both and , but neither nor . The relation ''"is a nontrivial divisor of"'' on the set of one-digit natural numbers is sufficiently small to be shown here: ; for example 2 is a nontrivial divisor of 8, but not vice versa, hence , but . If is a relation that holds for and one often writes . For most common relations in mathematics, special symbols are introduced, like "<" for ''"is less than"'', and ", " for ''"is a nontrivial divisor of"'', and, most popular "=" for ''"is equal to"''. For example, "1<3", "1 is less than 3", and "" mean all the same; some authors also write "". Various properties of relations are investigated. A relation is reflexive if holds for all , and irreflexive if holds for no . It is symmetric if always implies , and asymmetric if implies that is impossible. It is transitive if and always implies . For example, ''"is less than"'' is irreflexive, asymmetric, and transitive, but neither reflexive nor symmetric, ''"is sister of"'' is symmetric and transitive, but neither reflexive (e.g.
Pierre Curie Pierre Curie ( , ; 15 May 1859 – 19 April 1906) was a French physicist, a pioneer in crystallography Crystallography is the experimental science of determining the arrangement of atoms in crystalline solids. Crystallography is a fundamen ...
is not a sister of himself) nor asymmetric, while being irreflexive or not may be a matter of definition (is every woman a sister of herself?), ''"is ancestor of"'' is transitive, while ''"is parent of"'' is not. Mathematical theorems are known about combinations of relation properties, such as "A transitive relation is irreflexive if, and only if, it is asymmetric". Of particular importance are relations that satisfy certain combinations of properties. A
partial order In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in m ...
is a relation that is irreflexive, asymmetric, and transitive, an
equivalence relation In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented i ...
is a relation that is reflexive, symmetric, and transitive, a function is a relation that is right-unique and left-total (see below). Since relations are sets, they can be manipulated using set operations, including
union Union commonly refers to: * Trade union A trade union (labor union in American English), often simply referred to as a union, is an organization of workers intent on "maintaining or improving the conditions of their employment Employ ...
,
intersection In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented ...
, 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 In the mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
are available, satisfying the laws of a calculus of relations. Ernst Schröder (1895
Algebra und Logic der Relative
via
Internet Archive The Internet Archive is an American digital library with the stated mission of "universal access to all knowledge". It provides free public access to collections of digitized materials, including websites, software applications/games, music ...
C. I. Lewis (1918
A Survey of Symbolic Logic
, pages 269 to 279, via internet Archive
The above concept of relationcalled "homogeneous binary relation (on sets)" when delineation from its generalizations is important has been generalized to admit relations between members of two different sets ('' heterogeneous relation'', like ''"lies on"'' between the set of all points and that of all
lines Line most often refers to: * Line (geometry) In geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related s ...
in geometry), relations between three or more sets ('' Finitary relation'', like ''"person x lives in town y at time z"''), and relations between classesa generalization of sets (like ''"is an element of"'' on the class of all sets, see ).


Definition

Given a set ''X'', a relation ''R'' over ''X'' is a set of
ordered pair In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mo ...
s of elements from ''X'', formally: . The statement reads "''x'' is ''R''-related to ''y''" and is written in
infix notation Infix notation is the notation commonly used in arithmetic Arithmetic () is an elementary part of mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spac ...
as ''xRy''. The order of the elements is important; if then ''yRx'' can be true or false independently of ''xRy''. For example, 3 divides 9, but 9 does not divide 3.


Representation of relations

A relation on a finite set may be represented as: * Hasse diagram *
directed graph In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in m ...
* boolean matrix * 2D-plot For example, on the set of all divisors of 12, define the relation ''R''div by :''x'' ''R''div ''y'' if ''x'' is a divisor of ''y'' and ''x''≠''y''. Formally, ''X'' = and ''R''div = . The representation of ''R''div as a boolean matrix is shown in the left table; the representation both as a Hasse diagram and as a directed graph is shown in the right picture. The following are equivalent: * ''x'' ''R''div ''y'' is true. * (''x'',''y'') ∈ ''R''div. * A path from ''x'' to ''y'' exists in the Hasse diagram representing ''R''div. * A vertice from ''x'' to ''y'' exists in the directed graph representing ''R''div. * In the boolean maxtrix representing ''R''div, the element in line ''x'', column ''y'' is "".


Properties of relations

Some important properties that a relation over a set may have are: ; : for all , . For example, ≥ is a reflexive relation but > is not. ; (or ): for all , not . For example, > is an irreflexive relation, but ≥ is not. The previous 2 alternatives are not exhaustive; e.g., the red binary relation given in the section is neither irreflexive, nor reflexive, since it contains the pair , but not , respectively. ; : for all , if then . For example, "is a blood relative of" is a symmetric relation, because is a blood relative of if and only if is a blood relative of . ; : for all , if and then . For example, ≥ is an antisymmetric relation; so is >, but vacuously (the condition in the definition is always false). ; : for all , if then not . A relation is asymmetric if and only if it is both antisymmetric and irreflexive. For example, > is an asymmetric relation, but ≥ is not. Again, the previous 3 alternatives are far from being exhaustive; as an example over the natural numbers, the relation defined by is neither symmetric nor antisymmetric, let alone asymmetric. ; : for all , if and then . A transitive relation is irreflexive if and only if it is asymmetric. For example, "is ancestor of" is a transitive relation, while "is parent of" is not. ; : for all , if then or . This property is sometimes called "total", which is distinct from the definitions of "total" given in the section . ; : for all , or . This property is sometimes called "total", which is distinct from the definitions of "total" given in the section . ; : every nonempty subset of contains a minimal element with respect to . Well-foundedness implies the descending chain condition (that is, no infinite chain ... can exist). If the axiom of dependent choice is assumed, both conditions are equivalent. Uniqueness properties: ; ''Injective''These properties also generalize to heterogeneous relations. (also called ''left-unique''): For all , if and then . For example, the green and blue binary relations in the diagram are injective, but the red one is not (as it relates both −1 and 1 to 1), nor the black one (as it relates both −1 and 1 to 0). ; ''Functional'' (also called ''right-unique'',Kilp, Knauer and Mikhalev: p. 3. The same four definitions appear in the following: * * * ''right-definite'' or ''univalent''): Gunther Schmidt, 2010. ''Relational Mathematics''. Cambridge University Press, , Chapt. 5 For all , if and then . Such a binary relation is called a . For example, the red and green binary relations in the diagram are functional, but the blue one is not (as it relates 1 to both −1 and 1), nor the black one (as it relates 0 to both −1 and 1). Totality properties: ; (also called or ): for all , there exists some such that . Such a relation is called a ''
multivalued function In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented i ...
''. For example, the red and green binary relations in the diagram are total, but the blue one is not (as it does not relate −1 to any real number), nor the black one (as it does not relate 2 to any real number). As another example, > is a serial relation over the integers. But it is not a serial relation over the positive integers, because there is no in the positive integers such that . However, < is a serial relation over the positive integers, the rational numbers and the real numbers. Every reflexive relation is serial: for a given , choose . ; ''Surjective'' (also called ''right-total'' or ''onto''): For all ''y'' in ''X'', there exists an ''x'' in ''X'' such that ''xRy''. For example, the green and blue binary relations in the diagram are surjective, but the red one is not (as it does not relate any real number to −1), nor the black one (as it does not relate any real number to 2).


Combinations of properties

: Relations that satisfy certain combinations of the above properties are particularly useful, and thus have received names by their own. ; : A relation that is reflexive, symmetric, and transitive. It is also a relation that is symmetric, transitive, and serial, since these properties imply reflexivity. Orderings: ; : A relation that is reflexive, antisymmetric, and transitive. ; : A relation that is irreflexive, antisymmetric, and transitive. ; : A relation that is reflexive, antisymmetric, transitive and connected. ; : A relation that is irreflexive, antisymmetric, transitive and connected. Uniqueness properties: ; ''One-to-one'': Injective and functional. For example, the green binary relation in the diagram is one-to-one, but the red, blue and black ones are not. ; ''One-to-many'': Injective and not functional. For example, the blue binary relation in the diagram is one-to-many, but the red, green and black ones are not. ; ''Many-to-one'': Functional and not injective. For example, the red binary relation in the diagram is many-to-one, but the green, blue and black ones are not. ; ''Many-to-many'': Not injective nor functional. For example, the black binary relation in the diagram is many-to-many, but the red, green and blue ones are not. Uniqueness and totality properties: ; A : A binary relation that is functional and total. For example, the red and green binary relations in the diagram are functions, but the blue and black ones are not. ; An : A function that is injective. For example, the green binary relation in the diagram is an injection, but the red, blue and black ones are not. ; A : A function that is surjective. For example, the green binary relation in the diagram is a surjection, but the red, blue and black ones are not. ; A : A function that is injective and surjective. For example, the green binary relation in the diagram is a bijection, but the red, blue and black ones are not.


Operations on relations

; This operations also generalizes to heterogeneous relations.: If ''R'' and ''S'' are relations over ''X'' then ''R'' ∪ ''S'' = is the of ''R'' and ''S''. The identity element of this operation is the empty relation. For example, ≤ is the union of < and =, and ≥ is the union of > and =. ; : If ''R'' and ''S'' are binary relations over ''X'' then ''R'' ∩ ''S'' = is the of ''R'' and ''S''. The identity element of this operation is the universal relation. ; : If ''R'' and ''S'' are binary relations over ''X'' then ''S'' ∘ ''R'' = (also denoted by ) is the of ''R'' and ''S''. The identity element is the identity relation. The order of ''R'' and ''S'' in the notation , used here agrees with the standard notational order for
composition of functions In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented i ...
. For example, the composition "is mother of" ∘ "is parent of" yields "is maternal grandparent of", while the composition "is parent of" ∘ "is mother of" yields "is grandmother of". For the former case, if ''x'' is the parent of ''y'' and ''y'' is the mother of ''z'', then ''x'' is the maternal grandparent of ''z''. ; : If ''R'' is a binary relation over sets ''X'' and ''Y'' then ''R''T = is the ''converse relation'' of ''R'' over ''Y'' and ''X''. For example, = is the converse of itself, as is ≠, and < and > are each other's converse, as are ≤ and ≥. A binary relation is equal to its converse if and only if it is symmetric. ; : If ''R'' is a binary relation over ''X'' then = (also denoted by or ) is the ''complementary relation'' of ''R''. For example, = and ≠ are each other's complement, as are ⊆ and ⊈, ⊇ and ⊉, and ∈ and ∉, and, for
total order In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
s, also < and ≥, and > and ≤. The complement of the
converse relation In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in m ...
is the converse of the complement: \overline = \bar^\mathsf. ; : If ''R'' is a relation over ''X'' and ''S'' is a subset of ''X'' then ''R'', ''S'' = is the of ''R'' to ''S''. The expression ''R'', ''S'' = is the of ''R'' to ''S''; the expression ''R'', ''S'' = is called the of ''R'' to ''S''. If a relation is reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive, total, trichotomous, a
partial order In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in m ...
,
total order In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
, strict weak order, total preorder (weak order), or an
equivalence relation In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented i ...
, 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. A binary relation ''R'' over sets ''X'' and ''Y'' is said to be a relation ''S'' over ''X'' and ''Y'', written R \subseteq S, if ''R'' is a subset of ''S'', that is, for all x \in X and y \in Y, if ''xRy'', then ''xSy''. If ''R'' is contained in ''S'' and ''S'' is contained in ''R'', then ''R'' and ''S'' are called ''equal'' written ''R'' = ''S''. If ''R'' is contained in ''S'' but ''S'' is not contained in ''R'', then ''R'' is said to be than ''S'', written . For example, on the
rational number In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented i ...
s, the relation > is smaller than ≥, and equal to the composition


Examples

* Order relations, including strict orders: ** Greater than ** Greater than or equal to ** Less than ** Less than or equal to **
Divides In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented i ...
(evenly) **
Subset In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented i ...
of *
Equivalence relation In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented i ...
s: ** Equality ** Parallel with (for
affine space In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
s) ** Is in
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
with **
Isomorphic In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
*
Tolerance relation In universal algebra and lattice theory, a tolerance relation on an algebraic structure is a reflexive symmetric relation A symmetric relation is a type of binary relation. An example is the relation "is equal to", because if ''a'' = ''b'' i ...
, a reflexive and symmetric relation: **
Dependency relation In computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practi ...
, a finite tolerance relation ** Independency relation, the complement of some dependency relation * Kinship relations


Generalizations

The above concept of relation has been generalized to admit relations between members of two different sets. Given sets ''X'' and ''Y'', a '' heterogeneous relation'' ''R'' over ''X'' and ''Y'' is a subset of . When , the relation concept describe above is obtained; it is often called ''homogeneous relation'' (or ''endorelation'') to distinguish it from its generalization. The above properties and operations that are marked "" and "", respectively, generalize to heterogeneous relations. An example of a heterogeneous relation is "ocean ''x'' borders continent ''y''". The best-known examples are functionsthat is, right-unique and left-total heterogeneous relations with distinct domains and ranges, such as sqrt: \mathbb \rarr \mathbb_.


See also

* Abstract rewriting system * Additive relation, a many-valued homomorphism between modules * Category of relations, a category having sets as objects and heterogeneous binary relations as morphisms * Confluence (term rewriting), discusses several unusual but fundamental properties of binary relations * Correspondence (algebraic geometry), a binary relation defined by algebraic equations * Hasse diagram, a graphic means to display an order relation * Incidence structure, a heterogeneous relation between set of points and lines * Logic of relatives, a theory of relations by Charles Sanders Peirce *
Order theory Order theory is a branch of mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These t ...
, investigates properties of order relations


Notes


References


Bibliography

* * * * * {{DEFAULTSORT:Relation