SP20:Lecture 10 prep

From CS2800 wiki

Here are last semester's notes for lecture 10.

We will be covering the following definitions:


Definition: Relation
A relation [math]R [/math] on sets [math]A_1, A_2, \dots, A_n [/math] is a subset of [math]A_1 \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} A_2 \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} \cdots \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} A_n [/math].


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


Definition: Reflexive
A binary relation [math]R [/math] on a set [math]A [/math] is reflexive if for every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], [math]\href{/cs2800/wiki/index.php/XRy}{xRx} [/math].


Definition: Symmetric
A binary relation [math]R [/math] on a set [math]A [/math] is symmetric if for all pairs of elements [math]x [/math] and [math]y \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] with [math]\href{/cs2800/wiki/index.php/XRy}{xRy} [/math], we also have [math]\href{/cs2800/wiki/index.php/XRy}{yRx} [/math].


Definition: Transitive
A binary relation [math]R [/math] on a set [math]A [/math] is transitive if for all elements [math]x [/math], [math]y [/math], and [math]z \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] with [math]\href{/cs2800/wiki/index.php/XRy}{xRy} [/math] and [math]\href{/cs2800/wiki/index.php/XRy}{yRz} [/math], we also have [math]\href{/cs2800/wiki/index.php/XRy}{xRz} [/math].


A binary relation [math]R [/math] is an equivalence relation if [math]R [/math] is reflexive, symmetric, and transitive.