Namespaces
Variants
Actions

Difference between revisions of "Binary relation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX)
m (links)
Line 4: Line 4:
 
The empty subset $\emptyset$ in $A\times A$ and the set $A\times A$ itself are called, respectively, the nil relation and the universal relation in the set $A$. The diagonal of the set $A\times A$, i.e. the set $\Delta=\{(a,a)\colon a\in A\}$, is the equality relation or the identity binary relation in $A$.
 
The empty subset $\emptyset$ in $A\times A$ and the set $A\times A$ itself are called, respectively, the nil relation and the universal relation in the set $A$. The diagonal of the set $A\times A$, i.e. the set $\Delta=\{(a,a)\colon a\in A\}$, is the equality relation or the identity binary relation in $A$.
  
Let $R,R_1,R_2$ be binary relations in a set $A$. In addition to the set-theoretic operations of union $R_1\cup R_2$, intersection $R_1\cap R_2$, and complementation $R'=(A\times A)\setminus R$, one has the inversion
+
Let $R,R_1,R_2$ be binary relations in a set $A$. In addition to the set-theoretic operations of [[Union of sets|union]] $R_1\cup R_2$, [[Intersection of sets|intersection]] $R_1\cap R_2$, and [[Relative complement|complementation]] $R'=(A\times A)\setminus R$, one has the inversion
  
 
$$R^{-1}=\{(a,b)\colon(b,a)\in R\},$$
 
$$R^{-1}=\{(a,b)\colon(b,a)\in R\},$$
  
as well as the operation of multiplication:
+
as well as the operation of multiplication (or composition):
  
 
$$R_1\circ R_2=\{(a,b)\colon(\exists c\in A)(aR_1c\text{ and }cR_2b)\}.$$
 
$$R_1\circ R_2=\{(a,b)\colon(\exists c\in A)(aR_1c\text{ and }cR_2b)\}.$$
Line 14: Line 14:
 
The binary relation $R^{-1}$ is said to be the inverse of $R$. Multiplication of binary relations is associative, but as a rule not commutative.
 
The binary relation $R^{-1}$ is said to be the inverse of $R$. Multiplication of binary relations is associative, but as a rule not commutative.
  
A binary relation $R$ in $A$ is said to be 1) reflexive if $\Delta\subseteq R$; 2) transitive if $R\circ R\subseteq R$; 3) symmetric if $R^{-1}\subseteq R$; and 4) anti-symmetric if $R\cap R^{-1}\subseteq\Delta$. If a binary relation has some of the properties 1), 2), 3) or 4), the inverse relation $R^{-1}$ has these properties as well. The binary relation $R\subseteq A\times A$ is said to be functional if $R^{-1}\circ R\subseteq\Delta$.
+
A binary relation $R$ in $A$ is said to be 1) [[Reflexivity|reflexive]] if $\Delta\subseteq R$; 2) [[Transitivity|transitive]] if $R\circ R\subseteq R$; 3) [[Symmetry (of a relation)|symmetric]] if $R^{-1}\subseteq R$; and 4) anti-symmetric if $R\cap R^{-1}\subseteq\Delta$. If a binary relation has some of the properties 1), 2), 3) or 4), the inverse relation $R^{-1}$ has these properties as well. The binary relation $R\subseteq A\times A$ is said to be [[Functional relation|functional]] if $R^{-1}\circ R\subseteq\Delta$.
  
The most important types of binary relations are equivalences, order relations (total and partial), and functional relations (cf. [[Equivalence|Equivalence]]; [[Order relation|Order relation]]; [[Functional relation|Functional relation]]).
+
The most important types of binary relations are [[equivalence]]s, [[order relation]]s (total and partial), and [[functional relation]]s.

Revision as of 21:38, 13 October 2014

A two-place predicate on a given set. The term is sometimes used to denote a subset of the set $A\times A$ of ordered pairs $(a,b)$ of elements of a given set $A$. A binary relation is a special case of a relation. Let $R\subseteq A\times A$. If $(a,b)\in R$, then one says that the element $a$ is in binary relation $R$ to the element $b$. An alternative notation for $(a,b)\in R$ is $aRb$.

The empty subset $\emptyset$ in $A\times A$ and the set $A\times A$ itself are called, respectively, the nil relation and the universal relation in the set $A$. The diagonal of the set $A\times A$, i.e. the set $\Delta=\{(a,a)\colon a\in A\}$, is the equality relation or the identity binary relation in $A$.

Let $R,R_1,R_2$ be binary relations in a set $A$. In addition to the set-theoretic operations of union $R_1\cup R_2$, intersection $R_1\cap R_2$, and complementation $R'=(A\times A)\setminus R$, one has the inversion

$$R^{-1}=\{(a,b)\colon(b,a)\in R\},$$

as well as the operation of multiplication (or composition):

$$R_1\circ R_2=\{(a,b)\colon(\exists c\in A)(aR_1c\text{ and }cR_2b)\}.$$

The binary relation $R^{-1}$ is said to be the inverse of $R$. Multiplication of binary relations is associative, but as a rule not commutative.

A binary relation $R$ in $A$ is said to be 1) reflexive if $\Delta\subseteq R$; 2) transitive if $R\circ R\subseteq R$; 3) symmetric if $R^{-1}\subseteq R$; and 4) anti-symmetric if $R\cap R^{-1}\subseteq\Delta$. If a binary relation has some of the properties 1), 2), 3) or 4), the inverse relation $R^{-1}$ has these properties as well. The binary relation $R\subseteq A\times A$ is said to be functional if $R^{-1}\circ R\subseteq\Delta$.

The most important types of binary relations are equivalences, order relations (total and partial), and functional relations.

How to Cite This Entry:
Binary relation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Binary_relation&oldid=33627
This article was adapted from an original article by D.M. Smirnov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article