Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Binary relation"

m
(→‎Formal Definition and Notation)
 
(8 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
A '''binary relation''' is a [[relation]] which relates pairs of objects.
 
A '''binary relation''' is a [[relation]] which relates pairs of objects.
  
−
Thus, the relation <math>\sim</math> of [[triangle]] [[similarity]] is a binary relation over the [[set]] of triangles but the relation <math>R(x, y, z) = \{(x, y, z) \mid x, y, z \in \mathbb{Z}_{>0}, x\cdot y = z\}</math> which says <math>x\cdot y</math> is a [[factor]]ization of <math>z</math> over the [[positive integer]]s is not a binary relation because it takes 3 arguments.
+
Thus, the relation <math>\sim</math> of [[triangle]] [[similarity]] is a binary relation over the [[set]] of triangles but the relation <math>R(x, y, z) = \{(x, y, z) \mid x, y, z \in \mathbb{Z}_{>0}, x\cdot y = z\}</math> which says <math>x\cdot y</math> is a [[divisor | factor]]ization of <math>z</math> over the [[positive integer]]s is not a binary relation because it takes 3 arguments.
 +
 
 +
== Formal Definition and Notation ==
 +
 
 +
Formally, we say that a relation <math>\mathfrak{R}</math> on sets <math>A</math> and <math>B</math> is a subset of <math>A \times B</math> (the [[Cartesian product]] of <math>A</math> and <math>B</math>).  We often write <math>a \, \mathfrak{R} \, b</math> instead of <math>(a,b) \in \mathfrak{R}</math>.  If <math>A=B</math> (the case of most common interest), then we say that <math>\mathfrak{R}</math> is a relation on <math>A</math>.
 +
 
 +
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]].
 +
 
 +
More generally, we say that a relation <math>\mathfrak{R}(x,y)</math> is a mathematical sentence in which two letters, <math>x</math> and <math>y</math>, are of particular interest.  This more general definition is useful because it admits relations whose "domain" is a class of sets too large to constitute a set.  For instance, the relation <math>\mathfrak{R}(x,y)</math> defined as <math>(x=y)</math> applies to all sets, not just sets contained in some larger set.
 +
 
 +
== 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>.
 +
 
 +
== Reflexivity, Symmetry and Transitivity ==
 +
 
 +
A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be reflexive if <math>(\forall a \in A)(a \mathfrak{R} a)</math>.
 +
 
 +
A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be symmetric if <math>(\forall (a,b) \in A^2)((a \mathfrak{R} b) \rightarrow (b \mathfrak{R} a))</math>.
 +
 
 +
A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be anti-symmetric if <math>(\forall (a,b) \in A^2)(((a \mathfrak{R} b) \wedge (b \mathfrak{R} a)) \rightarrow (a = b))</math>.
 +
 
 +
A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be transitive if <math>(\forall (a,b,c) \in A^3)(((a \mathfrak{R} b) \wedge (b \mathfrak{R} c)) \rightarrow (a \mathfrak{R} c))</math>.
 +
 
 +
A reflexive, symmetric and transitive relation is called an [[equivalence relation]]. A reflexive, anti-symmetric and transitive relation is called an [[order relation]].
 +
 
 +
==See also==
 +
 
 +
* [[Equivalence relation]]
 +
* [[Order relation]]
 +
* [[Function]]
 +
* [[Reflexive]]
 +
 
 +
{{stub}}

Latest revision as of 21:33, 18 May 2008

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.

More generally, we say that a relation $\mathfrak{R}(x,y)$ is a mathematical sentence in which two letters, $x$ and $y$, are of particular interest. This more general definition is useful because it admits relations whose "domain" is a class of sets too large to constitute a set. For instance, the relation $\mathfrak{R}(x,y)$ defined as $(x=y)$ applies to all sets, not just sets contained in some larger set.

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}$.

Reflexivity, Symmetry and Transitivity

A binary relation $\mathfrak{R}$ over $A$ is defined to be reflexive if $(\forall a \in A)(a \mathfrak{R} a)$.

A binary relation $\mathfrak{R}$ over $A$ is defined to be symmetric if $(\forall (a,b) \in A^2)((a \mathfrak{R} b) \rightarrow (b \mathfrak{R} a))$.

A binary relation $\mathfrak{R}$ over $A$ is defined to be anti-symmetric if $(\forall (a,b) \in A^2)(((a \mathfrak{R} b) \wedge (b \mathfrak{R} a)) \rightarrow (a = b))$.

A binary relation $\mathfrak{R}$ over $A$ is defined to be transitive if $(\forall (a,b,c) \in A^3)(((a \mathfrak{R} b) \wedge (b \mathfrak{R} c)) \rightarrow (a \mathfrak{R} c))$.

A reflexive, symmetric and transitive relation is called an equivalence relation. A reflexive, anti-symmetric and transitive relation is called an order relation.

See also

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Binary_relation&oldid=26040"