Relation (mathematics)

From Citizendium, the Citizens' Compendium

Jump to: navigation, search

This article is developing and not approved.
Main Article
Talk
Related Articles  [?]
Bibliography  [?]
External Links  [?]
 
http://en.citizendium.org/wiki?title=Relation_(mathematics)&printable=yes
This is a draft article, under development and not meant to be cited but you can help to improve it. These unapproved articles are subject to a disclaimer.

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 \subseteq X \times Y. We write x~R~y to indicate that (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^\top between Y and X defined by

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 \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 \subseteq X _1\times \cdots \times X_n.

Contents

Relations on a set

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

  • R is reflexive if (x,x) \in R for all x \in X.
  • R is irrreflexive if (x,x) \not\in R for all x \in X.
  • R is symmetric if (x,y) \in R \Leftrightarrow (y,x) \in R; that is, R = R^\top.
  • R is antisymmetric if (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) \in R \Rightarrow (x,z); that is, R \circ R \subseteq R.

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

Equivalence relation

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 \in X \}.

Order

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 \le y or x \preceq y for weak orders and x < y or 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, x = y, x > y holds.

Functions

For more information, see: Function (mathematics).

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

Retrieved from "http://en.citizendium.org/wiki/Relation_%28mathematics%29"
Views
Personal tools