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"
Line 14: Line 14:
  
 
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>.
 
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>.
  
 
==See also==
 
==See also==

Revision as of 17:13, 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}$.

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

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=20362"