Relation (mathematics): Difference between revisions
imported>Richard Pinch (new article, needs work) |
mNo edit summary |
||
| (14 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{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 9: | 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 14: | Line 20: | ||
* ''R'' is ''reflexive'' if <math>(x,x) \in R</math> for all <math>x \in X</math>. | * ''R'' is ''reflexive'' if <math>(x,x) \in R</math> for all <math>x \in X</math>. | ||
* ''R'' is ''irrreflexive'' if <math>(x,x) \not\in R</math> for all <math>x \in X</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 ''symmetric'' if <math>(x,y) \in R \Leftrightarrow (y,x) \in R</math>; that is, <math>R = R^\top</math>. | ||
* ''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 ''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 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''. | |||
==Equivalence relation== | |||
{{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== | |||
{{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 '''total''' or '''linear order''' is one which has the ''trichotomy'' property: for any ''x'', ''y'' exactly one of the three statements <math>x < y</math>, <math>x = y</math>, <math>x > y</math> holds. | |||
==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''.[[Category:Suggestion Bot Tag]] | |||
Latest revision as of 06:00, 11 October 2024
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, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R \subseteq X \times Y} . We write Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x~R~y} to indicate that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,y) \in R} , 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R^\top} between Y and X defined by
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R^\top = \{ (y,x) \in Y \times X : (x,y) \in R \} . \, }
The composition of a relation R between X and Y and a relation S between Y and Z is
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R \circ S = \{ (x,z) \in X \times Z : \exists y \in Y, ~ (x,y) \in R \hbox{ and } (y,z) \in S \} . \, }
More generally, we define an n-ary relation to be a subset of the product of n sets Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R \subseteq X _1\times \cdots \times X_n} .
Relations on a set
A relation R on a set X is a relation between X and itself, that is, a subset of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \times X} .
- R is reflexive if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,x) \in R} for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in X} .
- R is irrreflexive if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,x) \not\in R} for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in X} .
- R is symmetric if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,y) \in R \Leftrightarrow (y,x) \in R} ; that is, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R = R^\top} .
- R is antisymmetric if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,y) \in R \Rightarrow (y,x) \not\in R} ; that is, R and its transpose are disjoint.
- R is transitive if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,y), (y,z) \in R \Rightarrow (x,z)} ; that is, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R \circ R \subseteq R} .
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ (x,x) : x \in X \}} .
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \le y} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \preceq y} for weak orders and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x < y} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \prec y} 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x < y} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = y} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x > y} holds.
Functions
We say that a relation R is functional if it satisfies the condition that every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in X} occurs in exactly one pair Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,y) \in R} . 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.