Motivation
A quotient construction starts with a decision to regard some descriptions as the same object. That decision has consequences. If the description is identified with , and with , then must also be identified with . Simply listing the original pairs does not necessarily describe a consistent equality relation on the new objects.
There is a second question after the quotient exists. A formula written using a representative must give the same answer for every representative of the same class. This is the content of being well-defined on the quotient. It is a theorem to prove, rather than a convention that can make an ambiguous formula valid.
This section develops those two steps in ZF. We use the earlier constructions of ordered pairs, function graphs, natural numbers and quotient sets. No axiom of choice is assumed.
Relations generated by finite identifications
Fix a set and a relation . Write for . The relation need not be reflexive, symmetric or transitive. Its pairs specify the identifications that we want to impose.
Definition 1.4.1
(-path and the generated relation)
An -path from to is a finite sequence , for some , such that , , and, for each ,
The length is the number of steps, so a path of length zero has one vertex. Either direction of an -pair may be traversed: identifying two objects cannot depend on which one was written first. Define
This defines a set relation by Separation inside . The paths also have a concrete set bound. Every such sequence has graph contained in , so all candidate graphs lie in . Separation selects the functions with a finite nonempty initial domain and the required edge conditions. We are not quantifying over a supposed set of all functions on arbitrary domains.
Theorem 1.4.2
(The least equivalence relation containing a relation)
The relation is an equivalence relation on containing . If is any equivalence relation on with , then .
Proof
(Paths give the least equivalence relation)
The one-vertex path at proves . Reversing a path proves symmetry, because each allowed step can be traversed in either direction. Given paths from to and from to , concatenate them, writing the common endpoint only once. This is a path from to , including when either path has length zero. Thus is transitive. A pair supplies a path of length one, so .
Now let be as in the statement. Every step of an -path is an -step, using symmetry of when the -pair is traversed backwards. Induction on the path length, using reflexivity at length zero and transitivity for the next step, proves that its endpoints are -related. Consequently .
There is another description of the same construction. Let
This is a nonempty set: belongs to it, even when . The intersection of its members is an equivalence relation containing , since each of the three equivalence-relation axioms survives intersection. The leastness just proved therefore gives
The intersection describes what every permitted identification system must contain. The finite-path description supplies witnesses for belonging to it. Neither construction selects representatives.
Proof X-ray
Why finite paths give exactly the required closure
There are two inclusions to establish. To show that the path relation is large enough, prove that it contains the original pairs and satisfies the equivalence axioms. To show that it is no larger than necessary, place it inside an arbitrary equivalence relation containing those pairs. The second inclusion prevents accidental extra identifications.
A phrase such as “add the missing pairs” hides both obligations. Finite paths make transitivity concrete, while the arbitrary-containing-relation argument proves minimality without an algorithm for searching through every possible closure.
Equivalence relations and partitions
Definition 1.4.3
(Partition and quotient set)
A partition of is a set of nonempty subsets, called blocks, whose union is and whose distinct members are disjoint. The partition of the empty set is , not : the latter has an empty block.
For an equivalence relation on , define
The foundational construction of bounds it by . Its members are whole subsets of , not names for unspecified preferred elements.
Theorem 1.4.4
(Partitions are precisely equivalence-class families)
The classes of an equivalence relation partition , and
Conversely, a partition determines an equivalence relation by declaring and related exactly when some block contains both. These constructions are inverse to one another.
Proof
(Classes and blocks determine each other)
Reflexivity puts in , so every class is nonempty and the classes cover . If and , symmetry and transitivity give ; the reverse argument gives equality of the two classes. Conversely, equality of the classes puts , giving .
If lies in both and , then and , so symmetry and transitivity give . Thus intersecting classes coincide, proving disjointness of distinct classes.
Now take a partition. Each point lies in a unique block: existence follows from the union condition, and two blocks containing it would intersect and hence be equal. Sharing a block is reflexive and symmetric. If share one block and share another, those blocks coincide because they both contain ; thus share a block. The resulting relation is therefore an equivalence relation, and the class of is exactly its unique block. This recovers . Starting with , the displayed class identity recovers from its partition. The empty case satisfies all assertions as well.
The projection , given by , is onto. Its fiber over the point of the quotient is exactly the subset of the original set. The same class has these two roles, which explains why distinguishing the domain from the quotient matters.
Passing a function through a quotient
Definition 1.4.5
(Kernel equivalence relation)
Let be a function. Its kernel equivalence relation is
This use of “kernel” refers to equality of outputs, with no group or vector-space structure required. The equivalence axioms follow from the corresponding properties of equality.
Theorem 1.4.6
(Factorization through classes)
For an equivalence relation on , there is a unique function satisfying if and only if . When this condition holds, is onto exactly when is onto, and it is one-to-one exactly when .
Proof
(Factor through the quotient by unique outputs)
If a factor exists and , then . Therefore , proving the necessary inclusion.
Conversely, suppose . Define a graph inside by
Every class has at least one such value. If and both represent , they are -related, so . The value is therefore unique. Separation gives a function graph , defining and the required equation. Any other factor must take to ; since every class is of that form, the factor is unique.
The two maps and have exactly the same range, proving the assertion about surjectivity. If is injective and , its two class arguments must coincide, so . Thus , which together with the assumed inclusion gives equality. Conversely, if and , then gives and hence equality of the classes. This proves injectivity.
In particular, there is a canonical bijection
Every set function thus separates into an onto projection, a bijection onto its image, and the inclusion of that image in its declared codomain. This is a theorem about arbitrary sets in ZF.
Concept lensStructural
A unique output replaces representative selection
Writing does not instruct us to choose one in every class. The graph proof quantifies over all possible representatives and proves that they give one output. Uniqueness supplies a function without any selection rule.
If different representatives give different answers, choosing a preferred representative might define a different function after extra data are supplied. It does not prove that the original rule was independent of representatives. The distinction is especially useful when constructing numbers or a model from equivalence classes of descriptions.
For a relation specified by generators, the test is simpler still: factors through exactly when implies . Necessity follows because . For sufficiency, equality of outputs persists along every path, so . Equivalently, is an equivalence relation containing , and minimality applies.
Comparing and combining equivalence relations
The equivalence relations on a fixed set are subsets of , so they form a set, partially ordered by inclusion. A smaller relation identifies fewer pairs and has a finer partition. Two questions arise. How are the quotients by two comparable relations related? And what is the least relation identifying everything that either of two relations identifies?
Theorem 1.4.7
(Quotients by a finer and a coarser relation)
Let be equivalence relations on , with projections and . There is a unique function with , namely , and it is onto. The relation on given by
is a well-defined equivalence relation. It equals the kernel relation , and induces a bijection .
Proof
(Apply the factorization theorem twice)
The class identity proved for partitions says exactly when , so . The hypothesis is therefore the condition of the factorization theorem, which supplies the unique . It is onto because is onto.
Next, means , that is, . So the displayed condition describes the kernel relation , which is an equivalence relation on . The condition cannot depend on the chosen representatives , because is defined from the classes alone. Finally, the factorization theorem applied to and gives an induced map that is onto, because is, and one-to-one, because is the whole kernel.
Definition 1.4.8
(Composite of two relations)
For relations , define
As with functions, is applied first. Composition of relations is associative: both and contain exactly when there are with , and . Also .
Theorem 1.4.9
(Meet and join of two equivalence relations)
Let and be equivalence relations on .
- is an equivalence relation, and it is the largest one contained in both and .
- The least equivalence relation containing is . We have exactly when, for some , there are in with and for every .
- is an equivalence relation if and only if . In that case .
Proof
(Alternating chains and commuting composites)
Part 1. Reflexivity, symmetry and transitivity each say that certain pairs belong to the relation whenever certain other pairs do. If these hold for and for , they hold for . Any equivalence relation contained in both and is contained in .
Part 2. The relation is the least one containing by the theorem on the least equivalence relation containing a relation, at the start of this unit. An alternating chain is an -path, which gives one inclusion. Conversely, take an -path from to . Because and are symmetric, each step, in whichever direction it was traversed, is a forward -step or a forward -step. Where two consecutive steps have the same type, repeat the vertex between them and label the new trivial step by the other relation, using its reflexivity. If the path starts with an -step, repeat the first vertex in front with an -label; if it ends with an -step, repeat the last vertex at the end with an -label. The new path has the same endpoints and alternates , so its length is even. The path of length zero is the case .
Part 3. Taking or in the definition, reflexivity of and shows ; in particular is reflexive. Since and are their own inverses, . If is an equivalence relation, it is symmetric, so .
Conversely, suppose . Then equals its own inverse, so it is symmetric. Reflexivity and transitivity of give , and likewise . By associativity,
which in particular gives transitivity. So is an equivalence relation containing , and hence contains . Each pair in is joined by a two-step -path, so .
Worked example 1.4.10
(Congruences always commute)
For a positive integer , write for congruence modulo on . Let be positive integers. If and , then . Conversely, if , put ; then and . Hence
This description is symmetric in and , so the two relations commute. By Bézout's identity, with , so the join is . The meet is with , because .
For and , the join is parity and the meet is congruence modulo . Since , the comparison theorem gives the onto map from the four classes modulo to the two parity classes. The relation has the two blocks and , matching .
Worked examples
A pair list can force a larger block
Worked example 1.4.11
(Three descriptions become one class)
Let , with distinct labels, and let . There are paths between any two points of . No path can connect to a different vertex, since no allowed step touches . Thus the blocks of are and . The relation contains all nine ordered pairs within the first block and the one pair .
A function on passes to this quotient exactly when ; its value at is unrestricted. Checking only misses the other specified identification, while allowing contradicts its transitive consequence.
The union of two equivalence relations can fail
Counterexample mode
The union of two equivalence relations
Claim: the union of two equivalence relations on a set is again an equivalence relation. On , let have blocks and have blocks . Their union relates to and to , but does not relate to . It is not transitive. The least equivalence relation containing both is ; here it has one block, the whole set.
In contrast, is equality on this set. Intersections preserve the equivalence axioms, while unions generally need the finite-path closure.
Forgetting signs retains a precise image
Worked example 1.4.12
(The quotient of integers by equal squares)
For with , equality gives , hence or . The kernel classes are and the pairs for positive integers . The induced map sends each class to its common square.
It is a bijection onto , not onto all of : for example, is not a square. Quotienting by equal outputs removes exactly the failure of injectivity. It does not enlarge the range. If instead we identify integers only by parity, the square rule does not descend to an integer-valued function, since and have the same parity but different squares.
Operations have a compatibility condition too
Worked example 1.4.13
(A transformation of classes need not fix representatives)
Let be equality of parity on . A map induces exactly when implies . Its values need not be literally equal on a class; they need only lie in the same target class.
For , an even difference remains even after applying , so the induced map exchanges the two classes. By contrast, fails: , while and have different parity. A plausible formula on representatives can therefore fail even for a quotient with only two points.
Common mistakes and a quick check
Common mistake
(A class is neither an element of nor its representative)
An equivalence class is a subset of and an element of . It generally is not an element of . A class also is not its representative: distinct representatives can give the very same class.
Common mistake
(Least is not largest)
Minimality and maximality point in different directions. contains the required pairs but is contained in every equivalence relation that contains them. It is not the largest such relation; is the largest one.
Common mistake
(Equal outputs versus equal output classes)
A function with values in must have equal outputs on each class to factor to . A function with values in another quotient needs equal output classes. The last worked example illustrates why these conditions should not be interchanged.
Quick check
(What are and when , and when ?)
Treat a nonempty and separately.
Solution · Answer
If , the only possible paths have length zero, so is equality and no distinct points are identified. If , every two points of a nonempty are joined in one step, giving a one-point quotient. For , the quotient is empty instead. These boundary cases check both the path convention and the nonempty-block convention.
Exercises
Quick check
(Generated blocks)
Let and . Determine and prove that no other identifications are forced.
Solution · Answer
The proposed blocks are and . Inside , the path uses the second specified pair backwards; every two points are consequently connected. The two points of are connected directly. The relation of belonging to the same one of is an equivalence relation containing , so leastness prevents any path identification between the blocks. Thus .
Quick check
(Closing an order)
On , let be the usual relation . Find . Explain why this construction does not preserve the original order information.
Solution · Answer
For any , either or , so a one-step path joins them. Hence , and the quotient is . Equivalence closure deliberately makes every generator reversible. It records forced equalities, so it cannot retain the direction or distinction of a genuine order.
Quick check
(Subsets of a quotient)
Let be an equivalence relation on . Prove that subsets of correspond bijectively to subsets that are unions of -classes. Relate the correspondence to characteristic functions .
Solution · Answer
Send to . This is a union of classes. Conversely, for a union of classes , take . Every class is nonempty; disjointness implies that a class contained in must be one of the members of . The two constructions are therefore inverse, including the empty case. A characteristic function is constant on classes exactly when membership in is constant on classes, which is exactly the union-of-classes condition. The factorization theorem identifies it with the characteristic function of the corresponding subset of .
Quick check
(Restricting to a subset)
Let be an equivalence relation on , and let . Restrict to and prove that defines an injection . When is it onto?
Solution · Answer
Here and . If two representatives give the same restricted class, they are -related and give the same full class, so the map is well-defined. If their full classes agree, they are -related within , so the restricted classes agree, proving injectivity. Its image consists exactly of the full classes meeting . Thus it is onto precisely when meets every -class. No simultaneous representative choice is needed to construct this map.
Quick check
(Right inverses of the projection)
Show that a right inverse of exists exactly when there is a subset of meeting each -class in exactly one point. Explain which part of the quotient-factorization theorem avoids this additional requirement.
Solution · Answer
If satisfies , then . Its range meets each class, and a value selected for a different class cannot lie in , so the meeting point is unique. Conversely, if meets every class exactly once, the relation iff defines a function by unique existence and satisfies . Both statements hold for empty , with empty . The factorization proof instead gives each class a unique output in because all its representatives already have that same output; it never needs to select a point of the class itself. This equivalence for a given quotient does not assert that every quotient has a right inverse in ZF.
Quick check
(Induced operations)
For a binary operation , prove that is well-defined exactly when and imply . If is associative, prove that the induced operation is associative.
Solution · Answer
Necessity follows by using equal class arguments and in a well-defined operation. For sufficiency, the stated implication makes the output class independent of both representatives. Each pair of classes has a uniquely determined output class, so Separation defines its graph without selecting representatives simultaneously. If is associative, then for any representatives the two bracketings are represented by and , which are equal in . Their classes agree, proving associativity on the quotient. Every triple of classes has representatives locally by the definition of the quotient; only finitely many existential witnesses are used in this proof.
Quick check
(Composites that do not commute)
On , with distinct labels, let have blocks and have blocks , as in the counterexample on unions. Compute and . Show that neither is an equivalence relation, and find .
Solution · Answer
A pair lies in when some has and . From the only is , so . From or we may take , so can be any of . Thus consists of all nine pairs except . Its inverse consists of all pairs except . Neither is symmetric, as part 3 of the theorem predicts for non-commuting relations. The alternating chain joins to , so , with a single block.
Quick check
(Refinement in three forms)
Let and be equivalence relations on . Prove that the following are equivalent: (i) ; (ii) every -class is contained in some -class; (iii) every -class is a union of -classes.
Solution · Answer
(i)⇒(ii): if then , so . (ii)⇒(i): if , let be an -class containing . Then , and because classes partition , so . (ii)⇒(iii): for an -class and , the -class of lies in the unique -class containing , which is . So . (iii)⇒(ii): the -class of is a union of -classes, one of which contains ; that one must be , again because classes partition . Hence .
Summary
Finite reversible paths construct exactly the equivalence relation forced by a set of identifications. Its classes partition the underlying set. A function passes through the quotient precisely when its output is constant on those classes, and quotienting by its full kernel yields a bijection onto its image. The proofs use set bounds and unique outputs throughout; choosing one representative in every class is a separate issue.