Relation (mathematics)

| Main Article
| Discussion
| Related Articles  [?]
| Bibliography  [?]
| External Links  [?]
| Citable Version  [?]

|
|
|
|
|
|
|
|

This editable Main Article is under development and subject to a disclaimer.

[edit intro]

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,  R ⊆ X × Y {\displaystyle R\subseteq X\times Y} . We write  x R y {\displaystyle x~R~y} to indicate that  ( x , y ) ∈ R {\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  R ⊤ {\displaystyle R^{\top }} between Y and X defined by

R ⊤ = { ( y , x ) ∈ Y × X : ( x , y ) ∈ R } . {\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

R ∘ S = { ( x , z ) ∈ X × Z : ∃ y ∈ Y , ( x , y ) ∈ R and ( y , z ) ∈ S } . {\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  R ⊆ X 1 × ⋯ × X n {\displaystyle R\subseteq X_{1}\times \cdots \times X_{n}} .

## Contents

* 1 Relations on a set
* 2 Equivalence relation
* 3 Order
* 4 Functions

## Relations on a set[edit]

A relation R on a set X is a relation between X and itself, that is, a subset of  X × X {\displaystyle X\times X} .

* R is reflexive if  ( x , x ) ∈ R {\displaystyle (x,x)\in R} for all  x ∈ X {\displaystyle x\in X} .
* R is irrreflexive if  ( x , x ) ∉ R {\displaystyle (x,x)\not \in R} for all  x ∈ X {\displaystyle x\in X} .
* R is symmetric if  ( x , y ) ∈ R ⇔ ( y , x ) ∈ R {\displaystyle (x,y)\in R\Leftrightarrow (y,x)\in R} ; that is,  R = R ⊤ {\displaystyle R=R^{\top }} .
* R is antisymmetric if  ( x , y ) ∈ R ⇒ ( y , x ) ∉ R {\displaystyle (x,y)\in R\Rightarrow (y,x)\not \in R} ; that is, R and its transpose are disjoint.
* R is transitive if  ( x , y ) , ( y , z ) ∈ R ⇒ ( x , z ) {\displaystyle (x,y),(y,z)\in R\Rightarrow (x,z)} ; that is,  R ∘ R ⊆ R {\displaystyle R\circ R\subseteq R} .

A relation on a set X is equivalent to a directed graph with vertex set X.

## Equivalence relation[edit]

For more information, see: Equivalence relation.

An equivalence relation on a set X is one which is reflexive, symmetric and transitive. The identity relation X is the diagonal { ( x , x ) : x ∈ X } {\displaystyle \\{(x,x):x\in X\\}} .

## Order[edit]

For more information, see: 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  x ≤ y {\displaystyle x\leq y} or  x ⪯ y {\displaystyle x\preceq y} for weak orders and  x < y {\displaystyle x<y} or  x ≺ y {\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  x < y {\displaystyle x<y} ,  x = y {\displaystyle x=y} ,  x > y {\displaystyle x>y} holds.

## Functions[edit]

For more information, see: Function (mathematics).

We say that a relation R is functional if it satisfies the condition that every  x ∈ X {\displaystyle x\in X} occurs in exactly one pair  ( x , y ) ∈ R {\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.