Equivalence relations and partitions

A grouping rule decides which cards belong together

Write 0, 1, 2, 3, 4 and 5 on six cards. Group cards that have the same remainder after division by 3. The groups are {0, 3}, {1, 4} and {2, 5}. Every card has one home. Choosing 3 rather than 0 to name the first group does not change which cards belong to it.

Distinct classes and their names

The quotient as a collection of classes

A/R = {{0, 3}, {1, 4}, {2, 5}}

Now describe the same arrangement as a relation: two cards are related when they belong to the same group. Each card is related to itself. If 0 is related to 3, then 3 is related to 0. If two successive related pairs share a middle card, their outside cards still belong to the same group. These are the three equivalence properties.

A proposed grouping can fail. If a card belongs to two different groups, or a card is missing, it is not this kind of division into separate homes. We will state the conditions precisely, then prove that valid groups and equivalence relations describe the same structure.

Prepare the notation and follow one grouping first

Symbols, definitions and mathematical language supports giving symbols clear meanings and stating the scope of a claim. Variables, expressions and substitution supports reading xRy as a condition on two inputs. Order of operations and arithmetic properties supports the integer differences in the congruence example. Examples, explanations and counterexamples supports checking a claim with a general reason or one permitted failure.

A set A is our collection of allowed objects. The statement a ∈ A means that a is a member of A. The statement B ⊆ A means that every member of the set B belongs to A; B is a subset of A. An element is one object in a set, while a subset is itself a set of allowed objects. The Cartesian product A × A consists of all ordered pairs (x, y) with both entries in A. A relation R on A is a subset of that product; xRy means (x, y) belongs to R. For an equivalence relation we also write x ∼ y. The two earlier set lessons develop these ideas further; the definitions needed here are supplied in this paragraph.

On a first reading, follow the six cards, the three axiom checks and the class calculation. Then follow the partition-to-relation proof. Return to the equal-or-disjoint proof, quotient notation, general congruence proof and empty-domain conventions once you can explain one class and its members.

Every equivalence relation must pass three different checks

Reflexive means xRx for every x ∈ A. Symmetric means that for every x, y ∈ A, xRy implies yRx. Transitive means that for every x, y, z ∈ A, xRy and yRz together imply xRz. R is an equivalence relation on A exactly when all three properties hold.

Is this an equivalence relation?

Yes

These quantifiers range over the stated domain, not just the pairs already listed in R. To check reflexivity, inspect every allowed diagonal pair. To check symmetry, reverse every related pair. To check transitivity, inspect every two-link chain, including chains with repeated objects.

On a finite A, a complete matrix can check every case. A T in row x and column y means xRy; an F means that pair is absent. Loops in the graph correspond to diagonal T entries. Two opposite arrows check a reversed pair, and a path x → y → z requires the direct arrow x → z. Graph distances do not define the relation.

On an infinite domain, checking a finite sample cannot establish an axiom for every allowed input. A proof needs an arbitrary-input argument. One allowed missing diagonal, missing reversal or failed two-link chain is enough to refute its corresponding universal property.

Passing two checks does not supply the third

Use A = {0, 1, 2}. First take R = {1, 2} × {1, 2}. It is symmetric because reversing a pair stays in that square. It is transitive because the outside entries of any two-link chain are still in {1, 2}. It is not reflexive on A: (0, 0) is missing. The same relation would be reflexive if its domain were only {1, 2}.

Next use xRy exactly when x ≤ y on A. It is reflexive and transitive. It is not symmetric: 0 ≤ 1, but 1 ≤ 0 is false. Symmetry is not the same as transitivity.

Finally use xRy exactly when |x − y| ≤ 1 on A. It is reflexive and symmetric. It is not transitive: 0R1 and 1R2, but 0R2 is false because |0 − 2| = 2. Repeated closeness can move outside the permitted distance.

These three examples separately remove one axiom while retaining the other two. Identity, where xRy means x = y, and the universal relation A × A satisfy all three. Their classes are respectively the singleton sets and the single block A when A is nonempty.

A class contains all objects equivalent to its chosen member

For an equivalence relation R on A and a ∈ A, define [a] = {x ∈ A : aRx}. This is an equivalence class, a subset of A. Reflexivity puts a in [a], so every class is nonempty. Symmetry permits the equivalent definition using xRa.

Distinct classes and their names

The quotient as a collection of classes

A/R = {{0, 3}, {1, 4}, {2, 5}}

For the six-card remainder rule, [0] = {0, 3} and [3] = {0, 3}. Also [1] = [4] = {1, 4}, and [2] = [5] = {2, 5}. There are six possible names [a] but only three different classes. Different names do not automatically mean different sets.

The representative a is an element used to name [a]. The class [a] is the whole subset. In this example 0 ∈ [0], but 0 is not the set {0, 3}. Brackets change the kind of object you are describing.

For a relation that fails an equivalence axiom, the set {x ∈ A : aRx} can still be formed, but it need not behave like an equivalence class. Do not use the class-partition theorem until all three axioms have been established.

Classes that share a member must be the same class

First suppose aRb. If x ∈ [a], then aRx. Symmetry gives bRa, and transitivity applied to bRa and aRx gives bRx. Thus x ∈ [b], proving [a] ⊆ [b]. Reversing a and b proves [b] ⊆ [a], so [a] = [b].

Conversely, suppose [a] = [b]. Reflexivity gives a ∈ [a], so a ∈ [b] and hence bRa. Symmetry gives aRb. Therefore aRb if and only if [a] = [b].

If c belongs to both [a] and [b], then aRc and bRc. Symmetry turns bRc into cRb, and transitivity gives aRb. The preceding result then gives [a] = [b]. Consequently any two classes are either equal or have no common member.

This is a statement about distinct classes, not distinct representatives. In the six-card example, 0 ≠ 3 yet [0] = [3]. Those two names denote the same block, so it would be wrong to say their classes are disjoint.

The different classes cover A without overlap

A partition of A is a collection of nonempty subsets of A whose union is A and whose distinct blocks are disjoint. Within a collection of nonempty subsets of A, coverage and disjointness say that each member of A lies in exactly one block. The collection is a set of blocks: writing the same block twice does not create a second block.

Does the proposed family form a partition?

No

The family fails at least one partition condition. Check its induced relation separately: an empty block, for example, adds no pairs and can leave an equivalence relation unchanged.

Does the proposed family form a partition?

No

The family fails at least one partition condition. Check its induced relation separately: an empty block, for example, adds no pairs and can leave an equivalence relation unchanged.

The collection of distinct equivalence classes is a partition. Each class is a nonempty subset of A. Every a ∈ A belongs to [a], so their union covers A. The equal-or-disjoint result proves that distinct classes do not overlap.

For A = {0, 1, 2, 3, 4, 5}, the collection {{0, 3}, {1, 4}, {2, 5}} is a partition. The nested braces matter: its three elements are subsets of A. The card 0 belongs to one of those subsets; it is not itself a block.

A cover alone is not a partition. The blocks {0, 1, 2} and {2, 3, 4, 5} cover A but overlap at 2. A disjoint family alone is not a partition either: {{0, 1}, {2, 3}, {4}} misses 5. An empty block or an outside member also violates the definition.

Sharing a block reconstructs an equivalence relation

Start with a partition Π of A. Define xRy exactly when x and y belong to the same block of Π. We must prove the three axioms, rather than treating the drawing as the proof.

Does the proposed family form a partition?

Yes

The valid partition theorem applies. The induced classes are exactly these blocks.

Is this an equivalence relation?

Yes

Reflexivity: every x ∈ A belongs to a block by coverage. It shares that block with itself, so xRx. Symmetry: if x and y are in one block, then y and x are in that same block, so xRy implies yRx.

Transitivity: suppose x and y lie in block B, and y and z lie in block C. The middle member y belongs to both B and C. Disjointness of distinct blocks forces B = C. Hence x and z lie together, giving xRz.

If a belongs to block B, its reconstructed class is exactly B: every member of B shares that block with a, and no member outside B can share a different block with a. Nonempty blocks ensure each block has such an a. Thus taking classes returns the original partition. Starting with an equivalence relation, taking its classes and then using same-block membership returns the original relation because aRb is equivalent to [a] = [b].

The theorem requires a valid partition. An invalid family need not produce a failed relation: adding an empty block changes no related pairs, although it makes the family invalid. Other failures can break an axiom; overlapping blocks in the earlier example give 0R2 and 2R5 but not 0R5. Check the actual family and the actual induced relation separately.

The quotient is a set of classes, not a set of chosen cards

The quotient set A/R is the collection of distinct equivalence classes: A/R = {[a] : a ∈ A}. For the six-card remainder rule, A/R = {{0, 3}, {1, 4}, {2, 5}}. It has three elements, each of which is a two-card set.

Distinct classes and their names

The quotient as a collection of classes

A/R = {{0, 3}, {1, 4}, {2, 5}}

The selected representatives {0, 1, 2} are a different set. Choosing {3, 4, 5} would name the same three classes. A representative system can help label the quotient, but its integers are not the quotient’s actual elements.

In this example, 0 ∈ A and [0] ∈ A/R. The class [0] is a subset of A, and 0 ∈ [0]. Keep these membership and containment statements separate. Equality of classes is determined by their members, not the spelling of their chosen representative.

Grouping objects supplies the quotient as a set. It does not automatically supply addition, multiplication, an order or a distance on its classes. Any further operation defined using representatives must be checked to give the same result when a different representative of the same class is chosen.

Congruence groups all integers by a fixed positive modulus

Fix an integer m ≥ 1 and use the domain ℤ, the set of all integers. Define x ≡ y (mod m) when m divides x − y. This means x − y = mk for some integer k. Negative differences and negative values of k are allowed.

m = 3; W = {-3, -2, -1, 0, 1, 2, 3, 4, 5}

Complete finite-window remainder certificates

The quotient as a collection of classes

ℤ/≡ = {[0], [1], [2]}

[0] = 0 + 3ℤ; [1] = 1 + 3ℤ; [2] = 2 + 3ℤ

The boxes show intersections of full integer classes with W. Each full class continues infinitely in both directions. The divisibility proof in the article establishes the equivalence axioms on all integers.

Reflexivity follows from x − x = m × 0. For symmetry, x − y = mk implies y − x = m(−k), where −k is an integer. For transitivity, x − y = mk and y − z = mℓ imply x − z = m(k + ℓ), with integer k + ℓ. Thus congruence is an equivalence relation on all of ℤ.

Its class [r] is r + mℤ = {r + mk : k ∈ ℤ}. Integer division gives each x a unique remainder r with 0 ≤ r < m and x = mq + r for integer q. Therefore the m distinct classes are [0], [1], …, [m − 1]. Each is infinite, but the quotient ℤ/≡ has exactly m elements.

For m = 3, −2 ≡ 4 because −2 − 4 = −6 = 3 × (−2). Also [−1] = [2], because −1 = 3 × (−1) + 2. The three classes contain all integers of the forms 3k, 3k + 1 and 3k + 2, not just 0, 1 and 2.

The pictured window W = {−3, −2, −1, 0, 1, 2, 3, 4, 5} shows only intersections [r] ∩ W. It does not display entire integer classes or prove the infinite-domain axioms by enumeration. For m = 1, every integer lies in the sole class ℤ; the quotient has one element. We keep m positive throughout, so no division-by-zero or alternate zero-modulus convention is used.

The empty domain has one relation and one partition

We permit an empty collection of blocks. Under this convention the empty set ∅ has exactly one partition: the empty family ∅. Its union is ∅, and the nonempty-block and disjointness requirements hold because there are no blocks to violate them.

The family {∅} is different. It contains one block, which is empty, so it is not a partition. For a nonempty A, the empty family does not cover A. These statements keep the empty set, an empty family and a family containing an empty block distinct.

There is exactly one relation on ∅: the empty subset of ∅ × ∅. Reflexivity, symmetry and transitivity hold vacuously because there is no permitted input or pair that violates them. There is no a ∈ ∅ from which to form a class, so the quotient is the empty collection of classes. This agrees with the empty partition.

For nonempty A, the identity relation gives the partition into singleton blocks, while A × A gives the one-block partition {A}. When A = ∅, these two relations coincide, and their partition is ∅, not {∅}.

Use the complete finite evidence and state its scope

In Axiom checks, predict which property fails before revealing the complete directed graph, matrix and failure certificate. A missing loop, reversed arrow or two-link shortcut corresponds to a different axiom. The empty-domain case has no invented node or pair.

In Blocks and classes, inspect all four partition conditions. Compare the overlapping, missing-member, empty-block and outside-member cases. The complete induced relation is computed on exactly A; a proposed outside member does not enlarge that domain. Quotient classes appear only when the induced relation is an equivalence relation.

In Integer congruence, choose a positive modulus and compare each window member with its canonical remainder. The table gives x − r and its integer multiple of m, including negative values. The general divisibility argument supplies the claim on all integers; the finite table supplies exact examples.

A complete proof names A and R, establishes each equivalence axiom with its own reason, defines classes, and distinguishes representatives from blocks. A partition proof checks every defining condition. A reconstructed-relation proof uses coverage for reflexivity and the unique block of the middle member for transitivity.

Worked examples

Try it yourself

1. Let R = {1, 2} × {1, 2}. Is R reflexive on {0, 1, 2}? Is it reflexive on {1, 2}? Explain the change.

   Show the answer and reasoning

   No on {0, 1, 2}, because (0, 0) is absent. Yes on {1, 2}, because both required diagonal pairs are present.

   Reflexivity quantifies over every member of the stated domain. A relation’s allowed domain is part of the claim; it cannot be silently reduced to the members appearing in its pairs.

2. On {0, 1, 2}, use xRy exactly when x ≤ y. Which equivalence axiom fails, and which two still hold?

   Show the answer and reasoning

   Symmetry fails at 0R1 without 1R0. Reflexivity and transitivity hold.

   Every x ≤ x. If x ≤ y and y ≤ z, then x ≤ z. Neither fact forces the reverse of an unequal ordered pair.

3. For the six-card remainder rule, are [0] and [3] disjoint? How many distinct classes exist?

   Show the answer and reasoning

   They are equal: [0] = [3] = {0, 3}. There are three distinct classes.

   Different representatives may name the same block. Disjointness applies to distinct classes, which here are {0, 3}, {1, 4} and {2, 5}.

4. For A = {0, 1, 2, 3, 4, 5}, do {0, 1, 2} and {2, 3, 4, 5} form a partition? Show a failed transitivity chain in their induced same-block relation.

   Show the answer and reasoning

   No: they overlap at 2. The induced relation has 0R2 and 2R5 but not 0R5.

   Both blocks cover A, but the middle member 2 has two different homes. No single block contains both 0 and 5, so the required outside pair is missing.

5. On A = {0, 1, 2, 3, 4, 5}, add ∅ to the valid blocks {0, 1, 2} and {3, 4, 5}. Is the family a partition? Does adding ∅ change its same-block relation?

   Show the answer and reasoning

   The family is not a partition because it contains an empty block. The same-block relation is unchanged and is still an equivalence relation.

   An empty block contains no pair of domain members, so it adds no related pair. This is why the partition definition needs nonempty blocks, even though an induced relation may happen to pass all three axioms.

6. For A/R = {{0, 3}, {1, 4}, {2, 5}}, decide whether 0, [0], and {0, 1, 2} are elements of A/R.

   Show the answer and reasoning

   [0] = {0, 3} is an element. The integer 0 and the subset {0, 1, 2} are not elements of this quotient.

   The quotient’s elements are exactly its three listed classes. The representative 0 belongs to A and to [0]; the representative system {0, 1, 2} is a different subset of A.

7. On ℤ with modulus 3, compare −1 and 5. Give their common canonical remainder and an integer divisibility certificate.

   Show the answer and reasoning

   −1 ≡ 5 (mod 3). Their canonical remainder is 2, and −1 − 5 = −6 = 3 × (−2).

   Negative multiples are permitted. The remainder uses 0 ≤ r < 3: −1 = 3 × (−1) + 2 and 5 = 3 × 1 + 2. The full class is 2 + 3ℤ, not just the two checked members.

8. For congruence modulo 1 on ℤ, how many classes exist and what is the sole class? Is its quotient equal to ℤ?

   Show the answer and reasoning

   There is one class, namely ℤ. The quotient is {ℤ}, a one-element set, and is not the set of integers ℤ.

   Every difference of two integers is a multiple of 1. Each integer therefore represents the same entire class. A collection containing ℤ as one element differs from the members of ℤ themselves.

9. Under this lesson’s convention, compare the empty family ∅ and the family {∅} as partitions of ∅. What are the equivalence relation and quotient on ∅?

   Show the answer and reasoning

   The empty family ∅ is the unique partition. The family {∅} is not a partition. The sole relation and its quotient are both ∅.

   There are no blocks in the empty family and no domain members to cover. The family {∅} violates the nonempty-block requirement. All relation axioms on the empty domain hold vacuously, but no class can be named by a domain member.

What to carry forward

• An equivalence relation passes reflexivity, symmetry and transitivity on its exact domain; none of the three checks replaces another.
• A representative belongs to its class. Related representatives name equal classes, and distinct classes are disjoint.
• Nonempty classes cover the domain and form a partition. A valid partition reconstructs its relation by same-block membership.
• A quotient’s elements are classes, not chosen representatives. Congruence with positive modulus m has m distinct integer classes, each containing infinitely many integers.
• With empty families allowed, the empty domain has the empty partition, empty relation and empty quotient; the one-block family {∅} is not a partition.