Refinement of equivalence relations
Partition P refines Q if every block of P sits inside some block of Q — equivalently, the corresponding relations satisfy ∼_P ⊆ ∼_Q. Refinement is a partial order on the set of equivalence relations, with the all-singletons partition at the bottom and the one-block partition at the top, and it makes the equivalence relations on a set into a lattice.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Compare as relationsP refines Q iff every pair related by ∼_P is related by ∼_Q. Set inclusion is the cleanest test.
- Check block containmentEquivalently, each block of P must be a subset of a single block of Q. A block straddling two Q-blocks refutes it.
- Find the meetThe greatest common refinement is the intersection ∼_P ∩ ∼_Q — its blocks are the non-empty intersections of blocks.
- Find the joinThe least common coarsening is the equivalence closure of ∼_P ∪ ∼_Q. The union alone is usually not transitive.
Worked example
On {1,…,6}, does P = {{1,2},{3,4},{5},{6}} refine Q = {{1,2,3,4},{5,6}}? Find their meet.
- {1,2} ⊆ {1,2,3,4} ✓; {3,4} ⊆ {1,2,3,4} ✓; {5} ⊆ {5,6} ✓; {6} ⊆ {5,6} ✓.
- So every P-block lies inside a Q-block, and P refines Q.
- The meet is the intersection of the relations: blocks are non-empty intersections of P-blocks with Q-blocks.
- Those intersections are {1,2}, {3,4}, {5}, {6} — which is P itself.
Answer. Yes, P refines Q, and their meet is P — as it must be whenever P ≤ Q in the refinement order.
Where marks get dropped
These are the specific errors that cost credit on refinement of equivalence relations questions — QED's rubric penalises each of them separately.
- Getting the direction backwards. The finer partition has more, smaller blocks and corresponds to the SMALLER relation.
- Taking the union of relations as the join. The union need not be transitive; the join is its equivalence closure.
- Assuming any two partitions are comparable. Refinement is only a partial order — {{1,2},{3}} and {{1,3},{2}} refine neither the other.
Practise this until it is automatic
Unlimited fresh questions
QED generates new refinement of equivalence relations problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Equivalence Relations mastery is tracked so you know when this is exam-ready.
Refinement of equivalence relations — frequently asked questions
Is the set of equivalence relations a lattice?
Yes, a complete lattice. Every family has a meet (intersection) and a join (equivalence closure of the union), with equality at the bottom and the total relation at the top.
Where does refinement appear in practice?
In automaton minimisation, where states are progressively refined until the partition is stable, and in statistics, where nested factors form a refinement chain.
Why is the join harder than the meet?
Intersection of transitive relations is transitive, so the meet is immediate. Union is not, so the join needs a closure step.
The rest of Equivalence Relations
Equivalence classes, partitions and quotient sets. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Verifying an equivalence relation
- 2Equivalence classes [a]
- 3The class–partition correspondence
- 4The quotient set A/∼
- 5Congruence mod n
- 6The kernel of a function as an equivalence
- 7Well-definedness of operations on classes
- 8Counting equivalence relations
- 9Equivalence closure of a relation
- 10Refinement of equivalence relations
- 11Intersections & unions of equivalence relations
- 12Bell numbers & counting partitions
- 13Isomorphism & similarity as equivalences
Ready to make refinement of equivalence relations exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →