Functions

Based on 21-127 Concepts of Mathematics

Given sets $X$ and $Y$, a function $f$ from $X$ to $Y$, or $f: X \to Y$, is a mapping of each element $x \in X$ to a unique element $f(x) \in Y$. In symbolic expression:
$$\forall x \in X, \exists! y \in Y, y = f(x)$$
Some terminology:

• Let $x \in X$, then $f(x) \in Y$ is the value of $f$ at $x$.
• $X$ is called the domain aka source of $f$, and $Y$ is called the co-domain aka target aka range of $f$.

1. List the values
   • e.g. $f:{1,2,3} \rightarrow \mathbb{R} \backslash \mathbb{Q}$ by defining $f(1)=\sqrt{2}, f(2)=\pi, f(3)=\sqrt{7}$.
2. Give a formula
   • e.g. $f:\mathbb{R} \to \mathbb{R}$ via $f(x) = e^{e^x}$ for all $x \in \mathbb{R}$.
3. An algorithm (must be deterministic)
   • e.g. take the input, add 3 to it, return 1 if it’s prime and 0 otherwise.

Let there be sets $X$ and $Y$ and a function $f: X\to Y$.

A well-defined function must satisfy the following

• Totality - $f(x)$ is defined for all $x \in X$ (corresponds to $\forall x \in X$)
• Existence - $f(x)$ exists and $f(x) \in Y$ (corresponds to $\exists y \in Y, y = f(x)$)
• Uniqueness - $f(x)$ refers to only one $y$ (corresponds to $\exists!$)

Essentially another way to do the same thing of assigning unique output to every input.

Let there be a function $f: X\to Y$. Then the graph of $f$, written $Gr(f)$, is a subset of $X \times Y$ defined as the following: $$Gr(f) \subseteq X \times Y \text{ and } Gr(f) = {(x, y) \in X \times Y \mid y = f(x)}$$This can be understood as all (input, output) pairs of the function. It follows that: $$(x, y) \in Gr(f) \Leftrightarrow f(x) = y$$

via Function extensionality axiom, which basically treats two functions as black box and see if they do the same thing.

Take functions $f : X \to Y$ and $g : A \to B$. We say $f = g$ iff:

1. $X=A$ and $Y=B$, and
2. $\forall x \in X, f(x) = g(x)$ i.e. same output for all inputs.

Note that two functions with same domain and outputs but different co-domain are considered different.

It follows that if $f$ and $g$ have the same domain and co-domain, $f = g \Leftrightarrow Gr(f) = Gr(g)$.

The identity function on set $X$ is $\text{id}{X} : X \to X$ via $\text{id}{X}(x) = x$ for all $x \in X$.

Useful: identity functions are bijections (well obviously)

Let $f : X \to Y$ and $g:Y \to Z$. The composite of $f$ and $g$ denoted by $g \circ f$, is a function $X \to Z$ via $(g \circ f)(x) = g(f(x))$ for all $x \in X$.

Also let $h:Z \to U$. It follows that:

• $f \circ \mathrm{id}_X=f=\mathrm{id}_Y \circ f$ — compositing with identity function does nothing.
• $h \circ(g \circ f)=(h \circ g) \circ f$ — the order of brackets in a composition does nothing.

Given function $f : X \to Y$ and $U \subseteq X$ and $V \subseteq Y$, then:

• The image of $U$ under $f$ is $f[U] \subseteq Y$ given by $f[U] = { y \in Y \mid \exists x \in U, y = f(x) }$. Think of this as the set of all possible outputs given a set of inputs.
• The image of $U$ is just $f[U]$.
• The preimage of $V$ under $f$ is the $f^{-1}[V] \subseteq X$ given by $f^{-1}[V] = { x \in X \mid f(x) \in V }$. Think of this as the set of inputs that, upon going through the function, lands in $V$.

Given function $f : X \to Y$:

• $f$ is injective if $\forall a,b \in X, (f(a) = f(b) \Rightarrow a = b)$. Think of this as inputs map to unique outputs.
• $f$ is surjective if $\forall y \in Y, \exists x \in X, y = f(x)$. Think of this as all outputs are mapped to from some element.
• $f$ is bijective if it is both injective and surjective.
• $f$ is nonjective (this is a joke) if it is neither bijective nor surjective

Given function $f : X \to Y$:

• A left inverse of $f$ is $g : Y \to X$ s.t. $g \circ f = \text{id}_{X}$
• A left inverse of $f$ is $g : Y \to X$ s.t. $f \circ g = \text{id}_{Y}$
• The inverse of $f$ is $f^{-1}:Y \to X$ s.t. $f^{-1} \circ f = \text{id}{X}$ and $f \circ f^{-1} = \text{id}{Y}$

Theorem: if $f$ has a right inverse $g_{1}$ and right inverse $g_{2}$, then $g_{1} = g_{2}$. Proof $g_1=g_1 \circ \text{id}_X=g_1 \circ \left(f \circ g_2\right)=(g_1 \circ f) \circ g_2= \text{id}_X \circ g_2=g_2$.
It then follows that if a function has an inverse $f^{-1}$, it’s both the left inverse and the right inverse, so $f^{-1}$ is unique (which is why we wrote “the inverse”).

Theorem: inverse and jections:

• If $f$ has left inverse, then $f$ injective. (The converse is true if $X$ inhabited. Mostly because if $X = \varnothing$, there will be nothing to map to from $Y$, so the left inverse is not well defined)
• If $f$ has right inverse, then $f$ surjective.
• $f$ has inverse iff $f$ bijective.