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. We write xRy to indicate that (x,y)∈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⊤ between Y and X defined by

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

More generally, we define an n-ary relation to be a subset of the product of n sets R⊆X1×⋯×Xn.

## 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.

* R is reflexive if (x,x)∈R for all x∈X.
* R is irrreflexive if (x,x)∉R for all x∈X.
* R is symmetric if (x,y)∈R⇔(y,x)∈R; that is, R=R⊤.
* R is antisymmetric if (x,y)∈R⇒(y,x)∉R; that is, R and its transpose are disjoint.
* R is transitive if (x,y),(y,z)∈R⇒(x,z); that is, R∘R⊆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}.

## 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 or x⪯y for weak orders and x<y or x≺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, x=y, 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 occurs in exactly one pair (x,y)∈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.