Relations

A relation captures the idea that some pairs of objects are connected by a rule while others are not — "is the price of", "is older than", "is the capital of". Formally, a relation links elements of one set to elements of another, and every such link is an ordered pair, so a relation is naturally a set of ordered pairs.

Definition. Let $A$ and $B$ be two non-empty sets. A relation $R$ from $A$ to $B$ is any subset of the Cartesian product $A \times B$:

If $(a, b) \in R$, we say "$a$ is related to $b$" and write $a\,R\,b$. A relation from a set $A$ to itself (a subset of $A \times A$) is called a relation on $A$.

Because a relation is just a subset of $A \times B$, and $A \times B$ has $n(A)\,n(B)$ elements, the total number of possible relations from $A$ to $B$ is $2^{\,n(A)\,n(B)}$ (every subset of $A \times B$ is a relation).

Describing a relation. A relation can be given by listing its ordered pairs (roster form) or by a rule. For example, with $A = \{1, 2, 3\}$ and $B = \{4, 5, 6\}$, the rule "$b = a + 3$" gives the relation

Domain, range and codomain. For a relation $R$ from $A$ to $B$: