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.

Conditions and key results

Domain and codomain are part of the function, so the same formula can have different properties on different sets. For finite sets of equal size, injective is equivalent to surjective; that equivalence can fail for infinite sets. An inverse relation is a function only when the original function is bijective.

A reliable strategy

1. Write the domain, codomain, and assignment rule; verify every domain input has exactly one permitted output.
2. Test injectivity by assuming equal outputs; test surjectivity by solving $f(x)=y$ for arbitrary codomain $y$.
3. For composition, apply the rightmost function first and check compatible sets.
4. For a claimed inverse, verify both $f^{-1}\circ f=\operatorname{id}_A$ and $f\circ f^{-1}=\operatorname{id}_B$.

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

Verification and reasonableness

• Use an arrow diagram for a small finite domain to expose missing outputs or collisions.
• Check inverse identities in both directions; one direction alone may establish only a one-sided inverse.
• Compare cardinalities: a finite map from a larger domain to a smaller codomain cannot be injective.

Practice

1. How many functions map a three-element set to a two-element set?
2. Is $f:\mathbb Z\to\mathbb Z$, $f(n)=n+2$, bijective?
3. Is $f:\mathbb Z\to\mathbb Z$, $f(n)=n^2$, injective?

Further deduction

For finite sets $A$ and $B$ with $|A|=|B|$, injectivity forces surjectivity: distinct domain elements have distinct images, so the image already contains $|A|=|B|$ elements and must equal $B$. Surjectivity similarly forces injectivity. The result fails for infinite sets: $f:\mathbb N\to\mathbb N$ defined by $f(n)=n+1$ is injective but misses $0$ under the convention $\mathbb N=\{0,1,2,\ldots\}$. The hypothesis of finiteness therefore does real work.

Related topics

• Relations
• Sets
• Counting