Relation

Let $X$ and $Y$ be sets. A relation from $X$ to $Y$ is a subset

If $(x,y)\in R$, one often writes $xRy$. A relation on $X$ is a subset $R\subseteq X\times X$.

Relations generalize functions by allowing an input $x$ to be related to zero, one, or many outputs $y$. Equivalence relations and order relations are special kinds of relations that structure sets.

Examples:

• The “less-than-or-equal” relation on $\mathbb{R}$ is $\le\ \subseteq \mathbb{R}\times\mathbb{R}$, where $(x,y)\in \le$ iff $x\le y$.
• A function $f:X\to Y$ can be identified with its graph $\{(x,f(x)):x\in X\}\subseteq X\times Y$, which is a relation satisfying a uniqueness property.
• The divisibility relation on $\mathbb{N}$ is $|\ \subseteq \mathbb{N}\times\mathbb{N}$, where $(a,b)\in |\$ iff $a$ divides $b$.