Theorem 6.6: Let M and N be two sets with #(M ) = m and #(N ) = n. Then

#(M x N ) = mn.

Proof: Since #(N ) = n, we can write

N = {a1, . . . , an }

where the ai are all distinct elements. Then

Then by Theorem 2.8, the distributivity of Cartesian products across unions,

Since the ai are all distinct elements, the sets are pairwise disjoint, and

#(M x N ) = #(M x {a1}) + , . . . , + #(M x {an})

By Theorem 5.9,

#(M x {ai}) = #(M ) = m

for all i = 1, 2, . . . , n, and so we get m added to itself n times which by Definition 6.3 is mn