Fundamentals of Computing: Equivalence Relations and Partitions

Lesson overview

Use equivalence relations to group objects by shared properties.

CourseFundamentals of Computing

Topic strandRelations

Assessment styleDigital exam practice

EvidenceWorked answer plus justification

Starter: make the model explicit

Before reading the worked example, write down the objects involved, the claim being made and the notation you expect to use. This prevents the common error of calculating before modelling.

Learning objectives

Identify when a relation is an equivalence relation.
Explain how equivalence classes form a partition.
Apply equivalence reasoning to computing categories.

Learning outcomes

By the end of this lesson, you can identify when a relation is an equivalence relation.
By the end of this lesson, you can explain how equivalence classes form a partition.
By the end of this lesson, you can apply equivalence reasoning to computing categories.

Key vocabulary

What this lesson is about

An equivalence relation is a relation that is reflexive, symmetric and transitive. It groups objects into equivalence classes where objects in the same class are equivalent under the chosen rule.

A partition divides a set into non-overlapping, non-empty groups that cover the whole set. Equivalence relations and partitions are two views of the same structure.

Computing examples must state their assumptions. Grouping files by the same extension is an equivalence relation on filenames; grouping by hash value is useful duplicate evidence only if the risk of collisions is accepted or controlled.

Terms, acronyms and named methods

These are the phrases and named techniques used in this lesson. Read this section before the worked example so the notation and examples have a clear meaning.

Equivalence relationNamed structure. A relation that is reflexive, symmetric and transitive. It formalises when objects count as the same under a chosen property.

Equivalence classPhrase. The set of all objects equivalent to a given object.

PartitionPhrase. A division of a set into non-empty, non-overlapping blocks whose union is the whole set.

ModuloNamed operation. A remainder-based operation. For example, integers are equivalent modulo 3 when they have the same remainder after division by 3.

Hash collisionComputing phrase. A case where two different inputs produce the same hash value. Duplicate-file reasoning using hashes depends on an explicit collision-resistance assumption.

Formal notation and definitions

R is an equivalence relation iff R is reflexive, symmetric and transitive. [a] = {x \in A | xRa}. Equivalence classes form a partition of A.

How to read the symbols

$[a]$ The equivalence class containing a.

$xRa$ x is related to a under relation R.

partitionNon-empty, non-overlapping blocks whose union is the whole set.

Use equivalence-class notation to move from individual related objects to whole groups in a partition.

Degree-level reasoning

Relations are central to databases, graphs, equivalence classes and ordering problems. The same ordered-pair definition supports several computing representations.

Property checks require quantifiers. One missing pair can disprove reflexivity, symmetry or transitivity, but proving the property needs all relevant cases.

Do not stop at a correct-looking answer. State why the method is valid, whether the result depends on a hidden assumption, and what would count as a counterexample.

Worked formal model

This section shows the model, notation, calculation and interpretation as one worked answer. The notation is part of the reasoning, not decoration.

1. Context and objects

Files with the same hash value can be grouped into classes for duplicate-detection reasoning, subject to the assumptions of the hash method.

Objects: the base set A, relation R, equivalence classes [a], and the partition blocks.

Model cue: Use a partition diagram: the universal set is split into non-overlapping blocks, and each block is one equivalence class.

2. Mathematical working

aRb\iff a\equiv b\pmod 3

[1]=\{\ldots,-5,-2,1,4,7,\ldots\}

\mathbb{Z}=[0]\cup[1]\cup[2]\quad\text{and the classes do not overlap}

Hash(a)=Hash(b)\text{ groups files by digest, but identity needs a collision assumption or byte check}

Plain text version

R is an equivalence relation iff R is reflexive, symmetric and transitive.
[a] = {x ∈ A | xRa}.
Equivalence classes form a partition of A.

Worked use: If files are related by having the same extension, then each equivalence class contains files sharing an extension, such as all .txt files. If files are related by having the same hash value, the classes are useful for duplicate detection only when the risk of hash collisions is accepted, controlled or followed by byte-by-byte verification.

3. How to read the working

Read aRb iff a ≡ b mod 3 as the definition of the relation: two integers are related when they have the same remainder after division by 3.
Read [1] as the whole equivalence class of integers related to 1, not just the single number 1.
The union Z = [0] ∪ [1] ∪ [2] says the classes cover all integers.
The classes do not overlap because an integer cannot have two different remainders modulo 3.
For hashes, distinguish the formal equivalence class of equal digest values from the stronger computing claim that the files are identical.

4. Computing meaning and check

Equivalence classes justify grouping. Once the relation is proved reflexive, symmetric and transitive, each object belongs to exactly one class.

Now check: Explain why equivalence classes cannot overlap. Then state the extra assumption needed before treating equal hash values as proof that two files are identical.

Worked example

From scenario to formal reasoning

Scenario: Files with the same hash value can be grouped into classes for duplicate-detection reasoning, subject to the assumptions of the hash method.

Method: Use the definitions and notation introduced above, then state what the result means in this computing scenario.

Reveal model answer

If files are related by having the same extension, then each equivalence class contains files sharing an extension, such as all .txt files. If files are related by having the same hash value, the classes are useful for duplicate detection only when the risk of hash collisions is accepted, controlled or followed by byte-by-byte verification.

Worked solution structure

How a strong answer should be written

Define: State the domain and the objects under discussion. For this lesson, begin from R is an equivalence relation iff R is reflexive, symmetric and transitive.
Apply: Use the relevant definition from relations; do not rely on the diagram, wording or intuition alone.
Check: Test a boundary case, counterexample candidate or representation limit.
Conclude: Write one sentence that connects the formal result back to the computing scenario.

Common misconception

A common mistake is grouping items by a vague similarity. Equivalence requires reflexive, symmetric and transitive behaviour.

Guided practice

For integers modulo 3, list the equivalence classes [0], [1] and [2] using several examples.
Explain why the classes do not overlap and together cover all integers.
Compare grouping files by extension with grouping files by cryptographic hash.
State the extra assumption needed before 'same hash' can be treated as reliable duplicate evidence.

Quick checks

1. Equivalence classes of an equivalence relation must:

overlap whenever objects are similarcontain exactly two objectsbe non-overlapping and cover the whole set

2. Why is 'same hash' not absolute proof of identical files without an assumption?

Hashes cannot be compared.Extensions and hashes are the same thing.Different files can theoretically collide under a hash.

Digital exam practice

Example exam task

Use congruence modulo 3 to show how equivalence classes form a partition. Then discuss why grouping files by same hash needs an assumption about collisions.

Notation toolkit

aRb

Means: a is related to b under relation R

How to use: Use it before testing relation properties.

[a]

Means: the equivalence class containing a

How to use: Use it when grouping all objects equivalent to one representative.

A=\bigcup_i C_i

Means: a set covered by classes

How to use: Use it when explaining how a partition covers the whole domain.

What a good answer is expected to show

A strong answer for this lesson defines the base set A, relation R, equivalence classes [a], and the partition blocks, applies the relations method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

Read aRb iff a ≡ b mod 3 as the definition of the relation: two integers are related when they have the same remainder after division by 3.
Read [1] as the whole equivalence class of integers related to 1, not just the single number 1.
The union Z = [0] ∪ [1] ∪ [2] says the classes cover all integers.
The classes do not overlap because an integer cannot have two different remainders modulo 3.
For hashes, distinguish the formal equivalence class of equal digest values from the stronger computing claim that the files are identical.

Model answer

Reveal model answer

aRb\iff a\equiv b\pmod 3

[a]=\{x\in\mathbb{Z}\mid xRa\}

\mathbb{Z}=[0]\cup[1]\cup[2]\quad\text{with disjoint equivalence classes}

Modulo 3 partitions the integers into [0], [1] and [2], covering all integers without overlap because each integer has exactly one remainder modulo 3. The relation is reflexive, symmetric and transitive. Grouping files by equal hash values is useful duplicate evidence, but hash collisions are possible in principle; treat the result as reliable only under a collision-resistance assumption or after byte-by-byte verification.

Practise next

For integers modulo 3, list the equivalence classes [0], [1] and [2] using several examples.
Explain why the classes do not overlap and together cover all integers.

Self-marking criteria

States reflexive, symmetric and transitive requirements.
Lists or describes the three modulo-3 classes.
Explains non-overlap and coverage.
Connects equivalence classes to partition blocks.
Explains that hash collisions are possible and confirms matches with byte-by-byte verification or an explicit collision-resistance assumption.

Extension

Change one assumption in the worked scenario and decide whether the same method still applies. If it does not, name the exact point where the reasoning breaks.

Study route

Save one clean worked answer from this lesson. Include the problem statement, notation, working, final answer and a short note explaining the computing meaning of the result.

Next lesson: Functions Revisited: Injective, Surjective and Bijective.