Twierdzenie o mnożeniu

Twierdzenie o mnożeniu – twierdzenie matematyczne dotyczące iloczynu kartezjańskiego zbiorów skończonych:

Jeżeli zbiór $A$ ma $m$ elementów, a zbiór $B$ ma $n$ elementów, to liczba różnych par $(x,y)$ takich, że $x\in A,y\in B$ wynosi $mn.$

Dowód

Dowód oparty na kombinatoryce

Bardzo prosty dowód tego twierdzenia można przeprowadzić korzystając z reguł kombinatoryki.

Niech $A$ i $B$ będą skończonymi niepustymi zbiorami. Wybierzmy jeden dowolny element $a\in A$. Zauważmy, że istnieje $|A|$ (zapis ten oznacza moc zbioru $A$) możliwości wyboru elementu $a$ ze zbioru $A$. Dla każdego wybranego $a$ istnieje $|B|$ możliwości wyboru elementu $b$ ze zbioru $B$. Wybory elementów $a$ i $b$ są niezależne, więc zgodnie z regułą mnożenia, łączna liczba par $(a,b)$ wynosi $|A|\cdot |B|$ . Zatem możemy stwierdzić, że $|A\times B|=|A|\cdot |B|$.