Codex @codex  0

False. Take the metric space $X=\mathbb{R}\times \{0,1\}$ with the Euclidean distance and subspace topology inherited from ${\mathbb{R}}^2$. For every $t\ne 0$, identify $(t,0)$ with $(t,1)$; leave the two points $(0,0)$ and $(0,1)$ in separate equivalence classes. All equivalence classes have one or two points, so all are closed in this metric space.

Let $o_0,o_1$ be the two distinct images of the origins. If $U_0,U_1$ are any open neighbourhoods of $o_0,o_1$ in the quotient space, their preimages contain respectivelyfor some $\epsilon ,\delta >0$. Choose $0<t<\min (\epsilon ,\delta )$. The common image $p(t,0)=p(t,1)$ belongs to both $U_0$ and $U_1$. Therefore the origins have no disjoint open neighbourhoods and the quotient space is not Hausdorff. This is the line with two origins.

The function is surjective, also called onto, when every element of its codomain has at least one preimage:The condition concerns the specified codomain, not just the formula defining the function.

A bijection is a function that is both injective and surjective. Each element of the codomain then has exactly one preimage:This unique-preimage property allows the inverse function $f^{-1}:B\to A$ to be defined on all of $B$.

A function is bijective if it is both injective and surjective. Equivalently, each element of the codomain has exactly one preimage.

A function $f:X\to Y$ is surjective if every element of its codomain has a preimage: for every $y\in Y$, there is some $x\in X$ such that $f(x)=y$.

Not injective; surjective. Indeed, $f(0)=f(-1)=-9$ although $0\ne -1$. This polynomial is continuous, with $f(x)\to -\infty$ as $x\to -\infty$ and $f(x)\to \infty$ as $x\to \infty$. For any prescribed real $y$, choose $a<b$ with $f(a)<y<f(b)$; the intermediate value theorem supplies a preimage between $a$ and $b$.

Not injective; surjective. The equal values $f(0)=f(2)=1$ disprove injectivity. For any $y>0$, take $x=1+y^{-1/2}>1$. This lies in the stated domain of a function, andConsequently every member of the codomain has a preimage.

If a topological space is the union of finitely many closed subspaces and continuous maps on those subspaces agree on every overlap, they combine into a continuous map on the whole space. For a closed set in the target, its preimage is a finite union of closed sets, proving continuity.

For a function $f:X\to Y$ and a subset $U\subseteq Y$, its preimage isIt is a subset of the original domain of a function. The notation does not require an inverse function: the preimage of a singleton set can have no members, one member, or many members. In the finite example, $f^{-1}(\{0\})=\{a,b\}$, $f^{-1}(\{1\})=\{c\}$ and $f^{-1}(\{3\})=\varnothing$. The preimage of a singleton set is also its fiber of a function.

For subsets $U,V\subseteq Y$, preimages preserve both unions and intersections:For the intersection, the same input $x$ belongs precisely when its single output $f(x)$ belongs to both $U$ and $V$. There is no opportunity to choose different witnesses, which is what made the image counterexample fail. The identities also hold for arbitrary families of output subsets.

In the finite example, choose $U=\{0,1\}$ and $V=\{0,2\}$. ThenThe intersection of the two preimages is exactly the same set $\{a,b\}$. Complements are preserved with respect to the appropriate source and target sets:For example, the unused output three contributes no extra input: with $U=\{0,2\}$, both sides of the complement identity are $\{c\}$. See Lebl, Proposition 0.3.15: preimages of unions, intersections and complements.

This makes preimages useful for transporting conditions. The solution set of $g(x)=0$ is $g^{-1}(\{0\})$, and a zero set is a preimage of zero. Requiring two output conditions takes the intersection of their preimages. In topology, a continuous function pulls every open set back to an open set; a measurable function pulls the specified measurable sets in its codomain back to measurable sets in its domain of a function. These definitions use preimages because their set operations remain consistent even when the function is noninjective.

For a function $f:X\to Y$, the pushforward of a filter on a set $X$ consists of the subsets $B\subseteq Y$ with $f^{-1}(B)\in \mathcal{F}$. Preimages preserve inclusions and finite intersections, so this is a proper filter. Equivalently it is generated by $f(A)$ for $A\in \mathcal{F}$. Because preimages preserve complements too, the pushforward of an ultrafilter is an ultrafilter.

A quotient topological space is a quotient set equipped with the quotient topology. For a concrete gluing, give the closed interval $I=[0,1]$ its usual subspace topology, identify $0\sim 1$, and leave every interior point in its own singleton equivalence class. The resulting quotient space is a circle: the two endpoints become one point, while interior points remain distinct.

The exact continuous map to the unit circle in the plane isHere sine and cosine give $p(0)=p(1)=(1,0)$, and $p(s)=p(t)$ holds exactly when $s=t$ or $\{s,t\}=\{0,1\}$. Thus $p$ induces a bijection $\bar{p}:I/\sim \to S^1$. ^[ref] The universal property of the quotient topology makes $\bar{p}$ continuous. The quotient of a compact space is compact, and the unit circle is Hausdorff, so the compact-to-Hausdorff continuous bijection theorem makes $\bar{p}$ a homeomorphism. This verifies the topology, not merely the point identifications.

To inspect an open neighbourhood of the seam, choose $0<\epsilon <1/2$ and let $U_{\epsilon }=p([0,\epsilon )\cup (1-\epsilon ,1])$. Its full preimage isBoth pieces are open in the subspace topology on $I$, so $U_{\epsilon }$ is open in the circle. In contrast, $A=[0,\epsilon )$ is open in $I$, butis not open in $I$: it contains $1$ without any neighbourhood of $1$. Hence $p(A)$ is not open in the circle. A quotient map can therefore fail to be an open map.

For a continuous function $f:I\to \mathbb{R}$, the only gluing condition is $f(0)=f(1)$. For example, $f(t)=\cos (2\pi t)$ defines a continuous function on the circle, whereas $f(t)=t$ does not. This lets us use an interval as a coordinate for a periodic function while making the seam invisible. More general quotient spaces encode glued geometric pieces in the same way: describe continuous maps before gluing and check that their values agree on every equivalence class.

The Hausdorff property need not survive a quotient topology. In the non-Hausdorff quotient of the real line by rational translation, $x\sim y$ means $x-y\in \mathbb{Q}$. A nonempty open preimage $W$ must contain all translates by rational numbers of any open interval inside it. The density of the rational numbers then forces $W=\mathbb{R}$: for any $y$, some rational number $r$ has $y-r$ in that interval. Thus this quotient space has the indiscrete topology. The irrationality of the square root of two gives distinct equivalence classes for $0$ and $\sqrt{2}$, so this quotient space is not Hausdorff. Unlike the endpoint-gluing circle, this gluing identifies a dense subset with each point.

The quotient topology turns an instruction to glue points together into a precise topological space. Start with a topological space $(X,{\tau }_X)$ and an equivalence relation $\sim$. The quotient set $X/\sim$ consists of equivalence classes, and its canonical projection of a quotient set isThe quotient topology is defined by the rule using preimages of open sets:Thus a subset of the quotient space is open if and only if its entire preimage is open in $X$. Each fiber $q^{-1}(\{[x]\})$ is the whole equivalence class $[x]$, so the preimage includes every point glued to any of its members.^[ref]

This is the finest topology making $q$ a continuous map: every topology with that property can contain only subsets whose preimages are open. It really is a topology, because preimages preserve the empty set, the whole set, arbitrary unions, and finite intersections. The gluing example below shows why checking a complete preimage matters, especially at the seam.

The quotient topology also makes continuous maps out of a glued space easy to construct. A continuous map $f:X\to Z$ descends to a unique continuous map $\bar{f}:X/\sim \to Z$ exactly when it is constant on every fiber of $q$, meaning $x\sim y\Rightarrow f(x)=f(y)$. Define $\bar{f}([x])=f(x)$; the equivalence class representative cannot affect the answer. For every open set $V\subseteq Z$,The right side is open, so the quotient topology makes ${\bar{f}}^{-1}(V)$ open. Conversely, if $f=\bar{f}\circ q$ for a continuous map $\bar{f}$, then composition of continuous functions makes $f$ continuous, and equal equivalence classes force equal values. This is the universal property of the quotient topology. ^[ref]

A surjective continuous map is not automatically a quotient map. On the same two-point set $D=\{a,b\}$, take the identity map from the discrete topology to the indiscrete topology. It is continuous and surjective, but $\{a\}$ is not open in the target even though its preimage is open in the domain. The quotient topology for this identity map would be the discrete topology. Thus continuity supplies only one direction of the rule using preimages of open sets; a quotient map requires both.

A quotient space of a space carrying the cofinite topology has a topology contained in the cofinite topology on its underlying quotient set. If $q:X\to Y$ is the quotient map and $U$ is a nonempty open subset of $Y$, its preimage has finite complement. Since $q$ is surjective, the complement of $U$ is the image of that finite complement, hence is finite. Equality need not hold: partition $\mathbb{Z}$ into its even and odd integers. Both classes are infinite, so their two-point quotient space has the indiscrete topology, whereas the cofinite topology on a finite set is the discrete topology.

In Simon's algorithm, conditioning on a function value leaves the first quantum register in an equal coherent sum of its two preimages. This is a pure state, even though discarding the second quantum register without retaining its outcome generally leaves a mixed state. The label $x$ depends on the measured value; the period $s$ does not.

For nonnegative integers $n,k$, the Stirling number of the second kindcounts the set partitions of an $n$-element finite set into exactly $k$ unlabelled blocks of a set partition. Set $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,k)=0$ for $k>n$. Also $S(n,1)=S(n,n)=1$ for $n\ge 1$. Grassl and Levin develop these counts through explicit set partitions and a recurrence relation. ^[ref]

Insert one distinguished element. For $n\ge 1$ and $1\le k\le n$, the Stirling numbers of the second kind obeyProof outline. Inspect the block of a set partition containing $n$. If it contains another element, removing $n$ leaves a set partition into $k$ blocks of a set partition; conversely, insert $n$ into any of those $k$ blocks of a set partition. If $n$ is alone, remove its singleton set and obtain a set partition into $k-1$ blocks of a set partition. The cases cannot overlap, and deletion reverses each construction. This explains the factor $k$ even though the blocks of a set partition have no names. ^[ref]

For $n=4,k=2$, start with the three two-block set partitions of $\{1,2,3\}$. Inserting $4$ into either block of a set partition gives six possibilities. The remaining possibility is $\{\{1,2,3\},\{4\}\}$, obtained by making $4$ a singleton set. Hence $S(4,2)=2\cdot 3+1=7$. The seven set partitions in the diagram comprise four with sizes $3+1$ and three with sizes $2+2$; this grouping by sizes independently gives $4+3=7$.

Three different counting questions. The binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ selects one $k$-element subset. The Stirling number of the second kind $S(n,k)$ groups all $n$ distinct elements into $k$ nonempty unnamed blocks of a set partition. The power $k^n$ counts all functions to a specified $k$-element finite set, allowing some destination labels to go unused. At $n=4,k=2$, these counts are respectively $6$, $7$, and $16$. Choosing two people, making two unnamed nonempty teams, and assigning each person a red or blue label are different tasks.

When the destinations have labels. For fixed finite sets $X,Y$ of sizes $n,k$, respectively, the number of surjective functions $X\to Y$ isHere every element of $Y$ must be used. Each surjective function gives a set partition of $X$ into its nonempty preimages $f^{-1}(\{y\})$. Conversely, assign the $k$ distinct destination labels to the $k$ blocks of a set partition in $k!$ ways, where $k!$ is a factorial. For two labelled teams of four people this gives $2!\cdot 7=14$: of the $2^4=16$ assignments, exactly two use only one label. Dividing arbitrary function counts by $k!$ fails in general because unused labels can be permuted without changing a function. For example, $3^4/3!=13.5$ cannot count set partitions. The empty-to-empty function is a surjection, consistent with $0!S(0,0)=1$. Stanley gives the bijection underlying this qualification.^[ref]

For example, the inclusion-exclusion principle counts the surjections from four elements to three labelled destinations as $3^4-3\cdot 2^4+3\cdot 1^4=36$. Thus $S(4,3)=36/3!=6$. An independent check chooses the only two-element block of a set partition in $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ ways; the other two elements form singleton sets.

Why these numbers also occur in algebra. Classifying all functions to an $m$-element finite set by the size $k$ of their image givesFor a fixed set partition, the falling factorial $(m{)}_k$ counts assignments of distinct labels to its $k$ blocks of a set partition, and is zero when $k>m$. At $n=3,m=4$, this reads $64=1\cdot 4+3\cdot 12+1\cdot 24$. Replacing $m$ by $x$ yields a polynomial identity: both sides agree at every nonnegative integer. Thus the Stirling numbers of the second kind translate powers into falling factorials. Grouping by equal values turns a counting rule into an algebraic change of coordinates. Summing $S(n,k)$ without destination labels instead gives the Bell number.

A real-valued function $f:D\to \mathbb{R}$ is a strictly increasing function if every pair $x<y$ in its domain of a function satisfies $f(x)<f(y)$. It is therefore injective, and each output has at most one preimage. Its inverse function on its image of a function is also strictly increasing. Every strictly increasing function is a nondecreasing function; the converse fails when outputs repeat.

The polynomial $f(x)=x^3$ is a strictly increasing function on the real line, although its derivative $f^{\prime }(x)=3x^2$ is zero at zero. Indeed, for $x<y$,because $x^2+xy+y^2=(x+y/2{)}^2+3y^2/4$ can vanish only when $x=y=0$. Thus a positive derivative everywhere is sufficient on a real interval, but is not necessary for a strictly increasing function.

Strict monotonicity does not ensure continuity: $g(x)=x$ for $x<0$ and $g(x)=x+1$ for $x\ge 0$ is a strictly increasing function with a jump discontinuity. Its image of a function omits $[0,1)$, so the inverse function exists only on the actual image of a function, rather than on all the real numbers.

The topological disjoint union of topological spaces $X_i$ has the labelled disjoint union as its underlying set. A subset is open exactly when its intersection with each labelled copy $X_i$ is open in that copy. Each copy is a clopen set, and a function from the topological disjoint union is continuous exactly when its restriction to every copy is continuous. This follows immediately by testing preimages of open sets on each copy. A topological space is homeomorphic to the topological disjoint union of its connected components exactly when all those connected components are open.

Applying the same measurable function $f$ to observations from two probability distributions cannot increase their total variation distance. Every output event $B$ is tested through its preimage $f^{-1}(B)$, which was already one of the input events. ThereforeFor the four-outcome example, recording only whether the result is $D$ makes the output probability distributions identical: each is a Bernoulli distribution with parameter $0.3$. The original total variation distance was $0.3$, but this coarse measurement leaves zero discrepancy. Discarding information can make two sources less distinguishable.

The same contraction holds for a common Markov kernel $K$: $d_{\mathrm{TV}}(PK,QK)\le d_{\mathrm{TV}}(P,Q)$. On a finite set, expand $PK-QK$, apply the triangle inequality to each output component, and use that each row of $K$ sums to one. A common randomized postprocessing step cannot increase distinguishability either.

The zero set of a function $f$ is the preimage $f^{-1}(\{0\})$, consisting of all its zeros of a function. For a real- or complex-valued continuous function, it is a closed set, because the preimage of the closed singleton $\{0\}$ under a continuous function is closed. A nonzero holomorphic function on a connected open set has isolated zeros by the identity theorem for holomorphic functions.