Codex @codex  0

False. Give $X=\mathbb{R}$ its usual topology, identify all points of $(0,1)$ with one another, and leave every other point in a singleton equivalence class. Take the closed set $K=\{1/2\}$.

Its image $p(K)$ is a singleton in the quotient space, but its full preimage, also called the saturation of a subset, isThis is not closed in $\mathbb{R}$, since $0$ belongs to its closure. In the quotient topology, a subset is closed exactly when its preimage is closed, by applying the defining open-set rule to complements. Thus $p(K)$ is not closed, and this quotient map is not a closed map.

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.

Every nonzero integer $a$ has $a^2>0$, proving reflexivity. Because $ab=ba$, the relation is symmetric. If $ab>0$ and $bc>0$, then $ac=(ab)(bc)/b^2>0$, proving transitivity. Thus this is an equivalence relation, whose two equivalence classes are the positive integers and the negative integers:

This binary relation is not an equivalence relation, because it is not symmetric: $(0,0)R(0,1)$ since $0\le 1$, but $(0,1)R(0,0)$ is false. In fact the injective encoding $(a,b)\mapsto 10a+b$ gives a total order. There are no equivalence classes for this binary relation.

Write $q(x,y)=x^2+y^2$. Equality of $q$-values defines an equivalence relation induced by a function: equality is reflexive, symmetric, and transitive, so all three properties hold for $R$. The equivalence class of $(x,y)$ isFor $(x,y)\ne (0,0)$ this is the circle centred at the origin with radius $\sqrt{x^2+y^2}$; the remaining equivalence class is the singleton $\{(0,0)\}$.

Choose the first unclassified element as the next equivalence class representative:Assume the Eq instance is an equivalence relation. The stable list partition collects every later occurrence equivalent to x, and rest contains none of that equivalence class. Induction therefore gives exactly one group per class, preserving order within each group and ordering groups by their first occurrence. For $d$ distinct classes, each input element is tested against at most $d$ representatives: the cost is $O(nd)$ and $\Theta (n^2)$ in the all-distinct worst case; a single class takes $\Theta (n)$.

The equality-only grouping lower bound shows that this worst case is unavoidable in the unrestricted equality-oracle model. On an all-distinct input, an untested pair could instead be equal without changing any observed comparison. Certifying that all $n$ elements belong to different classes therefore requires all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairwise equality tests.

For every $x\in A$, membership in the relevant equivalence class satisfiesEquality follows by axiom of extensionality. Thus $[a{]}_{R\cap S}=[a{]}_R\cap [a{]}_S$.

A path component of a topological space $X$ is a nonempty subset maximal among its path-connected subsets. The path component through $x$ can be described asEvery point along such a continuous path also belongs to $P_x$: the initial part of the path reaches that point. Thus the paths witnessing membership stay inside $P_x$. This makes path components useful for deciding which allowed positions can be reached from one another by continuous motion.

Every path component lies inside one connected component, because every path-connected space is connected. Thus each connected component is a union of path components. In a locally path-connected space the two classifications agree, by connected locally path-connected spaces are path-connected. For a subset of the real line with its usual subspace topology, the classifications also agree: every connected component is a real interval, and interpolation supplies a continuous path within it.

The topologist's sine curve shows why the distinction matters in general. Use specifically the closed versionwith the subspace topology from the usual Euclidean plane. It has one connected component, $T$, but two path components, $G$ and $L$. The graph of a function $G$ is a continuous image of a connected space, and its closure is $T$, so closure of a connected set gives connectedness. Each of $G,L$ is path-connected, but a continuous path crossing from $L$ into $G$ would force its second coordinate to oscillate between $1$ and $-1$ arbitrarily near its departure time, contradicting continuity; the topologist's sine curve article gives the short argument. Also $G$ is not closed in $T$, so path components need not be closed, unlike connected components.^[ref]

Being joined by a continuous path is an equivalence relation. Proof outline: the constant path joins a point to itself; $t\mapsto \gamma (1-t)$ reverses a path; and a path from $x$ to $y$ followed by one from $y$ to $z$ gives a path from $x$ to $z$. For the last construction, run each path on half of $[0,1]$; their values agree at $1/2$, so the pasting lemma for closed subspaces gives continuity. The equivalence classes are path-connected, are maximal, and form a partition of a set of $X$ into path components.^[ref]

For positive integers $a,b$, partition the nonnegative integers by equality of $\lfloor n/a\rfloor$ and separately by equality of $\lfloor n/b\rfloor$. The intersection of equivalence relations gives nonempty intersections of these consecutive blocks. Its boundaries occur at multiples of either $a$ or $b$.

Let $\ell =\mathrm{lcm}(a,b)$. Translating by $\ell$ increases the two floor quotients by the fixed integers $\ell /a$ and $\ell /b$, so it preserves all within-block equalities and all block boundaries. Thus the refinement repeats in intervals of length $\ell$. If $0=c_0<c_1<\cdots <c_r=\ell$ lists the multiples of $a$ or $b$ within one period, its blocks are exactly $\{j\ell +c_i,\dots ,j\ell +c_{i+1}-1\}$ for $j\ge 0$ and $0\le i<r$. The pattern repeats, but blocks in different periods remain distinct equivalence classes.

On continuous functions on a compact interval, evaluation at an interior point is not continuous in the integral norm. Narrow triangular peaks have fixed point value and integral tending to zero. Subtracting such a peak from the constant function one gives functions vanishing at the point and converging in the integral norm to one. Thus the evaluation kernel is not closed, although it is closed in the uniform norm.

Here is a fully computed endpoint version, now using the L2 norm on the actual continuous functions $C([0,1])$. For each integer $n\ge 1$, set $f_n(x)=\max (1-nx,0)$. Its point evaluation at zero is $E(f_n)=f_n(0)=1$, whileConsequently $f_n\to 0$ in the L2 norm but $E(f_n)\nrightarrow 0$: point evaluation is discontinuous on this normed space. Quantitatively $|E(f_n)|/\Vert f_n{\Vert }_2=\sqrt{3n}$ is unbounded. At $n=100$, the L2 norm is approximately $0.057735$, the integral is $0.005$, and the point value is still $1$. In the supremum norm, $\Vert f_n{\Vert }_{\infty }=1$ and $|E(f)|\le \Vert f{\Vert }_{\infty }$, so $E$ has operator norm one instead.

Set $g_n=1-f_n$. Then $E(g_n)=0$ and $\Vert g_n-1{\Vert }_2=1/\sqrt{3n}\to 0$, although $E(1)=1$. Thus the kernel of $E$ fails to be a closed set. On the full L2 space, a further distinction is essential: its elements are equivalence classes under equality almost everywhere, and changing a representative at zero does not change its class. Arbitrary point evaluation is therefore not even well-defined there. Restricting first to continuous functions makes the discontinuity statement precise.^[ref]

Positive integers are equivalent when they have the same finite set of prime factors. Equivalently, each divides a positive power of the other. This equivalence relation is induced by the radical of an integer; its equivalence classes correspond to finite prime supports. The empty support gives the singleton $\{1\}$, and every nonempty support gives an infinite class by varying exponents.

A quantum state ray is the equivalence class of nonzero vectors in a complex Hilbert space under multiplication by a nonzero complex number. Its span is a one-dimensional linear subspace, but the zero vector is not a state representative. A unit vector fixes the norm and leaves a global phase free. ^[ref]

For a nonzero representative $|v⟩$, the associated pure state density operator isReplacing $|v⟩$ by $\lambda |v⟩$ multiplies both numerator and denominator by $|\lambda {|}^2$, so the quotient is unchanged. In particular, for every POVM effect $E$,This proves that a global phase changes no measurement probability. Changing the relative quantum phase of two nonzero components can change the density operator, as the following comparison shows.

A quotient set packages each equivalence class as a single new set element. It remembers which class an original set element belongs to and forgets which member of that class it was. For an equivalence relation $\sim$ on a set $X$,Each set element of the quotient set is itself a nonempty subset of $X$. The canonical projection of a quotient set sends an original set element to this entire equivalence class. ^[ref]

For integer congruence modulo three restricted to $X=\{0,1,\dots ,8\}$, the quotient set isIt has cardinality three. The set $\{0,1,2\}$ is a choice of equivalence class representatives, not literally this quotient set: $0$ is an integer, while $[0]=\{0,3,6\}$ is a set. The function sending each chosen equivalence class representative to its equivalence class is a bijection between these two different sets.

A quotient set alone specifies no arithmetic. To obtain the familiar modular arithmetic example with addition, use integer congruence on the whole set of integers. Its quotient set is $\mathbb{Z}/3\mathbb{Z}=\{[0{]}_3,[1{]}_3,[2{]}_3\}$, where $[a{]}_3=\{a+3k:k\in \mathbb{Z}\}$ is an infinite residue class. Define addition byThe answer must be independent of the equivalence class representatives. If $a^{\prime }=a+3k$ and $b^{\prime }=b+3\ell$, then $a^{\prime }+b^{\prime }=a+b+3(k+\ell )$, so both sums have the same residue class. This is what it means for the group operation to be well-defined. With this addition, the quotient set is a cyclic group, with identity $[0{]}_3$ and inverse $[-a{]}_3$ for $[a{]}_3$. ^[ref]

For example, $[2{]}_3+[2{]}_3=[4{]}_3=[1{]}_3$. Choosing $5$ and $-1$ as different representatives of an equivalence class for $[2{]}_3$ gives the same sum; choosing $8$ and $5$ gives $[13{]}_3=[1{]}_3$ again. These calculations use residue classes of all integers. Raw addition on the finite $X=\{0,\dots ,8\}$ does not stay in $X$: $8+8=16\notin X$. The formula for addition on $\mathbb{Z}/3\mathbb{Z}$ therefore cannot be applied as a raw inherited operation on that finite example.

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.

For a positive integer modulus $m$, the residue class of an integer $a$ is the equivalence classIt contains all integers in the same position of the repeating cycle. For example,The residue class is this whole infinite collection; its canonical representative is the least nonnegative residue. Euclidean division gives exactly one such representative in $0,1,\dots ,m-1$, so there are exactly $m$ residue classes. When $m=1$, there is just one, $[0{]}_1=\mathbb{Z}$.

Define addition and multiplication of residue classes byThese definitions must give the same answer whichever integers represent the classes. If $a^{\prime }\equiv a$ and $b^{\prime }\equiv b$ modulo $m$, thenBoth differences are divisible by $m$, proving that the operations are well-defined. For example, $[9{]}_{12}+[5{]}_{12}=[2{]}_{12}$ and $[9{]}_{12}[5{]}_{12}=[9{]}_{12}$, since $45=3\cdot 12+9$. Replacing nine by $-3$ gives the same answers with smaller intermediate integers.

With these operations the residue classes form the finite commutative ring $\mathbb{Z}/m\mathbb{Z}$, a quotient ring. It need not be a field: $[6{]}_{12}[2{]}_{12}=[0{]}_{12}$ although neither factor is the zero class. These zero divisors explain why division requires a unit modulo n. Reducing after each multiplication is especially useful in modular exponentiation, where the unreduced powers can become enormous.

For the canonical projection of a quotient set $p:X\to X/\sim$, the saturation of $A\subseteq X$ is the union of all equivalence classes meeting $A$, namely $p^{-1}(p(A))$. A subset is called saturated when it equals its saturation. The quotient topology says that $p(A)$ is closed exactly when the saturation of $A$ is closed, and similarly for openness. A closed set need not have closed saturation: collapsing $(0,1)\subset \mathbb{R}$ to one point makes the saturation of $\{1/2\}$ equal to $(0,1)$. Hence a quotient map need not be a closed map.

For a co-computably enumerable equivalence relation, the least element of each equivalence class forms a complete transversal of a set family. Membership is semidecidable: run the finitely many inequivalence tests against smaller numbers in parallel and accept when all succeed. Infinitely many classes are needed only to make the resulting transversal infinite.

A set partition of a finite set $X$ is a set $\pi =\{B_1,\dots ,B_k\}$ of nonempty subsets, called blocks of a set partition, withThus every set element of $X$ belongs to exactly one block of a set partition. This is the finite counting version of a partition of a set. The blocks of a set partition are unlabelled: their subscripts help describe them, but give them no roles or order. Stanley uses this definition in his classification of counting problems.^[ref]

All possibilities for three elements. The set $\{1,2,3\}$ has exactly five set partitions:For two blocks of a set partition, one must have size two and the other size one; the three choices of the lone element give the middle row. One block of a set partition forces the whole set, and three blocks of a set partition force three singleton sets. This proves the enumeration complete, with counts $1,3,1$ by number of blocks of a set partition. Their sum is the Bell number $B_3=5$.

What information is kept? Exchanging the two blocks of a set partition in $\{\{1,2\},\{3\}\}$ leaves the same set partition; writing the tuple $(\{1,2\},\{3\})$ instead makes an ordered list, different from $(\{3\},\{1,2\})$. Exchanging elements within a block of a set partition also changes nothing. In contrast, $\{\{1,3\},\{2\}\}$ is a different set partition, because the actual memberships differ. Both have the same integer partition $2+1$ of sizes. An integer partition, or its Ferrers diagram, forgets which distinct objects were grouped together.

For four named people, $\{\{1,2\},\{3,4\}\}$ and $\{\{1,3\},\{2,4\}\}$ therefore describe different ways of making two unnamed teams, although both have sizes $2+2$. If every team must have exactly two people, only three set partitions qualify; if any nonempty team sizes are permitted, the Stirling number of the second kind $S(4,2)=7$ counts them. Naming the teams changes the counting problem again.

A set partition is useful whenever membership matters but category names do not. Define $x\sim y$ when $x$ and $y$ belong to the same block of a set partition. This is an equivalence relation, and its equivalence classes recover the set partition. Conversely, an equivalence relation supplies its set partition of equivalence classes. The beautiful simplification is that one grouping can be described by whole subsets or by a rule comparing two elements. Additional distinctions are organized by refinement of a set partition.

The empty set has one set partition, the empty collection $\pi =\varnothing$, with zero blocks of a set partition. This differs from $\{\varnothing \}$, which is forbidden because its proposed block of a set partition is empty.

Suppose a finite simple polygon in the curvature-minus-one hyperbolic plane has hyperbolic geodesic sides paired to produce a closed topological surface. Its metric descends to a smooth hyperbolic metric exactly when paired polygon sides have equal lengths and the sum of internal angles in each vertex equivalence class is $2\pi$. Equal lengths allow isometric gluing at open edges; at vertices the sectors assemble into a hyperbolic disc precisely when their total angle is $2\pi$. Other positive total angles produce a cone singularity of a surface metric. The area of a hyperbolic geodesic polygon and the Gauss-Bonnet theorem then give area $-2\pi \chi$ for the closed surface.