Contents/Index
1. Intro
2. Properties and Special Relations
@3. Functions as relations
A function is a binary relation $F$ on the set $X \times Y$ where for each element we have that
- $x\ R\ y_1 \land x\ R\ y_2 \Rightarrow y_1 = y_2$. That is every $x$ in $X$ can be related to at most one $y \in Y$. This property is called determinism.
- $\forall x \in X \exists y \in Y : x\ R\ y$. That is fore every $x$ in $X$ there must exists one $y$ in $Y$ that is related to this $x$.
If only 1. is satisfied, we call the function partial. If both we call the function total or well defined. Normally for a function $f$ we define it as
$$
f : A \rightarrow B
$$
instead of using the cartesian product notation.
We can expand on the definition, we say that
- A function is injective if
$$
x_1\ R\ y \land x_2\ R\ y \Rightarrow x_1 = x_2
$$
That is for every $y$ in $Y$ there is at most one $x$ in $X$ that is related to this $y$.
- A function is surjective if
$$
\forall y \in Y \exists x \in X : x\ R\ y
$$
That is for every $y$ in $Y$ there must exists a $x$ in $X$ that is related to this $y$.
- A function is bijective if it is both surjective and injective.