Functions

Definition

A function $f: A \to B$ is a special type of relation from $A$ to $B$ ; intuitively speaking, a totally and well-defined function must have a single output for each input, i.e. $f(a)$ is a single element for all $a \in A$ . In general, we are only interested in such functions.

Image

For some function $f: A \to B$ , the image of $A' \subseteq A$ are all elements that are "reached" from $A'$ , i.e. $f(A') = \{ b \in B \; \vert \; \exists a \in A' (f(a') = b) \}$

Preimage

The preimage of $B' \subseteq B$ under $f: A \to B$ are all elements in $A$ that map to some element in $B'$ , i.e. $f^{-1}(B') = \{ a \in A \; \vert \; f(a) \in B' \}$ .

💡

While the inverse $f^{-1}$ might not be defined, the preimage is always defined.

Note: The inverse exists if the preimage relation is a function.

Special Properties

A function $f: A \to B$ can have "special" properties:

A function is injective, if any two distinct input elements map to two different outputs ( $\forall a \forall a' \left[ a \ne a' \to f(a) \ne f(a') \right]$ ). For "finite" functions (the relation $f$ is finite), this is equivalent to $|A| = |f(A)|$ .
A function is surjective if for every element in $B$ there exists some element $a$ in $A$ such that $f(a) = b$ , or equivalently, that $f(A) = B$
A function is bijective if it is injective and surjective.

Exercises

Preimage relationSource: Max Obreiter

Show that for every $f: A \to B$ and $B' \subseteq B$ , the following holds:

\{ (f(a), a) \in B' \times A \} = \text{id}_{B'} \circ \hat{f}

If we "removed" the first element from the tuple of the LHS (but retaining the condition that $f(a) \in B'$ ), we would get the definition of the preimage. This definition is a bit more powerful since we also know which elements map to what.

No bijection to Powerset (Cantor's Theorem)Source: Max Obreiter

Prove that for any set $A$ and any function $f: A \to \mathcal P(A)$ , $f$ is not bijective.

(This exercise is quite difficult and the first step might appear "random"; with Hint 1 the exercise should be rather easy.)

Relations Countability