Difference between revisions of "Binary relation"

(Formal Definition and Notation)
Line 8: Line 8:
  
 
Thus, in the example of <math>\sim</math> above, we may let <math>\sim</math> be the set of ordered pairs of triangles in the Euclidean plane which are similar to each other.  We could also define a relation <math>\leq</math> on the [[power set]] of a set <math>S</math>, so that <math>(A,B) \in \leq</math>, or <math>A\leq B</math>, if and only if <math>A</math> and <math>B</math> are [[subset]]s of <math>S</math> and <math>A</math> is a subset of <math>B</math>.  This is a common example of an [[order relation]].
 
Thus, in the example of <math>\sim</math> above, we may let <math>\sim</math> be the set of ordered pairs of triangles in the Euclidean plane which are similar to each other.  We could also define a relation <math>\leq</math> on the [[power set]] of a set <math>S</math>, so that <math>(A,B) \in \leq</math>, or <math>A\leq B</math>, if and only if <math>A</math> and <math>B</math> are [[subset]]s of <math>S</math> and <math>A</math> is a subset of <math>B</math>.  This is a common example of an [[order relation]].
 +
 +
== Domain and Range ==
 +
 +
The domain of a binary relation <math>\mathfrak{R}</math> over <math>A</math> and <math>B</math>, written <math>\text{Dom}(\mathfrak{R})</math>, is defined to be the set <math>\{x \in A | (\exists y \in B)(x,y) \in \mathfrak{R}\}</math>. It is thus the set of the first components of the ordered pairs in <math>\mathfrak{R}</math>.
 +
 +
The range of a binary relation <math>\mathfrak{R}</math> over <math>A</math> and <math>B</math>, written <math>\text{Ran}(\mathfrak{R})</math>, is defined to be the set <math>\{y \in B | (\exists x \in A)(x,y) \in \mathfrak{R}\}</math>. It is thus the set of the second components of the ordered pairs in <math>\mathfrak{R}</math>.
  
 
==See also==
 
==See also==

Revision as of 17:58, 30 November 2007

A binary relation is a relation which relates pairs of objects.

Thus, the relation $\sim$ of triangle similarity is a binary relation over the set of triangles but the relation $R(x, y, z) = \{(x, y, z) \mid x, y, z \in \mathbb{Z}_{>0}, x\cdot y = z\}$ which says $x\cdot y$ is a factorization of $z$ over the positive integers is not a binary relation because it takes 3 arguments.

Formal Definition and Notation

Formally, we say that a relation $\mathfrak{R}$ on sets $A$ and $B$ is a subset of $A \times B$ (the Cartesian product of $A$ and $B$). We often write $a \, \mathfrak{R} \, b$ instead of $(a,b) \in \mathfrak{R}$. If $A=B$ (the case of most common interest), then we say that $\mathfrak{R}$ is a relation on $A$.

Thus, in the example of $\sim$ above, we may let $\sim$ be the set of ordered pairs of triangles in the Euclidean plane which are similar to each other. We could also define a relation $\leq$ on the power set of a set $S$, so that $(A,B) \in \leq$, or $A\leq B$, if and only if $A$ and $B$ are subsets of $S$ and $A$ is a subset of $B$. This is a common example of an order relation.

Domain and Range

The domain of a binary relation $\mathfrak{R}$ over $A$ and $B$, written $\text{Dom}(\mathfrak{R})$, is defined to be the set $\{x \in A | (\exists y \in B)(x,y) \in \mathfrak{R}\}$. It is thus the set of the first components of the ordered pairs in $\mathfrak{R}$.

The range of a binary relation $\mathfrak{R}$ over $A$ and $B$, written $\text{Ran}(\mathfrak{R})$, is defined to be the set $\{y \in B | (\exists x \in A)(x,y) \in \mathfrak{R}\}$. It is thus the set of the second components of the ordered pairs in $\mathfrak{R}$.

See also

This article is a stub. Help us out by expanding it.