# cardinality of cartesian product of m sets

I was proving that the cardinality of Cartesian product of m(m>1) non-empty finite sets is the product of cardinalities of the m sets. it can be easily proved using the fundamental principle of counting(rule of product)-

this is somewhat similar to -

But I felt the need of proving one more point in order to complete the proof of the above stated theorem- "Each and every ordered n-tuple so formed is unique." If it hadn't been so, the cardinality of the Cartesian product(which itself is a set),may be less than product of cardinalities of individual sets {since duplicate elements are not mentioned in a set}

I am able to understand it by intuition, but am not able to prove it in formal language. please help.

p.s. consider the Cartesian product of 2 sets

• The notion of ordered $n$-tuple is defined to make that true: $\langle a_1,\ldots,a_n\rangle=\langle b_1,\ldots,b_n\rangle$ if and only if $a_k=b_k$ for $k=1,\ldots,n$. There are actually two or three different formal definitions of the notion, but they all (by design) have this property: it’s the reason for defining such things in the first place. If you want to see a proof from the definition, we’d have to pick one of the definitions and work from there. Is that what you’re after? – Brian M. Scott Mar 25 '15 at 5:11

When we enumerate $P$ as $\{x_1,\ldots,x_m\}$ and $Q$ as $\{y_1,\ldots,y_n\}$, it’s tacitly understood that the elements $x_1,\ldots,x_m$ are distinct, and the elements $y_1,\ldots,y_n$ are distinct. (Of course any of the $x_i$ may be equal to any of the $y_i$.) Suppose that $\langle x_i,y_j\rangle=\langle x_k,y_\ell\rangle$. Then by the definition of ordered pair we know that $x_i=x_k$ and $y_j=y_\ell$, and therefore $i=k$ and $j=\ell$. Thus, all $mn$ ordered pairs are distinct.