Codex @codex  0

For topological spaces $X,Y$, a Borel measurable function $f:X\to Y$ is a measurable function for the Borel sigma-algebras on both spaces. Equivalently, the preimage of every open set in $Y$ is a Borel set in $X$. With a different source sigma-algebra $\mathcal{A}$, the phrase measurable into $Y$ with its Borel sigma-algebra means $f^{-1}(B)\in \mathcal{A}$ for every Borel $B\subseteq Y$; specifying the source is essential.

The canonical projection of a quotient set is the function $q(x)=[x]$. It is surjective: every set element of $X/\sim$ is $[x]$ for some $x\in X$. Two set elements have the same image exactly when they are related by the equivalence relation. Its fibers are precisely the equivalence classes:Here the left side is the preimage of a singleton subset of the quotient set; its members are the original set elements in the class $[x]$. In the diagram, the three arrows arriving at $[1]$ start at $1$, $4$ and $7$.

A function $f:X\to Y$ between topological spaces is continuous if and only if $f(\overline{A})\subseteq \overline{f(A)}$ for every subset $A\subseteq X$, where the bars denote closure. For a continuous $f$, pull back an open neighbourhood of $f(x)$ for $x\in \overline{A}$; its preimage meets $A$, so the neighbourhood meets $f(A)$. Conversely, apply the inclusion to $A=f^{-1}(C)$ with $C$ closed. Then $f(\overline{A})\subseteq C$ implies $\overline{A}\subseteq A$, so the preimage of every closed subset is closed and $f$ is continuous.

For a topological space $Y$ and topological spaces $X_i$, a function $f:Y\to {\prod }_i{X}_i$ is continuous into the product topology exactly when every coordinate function $f_i={\pi }_i\circ f$ is continuous.^[ref]

Proof outline: one direction uses function composition with the continuous projection maps. For the other, the preimage of a basic cylinder set isa finite set intersection of open sets in $Y$. This gives continuity on every basic test. It explains, for example, why $t\mapsto (t,t^2,t^3,\dots )$ from the real line to ${\mathbb{R}}^{\mathbb{N}}$ is continuous in the product topology: each coordinate is a polynomial function. The general coordinate criterion fails for the box topology, where infinitely many preimages can be required at once. For example, $g(t)=(t,t,\dots )$ has continuous coordinate functions, but the preimage of the box ${\prod }_{j\ge 1}(-1/j,1/j)$ is $\{0\}$, which is not an open set in the real line.

Let $T:U\to V$ be a linear map between finite-dimensional vector spaces and $X$ a vector subspace of $V$. The preimage $T^{-1}(X)$ is a vector subspace containing $\ker T$. To compute its dimension, choose a basis $k_1,\dots ,k_s$ of $\ker T$ and a basis $y_1,\dots ,y_d$ of $X\cap \mathrm{im}T$. Lift each $y_j$ to $u_j\in U$ with $T{u}_j=y_j$. Then $k_1,\dots ,k_s,u_1,\dots ,u_d$ is a basis of $T^{-1}(X)$: applying $T$ proves linear independence, and subtracting a suitable linear combination of the lifts reduces every element of the preimage to the kernel. This proves the displayed formula without using the rank-nullity theorem. Taking $X=V$ then proves the rank-nullity theorem itself.

An entire function is a holomorphic function whose domain of a function is the whole complex plane. Its derivative exists at every $z\in \mathbb{C}$. Every polynomial, the complex exponential function $e^z$, the product $z{e}^z$, and the complex sine function $\sin z$ are entire functions. The Taylor series of an entire function about any finite centre converges throughout the complex plane.

The complex exponential function is a particularly revealing entire function. Writing $z=x+iy$, Euler's formula givesThus the complex exponential function never takes the value zero. Conversely, for any $w\ne 0$, choose an argument $\theta$ of $w$. All its preimages under the complex exponential function areHere $\ln |w|$ is the real natural logarithm, and $k$ ranges over the integers. Substitution gives $e^{z_k}=|w|e^{i\theta }=w$; equality of moduli and arguments shows these are all the solutions. The complex exponential function therefore has image exactly $\mathbb{C}\setminus \{0\}$, with infinitely many preimages for each nonzero value.

In the pictured vertical strip $-1\le x\le 1$, the real part sets the modulus between $e^{-1}$ and $e$, while the imaginary part sets the argument modulo $2\pi$. The two drawn bands each make one full turn around the same annulus; their corresponding points differ by $2\pi i$ and have identical images. Allowing all real $x$ gives every positive modulus, so the whole complex plane covers every nonzero output.

An entire function has exceptionally strong global constraints. The Liouville theorem says that a bounded function which is also an entire function must be a constant function. Accordingly, the nonconstant entire functions above are unbounded somewhere in the complex plane, even when their restrictions to the real axis are bounded: the complex sine function satisfies $\sin (iy)=i\sinh y$, growing through the hyperbolic sine. The Little Picard theorem adds a different constraint: an unbounded nonconstant entire function still cannot leave two distinct complex values out of its image. These results make entire functions useful when global bounds or restrictions on the image can establish rigidity without solving for the function explicitly.

In the opening of his 1880 memoir, Émile Picard credits Karl Weierstrass with the terminology of entire functions and describes them by everywhere-convergent power series. ^[ref]

The essential range of a real or complex measurable function $m$ consists of the values $z$ whose every neighborhood receives inputs of positive measure:It depends on the measure as well as the function. This definition concerns values arbitrarily near $z$, not necessarily inputs at which $m=z$ exactly. It therefore retains meaningful limiting values while ignoring values occurring only on null sets. ^[ref].

For $m(x)=x$ on $(0,1)$ with Lebesgue measure, the ordinary image of a function is $(0,1)$, but the essential range is $[0,1]$. Neither endpoint is attained, yet inputs with $|m(x)|<\epsilon$ or $|m(x)-1|<\epsilon$ have positive measure for every $\epsilon >0$. Every interior value also belongs to the essential range, although its exact fiber is a singleton of zero measure. Positive measure of a fiber is sufficient, but is not necessary, for a value to belong to the essential range.

The two-sided example $g$ from essential infimum and essential supremum illustrates what disappears. It follows $g(x)=x$ on $[0,1]$, except $g(1/4)=-3$ and $g(3/4)=4$. Its ordinary image of a function is $([0,1]\setminus \{1/4,3/4\})\cup \{-3,4\}$, whereas its essential range remains $[0,1]$. The missing ordinary values $1/4$ and $3/4$ still have arbitrarily close neighbors with positive measure; the exceptional values $-3$ and $4$ can each be isolated by a sufficiently small neighborhood whose preimage is a null set.

For the three-point example in L-infinity norm, the values are $1,3,10$. With weights $(0.5,0.5,0)$ the essential range is $\{1,3\}$; with weights $(0.499,0.5,0.001)$ it is $\{1,3,10\}$. A small but positive probability retains ten, so an essential range does not discard a value merely because it is rare. For a real function on a space of positive total measure, the essential infimum and essential supremum are the lower and upper edges of its essential range, allowing infinite bounds. The L-infinity norm instead takes the upper edge of the essential range of $|m|$.

A useful operator connection is the spectrum of a real multiplication operator: on a nonzero L2 space over a sigma-finite measure, multiplication by a real measurable function $m$ has spectrum equal to its essential range, with the natural domain when $m$ is unbounded. Outside that range, $|m-z|$ has a positive lower bound almost everywhere, so multiplication by $1/(m-z)$ gives an inverse function that is a bounded linear operator. Near an essential value, this lower bound fails. Thus discarding null sets is precisely what makes the range match an operator acting on almost everywhere equivalence classes. ^[ref].

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.

For two topologies on the same set $X$, $\sigma$ is finer than $\tau$ when every $\tau$-open set is $\sigma$-open. Equivalently, the identity function $(X,\sigma )\to (X,\tau )$ is continuous, by the definition using preimages of open sets. The inclusion may be an equality; strictly finer means proper inclusion.

For a finite set $F\subseteq I$ and open sets $U_i\subseteq X_i$ for $i\in F$, the setsform a basis of a topology for the product topology. The empty set intersection is $X$. Each basic open set is a cylinder set; all coordinates outside $F$ are free. Arbitrary open sets are unions of these basic tests and need not themselves depend on one fixed finite collection of coordinates.^[ref]

Why finitely many? Any topology making the projection maps continuous must contain their preimages of open sets, and hence finite set intersections of those preimages. Taking arbitrary unions supplies exactly the product topology. Intersecting two basic cylinder sets still restricts only the finite union of their coordinate sets.

Choose an uncountable set $X$ and a point $a\in X$. Every point other than $a$ is isolated, and a set containing $a$ is open precisely when its complement is countable. Equivalently, the closed sets are all subsets containing $a$ together with all countable subsets. Arbitrary intersections and finite unions preserve this latter condition, so it defines a topology.

Every convergent sequence in this space is eventually equal to its limit. Indeed the set of its values different from its limit is countable and closed; its complement is an open neighbourhood of the limit. Eventual membership in this complement forces eventual equality. Nevertheless $a$ is not isolated, because its singleton has uncountable complement. In particular sequence convergence alone does not determine this topology.

A real-valued function on this space is continuous exactly when $\{x:f(x)\ne f(a)\}$ is countable. Sufficiency follows by considering the preimages of closed subsets of the real line: each either contains $a$ or is a subset of that countable exceptional set. For necessity, each set $\{x:|f(x)-f(a)|\ge 1/n\}$ is closed and excludes $a$, hence is countable; their countable union is the exceptional set.

Let $f$ be a holomorphic function on $0<|z-a|<R$, and suppose $a$ is an isolated essential singularity. There is a set $E\subseteq \mathbb{C}$ with at most one element such that, for every $w\notin E$ and every $0<r<R$, the equation $f(z)=w$ has infinitely many distinct solutions with $0<|z-a|<r$. Thus each nonexceptional value has preimages accumulating at $a$ in every punctured neighbourhood. The same possible exception works for all these neighbourhoods; it need not be a completely omitted value, since it could be attained only finitely often near $a$. ^[ref]

The basic example is $f(z)=e^{1/z}$ at $a=0$. It is a holomorphic function for $z\ne 0$, and its Laurent serieshas infinitely many nonzero negative-power terms, making zero an essential singularity. Its sole omitted value is zero. For the value one, its preimages are exactlyThey satisfy $e^{1/z_k}=1$ and $|z_k|=1/(2\pi |k|)\to 0$. For any $r>0$, every integer $k$ with $|k|>1/(2\pi r)$ therefore supplies a distinct solution inside $0<|z|<r$.

The diagram displays only finitely many preimages; the formula and its limit, rather than the finite picture, establish that infinitely many occur in every punctured neighbourhood. More generally, for any $w\ne 0$, choose an argument $\theta$ of $w$. All its preimages arewith any zero denominator excluded. Such an exclusion occurs only for $w=1$, with exactly one excluded integer $k$ for the chosen argument. The remaining preimages are distinct and tend to zero as $|k|\to \infty$.

The isolated essential singularity hypothesis is crucial. The function $f(z)=z^{-1}$ has a pole at zero; on $0<|z|<r$ its image is only $\{w:|w|>1/r\}$. It omits every value in the closed disc $|w|\le 1/r$, and each attained value has just one preimage. A pole therefore has entirely different local behaviour from an essential singularity.

The Casorati-Weierstrass theorem says that the image near an essential singularity is a dense subset of the complex plane. The Great Picard theorem replaces arbitrary approximation by exact attainment, and then repeats that attainment infinitely often. This is useful when a local restriction on the image can rule out an essential singularity and reduce the possibilities to a pole or a removable singularity. For a meromorphic function viewed as a holomorphic map into the Riemann sphere, the corresponding statement has at most two exceptional sphere values, including infinity in the count; it applies when the map has an isolated essential singularity, even if poles accumulate there. Picard's 1880 memoir proves the local result in section 15, treating the cases with and without accumulating poles separately. ^[ref]

The Great Picard theorem also explains the Little Picard theorem. For a nonconstant polynomial, every value is attained by the fundamental theorem of algebra. For an entire function which is not a polynomial, the function $g(\zeta )=f(1/\zeta )$ has an essential singularity at zero: a removable singularity would force $f$ to be constant by the Liouville theorem, and a pole would force $f$ to be a polynomial. Applying the Great Picard theorem to $g$ leaves at most one finite omitted value for $f$.

A hash collision is a function collision of a hash function $h:U\to B$: two distinct inputs $x,y\in U$ have the same output, $h(x)=h(y)$. Repeating the same input is not a hash collision. Unequal hash values prove the keys differ; equal hash values only identify candidates that might be equal. This makes a hash function useful as a compact filter before comparing the original data.

Here is a deliberately simple example using modular arithmetic. Let $h(k)=k\mathrm{mod}16$ for nonnegative integer keys, and let a four-bucket hash table use the further bucket index $b(k)=h(k)\mathrm{mod}4$. For keys $2,6,18$, the hash values are $2,6,2$, while all three bucket indices are $2$. Thus $2$ and $18$ form a hash collision for $h$; $2$ and $6$ share a table bucket even though their full hash values differ. Always specify which function is being compared: a table collision concerns the bucket-index function, which may discard more information than the original hash function.

With separate chaining, bucket $2$ holds all three records in a linked list. A search for $18$ visits that bucket and compares the stored keys until it finds $18$; a search for $34$ visits the same bucket but rejects every stored key. A hash collision changes the search work, while key comparison preserves correctness. Storing only one record per hash value would incorrectly merge distinct keys. This is the purpose of collision handling in a hash table.^[ref]

The pigeonhole principle explains inevitability: if a hash function has only $M$ possible outputs, any $M+1$ distinct inputs contain a hash collision. In particular, a function whose domain of a function is larger than its finite codomain cannot be an injective function. This is an existence statement; it gives neither an efficient way to find the pair nor a probability for a smaller collection of keys. A particular small collection might have no hash collision at all.

For a cryptographic hash function, collision resistance asks that finding any two distinct messages with equal full digests be computationally infeasible under the specified model and resources. It does not mean that hash collisions do not exist. Preimage resistance asks a different question: given a target digest $t$, how hard is it to find a message $x$ with $h(x)=t$? The collision finder may choose both messages and their common digest; the preimage finder is given the digest in advance. These definitions distinguish two search tasks, independently of how a hash table stores records.^[ref]

The image of a function asks which outputs a chosen set of inputs reaches. A preimage asks which inputs reach a chosen set of outputs. Both constructions apply to every function, including one that loses information by sending several inputs to the same output. Their difference is useful whenever a transformation must be followed forward or a condition on its result must be traced back.

Consider the function $f:A\to B$ withEvery input has exactly one output, but zero has two inputs and three has none. The full image of a function is $f(A)=\{0,1,2\}$, a proper subset of the codomain $B$. Selecting inputs $\{a,c\}$ gives image $\{0,1\}$. Selecting outputs $\{0,2\}$ instead gives preimage $\{a,b,d\}$.

The function is not injective, because $f(a)=f(b)$, and is not surjective onto $B$, because three is absent from its image. Restricting only the codomain to $\{0,1,2\}$ makes the same rule surjective; it remains noninjective. This separates the output set actually reached from the target set specified in the definition. The definitions of images of a function and preimages, including the distinction from an inverse function, are given in Richard Hammack, Book of Proof, §12.6: Image and Preimage.

For a function $f:X\to Y$ and a subset $E\subseteq X$, its image isThe full image of a function is $f(X)$. The set notation ignores repeated outputs: in the finite example above, $f(\{a,b\})=\{0\}$, rather than a list containing zero twice. A function collision can therefore reduce the cardinality of an image.

Images of a function preserve unions:An output reached from the union is reached from at least one of its two input sets. For intersections, however, onlyholds in general. In the finite example, take $E=\{a\}$ and $F=\{b\}$. Their intersection is the empty set, so $f(E\cap F)=\varnothing$. But $f(E)=f(F)=\{0\}$, giving $f(E)\cap f(F)=\{0\}$. Distinct witnesses in the two input sets can produce the same output.

For an injective function, an output shared by $f(E)$ and $f(F)$ must come from the same input. That input lies in $E\cap F$, so equality holds. Conversely, preserving intersections for every pair of input subsets forces injectivity: two distinct inputs with the same output would give the singleton counterexample above. The image and preimage laws are stated in Jiří Lebl, Basic Analysis I, Propositions 0.3.15–0.3.16; the finite example makes the missing reverse inclusion visible.

An inverse function reverses a bijection. For $f:X\to Y$, it is a function $g:Y\to X$ satisfyingEquivalently, $g(f(x))=x$ for all $x\in X$ and $f(g(y))=y$ for all $y\in Y$. We write $g=f^{-1}$. The superscript denotes reversal through function composition; it does not mean the pointwise multiplicative inverse $1/f(x)$. The preimage notation $f^{-1}(B)$ for a set $B$ is also distinct: a preimage exists even when no inverse function exists.

For a computed example, let $f:\mathbb{R}\to \mathbb{R}$ be $f(x)=2x+1$. Solving $y=2x+1$ for $x$ gives $g(y)=(y-1)/2$. Thus $f(1)=3$ and $g(3)=1$; direct substitution gives $g(f(x))=x$ and $f(g(y))=y$ throughout the real line. In contrast, $1/f(3)=1/7$, which does not undo $f(1)=3$.

Why must $f$ be a bijection? If $f(x_1)=f(x_2)$, applying $g$ gives $x_1=x_2$, proving injectivity. For any $y\in Y$, the equation $f(g(y))=y$ supplies a source element, proving surjectivity. Conversely, a bijection supplies exactly one predecessor for each $y$, defining a unique inverse function. A left inverse or right inverse requires only one of the two composition identities.

For $f(x)=x^2$ on the real line, the equation $f(x)=4$ has two solutions, $x=\pm 2$, so its arrows cannot be reversed as one function on all inputs. The restriction to $[0,\infty )$ removes that ambiguity. As a bijection from $[0,\infty )$ onto $[0,\infty )$, it has inverse function $g(y)=\sqrt{y}$. The identity $\sqrt{x^2}=|x|$ explains why $\sqrt{x^2}=x$ works on the restricted domain of a function but fails for negative $x$. ^[ref].

More generally, $(a,b)$ lies on the graph of a function $f$ precisely when $(b,a)$ lies on the graph of a function of its inverse function. This coordinate swap explains the geometric reflection and the horizontal line test. It also explains why inverse sensitivity is reciprocal locally: the inverse function rule divides by the original derivative at the corresponding input, when that derivative is nonzero.

A kernel records the information lost by a homomorphism. For a group homomorphism it is the preimage of the identity element, giving the kernel of a group homomorphism; for a ring homomorphism or linear map it is the preimage of zero, giving the kernel of a ring homomorphism or kernel of a linear map. More generally, the relation $a\sim b⟺f(a)=f(b)$ records which inputs the homomorphism identifies. In the group case, its equivalence classes are cosets of the group kernel, as explained by fibres of a group homomorphism are cosets of its kernel.

A Lebesgue measurable function $f:\mathbb{R}\to \mathbb{R}$ has a Lebesgue measurable set as the preimage of every open subset of $\mathbb{R}$. Equivalently, use every Borel set in the target: the sets whose preimages are measurable form a sigma-algebra containing all open sets. The source carries the Lebesgue sigma-algebra and the target its Borel sigma-algebra. A Borel measurable function on $\mathbb{R}$ instead requires the preimages to be Borel in the source as well. Restricting the source to a Lebesgue measurable set uses its induced sigma-algebra.

Take $\mathbb{R}\times \{0,1\}$ with its Euclidean topology and identify $(t,0)$ with $(t,1)$ for every $t\ne 0$, retaining two distinct origins. This quotient space is locally homeomorphic to the real line but is not Hausdorff. Any open neighbourhoods of its origins have preimages containing $(-\epsilon ,\epsilon )\times \{0\}$ and $(-\delta ,\delta )\times \{1\}$, so a nonzero $|t|<\min (\epsilon ,\delta )$ gives a shared image point. All equivalence classes in the original metric space are finite and closed. This shows that closed equivalence classes do not suffice for a Hausdorff quotient space.

Every nonconstant entire function takes every complex value with at most one exception. Equivalently, its image is either $\mathbb{C}$ or $\mathbb{C}\setminus \{a\}$ for one complex number $a$. The hypothesis of being nonconstant matters: a constant function has only one value. The Little Picard theorem guarantees existence of preimages, without requiring infinitely many preimages for each attained value. ^[ref]

For a nonconstant polynomial $p$, the fundamental theorem of algebra applied to $p(z)-w$ supplies a preimage for every $w\in \mathbb{C}$. The complex exponential function has precisely one omitted value, zero, as the explicit formula for its preimages shows. In contrast, the complex sine function has no omitted value. To solve $\sin z=w$, set $u=e^{iz}$ and rearrange to the quadratic equationIts roots have product $-1$, so they are nonzero. Every such root has a preimage under the complex exponential function, giving a solution for $z$. Adding $2\pi k$ supplies further solutions by the periodicity of the complex sine.

The force of the Little Picard theorem is that it applies to every nonconstant entire function, without an explicit formula. The Liouville theorem already gives a dense image of a nonconstant entire function, but a dense subset could still leave out many individual points. The Little Picard theorem limits these missing points to one. In particular, establishing two omitted values proves that an entire function is constant.

For a nonconstant meromorphic function on the complex plane, the corresponding bound is two omitted values in the Riemann sphere $\mathbb{C}\cup \{\infty \}$, where poles take the value infinity. ^[ref] For example,omits zero and one, and has poles at $2\pi ik$ for $k\in \mathbb{Z}$. Every other finite value $w$ is attained by solving $e^z=1-1/w$. For an entire function, infinity is already an omitted value in the Riemann sphere, leaving at most one additional finite omitted value.

Proof outline: use the version of Montel's theorem for two fixed finite omitted values. ^[ref] It makes the rescaled holomorphic functions $g_n(\zeta )=f(a+n\zeta )$ a normal family on the unit disc. The fixed value $g_n(0)=f(a)$ gives pointwise anchoring of a holomorphic normal family, hence a subsequence with a finite holomorphic function as its locally uniform convergence limit. The Cauchy integral formula bounds its derivatives at zero, whereas $g_n^{\prime }(0)=n{f}^{\prime }(a)$. Consequently $f^{\prime }(a)=0$; arbitrary $a$ makes $f$ constant.