Produkt kartezjański - Cartesian product
W matematyce , zwłaszcza teorii zbiorów , przez iloczyn kartezjański dwóch zestawów A i B , oznaczoną A × B jest zbiorem wszystkich par uporządkowanych ( , b ) , gdzie jest w A i b jest w B . Z punktu widzenia notacji konstruktora zbioru , czyli
Tabelę można utworzyć, biorąc iloczyn kartezjański zestawu wierszy i zestawu kolumn. Jeśli weźmiemy iloczyn kartezjański wiersze × kolumny , komórki tabeli zawierają uporządkowane pary formularza (wartość wiersza, wartość kolumny) .
W podobny sposób można zdefiniować iloczyn kartezjański n zbiorów, znany również jako n- krotny iloczyn kartezjański , który może być reprezentowany przez n- wymiarową tablicę, gdzie każdy element jest n - krotką . Uporządkowana para to 2-krotka lub para . Bardziej ogólnie, można zdefiniować iloczyn kartezjański indeksowanej rodziny zbiorów.
Produkt kartezjański nosi imię René Descartes'a , którego sformułowanie geometrii analitycznej dało początek koncepcji, która jest dalej uogólniana w kategoriach produktu bezpośredniego .
Przykłady
Talia kart
Ilustracyjnym przykładem jest standardowa talia 52 kart . W standardowych kart do gry szeregi {a, k, q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2}, tworząc zestaw 13 elementów. Karty w kolorach {♠, ♥ , ♦ , ♣} tworzą czteroelementowy zestaw. Iloczyn kartezjański tych zestawów zwraca 52-elementowy zestaw składający się z 52 uporządkowanych par , które odpowiadają wszystkim 52 możliwym kartom do gry.
Rangi × Garnitury zwraca zbiór postaci {(A, ♠), (A, ♥ ), (A, ♦ ), (A, ♣), (K, ♠), …, (3, ♣), (2 , ), (2, ♥ ), (2, ♦ ), (2, ♣)}.
Suits × Ranks zwraca zbiór postaci {(♠, A), (♠, K), (♠, Q), (♠, J), (♠, 10), …, (♣, 6), (♣ , 5), (♣, 4), (♣, 3), (♣, 2)}.
Te dwa zestawy są różne, a nawet rozłączne .
Dwuwymiarowy układ współrzędnych
Głównym przykładem historycznym jest płaszczyzna kartezjańska w geometrii analitycznej . W celu przedstawienia figur geometrycznych w sposób liczbowy i wydobycia informacji liczbowych z ich reprezentacji liczbowych, René Descartes przypisał każdemu punktowi na płaszczyźnie parę liczb rzeczywistych , zwaną jego współrzędnymi . Zwykle pierwszy i drugi składnik takiej pary nazywa się odpowiednio współrzędnymi x i y (patrz rysunek). Zbiór wszystkich takich par (tj. iloczyn kartezjański ℝ×ℝ , gdzie ℝ oznacza liczby rzeczywiste) jest zatem przypisany do zbioru wszystkich punktów na płaszczyźnie.
Najpopularniejsza implementacja (teoria mnogości)
Formalna definicja iloczynu kartezjańskiego z zasad teorii mnogości wynika z definicji pary uporządkowanej . Najpopularniejsza definicja par uporządkowanych, definicja Kuratowskiego , to . Zgodnie z tą definicją, jest elementem i jest podzbiorem tego zbioru, gdzie reprezentuje operator zbioru potęgowego . Dlatego istnienie iloczynu kartezjańskiego dowolnych dwóch zbiorów w ZFC wynika z aksjomatów parowania , sumy , zbioru potęgowego i specyfikacji . Ponieważ funkcje są zwykle definiowane jako szczególny przypadek relacji , a relacje są zwykle definiowane jako podzbiory iloczynu kartezjańskiego, definicja dwuzbiorowego iloczynu kartezjańskiego jest z konieczności poprzedzająca większość innych definicji.
Nieprzemienność i brak asocjacji
Niech A , B , C i D będą zbiorami.
Iloczyn kartezjański A × B nie jest przemienny ,
ponieważ uporządkowane pary są odwrócone, chyba że spełniony jest co najmniej jeden z następujących warunków:
- A jest równe B , lub
- A lub B to zestaw pusty .
Na przykład:
-
A = {1,2}; B = {3,4}
- A × B = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}
- B × A = {3,4} × {1,2} = {(3,1), (3,2), (4,1), (4,2)}
-
A = B = {1,2}
- A × B = B × A = {1,2} × {1,2} = {(1,1), (1,2), (2,1), (2,2)}
-
A = {1,2}; B =
- A × B = {1,2} × ∅ = ∅
- B × A = ∅ × {1,2} = ∅
Ściśle mówiąc, iloczyn kartezjański nie jest asocjacyjny (chyba że jeden z zaangażowanych zbiorów jest pusty).
Jeśli na przykład A = {1}, wtedy ( A × A ) × A = {((1, 1), 1)} ≠ {(1, (1, 1))} = A × ( A × A ) .
Skrzyżowania, sumy i podzbiory
Iloczyn kartezjański spełnia następującą właściwość w odniesieniu do przecięć (patrz środkowy rysunek).
W większości przypadków powyższe stwierdzenie nie jest prawdziwe, jeśli zastąpimy przecięcie sumą (patrz rysunek najbardziej po prawej).
W rzeczywistości mamy to:
Dla ustawionej różnicy mamy również następującą tożsamość:
Oto kilka zasad demonstrujących rozdzielność z innymi operatorami (patrz rysunek po lewej stronie):
gdzie oznacza absolutną dopełniacza z A .
Inne właściwości związane z podzbiorami to:
Kardynalność
Liczność zbioru jest liczba elementów zbioru. Na przykład zdefiniowanie dwóch zbiorów: A = {a, b} i B = {5, 6}. Zarówno zestaw A, jak i zestaw B składają się z dwóch elementów. Ich iloczyn kartezjański, zapisany jako A × B , daje w wyniku nowy zestaw zawierający następujące elementy:
- A × B = {(a,5), (a,6), (b,5), (b,6)}.
gdzie każdy element A jest sparowany z każdym elementem B i gdzie każda para stanowi jeden element zestawu danych wyjściowych. Liczba wartości w każdym elemencie zbioru wynikowego jest równa liczbie zbiorów, których iloczyn kartezjański jest brany; 2 w tym przypadku. Liczność zbioru wyjściowego jest równa iloczynowi liczności wszystkich zbiorów wejściowych. To znaczy,
- | A × B | = | | · | B |.
W tym przypadku | A × B | = 4
podobnie
- | A × B × C | = | | · | B | · | C |
i tak dalej.
Zbiór A × B jest nieskończony, jeśli A lub B jest nieskończony, a drugi zbiór nie jest zbiorem pustym.
Produkty kartezjańskie kilku zestawów
n- arny iloczyn kartezjański
Iloczyn kartezjański można uogólnić na n- arny iloczyn kartezjański na n zbiorach X 1 , ..., X n jako zbiór
z n -tuples . Jeśli krotki są zdefiniowane jako pary uporządkowane zagnieżdżone , można je zidentyfikować za pomocą ( X 1 × ⋯ × X n −1 ) × X n . Jeśli krotka jest zdefiniowana jako funkcja na {1, 2, …, n } , której wartość w i jest i- tym elementem krotki, to iloczyn kartezjański X 1 × ⋯ × X n jest zbiorem funkcji
n -ary potęga kartezjańska
Kartezjański kwadrat o zadanej X jest iloczyn X 2 = X x X . Przykładem jest dwuwymiarowa płaszczyzna R 2 = R × R gdzie R jest zbiorem liczb rzeczywistych : R 2 jest zbiorem wszystkich punktów ( x , y ) gdzie x i y są liczbami rzeczywistymi (patrz kartezjański układ współrzędnych ) .
N -ary kartezjański mocy o zadanej X , oznaczony , może być zdefiniowany jako
Przykładem tego jest R 3 = R × R × R , gdzie R ponownie jest zbiorem liczb rzeczywistych, a ogólniej R n .
N -ary kartezjański moc zbioru X jest izomorficzny w przestrzeni funkcji z n -elementowe zestawu do X . W szczególnym przypadku, 0-arna potęga kartezjańska X może być traktowana jako zbiór singletonów , odpowiadający pustej funkcji o kodziedzinie X .
Nieskończone produkty kartezjańskie
Możliwe jest zdefiniowanie iloczynu kartezjańskiego dowolnej (ewentualnie nieskończonej ) indeksowanej rodziny zbiorów. Jeśli I jest dowolnym zbiorem indeksowym i jest rodziną zbiorów indeksowanych przez I , to iloczyn kartezjański zbiorów w jest zdefiniowany jako
to znaczy zbiór wszystkich funkcji zdefiniowanych w zbiorze indeksów tak, że wartość funkcji pod określonym indeksem i jest elementem X i . Nawet jeśli każdy z X i jest niepusty, iloczyn kartezjański może być pusty, jeśli aksjomat wyboru , który jest równoważny stwierdzeniu, że każdy taki iloczyn jest niepusty, nie zostanie założony.
Dla każdego j w I funkcja
zdefiniowana przez nazywana jest j- tą mapą projekcyjną .
Potęga kartezjańska jest iloczynem kartezjańskim, w którym wszystkie czynniki X i są tym samym zbiorem X . W tym przypadku,
jest zbiorem wszystkich funkcji od I do X i jest często oznaczany jako X I . Ten przypadek jest ważny w badaniu potęgowania kardynalnego . Ważnym szczególny przypadek, gdy zestaw indeks jest , że liczby naturalne : Ten iloczyn jest zbiorem wszystkich nieskończonych sekwencji z I th określenie w odpowiedni zestaw X I . Na przykład każdy element
może być wizualizowany jako wektor z niezliczonymi nieskończonymi składowymi liczb rzeczywistych. Ten zestaw jest często oznaczany , lub .
Inne formy
Skrócona forma
Jeśli mnoży się kilka zbiorów (np. X 1 , X 2 , X 3 , …), to niektórzy autorzy wybierają skrót iloczynu kartezjańskiego po prostu jako × X i .
Iloczyn kartezjański funkcji
Jeśli f jest funkcją od A do B , a g jest funkcją od X do Y , to ich iloczyn kartezjański f × g jest funkcją od A × X do B × Y z
Można to rozszerzyć na krotki i nieskończone kolekcje funkcji. Różni się to od standardowego iloczynu kartezjańskiego funkcji rozpatrywanych jako zbiory.
Cylinder
Niech będzie zestaw i . Następnie cylinder od względem jest iloczyn z i .
Zwykle jest uważany za uniwersum kontekstu i jest pomijany. Na przykład, jeśli jest podzbiorem liczb naturalnych , to cylinder jest .
Definicje poza teorią mnogości
Teoria kategorii
Chociaż iloczyn kartezjański jest tradycyjnie stosowany do zbiorów, teoria kategorii zapewnia bardziej ogólną interpretację iloczynu struktur matematycznych. Różni się to, chociaż jest związane z pojęciem kwadratu kartezjańskiego w teorii kategorii, które jest uogólnieniem produktu włóknistego .
Potęgowanie jest właściwym sprzężeniem iloczynu kartezjańskiego; zatem każda kategoria z iloczynem kartezjańskim (i końcowym obiektem ) jest kartezjańską kategorią zamkniętą .
Teoria grafów
W teorii wykres The iloczyn dwóch wykresach G i H jest Wykres oznaczony jako G x H , którego wierzchołek zestaw jest (zwykła), iloczyn V ( G ) x V ( H ) oraz tak, że dwa wierzchołki ( U , V ) i ( U ', V ') przylega w G x H , wtedy i tylko wtedy, gdy u = U " i V sąsiaduje z v " w H , lub v = v ' , a u sąsiaduje z U ' w G . Iloczyn kartezjański grafów nie jest iloczynem w sensie teorii kategorii. Zamiast tego iloczyn kategoryczny jest znany jako iloczyn tensorowy grafów .
Zobacz też
- Relacja binarna
- Łączenie zestawów ciągów
- Współprodukt
- Produkt krzyżowy
- Iloczyn bezpośredni grup
- Pusty produkt
- Przestrzeń euklidesowa
- Obiekt wykładniczy
- Relacja skończona
- Łączenie (SQL) § Łączenie krzyżowe
- Zamówienia na produkt kartezjański kompletnie zamówionych zestawów
- Aksjomat zbioru potęgowego (do udowodnienia istnienia iloczynu kartezjańskiego)
- Produkt (teoria kategorii)
- Topologia produktu
- Rodzaj produktu
- Ultraprodukt