Relation (mathematics): Difference between revisions
imported>Richard Pinch (→Relations on a set: crossref to directed graph) |
imported>Richard Pinch m (link) |
||
| (9 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
In [[mathematics]] a '''relation''' is a property which holds between certain elements of some [[set (mathematics)|set]] or sets. Examples include [[equality]] between numbers or other quantities; comparison or [[order relation]]s such as "greater than" or "less than" between [[magnitude]]s; [[geometry|geometrical]] relations such as [[parallel]], [[congruence]], [[similarity]] or between-ness; abstract concepts such as [[isomorphism]] or [[homeomorphism]]. A relation may involve one term (''unary'') in which case we may identify it with a property or [[predicate]]; the commonest examples involve two terms (''binary''); three terms (''ternary'') and in general we write an ''n''-ary relation. | |||
Relations may be expressed by [[formula]]e, geometric concepts or [[algorithm]]s, but in keeping with the modern definition of [[function (mathematics)|mathematics]], it is most convenient to identify a relation with the set of values for which it holds true. | |||
Formally, then, we define a '''binary relation''' between sets ''X'' and ''Y'' as a [[subset]] of the [[Cartesian product]], <math>R \subseteq X \times Y</math>. We write <math>x~R~y</math> to indicate that <math>(x,y) \in R</math>, and say that ''x'' "stands in the relation ''R'' to" ''y'', or that ''x'' "is related by ''R'' to" ''y''. | |||
The ''transpose'' of a relation ''R'' between ''X'' and ''Y'' is the relation <math>R^\top</math> between ''Y'' and ''X'' defined by | The ''transpose'' of a relation ''R'' between ''X'' and ''Y'' is the relation <math>R^\top</math> between ''Y'' and ''X'' defined by | ||
| Line 10: | Line 10: | ||
:<math>R^\top = \{ (y,x) \in Y \times X : (x,y) \in R \} . \, </math> | :<math>R^\top = \{ (y,x) \in Y \times X : (x,y) \in R \} . \, </math> | ||
The ''[[relation composition|composition]]'' of a relation ''R'' between ''X'' and ''Y'' and a relation ''S'' between ''Y'' and ''Z'' is | |||
:<math> R \circ S = \{ (x,z) \in X \times Z : \exists y \in Y, ~ (x,y) \in R \hbox{ and } (y,z) \in S \} . \, </math> | |||
More generally, we define an ''n''-ary relation to be a subset of the product of ''n'' sets <math>R \subseteq X _1\times \cdots \times X_n</math>. | |||
==Relations on a set== | ==Relations on a set== | ||
| Line 20: | Line 23: | ||
* ''R'' is ''symmetric'' if <math>(x,y) \in R \Leftrightarrow (y,x) \in R</math>; that is, <math>R = R^\top</math>. | * ''R'' is ''symmetric'' if <math>(x,y) \in R \Leftrightarrow (y,x) \in R</math>; that is, <math>R = R^\top</math>. | ||
* ''R'' is ''antisymmetric'' if <math>(x,y) \in R \Rightarrow (y,x) \not\in R</math>; that is, ''R'' and its transpose are disjoint. | * ''R'' is ''antisymmetric'' if <math>(x,y) \in R \Rightarrow (y,x) \not\in R</math>; that is, ''R'' and its transpose are disjoint. | ||
* ''R'' is ''transitive'' if <math>(x,y), (y,z) \in R \Rightarrow (x,z)</math>; that is, <math>R \circ R \subseteq R</math>. | * ''R'' is ''[[transitive relation|transitive]]'' if <math>(x,y), (y,z) \in R \Rightarrow (x,z)</math>; that is, <math>R \circ R \subseteq R</math>. | ||
A relation on a set ''X'' is equivalent to a [[directed graph]] with vertex set ''X''. | A relation on a set ''X'' is equivalent to a [[directed graph]] with vertex set ''X''. | ||
==Equivalence relation== | ==Equivalence relation== | ||
An '''equivalence relation''' on a set ''X'' is one which is reflexive, symmetric and transitive. The ''identity'' relation ''X'' is the ''diagonal'' <math>\{ (x,x) : x \in X \}</math>. | {{main|Equivalence relation}} | ||
An '''[[equivalence relation]]''' on a set ''X'' is one which is reflexive, symmetric and transitive. The ''identity'' relation ''X'' is the ''diagonal'' <math>\{ (x,x) : x \in X \}</math>. | |||
==Order== | ==Order== | ||
{{main|Order (relation)}} | |||
A ('''strict''') '''partial order''' is which is irreflexive, antisymmetric and transitive. A '''weak''' partial order is the union of a strict partial order and the identity. The usual notations for a partial order are <math>x \le y</math> or <math>x \preceq y</math> for weak orders and <math>x < y</math> or <math>x \prec y</math> for strict orders. | A ('''strict''') '''partial order''' is which is irreflexive, antisymmetric and transitive. A '''weak''' partial order is the union of a strict partial order and the identity. The usual notations for a partial order are <math>x \le y</math> or <math>x \preceq y</math> for weak orders and <math>x < y</math> or <math>x \prec y</math> for strict orders. | ||
| Line 33: | Line 38: | ||
==Functions== | ==Functions== | ||
We say that a relation ''R'' is ''functional'' if it satisfies the condition that every <math>x \in X</math> occurs in exactly one pair <math>(x,y) \in R</math>. We then define the value of the function at ''x'' to be that unique ''y''. We thus identify a [[function (mathematics)|function]] with its [[graph]]. | {{main|Function (mathematics)}} | ||
We say that a relation ''R'' is ''functional'' if it satisfies the condition that every <math>x \in X</math> occurs in exactly one pair <math>(x,y) \in R</math>. We then define the value of the function at ''x'' to be that unique ''y''. We thus identify a [[function (mathematics)|function]] with its [[graph]]. Composition of relations corresponds to [[function composition]] in this definition. The identity relation is functional, and defines the [[identity function]] on ''X''. | |||
Latest revision as of 11:25, 31 December 2008
In mathematics a relation is a property which holds between certain elements of some set or sets. Examples include equality between numbers or other quantities; comparison or order relations such as "greater than" or "less than" between magnitudes; geometrical relations such as parallel, congruence, similarity or between-ness; abstract concepts such as isomorphism or homeomorphism. A relation may involve one term (unary) in which case we may identify it with a property or predicate; the commonest examples involve two terms (binary); three terms (ternary) and in general we write an n-ary relation.
Relations may be expressed by formulae, geometric concepts or algorithms, but in keeping with the modern definition of mathematics, it is most convenient to identify a relation with the set of values for which it holds true.
Formally, then, we define a binary relation between sets X and Y as a subset of the Cartesian product, . We write to indicate that , and say that x "stands in the relation R to" y, or that x "is related by R to" y.
The transpose of a relation R between X and Y is the relation between Y and X defined by
The composition of a relation R between X and Y and a relation S between Y and Z is
More generally, we define an n-ary relation to be a subset of the product of n sets .
Relations on a set
A relation R on a set X is a relation between X and itself, that is, a subset of .
- R is reflexive if for all .
- R is irrreflexive if for all .
- R is symmetric if ; that is, .
- R is antisymmetric if ; that is, R and its transpose are disjoint.
- R is transitive if ; that is, .
A relation on a set X is equivalent to a directed graph with vertex set X.
Equivalence relation
An equivalence relation on a set X is one which is reflexive, symmetric and transitive. The identity relation X is the diagonal .
Order
A (strict) partial order is which is irreflexive, antisymmetric and transitive. A weak partial order is the union of a strict partial order and the identity. The usual notations for a partial order are or for weak orders and or for strict orders.
A total or linear order is one which has the trichotomy property: for any x, y exactly one of the three statements , , holds.
Functions
We say that a relation R is functional if it satisfies the condition that every occurs in exactly one pair . We then define the value of the function at x to be that unique y. We thus identify a function with its graph. Composition of relations corresponds to function composition in this definition. The identity relation is functional, and defines the identity function on X.