Let Pn denote the set of all partitions of the set {1, 2, . . . , n}. Given two

partitions π and σ in Pn define π ≤ σ provided each part of π is contained in a part of

σ. Thus, the partition π can be obtained by partitioning the parts of σ. This relation

is usually expressed by saying that π is a refinement of σ.

(a) Prove that this relation is a partial order on Pn.

(b) Construct the Hasse diagram of (Pn,≤) for n = 1, 2,3 and 4.