Why grouping objects requires a proof
Suppose a program stores words but an operation only needs their lengths. Keeping every letter records information the operation will never use. We might replace all words of length three by one object, all words of length four by another, and so on. A later operation can act on these groups only if words in the same group always produce the same answer.
There are two separate questions here. Does the proposed rule really divide the original set into nonoverlapping groups? Does the operation respect those groups? Equivalence relations answer the first question; the requirement that a formula be well defined answers the second. Neither question is settled by writing square brackets around an object.
Relations and their different properties
Definition 1.2.1
(Binary relations on a set)
A binary relation on a set is a subset , where is the set of ordered pairs of elements of . Write when . The relation is:
- reflexive if for every ;
- symmetric if implies for every ;
- antisymmetric if and together imply ;
- transitive if and together imply for every .
An equivalence relation is a reflexive, symmetric and transitive relation.
Each property has its own quantifiers. To disprove transitivity, find three elements for which both antecedent pairs belong to the relation but the conclusion pair does not. A missing conclusion pair alone proves nothing if one of the required antecedents also fails.
Common mistake
(Antisymmetric is not the opposite of symmetric)
Symmetry and antisymmetry are not logical negations. Equality has both properties: reversing an equality is valid, and two elements related in both directions are equal. The usual order on integers is antisymmetric and transitive but not symmetric. An equivalence relation generally fails antisymmetry because its purpose is to allow different elements to count as equivalent.
Worked example 1.2.2
(Closeness does not necessarily define a group)
On define when . The relation is reflexive and symmetric. It is not transitive: and , but is false. The sets of elements related to and are and , which overlap without being equal. Thus a rule that looks like similarity need not divide a set into classes.
Equivalence classes and partitions
Definition 1.2.3
(Classes and quotient sets)
Let be an equivalence relation on . The class of is
The quotient set is the set of distinct classes. Its elements are subsets of , rather than the individual elements of . The quotient map sends to .
A partition of is a collection of nonempty, pairwise disjoint subsets whose union is . The empty collection is the partition of the empty set. A class representative is an element chosen from a class; the class is the whole subset, not the chosen representative.
Theorem 1.2.4
(Equivalence relations and partitions describe the same grouping)
For an equivalence relation on ,
Its distinct classes form a partition of . Conversely, every partition defines an equivalence relation by declaring two elements equivalent exactly when they lie in the same block. These two constructions undo each other.
Proof
(Classes from the relation, the relation from blocks)
Suppose . If , then and , so transitivity gives . Thus . Symmetry gives and the reverse inclusion. If , reflexivity gives , hence .
Every class is nonempty because , and every element belongs to its own class. If two classes have a common element , then and . Symmetry and transitivity give , so the two classes are equal. Therefore distinct classes are disjoint and together cover .
Conversely, given a partition, each element lies in exactly one block. It shares that block with itself, sharing a block is symmetric, and if share a block and share a block, the two blocks must be equal because both contain . Hence share a block. These are the three equivalence axioms. The class of an element is precisely its original block, proving that the constructions are inverse. The empty-set case satisfies all statements vacuously.
Proof X-ray
Why one common element forces equal classes
The key step is stronger than saying that every element has a class. Given a point in an intersection, symmetry lets us turn toward one representative and transitivity lets us travel to the other. This proves that the representatives are equivalent, after which every member of either class belongs to the other. Without transitivity, the overlapping sets in the closeness example remain possible.
Worked example 1.2.5
(Remainders group infinitely many integers into finitely many classes)
Fix an integer and define when divides . Since , reflexivity holds. Negating a divisible difference proves symmetry; adding two divisible differences proves transitivity.
Write for the class of . The division algorithm gives exactly one remainder in for each integer. Integers have the same remainder exactly when their difference is divisible by . Thus the quotient, denoted , has exactly elements. For example, , even though are different integers. Each class is infinite; the set of classes is finite.
Common mistake
(A class is a set, not its representative)
From one may not conclude : the two classes are the same subset of , because . Equality of classes is decided by the relation, exactly when , never by comparing the chosen representatives. Nor does choosing the representative make the class small: is infinite.
Combining grouping rules carefully
The intersection of two equivalence relations on the same set is an equivalence relation. Indeed, equality with oneself holds in both, reversing a pair works in both, and a two-step implication can be applied separately in both. This intersection groups objects only when both original tests agree. For integers, requiring the same remainder modulo two and modulo three is equivalent to requiring the same remainder modulo six.
Counterexample mode
A union of equivalence relations need not be one
Claim: the union of two equivalence relations on the same set is an equivalence relation. On let the first partition have blocks and the second have blocks . In the union relation, is related to through the first relation and to through the second, but belongs to neither, so the union fails transitivity. Reflexivity and symmetry do survive a union, since each is checked pair by pair. The repair is to pass to the equivalence relation generated by the union, described next, which here merges all three elements.
If we really want the smallest equivalence relation containing a collection of declared pairs, declare two elements equivalent when a finite chain of declared pairs, traversed in either direction, joins them. Allow a chain of length zero. This rule is reflexive by the zero-step chain, symmetric by reversing a chain, and transitive by concatenating chains. Any equivalence relation containing the declared pairs must contain every such chain's endpoints, so this construction is the smallest one. In the example, it merges all three elements. Requiring both rules and allowing either rule therefore produce different groupings.
Functions, fibers and loss of information
A function assigns exactly one element to each . Its image is . For , its fiber is ; this notation means inverse image and does not require an inverse function. A fiber outside the image is empty and is not a partition block.
The function is injective if implies , and surjective if every has a preimage. A bijection has both properties. These definitions distinguish the domain, the stated codomain and the actual image.
Theorem 1.2.6
(Every function identifies exactly its nonempty fibers)
For , define if . This is an equivalence relation, and its classes are precisely the nonempty fibers. The function
is a bijection. In particular, is injective exactly when all its classes are singletons.
Proof
(Fibers are the classes)
Reflexivity, symmetry and transitivity follow from the corresponding properties of equality in . By definition, the class of consists exactly of inputs with value , which is the fiber over .
Before checking injectivity or surjectivity of , check that it is a function: if , then , so . The output is independent of the representative. Every element of has the form , proving surjectivity. If two classes have the same output, their representatives have equal -values and are equivalent, so the classes are equal. This proves injectivity. Finally, a fiber contains no two different inputs exactly when is injective.
Worked example 1.2.7
(A finite map, its classes and its codomain)
Let , , and specify
The nonempty fibers are . There are three classes, and matches them with . The fiber over is empty. Therefore the induced map to the image is a bijection, but the original map to is not surjective. There is also no common class size: dividing six inputs by the size of the first class would not justify a class count.
When an operation can act on classes
Now fix an equivalence relation on , independently of a function . We want to retain only the class while still computing . This is possible exactly when the information discarded by grouping is irrelevant to .
Theorem 1.2.8
(The representative-independence criterion)
There is a function satisfying , where , if and only if
If it exists, is unique and is given by .
Proof
(Defining a function through representatives)
If and , then , so applying gives . Conversely, suppose the implication holds. To define on a class, take any representative and use . Any other representative is equivalent to and therefore gives the same value. This defines a function with . For uniqueness, every class is for some , and any proposed function satisfying the equation must send it to . No finite-set hypothesis is needed.
For example, word length is constant on anagram classes, so it defines a function on those classes. It is not injective: the anagram classes of ab and aa are different, but both have length two. On nonempty words, taking the first letter defines an ordinary function, but it fails to define a function on anagram classes, since ab and ba are equivalent but have different first letters.
If the output is also an equivalence class
Suppose is an equivalence relation on and is an ordinary function. The proposed rule
is well defined exactly when implies . To prove this, apply the preceding criterion to the function . The required outputs are classes, so they must be equal as classes; their representatives need only be equivalent. Requiring would be stronger than necessary.
Worked example 1.2.9
(A complete test for an arithmetic formula on classes)
Let and . Consider
This rule is well defined if and only if divides . Necessity follows by using the two representatives and of the same input: the outputs and agree only if . For sufficiency, if , then , which is divisible by under that hypothesis.
Thus is valid because . Its outputs on are respectively , so it is neither injective nor surjective. The rule is invalid: and describe the same input but give different output classes. A finite list using only the representatives could define some function, but it would not validate the asserted formula for every representative.
Practice
Quick check
(On , declare when is even. List the classes and count the ordered pairs in the relation.)
Count all pairs within each block, including diagonal pairs.
Solution · Answer
The classes are and . The relation is , a disjoint union. It has ordered pairs. Counting only distinct unordered pairs would omit the diagonal and identify a pair with its reverse, so it would count a different object.
Quick check
(Prove that a relation on is both an equivalence relation and a partial order if and only if it is equality on .)
A partial order is reflexive, antisymmetric and transitive. Use the extra symmetry of an equivalence relation.
Solution · Answer
If , symmetry gives ; antisymmetry then gives . Hence contains no pairs other than equality pairs. Reflexivity supplies every equality pair, so . Conversely equality is reflexive, symmetric, antisymmetric and transitive, so it has both required structures. This also covers .
Quick check
(Let have blocks and . A function sends to red and to blue. Prove that it descends to the quotient. Does the function that sends only to red and all other inputs to blue descend?)
For a failed rule, give two representatives of one input class with different outputs.
Solution · Answer
The first function is constant on each block, so it induces the function sending the class to red and to blue. The criterion proves existence, and surjectivity of the quotient map proves uniqueness. For the second rule, but the proposed outputs are red and blue. It therefore does not descend, even though it is a valid ordinary function on the original four-element set.
Quick check
(Find every integer for which the rule is well defined. For , determine its image and the size of each nonempty fiber on the quotient.)
The domain has six classes and the codomain has eight. Check representative independence before counting outputs.
Solution
The condition is , equivalently , equivalently . For the last implication, and give . Conversely a multiple of four clearly makes a multiple of eight.
For , the even domain classes map to , and the odd classes map to . Thus the image has two elements and each nonempty fiber consists of three domain classes. The six other codomain classes have empty fibers. Parity is independent of the representative modulo six, as the validity proof also guarantees.
Quick check
(Let and be equivalence relations on . Prove that the classes of their intersection are precisely the nonempty intersections of an -class with an -class. State the answer when is empty.)
First identify the class of an individual element for the intersection relation.
Solution
Let . It is an equivalence relation, and for each ,
This intersection is nonempty because it contains . Conversely, if an -class and an -class have nonempty intersection, choose . The class theorem gives and , so . Hence these are exactly the classes. For the empty set, all three partitions are the empty collection and there are no nonempty intersections.
Connections and limits
The partition-counting notes count the blocks produced by this construction; automata group prefixes that admit the same future behavior; strongly connected components group vertices by mutual reachability. Each application must prove its own equivalence and compatibility conditions. Here we have established the common set-theoretic foundation, without claiming a full treatment of automata minimization, graph algorithms or algebraic quotient structures.