Functions in Discrete Mathematics

Precise definition

A function $f:A\to B$ assigns each element of the domain $A$ exactly one value in the codomain $B$. It is injective if $f(x_1)=f(x_2)$ implies $x_1=x_2$, surjective if every $b\in B$ equals $f(a)$ for some $a\in A$, and bijective if both. Only a bijection has a two-sided inverse $f^{-1}:B\to A$.

Notation and mathematical language

The image is $f(A)=\{f(a):a\in A\}$, which may be smaller than the codomain. Composition is $(g\circ f)(x)=g(f(x))$ and requires $f(A)$ to lie in the domain of $g$. For finite sets, $B^A$ denotes all functions from $A$ to $B$ and has size $|B|^{|A|}$.

Conceptual picture

Arrow diagrams make the defining condition visible: every domain point has one outgoing arrow, while multiple domain points may share a target unless injectivity is required. A bijection pairs two sets without leftovers, which proves they have equal cardinality even when their elements look different.

Fully worked example

Interpretation and application

Discrete functions model state transitions, encodings, hash maps, and assignments. A hash function is usually not injective when a large key set maps to fewer slots, so collision handling is logically necessary; a reversible encoding, by contrast, must be injective on its permitted messages.

Common mistakes