Produkt kartezjański - Cartesian product

Iloczyn kartezjański zbiorów i

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

Standardowa talia 52 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

Współrzędne kartezjańskie przykładowych punktów

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:

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

Przykładowe zestawy

A  = { y  ∈   : 1 ≤  y  ≤ 4}, B  = { x  ∈ ℝ : 2 ≤  x  ≤ 5}
i C = { x  ∈ ℝ : 4 ≤  x  ≤ 7}, wykazując
A × ( B C ) = ( A × B ) ( A × C ),
A × ( B C ) = ( A × B ) ∪ ( A × C ) i

A × ( B  \  C ) = ( A × B ) \ ( A × C )
Przykładowe zestawy

A  = { x  ∈ ℝ : 2 ≤  x  ≤ 5}, B  = { x  ∈ ℝ : 3 ≤  x  ≤ 7},
C  = { y  ∈ ℝ : 1 ≤  y  ≤ 3}, D  = { y  ∈ ℝ : 2 ≤  y  ≤ 4}, wykazując

( ∩ B ) x ( CD ) = ( x C ) ∩ ( B x D ).
( AB ) × ( CD ) ≠ ( A × C ) ∪ ( B × D ) można zobaczyć na tym samym przykładzie.

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

Bibliografia

Linki zewnętrzne