Functions and Relations
Functions
Recall that if $X$ and $Y$ are sets then a function $f : X \to Y$ is a rule which assigns to each $x \in X$ a unique $y \in Y$. We can more precisely define a function in terms of sets.
| Definition: Let $X$ and $Y$ be sets. A Function from $X$ to $Y$ is a subset $f$ of $X \times Y$ such that for every $x \in X$ if $(x, y_1), (x, y_2) \in f$ then $y_1 = y_2$. |
In other words, a function from a set $X$ to a set $Y$ can be defined as a subset of the cartesian product $X \times Y$ such that for each $x \in X$ there is exactly one ordered pair $(x, y)$ where $y \in Y$.
Relations
| Definition: Let $X$ and $Y$ be sets. A Relation from $X$ to $Y$ is a subset $R$ of $X \times Y$. |
The definition above is more precisely defining a binary relation. More generally, if $X_1, X_2, ..., X_n$ are sets then an $n$-ary relation on $X_1$, $X_2$, …, $X_n$ is a subset $R$ of $X_1 \times X_2 \times ... \times X_n$. The terms "relation" and "binary relation" will mean the same thing unless specified otherwise.
Observe the definition of a relation closely. Note that a relation from $X$ to $Y$ is simply a subset $R$ of the cartesian product $X \times Y$. There is nothing more to it!
Also observe that every function is by definition a relation. However, there are many relations that are not functions. For example, let $X = \{ 0, 1 \}$ and let $Y = \{ a, b \}$ with $a \neq b$. Let:
(1)Clearly $R$ is a relation. Is $R$ a function? If $R$ is a function then for $0 \in X$ we must have that $(0, a) = (0, b)$. But then $a = b$ which is a contradiction. So $R$ is NOT a function.