PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (22)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] partitions form a lattice (Derivation)

Let $ S$ be a set. Let $ \operatorname{Part}(S)$ be the set of all partitions on $ S$. Since each partition is a cover of $ S$, $ \operatorname{Part}(S)$ is partially ordered by covering refinement relation, so that $ P_1\preceq P_2$ if for every $ a\in P_1$, there is a $ b\in P_2$ such that $ a\subseteq b$. We say that a partition $ P$ is finer than a partition $ Q$ if $ P\preceq Q$, and coarser than $ Q$ if $ Q\preceq P$.

Proposition 1   $ \operatorname{Part}(S)$ is a complete lattice
Proof. For any set $ \mathcal{P}$ of partitions $ P_i$ of $ S$, the intersection $ \bigcap \mathcal{P}$ is a partition of $ S$. Take the meet of $ P_i$ to be this intersection. Next, let $ \mathcal{Q}$ be the set of those partitions of $ S$ such that each $ Q\in \mathcal{Q}$ is coarser than each $ P_i$. This set is non-empty because $ S\times S\in \mathcal{Q}$. Take the meet $ P'$ of all these partitions which is again coarser than all partitions $ P_i$. Define the join of $ P_i$ to be $ P'$ and the proof is complete. $ \qedsymbol$

Remarks.

  • The top element of $ \operatorname{Part}(S)$ is $ S\times S$ and the bottom is the diagonal relation on $ S$.
  • Correspondingly, the partition lattice of $ S$ also defines the lattice of equivalence relations $ \Delta$ on $ S$.
  • Given a family $ \lbrace E_i\mid i\in I\rbrace$ of equvialence relations on $ S$, we can explicitly describe the join $ E:=\bigvee E_i$ of $ E_i$, as follows: $ a\equiv b\pmod E$ iff there is a finite sequence $ a=c_1,\ldots,c_n=b$ such that
    $\displaystyle c_k\equiv c_{k+1} \pmod {E_{i(k)}}$    for $\displaystyle k=1,\ldots,n-1.$     (1)

    It is easy to see this definition makes $ E$ an equivalence relation. To see that $ E$ is the supremum of the $ E_i$, first note that each $ E_i\le E$. Suppose now $ F$ is an equivalence relation on $ S$ such that $ E_i\le F$ and $ a\equiv b\pmod E$. Then we get a finite sequence $ c_k$ as described by (1) above, so $ c_k\equiv c_{k+1}\pmod F$ for each $ k\in \lbrace 1,\ldots,n-1\rbrace$. Hence $ a\equiv b\pmod F$ also.



"partitions form a lattice" is owned by CWoo.
(view preamble | get metadata)

View style:

Also defines:  lattice of equivalence relations

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: supremum, equivalence relation, easy to see, finite sequence, iff, partition lattice, diagonal relation, bottom, top, complete, proof, join, meet, intersection, complete lattice, coarser, finer, relation, refinement, covering, cover, partitions
There are 2 references to this entry.

This is version 3 of partitions form a lattice, born on 2007-02-24, modified 2007-05-19.
Object id is 8982, canonical name is PartitionsFormALattice.
Accessed 1101 times total.

Classification:
AMS MSC: 06B20 (Order, lattices, ordered algebraic structures :: Lattices :: Varieties of lattices)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)