Functions: Partial and Total

Partial Functions

Definition

A relation $f : A \nrightarrow B$ is functional (or a partial function) if:

$\forall a \in A. \forall b_1, b_2 \in B. (afb_1 \land afb_2 \Rightarrow b_1 = b_2)$

Each input $a$ is related to at most one output.

Notation

• $f(a)\downarrow$ means $f$ is defined at $a$ (there exists $b$ with $afb$)
• $f(a)\uparrow$ means $f$ is undefined at $a$
• When defined, $f(a)$ denotes the unique $b$ with $afb$

Domain

The domain of partial function $f : A \nrightarrow B$ is:

$\text{dom}(f) = \{a \in A : f(a)\downarrow\}$

Total Functions

Definition

A partial function $f : A \nrightarrow B$ is total if $\text{dom}(f) = A$.

We write $f : A \to B$ for a total function from $A$ to $B$.

Verification: For all $a \in A$, there exists exactly one $b \in B$ with $afb$.

Examples

Function	Total?	Notes
$f : \mathbb{R} \to \mathbb{R}, f(x) = x^2$	Yes	Defined everywhere
$f : \mathbb{R} \nrightarrow \mathbb{R}, f(x) = \sqrt{x}$	Partial	Only defined for $x \geq 0$
$f : \mathbb{R} \nrightarrow \mathbb{R}, f(x) = 1/x$	Partial	Undefined at $x = 0$

Cardinality of Function Spaces

Partial Functions

$|A \nrightarrow B| = (|B| + 1)^{|A|}$

Each of the $|A|$ inputs independently chooses one of $|B|$ outputs or “undefined”.

Total Functions

$|A \to B| = |B|^{|A|}$

Each of the $|A|$ inputs independently chooses one of $|B|$ outputs.

Example

For $A = \{0, 1\}$ and $B = \{a, b\}$:

• $|A \to B| = 2^2 = 4$: constant functions $x \mapsto a$, $x \mapsto b$, swap $0 \mapsto a, 1 \mapsto b$, swap $0 \mapsto b, 1 \mapsto a$
• $|A \nrightarrow B| = (2+1)^2 = 9$: the 4 total functions plus 5 partial ones

Composition of Functions

Partial Function Composition

Given $f : A \nrightarrow B$ and $g : B \nrightarrow C$, define $g \circ f : A \nrightarrow C$ by:

$(g \circ f)(a) = \begin{cases} g(f(a)) & \text{if } f(a)\downarrow \text{ and } g(f(a))\downarrow \\ \text{undefined} & \text{otherwise} \end{cases}$

Total Function Composition

Given $f : A \to B$ and $g : B \to C$, the composite $g \circ f : A \to C$ is always total:

$\forall a \in A. (g \circ f)(a) = g(f(a))$

Closure Properties

• The composite of two functional relations is functional
• The composite of two total functions is total

Identity Function

The identity function $\text{id}_A : A \to A$ is:

$\text{id}_A(a) = a \quad \text{for all } a \in A$

This is total and serves as the unit for composition.

Function Application vs Relational Image

For a function $f : A \to B$ and $S \subseteq A$:

• Direct image: $f(S) = \{f(a) : a \in S\} \subseteq B$
• Inverse image: $f^{-1}(T) = \{a : f(a) \in T\} \subseteq A$

These extend relational images to the functional case.

---

Summary

• A partial function $f : A \nrightarrow B$ maps each $a$ to at most one $b$
• A total function $f : A \to B$ maps each $a$ to exactly one $b$
• $|A \to B| = |B|^{|A|}$ and $|A \nrightarrow B| = (|B|+1)^{|A|}$
• Composition preserves functionality; total functions are closed under composition