Namespaces
Variants
Actions

Difference between revisions of "Binary relation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(isbn)
 
(14 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A two-place [[Predicate|predicate]] on a given set. The term is sometimes used to denote a subset of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b0163801.png" /> of ordered pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b0163802.png" /> of elements of a given set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b0163803.png" />. A binary relation is a special case of a [[Relation|relation]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b0163804.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b0163805.png" />, then one says that the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b0163806.png" /> is in binary relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b0163807.png" /> to the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b0163808.png" />. An alternative notation for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b0163809.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638010.png" />.
+
{{TEX|done}}{{MSC|03}}
  
The empty subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638011.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638012.png" /> and the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638013.png" /> itself are called, respectively, the nil relation and the universal relation in the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638014.png" />. The diagonal of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638015.png" />, i.e. the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638016.png" />, is the equality relation or the identity binary relation in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638017.png" />.
+
A two-place [[Predicate|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|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$.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638018.png" /> be binary relations in a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638019.png" />. In addition to the set-theoretic operations of union <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638020.png" />, intersection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638021.png" />, and complementation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638022.png" />, one has the inversion
+
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$.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638023.png" /></td> </tr></table>
+
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 negation or [[Relative complement|complementation]] $R'=(A\times A)\setminus R$, one has the inversion (also inverse, converse or transpose)
  
as well as the operation of multiplication:
+
$$R^{-1}=\{(a,b)\colon(b,a)\in R\},$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638024.png" /></td> </tr></table>
+
as well as the operation of multiplication (or [[composition]]):
  
The binary relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638025.png" /> is said to be the inverse of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638026.png" />. Multiplication of binary relations is associative, but as a rule not commutative.
+
$$R_1\circ R_2=\{(a,c) \in A\times A\colon(\exists b\in A)(aR_1b\text{ and }bR_2c)\}.$$
  
A binary relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638027.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638028.png" /> is said to be 1) reflexive if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638029.png" />; 2) transitive if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638030.png" />; 3) symmetric if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638031.png" />; and 4) anti-symmetric if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638032.png" />. If a binary relation has some of the properties 1), 2), 3) or 4), the inverse relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638033.png" /> has these properties as well. The binary relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638034.png" /> is said to be functional if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016380/b01638035.png" />.
+
Multiplication of binary relations is associative, but as a rule not commutative.
  
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]]).
+
A binary relation $R$ in $A$ is said to be 1) [[Reflexivity|reflexive]] if $\Delta\subseteq R$; 2) [[Transitive relation|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 [[equivalence]]s, order relations ([[totally ordered set|total]] and [[partially ordered set|partial]]), and [[functional relation]]s.
 +
 
 +
====Comments====
 +
More generally, a binary relation $R$ may be defined between two sets $A$ and $B$ as a two-place predicate or realised as a subset of the Cartesian product $A \times B$.  As before we may speak of the union, intersection or negation of $R$ as a relation on $A \times B$.  The transpose $R^t$ is now a relation on $B \times A$.  Given relations $R_1$ on $A\times B$ and $R_2$ on $B\times C$, the composition $R_1 \circ R_2$ is a relation on $A \times C$:
 +
 
 +
$$R_1\circ R_2=\{(a,c) \in A \times C\colon(\exists b\in B)(aR_1b\text{ and }bR_2c)\}.$$
 +
 
 +
A relation $R$ on $A\times B$ is ''functional'' if for each $a \in A$ there is at most one $b \in B$ such that $a R b$.  Such a relation defines a (partial) function from $A$ to $B$: cf. [[Functional relation]].
 +
 
 +
====References====
 +
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  P. R. Halmos, ''Naive Set Theory'', Springer (1960) {{ISBN|0-387-90092-6}}</TD></TR>
 +
</table>
 +
 
 +
====Comments====
 +
The set $\mathcal{R}(A)$ of binary relations on $A$ form a [[monoid]] under composition of relations with the equality relation as [[identity element]] and the empty relation as a [[zero]]; indeed, it is a [[Baer semigroup]].
 +
 
 +
====References====
 +
<table>
 +
<TR><TD valign="top">[b1]</TD> <TD valign="top"> T.S. Blyth  ''Lattices and Ordered Algebraic Structures''  Springer (2006) {{ISBN|184628127X}}</TD></TR>
 +
<TR><TD valign="top">[b2]</TD> <TD valign="top">  R. Fraïssé, ''Theory of Relations'', Studies in Logic and the Foundations of Mathematics, Elsevier (2011) {{ISBN|0080960413}}</TD></TR>
 +
</table>

Latest revision as of 08:47, 26 November 2023

2020 Mathematics Subject Classification: Primary: 03-XX [MSN][ZBL]

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 negation or complementation $R'=(A\times A)\setminus R$, one has the inversion (also inverse, converse or transpose)

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

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

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

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.

Comments

More generally, a binary relation $R$ may be defined between two sets $A$ and $B$ as a two-place predicate or realised as a subset of the Cartesian product $A \times B$. As before we may speak of the union, intersection or negation of $R$ as a relation on $A \times B$. The transpose $R^t$ is now a relation on $B \times A$. Given relations $R_1$ on $A\times B$ and $R_2$ on $B\times C$, the composition $R_1 \circ R_2$ is a relation on $A \times C$:

$$R_1\circ R_2=\{(a,c) \in A \times C\colon(\exists b\in B)(aR_1b\text{ and }bR_2c)\}.$$

A relation $R$ on $A\times B$ is functional if for each $a \in A$ there is at most one $b \in B$ such that $a R b$. Such a relation defines a (partial) function from $A$ to $B$: cf. Functional relation.

References

[a1] P. R. Halmos, Naive Set Theory, Springer (1960) ISBN 0-387-90092-6

Comments

The set $\mathcal{R}(A)$ of binary relations on $A$ form a monoid under composition of relations with the equality relation as identity element and the empty relation as a zero; indeed, it is a Baer semigroup.

References

[b1] T.S. Blyth Lattices and Ordered Algebraic Structures Springer (2006) ISBN 184628127X
[b2] R. Fraïssé, Theory of Relations, Studies in Logic and the Foundations of Mathematics, Elsevier (2011) ISBN 0080960413
How to Cite This Entry:
Binary relation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Binary_relation&oldid=17163
This article was adapted from an original article by D.M. Smirnov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article