Binary relation

From CS2800 wiki


Most of the relations we will discuss in this course are binary relations: they relate a set with itself.


Definition: Binary relation
A binary relation [math]R [/math] on a set [math]A [/math] is a subset of [math]A \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} A [/math] (i.e. a set of pairs of elements of [math]A [/math]).


Notation: If [math]R [/math] is a binary relation on a set [math]A [/math], and if [math]x [/math] and [math]y [/math] are elements of [math]A [/math], then [math]xRy [/math] is shorthand for [math](x,y) \href{/cs2800/wiki/index.php/%E2%88%88}{∈} R [/math].

For example, we usually write [math]x ≤ y [/math] instead of [math](x,y) \href{/cs2800/wiki/index.php/%E2%88%88}{∈} ≤ [/math].

Examples:

Drawing binary relations

Although it is hard to draw diagrams of general relations, we can draw a binary relation the same way we draw functions:

Binary-relation-2sets.svg

However, because binary relations only relate one set [math]A [/math] to itself, we can draw them more compactly by only including one copy of [math]A [/math].

Binary-relation.svg

Here, an arrow from [math]x [/math] to [math]y [/math] indicates [math]x R y [/math]. This diagram represents the relation [math]R := \{(a,b), (b,c), (c,c), (d,e), (e,e), (e,d)\} [/math] on the set [math]A := \{a,b,c,d,e,f\} [/math].