Functions

Definition1: A function $f: A \rightarrow B$ from a domain $A$ to a codomain $B$ is a set of pairs $(x,y): x \in A, y \in B$, each $x \in A$ appears in exactly one pair. e.g.

$$\{(x,x^2) \in \mathbb{R}^2 \mid x \in \mathbb{R}\}$$

is a formal description of the square function.

Definition2: A function $f: A \rightarrow B$ from a domain $A$ to a codomain $B$ is a relation from $A$ to $B$ with the special properties (using the relation notation $a\ f\ b$):

1. $\forall a \in A\ \exists b \in B\ a\ f\ b$ ($f$ is totally defined)
2. $\forall a \in A\ \forall b, b' \in B (a\ f\ b \wedge a\ f\ b' \rightarrow b = b')$ ($f$ is well defined)

The first property means there’s always a $b$ in $B$ that $a$ can map to. The second property means there’s only one $b$ that $a$ can map to.

How many functions are possible from a set of $x$ elements to set of $y$ elements?

$$n(f) = y \times y \times y... \times y=y^x$$

Injective (one-to-one)

If $x_1 \not= x_2$, then $f(x_1) \not=f(x_2)$,i.e., not two distinct values are mapped to the same function value (there are no “collisions”).

Example: Let $f: \mathbb{Z} \rightarrow \mathbb{Q}$ be defined by $f(n)=n/1$. Then $f$ is one-to-one but not onto.

How many injective functions are possible from a set of $x$ elements to set of $y$ elements?

$$n(f) = y \times (y-1) \times (y-2)...(y-(x-1)) = y_{p_x}$$

If $x=y$, then $n(f) = n!$

Surjective (onto)

Let $f: X \rightarrow Y$

$f$ is surjective iff $\forall y \in Y, \exists x \in X$ such that $f(x) = y$ (every value in the codomain is taken on for some argument).

Example: Define $g: \mathbb{Q} \rightarrow \mathbb{Z}$ by $g(p/q)=p$ where $p/q$ is a rational number expressed in its lowest terms with a positive denominator. The function $g$ is onto but not one-to-one.

Bijective (one-to-one and onto)

If it is both injective and surjective.

Let $f: A \rightarrow B, g: B \rightarrow C,\ \text{and} h: C \rightarrow D$. Then

1. The composition of mapping is associative: that is, $(h \circ g) \circ f = h \circ (g \circ f)$;
2. If $f$ and $g$ are both one-to-one, then the mapping $g \circ f$ is one-to-one;
3. If $f$ and $g$ are both onto, then the mapping $g \circ f$ is onto;
4. If $f$ and $g$ are bijective, then so is $g \circ f$.