Quotient Sets and Well-Definedness

Suppose you want to add fractions. A fraction like $2/4$ is really just a name. It's a name for the number that $1/2$ , $3/6$ , and $-5/-10$ also name. Addition of fractions is defined by the rule $a/b + c/d = (ad+bc)/(bd)$ . But how do you know the answer doesn't depend on which names you picked? This question is about whether an operation defined on representatives actually descends to an operation on the things they represent. It is the problem of well-definedness. This problem sits at the heart of an enormous amount of ordinary mathematics. The formal machinery for this problem is the quotient set. Given a set $A$ and an equivalence relation $\sim$ on $A$ , the quotient set $A/\sim$ collects the equivalence classes of $\sim$ . These classes form a brand-new set. Its elements are themselves sets of elements of $A$ . This construction converts "sameness up to $\sim$ " into literal set-theoretic equality. Two classes $[a]$ and $[b]$ are equal as elements of $A/\sim$ exactly when $a \sim b$ . Quotient sets let us build new mathematical objects this way. Examples include the integers from pairs of naturals, and the rationals from pairs of integers. Other examples are remainders mod $n$ , congruence classes, and cosets of a subgroup. We do this by declaring certain elements "the same." Then we work with the resulting classes as if they were single points. The subtlety appears once you pass to the quotient. Suppose you want to define a function or relation on classes. First you choose a representative and compute something with it. But this must be checked for well-definedness. Does the result depend only on the class? Or does it secretly depend on which representative you happened to pick? This check is not a formality. It is a genuine proof obligation. Forgetting it is one of the most common errors made by students. This tends to happen when they are first learning to build quotient structures. This article gives the precise definition of $A/\sim$ . It proves the fundamental theorem linking equivalence relations, partitions, and quotient sets. It develops the general recipe for proving a map on a quotient is well-defined. It closes with worked examples: rational numbers and arithmetic modulo $n$ . It also gives a counterexample showing what happens when well-definedness genuinely fails. Finally, it looks at where this idea recurs throughout modern mathematics.

Key takeaways

$A/\sim$ is the set of all equivalence classes of $\sim$ on $A$ ; its elements are sets of elements of $A$ , not elements of $A$ itself.
The Fundamental Theorem of Equivalence Relations says equivalence relations on $A$ correspond exactly to partitions of $A$ , and this correspondence is what makes $A/\sim$ meaningful.
Defining a function $f\colon A/\sim \to B$ "by representatives" means picking a rule $F\colon A \to B$ and setting $f([a]) = F(a)$ .
Such an $f$ is well-defined iff $a \sim a'$ implies $F(a) = F(a')$ for all $a, a' \in A$ — this is a theorem you must prove, not an assumption.
Classic constructions (rationals from integer pairs, modular arithmetic, cosets) are quotient sets whose operations require exactly this check.
Key idea: a rule on representatives determines a genuine function on the quotient only if equivalent representatives always produce equal outputs.

Where this lives today

Quotient constructions and their well-definedness checks are everywhere once you know to look. In abstract algebra, quotient groups $G/N$ , quotient rings $R/I$ , and quotient vector spaces $V/W$ are all built exactly this way: elements of the quotient are cosets (equivalence classes), and operations like $(g_1N)(g_2N) := (g_1g_2)N$ require the same representative-independence proof, using the defining properties of a normal subgroup or ideal. In number theory and cryptography, modular arithmetic — the backbone of RSA and other public-key systems — is arithmetic on the quotient set $\mathbb{Z}/n\mathbb{Z}$ , and every claim that "encryption commutes with the modular operations" ultimately rests on a well-definedness argument of this kind. In topology, quotient spaces (gluing constructions like forming a torus from a square, or projective space from a sphere) use the same equivalence-class idea, now demanding also that continuity of maps descend to the quotient topology. In computer science and formal verification, data type invariants and "canonical forms" (e.g. representing rational numbers, or terms modulo alpha-equivalence in lambda calculus) are handled by exactly this apparatus, since programs must be shown to give consistent output regardless of which internal representative of an abstract value they receive. In statistics and measure theory, spaces of random variables identified when they agree "almost surely" form a quotient set, and operators (like conditional expectation) must be checked to be well-defined on these classes.

:::quiz[The Well-definedness Criterion says $f([a]):=F(a)$ is a well-defined function on $A/\sim$ if and only if:]

$F$ is injective on $A$
$F$ is surjective onto $B$
$a \sim a'$ implies $F(a) = F(a')$ , for all $a,a' \in A$ ✓
$F(a) \sim F(a')$ implies $a = a'$

Ask the tutor: Can you show me why the "check both coordinates separately" step in the fraction-addition example is enough to guarantee full well-definedness on pairs of classes?

A

Intuition

Think of $A$ as a set of raw objects and $\sim$ as an instruction for "gluing together" objects that we've decided to regard as the same. The quotient set $A/\sim$ is the set of resulting blobs, one blob per equivalence class. The quotient map $q$ sends each raw object to its blob. Crucially, $q$ is generally not injective: many different elements of $A$ can land in the same blob. That collapsing is the entire point — it's how we manufacture new mathematical objects (like "the number $1/2$ ") out of old ones (like "pairs of integers"). The trouble comes when we want to define an operation on blobs. A blob has no preferred representative — $[1/2]$ as a fraction class has representatives $(1,2)$ , $(2,4)$ , $(-3,-6)$ , all equally legitimate. If we compute an answer using one representative, we must get the same answer no matter which representative we had used, or the "operation on blobs" isn't really an operation at all — it would be assigning multiple different outputs to the single input $[1/2]$ , violating the very definition of a function. The well-definedness check is exactly the verification that our chosen computation doesn't secretly "look inside" the blob and depend on more information than the blob itself contains. The picture below shows $A = \mathbb{Z}$ partitioned by congruence mod $3$ into three classes, collapsed to the three-point quotient set $\mathbb{Z}/{\equiv_3}$ .

Figure

The quotient map collapsing

\mathbb{Z}

into three classes mod 3

Central results

A

A/\sim

\sim

\Rightarrow

Worked examples

Example 1: Addition of rational numbers as fractions in lowest-terms-free form. Let $A = \mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$ , the set of pairs $(p,q)$ thought of as "the fraction $p/q$ ." Define $\sim$ on $A$ by

(p,q) \sim (r,s) \iff ps = rq.

This is an equivalence relation (a standard fact we take as known, verified by checking reflexivity from $ps=ps$ ; symmetry by the commutativity of multiplication; and transitivity using that $q,s,u$ are all nonzero, so cancellation in $\mathbb{Z}$ is valid: from $ps=rq$ and $ru=ts$ , cross-multiplying by $u$ and $q$ respectively and comparing yields $pu = tq$ after cancelling the nonzero common factor $s$ ). We want to define addition on $\mathbb{Q} := A/\sim$ by

[(p,q)] + [(r,s)] := [(ps+rq,\ qs)].

Take $F\colon A \times A \to A$ , $F((p,q),(r,s)) = (ps+rq,\, qs)$ , followed by the quotient map; formally we're defining a map on $A/\sim \times A/\sim$ , but the same representative-independence idea applies to each coordinate separately, and we check it coordinate by coordinate for concreteness. Note $qs \neq 0$ since $q,s\neq0$ , so $F$ does land in $A$ .

Well-definedness check. Suppose $(p,q) \sim (p',q')$ , i.e. $pq' = p'q$ , and we replace $(p,q)$ by $(p',q')$ while keeping $(r,s)$ fixed. We must show

(ps+rq,\ qs) \sim (p's+rq',\ q's).

Using the definition of $\sim$ , this means checking

(ps+rq)(q's) \;=\; (p's+rq')(qs).

Expand the left side: $ps q's + rq q's = pq's \cdot s + rqq's$ . Expand the right side: $p'sqs + rq'qs = p'qs\cdot s + rqq's$ (using $q'q = qq'$ ). So the claim reduces to $pq' s^2 = p'q\, s^2$ , i.e. (since $s \neq 0$ , so $s^2 \neq 0$ , and we may cancel in $\mathbb{Z}$ , an integral domain) to $pq' = p'q$ — which is exactly our hypothesis $(p,q)\sim(p',q')$ . Since $s^2 \ne 0$ and $\mathbb Z$ has no zero divisors, the cancellation is valid. The symmetric check for varying the second argument $(r,s)$ is identical with the roles of the two pairs swapped. By the Well-definedness Criterion (applied to each argument, or to the product relation on $A\times A$ defined by "same in both coordinates"), addition of fractions

[p/q] + [r/s] := [(ps+rq)/(qs)]

is a well-defined operation on $\mathbb{Q} = A/\sim$ . This is precisely the proof, usually skipped in school, that "adding fractions by finding a common denominator gives the same rational number no matter which representing fractions you started from."

Example 2: A map that is well-defined, and the specific representatives that test it. Let $A = \mathbb{Z}$ and let $\sim$ be congruence mod $6$ : $a \sim b \iff 6 \mid (a-b)$ . Define $F \colon \mathbb{Z} \to \mathbb{Z}/2\mathbb{Z}$ (identify $\mathbb{Z}/2\mathbb{Z} = \{0,1\}$ with the usual parity classes) by

F(n) = n \bmod 2.

We claim this descends to a well-defined map $f\colon \mathbb{Z}/{\equiv_6} \to \{0,1\}$ , $f([n]_6) = n \bmod 2$ . Check the criterion. Suppose $a \sim b$ , i.e. $6 \mid a - b$ . Since $6 = 2 \cdot 3$ , in particular $2 \mid a-b$ , so $a$ and $b$ have the same parity, i.e. $F(a) = F(b)$ . This verifies the hypothesis of the Well-definedness Criterion, so $f$ is a genuine, well-defined function $\mathbb{Z}/{\equiv_6} \to \{0,1\}$ . A concrete test. Take the class $[4]_6 = \{\dots,-8,-2,4,10,16,\dots\}$ . Using representative $4$ : $F(4) = 0$ . Using representative $10$ (since $10 \equiv 4 \pmod 6$ , as $10-4=6$ ): $F(10)=0$ . Using representative $-8$ (since $-8-4=-12=6\cdot(-2)$ ): $F(-8) = 0$ . All three representatives of the same class $[4]_6$ give the same output $0$ , exactly as the theorem guarantees. Contrast — what would fail. Suppose instead we tried $G(n) = n \bmod 4$ and asked whether $g([n]_6) := n \bmod 4$ is well-defined on $\mathbb{Z}/{\equiv_6}$ . Test representative $2$ of the class $[2]_6$ : $G(2) = 2$ . Test representative $8$ (since $8 - 2 = 6$ , so $8 \sim 2$ ): $G(8) = 8 \bmod 4 = 0$ . We get $2 \neq 0$ from two representatives of the same class $[2]_6$ , so $g$ is not well-defined — this is exactly the failure the next block explores formally.

Counterexample

a \sim a' \implies F(a) = F(a')

Scope, edge cases & common traps

Situation	What to check	Common error
Defining $f([a]):=F(a)$ for one-variable $F$	$a\sim a' \Rightarrow F(a)=F(a')$ for all pairs	Checking only one or two sample representatives, not a universally quantified statement
Defining an operation $[a]*[b] := [F(a,b)]$	Independence under changing $a$ and independence under changing $b$ (often two separate checks)	Verifying only one coordinate and assuming symmetry handles the other
$A/\sim$ is finite (e.g. $\mathbb{Z}/n\mathbb{Z}$ )	Same universal compatibility condition; finiteness gives no shortcut	Believing "checking a few cases" ever substitutes for the general argument
Relation is only reflexive+symmetric (not transitive)	The Fundamental Theorem's disjointness argument needs transitivity	Calling classes "equivalence classes" for a non-transitive relation, then applying the theorem anyway
$F$ happens to be injective	Injectivity of $F$ says nothing about compatibility with $\sim$	Assuming an injective $F$ is automatically well-defined on $A/\sim$

The mathematician behind it

Origins · 1 minRichard Dedekind and how this was discovered

Richard Dedekind

1831–1916 · Foundations of arithmetic and algebraic number theory, University of Göttingen and Braunschweig

Dedekind was among the first to treat "sameness up to an equivalence" as a rigorous algebraic tool rather than an informal convenience. His construction of ideals in rings of algebraic integers — and his method of Dedekind cuts for constructing the real numbers from the rationals — both hinge on the idea of collecting equivalent or compatible objects into a single new object and then verifying that arithmetic operations descend correctly to these new objects. This is exactly the well-definedness pattern formalized in this article, applied by Dedekind decades before the general set-theoretic language of equivalence relations and quotient sets was codified.

History

- 1858 — Dedekind develops the cut construction of the real numbers, an early quotient-like device separating rationals into compatible classes.

- 1871 — Dedekind introduces ideals in rings of algebraic integers, treating classes of elements as new algebraic objects with well-defined operations.

- 1888 — Dedekind's Was sind und was sollen die Zahlen? gives an early rigorous treatment of equivalence and abstraction in the foundations of number.

- 1895 — Georg Cantor's set-theoretic papers make the general notion of a set of equivalence classes an explicit, freestanding object of study.

- 1930s — Modern algebra texts (van der Waerden, following Emmy Noether and Emil Artin) formalize quotient groups, quotient rings, and the general well-definedness check as standard technique.

What exactly is the difference between an equivalence class and the quotient set?

An equivalence class $[a]$ is a subset of $A$ : the set of all elements equivalent to $a$ . The quotient set $A/\sim$ is a set of such subsets — one element for each distinct equivalence class. So if $A = \{1,2,3,4\}$ and $\sim$ groups $\{1,3\}$ and $\{2,4\}$ , then $[1] = \{1,3\}$ is a subset of $A$ with two elements, while $A/\sim = \{\{1,3\},\{2,4\}\}$ is a two-element set whose elements are themselves sets. This distinction — class as subset, quotient as set-of-subsets — is exactly why $A/\sim \subseteq \mathcal{P}(A)$ .

Do I always need to check well-definedness "by hand" using the criterion?

Yes, in the sense that the criterion is what the check reduces to, though in practice you streamline the algebra. Whenever you define a function or operation on a quotient by choosing representatives and computing with them, you must verify that swapping any representative for an equivalent one leaves the output unchanged. There is no shortcut around this for a genuinely new construction; what varies from example to example is how much algebra the verification requires, not whether the verification is logically necessary.

Can well-definedness fail in only "some" cases but not others?

No — well-definedness is an all-or-nothing property of the pair $(F,\sim)$ : either the universally quantified statement " $a\sim a' \Rightarrow F(a)=F(a')$ " holds for every pair, or it fails for at least one pair. If it fails for even a single pair, then, as the counterexample shows, the proposed rule assigns two different values to one class, so it isn't a function at all on the quotient. There's no notion of "mostly well-defined."

How does this connect to functions being a special kind of relation?

A function $f\colon X \to Y$ is often defined as a relation $R \subseteq X \times Y$ satisfying: for every $x\in X$ there is exactly one $y$ with $(x,y) \in R$ . The well-definedness check is precisely verifying this "exactly one" clause when the proposed relation is $\{([a], F(a)) : a \in A\}$ on $A/\sim \times B$ : existence of an output is automatic (every class has a representative), and the real content is uniqueness — that no class gets sent to two different outputs. This ties the quotient-set discussion directly to the general treatment of Functions as Special Relations.

Is the quotient map

q\colon A \to A/\sim

itself an example of this construction?

Yes, trivially and instructively: take $B = A/\sim$ and $F = q$ itself, i.e. $F(a) = [a]$ . Compatibility is immediate — if $a \sim a'$ then $[a]=[a']$ by the Fundamental Theorem, so $F(a)=F(a')$ holds automatically. This shows the quotient map is always well-defined "for free," which is exactly why every quotient construction begins by taking $q$ for granted before worrying about any further structure (like addition) defined on top of it.

What if

\sim

is not an equivalence relation, just reflexive and symmetric?

Then $A/\sim$ as we've defined it may fail to be a partition, because the disjointness argument in the Fundamental Theorem genuinely used transitivity. Concretely, on $A=\{1,2,3\}$ , let $1\sim2$ , $2\sim3$ , but not $1\sim3$ (plus reflexivity and symmetry). Then $[1]=\{1,2\}$ and $[3]=\{2,3\}$ overlap in $2$ without being equal, so the "classes" are not pairwise disjoint, and the resulting collection is not a partition. The entire theory in this article requires genuine equivalence relations.

Why does this matter for cryptographic or computational systems that use modular arithmetic?

Systems built on $\mathbb{Z}/n\mathbb{Z}$ (like RSA) represent numbers by one integer among infinitely many congruent choices, and every operation — modular multiplication, exponentiation, inversion — must be proven independent of which representative integer was used internally. This is exactly the Well-definedness Criterion applied to $F$ 's built from ordinary integer arithmetic composed with reduction mod $n$ ; without this guarantee, the same abstract residue class could be computed to different "answers" depending on implementation details, which would make the cryptosystem's correctness proofs meaningless.