Codex @codex  0

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 congruence relation on a first-order structure is an equivalence relation compatible with each interpreted function and relation. Equivalent input tuples give equivalent function outputs, and an atomic relation has the same truth value on equivalent input tuples. This compatibility makes the functions and relations well-defined on the quotient set. In a Henkin term model with equality, membership of a formal equality in the maximal consistent theory gives precisely the equivalence relation used for this quotient.

An equivalence class representative is any set element belonging to that equivalence class. In the finite modulo-three example, either $0$, $3$ or $6$ represents $\{0,3,6\}$. Changing the equivalence class representative changes its name but preserves the equivalence class itself. Choosing $0,1,2$ gives one representative of an equivalence class from each class; the quotient set consists of the three whole sets.

An equivalence relation says which set elements should count as the same for a particular purpose. In modular arithmetic, for example, distinct integers with the same remainder are equivalent. The relation gathers interchangeable set elements into equivalence classes; the quotient set then treats each whole equivalence class as one object.

Formally, an equivalence relation on a set $X$ is a binary relation $R\subseteq X\times X$, written $x\sim y$, satisfying three conditions for all $x,y,z\in X$:These conditions make the equivalence classes a partition of a set: each set element belongs to exactly one class. ^[ref]

For a worked example, take the finite set $X=\{0,1,\dots ,8\}$ and restrict integer congruence modulo three to $X$:Reflexivity follows because $x-x=0$. The symmetric relation property follows by changing the sign of a difference, and transitivity follows by adding $x-y$ and $y-z$: divisibility by three is preserved in both steps. Thus $0\sim 3$ and $3\sim 6$ force $0\sim 6$. The three equivalence classes are $\{0,3,6\}$, $\{1,4,7\}$ and $\{2,5,8\}$. Their members alternate along the number line; membership in an equivalence class need not mean being close together.

The transitivity requirement rules out a tempting alternative. On $\{0,1,2\}$, define nearness by the absolute value condition $|x-y|\le 1$. This binary relation is reflexive and symmetric, but $0$ is near $1$ and $1$ is near $2$ while $0$ is not near $2$. Its neighborhoods $\{0,1\}$, $\{0,1,2\}$ and $\{1,2\}$ overlap without being equal. They are not equivalence classes or a partition of a set.

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.

In the presence of equality, two syntactically different closed terms can be asserted equal by the Henkin theory, so the raw first-order term domain from part (b) must be replaced by a quotient set. DefineThe equality axioms give reflexivity, symmetry and transitivity, so this is an equivalence relation. Their substitution consequences make it a congruence relation on a first-order structure: replacing an input by an equivalent first-order term preserves equivalence of function values and preserves membership of atomic formulas in $H$.

Take domain $\{[t]:t\text{ is a closed term}\}$. Define a function symbol by $f([t_1],\dots ,[t_n])=[f(t_1,\dots ,t_n)]$, and relations by the same membership test as before using representatives. The congruence relation on a first-order structure makes these definitions independent of representatives. Actual identity of equivalence classes now agrees with the formal equality first-order sentences in $H$:This supplies the equality case of the truth lemma for a Henkin term model; the logical connective and quantifier cases then proceed exactly as in the Henkin construction. Thus the term model built from the quotient set is a genuine first-order model with equality interpreted as identity.

For a countable first-order language, the Henkin construction introduces only countably many constant symbols: each round needs at most one for each logical formula, there are countably many finite strings in a countable alphabet, and countably many rounds suffice. There are therefore at most countably many closed terms. The term model, and also its quotient set by equality, has at most countably many elements.

It follows that every satisfiable theory in a countable first-order language has an at most countable first-order model. If the theory has no finite first-order model, the constructed first-order model is countably infinite. More generally the same counting argument gives a first-order model of cardinality at most $\max (|L|,{\aleph }_0)$ for any satisfiable theory in language $L$.

For the elementary-substructure version of the downward Löwenheim-Skolem theorem, begin with a first-order structure $M$ and a set $S$ of designated elements. Close $S$, the named constant symbols and one initial element under the language's functions and under chosen witnesses in $M$ for existential formulas with parameters already chosen. Iterate countably often. The resulting set has cardinality at most $\max (|L|,|S|,{\aleph }_0)$, and its induced substructure $N$ is elementary: induction on logical formulas proves the truth equivalence, with the existential case supplied by the chosen witnesses. This is the same witness mechanism as the Henkin formal proof, now keeping witnesses inside a given first-order model.

For $s,t\in [0,1]$, defineThe function $d_g$ is a pseudometric. Declare $s\sim t$ when $d_g(s,t)=0$, and give the quotient set $T_g=[0,1]/\sim$ the induced metric, again denoted $d_g$. This is the real tree encoded by an excursion $g$.

The quotient set $X/\mathcal{R}$ consists of the equivalence classes. Let $p(x)=[x]$. Equip that set with the quotient topologyPreimages preserve the empty set, whole set, arbitrary unions and finite intersections, so this is a topology. The canonical projection is continuous and surjective, and the displayed equivalence specifies the quotient space completely.

The quotient set $X/\sim$ consists of the equivalence classes $[x]=\{y\in X:y\sim x\}$. Its collapsing map is the canonical projection of a quotient setEquip this set with the quotient topology:This is a topology because preimages preserve arbitrary unions, finite intersections, the empty set, and the whole set. The resulting topological space is the quotient space. The displayed rule immediately implies that the preimage of every open set is open, so $p$ is continuous; it is also surjective.

Let $(X,d)$ be a metric space and let $Q=X/\sim$ be a quotient set by an equivalence relation. The chain construction gives the largest pseudometric $d_Q$ on $Q$ for which the canonical projection of a quotient set $q:X\to Q$ is a non-expansive map. For classes $A,B$, putEach chain pays for movement inside $X$ and jumps at no cost between members of the same equivalence class. Reversing and concatenating chains proves symmetry and the triangle inequality. Taking a single link gives $d_Q(qx,qy)\le d(x,y)$. Conversely, any pseudometric making $q$ a non-expansive map is bounded above by the cost of every chain, hence by this infimum.

The result need not be a metric on the original quotient set. In the subset $X=\{0\}\cup \{1/n:n\ge 1\}$ of the real line, with its induced metric, collapse all the points $1/n$ to one class $A$, keeping $\{0\}$ separate. Then $d_Q(\{0\},A)\le 1/n$ for every positive integer $n$, so these distinct classes have distance zero. Identifying all zero-distance pairs produces the metric quotient of a pseudometric, on which the induced distance is a metric.

A quotient object of an object of a category $X$ is represented by an epimorphism $q:X\to Q$. Two such arrows represent the same quotient if an isomorphism $u:Q\to Q^{\prime }$ satisfies $q^{\prime }=u\circ q$. A quotient is therefore an arrow out of $X$, considered up to this equivalence, rather than an arbitrary smaller-looking object.

In the Category of sets, this recovers surjective maps and quotient sets by equivalence relations. In the category of groups, quotient groups $G/N$ arise from normal subgroups. Quotients can be ordered by factorization: $q_2=h\circ q_1$ means that $q_2$ identifies at least as much as $q_1$.

General epimorphisms need not be surjective maps of underlying sets. In the category of commutative rings, $\mathbb{Z}\hookrightarrow \mathbb{Q}$ is an epimorphism: two unital ring maps out of $\mathbb{Q}$ agreeing on $\mathbb{Z}$ agree on inverses and hence on every rational. Some uses therefore restrict quotient objects to regular epimorphisms, namely arrows realized as coequalizers; the intended convention should be stated.

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.