partitions form a lattice

Let S be a set. Let Part(S) be the set of all partitionsMathworldPlanetmathPlanetmath on S. Since each partition is a cover of S, Part(S) is partially ordered by coveringPlanetmathPlanetmath refinement relationMathworldPlanetmathPlanetmath, so that P1P2 if for every aP1, there is a bP2 such that ab. We say that a partition P is finer than a partition Q if PQ, and coarser than Q if QP.

Proposition 1.

Part(S) is a complete latticeMathworldPlanetmath


For any set 𝒫 of partitions Pi of S, the intersectionMathworldPlanetmathPlanetmath 𝒫 is a partition of S. Take the meet of Pi to be this intersection. Next, let 𝒬 be the set of those partitions of S such that each Q𝒬 is coarser than each Pi. This set is non-empty because S×S𝒬. Take the meet P of all these partitions which is again coarser than all partitions Pi. Define the join of Pi to be P and the proof is completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. ∎


  • The top element of Part(S) is S×S and the bottom is the diagonal relation on S.

  • Correspondingly, the partition lattice of S also defines the lattice of equivalence relations Δ on S.

  • Given a family {EiiI} of equvialence relations on S, we can explicitly describe the join E:=Ei of Ei, as follows: ab(modE) iff there is a finite sequencePlanetmathPlanetmath a=c1,,cn=b such that

    ckck+1(modEi(k))   for k=1,,n-1. (1)

    It is easy to see this definition makes E an equivalence relationMathworldPlanetmath. To see that E is the supremumMathworldPlanetmathPlanetmath of the Ei, first note that each EiE. Suppose now F is an equivalence relation on S such that EiF and ab(modE). Then we get a finite sequence ck as described by (1) above, so ckck+1(modF) for each k{1,,n-1}. Hence ab(modF) also.

Title partitions form a latticeMathworldPlanetmath
Canonical name PartitionsFormALattice
Date of creation 2013-03-22 16:45:22
Last modified on 2013-03-22 16:45:22
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 6
Author CWoo (3771)
Entry type Derivation
Classification msc 06B20
Defines lattice of equivalence relations