Twierdzenie o mnożeniu

Ten artykuł od 2022-04 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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

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

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

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