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 ma elementów, a zbiór ma elementów, to liczba różnych par takich, że wynosi [1]
Dowód
Dowód oparty na kombinatoryce
Bardzo prosty dowód tego twierdzenia można przeprowadzić korzystając z reguł kombinatoryki.
Niech i będą skończonymi niepustymi zbiorami. Wybierzmy jeden dowolny element . Zauważmy, że istnieje (zapis ten oznacza moc zbioru ) możliwości wyboru elementu ze zbioru . Dla każdego wybranego istnieje możliwości wyboru elementu ze zbioru . Wybory elementów i są niezależne, więc zgodnie z regułą mnożenia, łączna liczba par wynosi . Zatem możemy stwierdzić, że [2].