Let A and B be sets with partitions P₁ = {A1,...,An} and P₂ = {B1,...,Bm}, respectively. Prove that P={Ai×Bj | 1≤i≤n, 1≤j≤m} is a partition of the set given by A×B. This is true intuitively, but i don't know how to prove it formally. How should i approach it?