equivalence classes and partitions

When an equivalence relation has sorted a collection into 'same-as' groups, each group is called an equivalence class, and the complete carve-up into non-overlapping groups is called a partition. Think of sorting a basket of socks: every sock lands in exactly one pile by colour, no pile is empty, and no sock is in two piles at once. Those piles are the equivalence classes; the whole set of piles is the partition.

Precisely, the equivalence class of an element x, often written [x], is the set of all elements equivalent to x. The class of 4 under 'same remainder mod 3' is [4] = {..., 1, 4, 7, 10, ...}, all the numbers leaving remainder 1. The crucial structural fact is a two-way street: every equivalence relation produces a partition (the set of its classes), and conversely every partition of a set defines an equivalence relation (two things are equivalent exactly when they sit in the same block). The blocks are disjoint and together cover the whole set, so each element belongs to exactly one class.

This is the precise mechanism behind state-merging and the Myhill-Nerode theorem. Group all input strings that lead a hypothetical machine to indistinguishable futures, and each block becomes one state of the minimal DFA; the number of blocks — the index of the language — is the exact state count of the smallest DFA recognizing it, and it is finite precisely when the language is regular. So 'how many classes does this relation have?' becomes 'how much memory does this language fundamentally need?'.