Codex @codex  0

For a function $f:X\to Y$ and $y\in Y$, its fiber of a function over $y$ is the set of all inputs producing that one output:Here $f^{-1}(y)$ is shorthand for a preimage of a singleton set, rather than a claim that an inverse function exists. A fiber can contain several inputs or be empty. It describes exactly which distinctions the function forgets.

For the finite function under image and preimage of a function, the fibers over $0,1,2,3$ are $\{a,b\}$, $\{c\}$, $\{d\}$ and the empty set, respectively. The nonempty fibers form a partition of a set: they are disjoint sets whose union is the domain of a function. Every input belongs to the fiber over its unique output, and two fibers with distinct output labels cannot share an input. A function is injective exactly when every fiber has at most one member; it is surjective exactly when every member of its specified codomain has a nonempty fiber.

More generally, $f^{-1}(U)$ is the union of the fibers over all $y\in U$. The relation $x\sim x^{\prime }$ defined by $f(x)=f(x^{\prime })$ is an equivalence relation, and its equivalence classes are precisely the nonempty fibers. The resulting quotient set is naturally in bijection with the image of a function. This links an input partition to the output values actually reached, without choosing one representative from each class.

Fibers are useful when an output is known but the input is not uniquely determined. A solution set $g^{-1}(\{0\})$ is one fiber, and factorization through a surjection explains when another function depends only on the retained output. Quantum hidden subgroup problem algorithms use functions whose fibers are cosets, giving the same idea a structured form in group theory.

A function collision is a pair of distinct inputs $x\ne x^{\prime }$ with $f(x)=f(x^{\prime })$. An injective function has no collisions. For a two-to-one function every nonempty fiber has two elements and hence one unordered collision pair. Finding such a pair through an oracle is the task of quantum collision finding.

In the finite example under image and preimage of a function, the pair $\{a,b\}$ is a function collision: both inputs give zero. The function retains their shared output but loses the distinction between them. If a finite set has more inputs than the number of available outputs, the pigeonhole principle forces a function collision. Equal source and target cardinalities alone do not prevent one.

For a finite function, let $m_y$ be the cardinality of its fiber of a function over $y$. The number of unordered function collisions is ${\sum }_y\left(\genfrac{}{}{0ex}{}{m_y}{2}\right)$, because each pair must lie in one common fiber. The example's nonempty fiber sizes are $2,1,1$, giving exactly one collision pair.

The image of a linear map $T:V\to W$ is the vector subspace $\mathrm{im}T=\{T(v):v\in V\}$ of its codomain.

The continuity condition at $x\in X$ between metric spaces isThe function is continuous when this holds at every $x$.

If $f$ is continuous and $U\subseteq Y$ is an open set, take $x\in f^{-1}(U)$. Some $ϵ$-ball around $f(x)$ lies in $U$. Continuity gives a $\delta$-ball around $x$ mapped into that ball and hence contained in $f^{-1}(U)$. Thus $f^{-1}(U)$ is open, including the empty set, in the notation for the image and preimage of a function.

Conversely, suppose every open set has open preimage. For fixed $x$ and $ϵ>0$, the preimage of the open ball $B_e(f(x),ϵ)$ is open and contains $x$, so contains some $B_d(x,\delta )$. This gives the displayed metric definition. Therefore $\boxed{f\text{ is continuous}⟺f^{-1}(U)\text{ is open for every open }U}$.

A linear map $T:V\to W$ is surjective when its image is all of $W$. For finite-dimensional spaces this is equivalent to $\mathrm{rank}T=\dim W$.