1
$\begingroup$

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)-

enter image description here

enter image description here

this is somewhat similar to -

enter image description here

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

enter image description here

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Brian M. Scott Mar 25 '15 at 5:11
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ got it. Thanks! $\endgroup$ – Shaelja Mishra Mar 25 '15 at 5:43
  • $\begingroup$ @Shaelja: You’re welcome! $\endgroup$ – Brian M. Scott Mar 25 '15 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.