Concepts and theorems · Intermediate

Equivalence relations: define which objects count as the same

Use integer remainders and approximate comparisons to examine reflexivity, symmetry, transitivity, and equivalence classes.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Equality depends on a stated relation
  2. Check the three properties separately
  3. Group integers by their remainder
  4. Equivalence classes form a partition
  5. Approximate equality can fail transitivity
  6. Define a relation through canonical values
  7. Ask Logeia about this articleCheck your understanding

Equality depends on a stated relation

Two objects can count as the same under one rule and different under another. Exact string equality differs from equality after case normalization. An equivalence relation formalizes a consistent rule for treating members of a specified set as interchangeable. Define that set before checking the rule: behavior on a few familiar inputs does not establish a property for every member. For usernames, Unicode normalization, case handling, and whitespace can all affect the relation. Visual similarity is not automatically an acceptable identity rule. The mathematical properties help describe the chosen rule, but they do not decide which interpretation is appropriate for the product.

Check the three properties separately

Reflexivity requires every element to relate to itself. Symmetry says that if a relates to b, then b relates to a. Transitivity says that if a relates to b and b relates to c, then a relates to c. Check these as three separate claims. A familiar word such as similar does not establish any of them by itself. In particular, self-similarity and mutual similarity do not prove transitivity. Omitting reflexivity can also leave members of the original set without the intended class membership. A complete verification uses arbitrary elements of the domain rather than only selected examples that happen to satisfy the conditions.

Group integers by their remainder

Define a relation on integers by requiring a minus b to be divisible by three. Reflexivity follows because a minus itself is zero. Reversing the subtraction changes only the sign, so symmetry holds. Adding two differences divisible by three produces another such difference, establishing transitivity. Thus one, four, and seven belong together, while two belongs elsewhere. Ordering and numerical magnitude do not define these groups. Negative integers use the same divisibility definition. When implementing the relation, account for the programming language’s remainder convention rather than assuming its raw remainder output always uses the canonical representatives zero, one, and two.

Equivalence classes form a partition

The class of a contains every element related to a. Under an equivalence relation, two classes that share even one member are the same class; separate classes cannot overlap only partially. Congruence modulo three partitions the integers into three classes. A representative can be chosen for each class, but choosing a different representative does not change the underlying relation. Using one or four as the displayed representative is an implementation convention, not a new classification. Distinguish grouping objects from selecting a convenient label for the group. This separation is useful in canonicalization, deduplication, and algorithms that maintain groups of connected or interchangeable objects.

Approximate equality can fail transitivity

Suppose real numbers count as equal when their absolute difference is less than one. Zero relates to 0.6, and 0.6 relates to 1.2, but zero does not relate to 1.2. The rule is reflexive and symmetric but not transitive. Using it directly for deduplication can make groups depend on comparison order. Rounding into fixed bins creates a different relation, but nearby values on opposite sides of a boundary can then fall into different classes. Numerical tolerance and consistent classification are different requirements. Choose the desired behavior explicitly and test the relevant properties instead of assuming that every reasonable similarity rule is an equivalence relation.

Define a relation through canonical values

One way to define an equivalence relation is to choose a deterministic canonicalization function c and relate a and b exactly when c(a)=c(b). Equality of canonical values supplies the three properties. The product requirements still determine whether that canonicalization is appropriate. Changing its rules can change historical classifications, so keep original inputs distinct from canonical keys and plan how a new canonicalization version treats existing records.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 13

Choose a learning path