Relation

Let $A$ and $B$ be sets . A (binary) relation $R$ from $A$ to $B$ is a subset $R \subseteq A\times B$ of the Cartesian product ; its elements are ordered pairs $(a,b)$ interpreted as “$a$ is related to $b$.”

A relation on a set $A$ means a subset $R \subseteq A\times A$. A function is a relation with a uniqueness/existence property (each input is related to exactly one output).

Examples:

• The usual $\le$ on $\mathbb{R}$ is a relation on $\mathbb{R}$.
• Divisibility on $\mathbb{N}$ is a relation: $a\,R\,b$ means “$a$ divides $b$.”
• If $A=\{1,2\}$, then $R=\{(1,1),(1,2)\}\subseteq A\times A$ is a relation on $A$.