Kartézský součin - Cartesian product

V matematiky , konkrétně teorie množin , z kartézského součinu dvou množin A a B , označený A  ×  B , je množina všech uspořádaných dvojic ( , b ), kde je v A a b je v B . Pokud jde o notaci set-builderu , to je

${\ Displaystyle A \ times B = \ {(a, b) \ mid a \ in A \ {\ mbox {and}} \ b \ in B \}.}$

Tabulku lze vytvořit odebráním karteziánského součinu sady řádků a sady sloupců. Pokud se vezme kartézský součin řádků × sloupců , buňky tabulky obsahují uspořádané páry formuláře (hodnota řádku, hodnota sloupce) .

Jeden může podobně definovat kartézský produkt n sad, také známý jako N -násobnou kartézského produktu , který může být vyjádřen pomocí N rozměrné pole, kde každý prvek je n - n-tice . Objednaný pár je 2-tice nebo pár . Ještě obecněji lze definovat karteziánský součin indexované rodiny množin.

Kartézský produkt je pojmenován po Reném Descartesovi , jehož formulace analytické geometrie dala vznik konceptu, který je dále zobecněn z hlediska přímého produktu .

Příklady

Balíček karet

Názorným příkladem je standardní balíček 52 karet . Tyto standardní hrací karta řady {A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2} tvoří 13-prvek nastaven na. Karetní obleky {♠, ♥ , ♦ , ♣} tvoří čtyřprvkovou sadu. Kartézský součin těchto sad vrací 52prvkovou sadu skládající se z 52 uspořádaných párů , které odpovídají všem 52 možným hracím kartám.

Hodnosti × Obleky vrací sadu formulářů {(A, ♠), (A,  ♥ ), (A,  ♦ ), (A, ♣), (K, ♠),…, (3, ♣), (2 (♠), (2,  ♥ ), (2,  ♦ ), (2, ♣)}.

Obleky × Hodnosti vrací sadu formulářů {(♠, A), (♠, K), (♠, Q), (♠, J), (♠, 10),…, (♣, 6), (♣ , 5), (♣, 4), (♣, 3), (♣, 2)}.

Tyto dvě sady jsou odlišné, dokonce nesouvislé .

Dvourozměrný souřadnicový systém

Hlavním historickým příkladem je karteziánská rovina v analytické geometrii . Aby mohl René Descartes reprezentovat geometrické tvary numerickým způsobem a extrahovat číselné informace z numerických reprezentací tvarů, přiřadil každému bodu v rovině dvojici skutečných čísel , které se nazývají jeho souřadnice . Obvykle se první a druhé složce takové dvojice říká její souřadnice x a y (viz obrázek). Množina všech takových dvojic (tj. Karteziánský součin ℝ × ℝ , kde ℝ označuje reálná čísla) je tedy přiřazena množině všech bodů v rovině.

Nejběžnější implementace (teorie množin)

Formální definice karteziánského produktu z množiny teoretických principů vyplývá z definice uspořádané dvojice . Mezi nejčastější definice uspořádaných dvojic, definice Kuratowského je . Pod touto definicí je prvek a je podmnožinou této sady, kde představuje operátor energetické sady . Existence karteziánského produktu jakýchkoli dvou sad v ZFC tedy vyplývá z axiomů párování , sjednocení , výkonové sady a specifikace . Protože funkce jsou obvykle definovány jako zvláštní případ relací a vztahy jsou obvykle definovány jako podmnožiny karteziánského součinu, je definice dvousetového karteziánského součinu nutně před většinou ostatních definic. ${\ Displaystyle (x, y) = \ {\ {x \}, \ {x, y \} \}}$${\ displaystyle (x, y)}$${\ displaystyle {\ mathcal {P}} ({\ mathcal {P}} (X \ cup Y))}$${\ displaystyle X \ times Y}$${\ displaystyle {\ mathcal {P}}}$

Nekomutativita a neasociativita

Nechť A , B , C a D jsou množiny.

Kartézský součin A × B není komutativní ,

${\ displaystyle A \ times B \ neq B \ times A,}$

protože seřazené páry jsou obráceny, pokud není splněna alespoň jedna z následujících podmínek:

• A se rovná B , nebo
• A nebo B je prázdná množina .

Například:

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} = ∅

Přesně řečeno, kartézský součin není asociativní (pokud jedna ze zapojených sad není prázdná).

${\ Displaystyle (A \ times B) \ times C \ neq A \ times (B \ times C)}$

Pokud například A  = {1}, pak ( A × A ) × A = {(((1, 1), 1)} ≠ {(1, (1, 1))} = A × ( A × A ) .

Křižovatky, odbory a podmnožiny

Kartézský součin splňuje následující vlastnost s ohledem na průsečíky (viz prostřední obrázek).

${\ Displaystyle (A \ cap B) \ times (C \ cap D) = (A \ times C) \ cap (B \ times D)}$

Ve většině případů výše uvedené tvrzení není pravdivé, pokud křižovatku nahradíme sjednocením (viz obrázek úplně vpravo).

${\ Displaystyle (A \ cup B) \ times (C \ cup D) \ neq (A \ times C) \ cup (B \ times D)}$

Ve skutečnosti to máme:

${\ Displaystyle (A \ times C) \ cup (B \ times D) = [(A \ setminus B) \ times C] \ cup [(A \ cap B) \ times (C \ cup D)] \ cup [ (B \ setminus A) \ krát D]}$

Pro nastavený rozdíl máme také následující identitu:

${\ Displaystyle (A \ times C) \ setminus (B \ times D) = [A \ times (C \ setminus D)] \ cup [(A \ setminus B) \ times C]}$

Zde jsou některá pravidla demonstrující distribučnost s jinými operátory (viz obrázek úplně vlevo):

${\ displaystyle {\ begin {aligned} A \ times (B \ cap C) & = (A \ times B) \ cap (A \ times C), \\ A \ times (B \ cup C) & = (A \ times B) \ cup (A \ times C), \\ A \ times (B \ setminus C) & = (A \ times B) \ setminus (A \ times C), \ end {aligned}}}$

${\ Displaystyle (A \ times B)^{\plement} = \ left (A^{\plement} \ times B^{\plement} \ right) \ cup \ left (A^{\plement} \ times B \ vpravo) \ pohár \ vlevo (A \ krát B^{\ doplněk} \ vpravo) \ !,}$

kde označuje absolutní doplněk z A . ${\ displaystyle A^{\plement}}$

Další vlastnosti související s podmnožinami jsou:

${\ displaystyle {\ text {if}} A \ subseteq B {\ text {, then}} A \ times C \ subseteq B \ times C;}$

${\ Displaystyle {\ text {if both}} A, B \ neq \ emptyset {\ text {, then}} A \ times B \ subseteq C \ times D \! \ iff \! A \ subseteq C {\ text { a}} B \ subseteq D.}$

Mohutnost

Mohutnost množiny je počet prvků množiny. Například definování dvou sad: A = {a, b} a B = {5, 6}. Sada A i sada B se skládají vždy ze dvou prvků. Jejich karteziánský součin, psaný jako A × B , má za následek novou sadu, která má následující prvky:

A × B = {(a, 5), (a, 6), (b, 5), (b, 6)}.

kde každý prvek A je spárován s každým prvkem B a kde každý pár tvoří jeden prvek výstupní sady. Počet hodnot v každém prvku výsledné množiny se rovná počtu množin, jejichž karteziánský součin je přijímán; 2 v tomto případě. Mohutnost výstupní sady se rovná součinu kardinalit všech vstupních sad. To znamená,

| A × B | = | A | · | B |.

V tomto případě | A × B | = 4

Podobně

| A × B × C | = | A | · | B | · | C |

a tak dále.

Množina A × B je nekonečná, pokud je A nebo B nekonečná, a druhá množina není prázdná množina.

Kartézské výrobky několika sad

n -ary karteziánský produkt

Kartézský součin lze zobecnit na n -ary kartézského součinu přes n množin X ₁ , ..., X _n jako sady

${\ Displaystyle X_ {1} \ times \ cdots \ times X_ {n} = \ {(x_ {1}, \ ldots, x_ {n}) \ mid x_ {i} \ in X_ {i} \ {\ text {pro každé}} \ i \ v \ {1, \ ldots, n \} \}}$

z n -tuples . Pokud jsou n -tice definovány jako vnořené uspořádané páry , lze je identifikovat pomocí ( X ₁ × ⋯ × X _{n −1} ) × X _n . Pokud je n -tice definována jako funkce na {1, 2,…, n }, která nabývá své hodnoty v i jako i -tý prvek řazené kolekce členů, pak kartézský součin X ₁ × ⋯ × X _n je množina funkcí

${\ Displaystyle \ {x: \ {1, \ ldots, n \} \ to X_ {1} \ cup \ cdots \ cup X_ {n} \ | \ x (i) \ in X_ {i} \ {\ text {pro každé}} \ i \ v \ {1, \ ldots, n \} \}.}$

n -arytní karteziánská moc

Kartézská čtverec o nastavené X je kartézský součin X ² = X × X . Příkladem je 2-dimenzionální rovina R ² = R × R kde R je množina reálných čísel : R ² je množina všech bodů ( x , y ), kde x a y jsou reálná čísla (viz kartézský souřadný systém ) .

N -ary kartézské síla ze souboru X , označený , může být definován jako ${\ displaystyle X^{n}}$

${\ Displaystyle X^{n} = \ underbrace {X \ times X \ times \ cdots \ times X} _ {n} = \ {(x_ {1}, \ ldots, x_ {n}) \ | \ x_ { i} \ v X \ {\ text {pro každé}} \ i \ v \ {1, \ ldots, n \} \}.}$

Příkladem toho je R ³ = R × R × R , kde R je opět množina reálných čísel a obecněji R ⁿ .

N -ary Kartézská výkon nastaveném X je isomorphic k prostoru funkcí z n -element nastaven na X . Jako zvláštní případ je 0 ary kartézský síla X může být použita pro být singleton soubor , odpovídající prázdné funkce s codomain X .

Nekonečné karteziánské produkty

Je možné definovat karteziánský součin libovolné (možná nekonečné ) indexované rodiny množin. Pokud I je libovolná sada indexů a je to rodina množin indexovaných I , pak je karteziánský součin množin definován jako ${\ displaystyle \ {X_ {i} \} _ {i \ in I}}$${\ displaystyle \ {X_ {i} \} _ {i \ in I}}$

${\ Displaystyle \ prod _ {i \ in I} X_ {i} = \ left \ {\ left.f: I \ to \ bigcup _ {i \ in I} X_ {i} \ \ right | \ (\ forall i) (f (i) \ v X_ {i}) \ vpravo \},}$

tj. množina všech funkcí definovaných v sadě indexů tak, že hodnota funkce v konkrétním indexu i je prvkem X _i . I když je každý z X _i neprázdný, kartézský součin může být prázdný, pokud se nepředpokládá zvolený axiom , který je ekvivalentní tvrzení, že každý takový součin je neprázdný.

Pro každé j v I funkce

${\ Displaystyle \ pi _ {j}: \ prod _ {i \ in I} X_ {i} \ až X_ {j},}$

definovaný se nazývá j th projekce mapy . ${\ Displaystyle \ pi _ {j} (f) = f (j)}$

Cartesian síla je kartézský součin, kde jsou všechny faktory Xa _i jsou stejné set X . V tomto případě,

${\ Displaystyle \ prod _ {i \ in I} X_ {i} = \ prod _ {i \ in I} X}$

je soubor všech funkcí od I až X , a je často označován X ^já . Tento případ je důležitý při studiu kardinálního umocňování . Důležitý zvláštní případ je, když je množina indexů je , že přirozená čísla : tento produkt je kartézský množinu všech nekonečných sekvencí s i th termín v jeho odpovídající nastavené X _i . Například každý prvek ${\ displaystyle \ mathbb {N}}$

${\ Displaystyle \ prod _ {n = 1}^{\ infty} \ mathbb {R} = \ mathbb {R} \ times \ mathbb {R} \ times \ cdots}$

lze zobrazit jako vektor s spočitatelně nekonečnými složkami reálného čísla. Tato sada je často označována , nebo . ${\ Displaystyle \ mathbb {R} ^{\ omega}}$${\ displaystyle \ mathbb {R} ^{\ mathbb {N}}}$

Jiné formy

Zkrácená forma

Pokud se násobí několik sad dohromady (např. X ₁ , X ₂ , X ₃ , ...), pak se někteří autoři rozhodnou zkrátit karteziánský součin jednoduše × X _i .

Kartézský součin funkcí

Pokud f je funkce od A do B a g je funkce od X do Y , pak jejich karteziánský součin f × g je funkcí od A × X do B × Y s

${\ Displaystyle (f \ times g) (a, x) = (f (a), g (x)).}$

To lze rozšířit na řazené kolekce členů a nekonečné kolekce funkcí. To se liší od standardního karteziánského součinu funkcí považovaných za sady.

Válec

Nechť je sada a . Potom se válec z s ohledem na je kartézský součin z a . ${\ displaystyle A}$${\ Displaystyle B \ subseteq A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B \ times A}$${\ displaystyle B}$${\ displaystyle A}$

Obvykle je považován za vesmír kontextu a je vynechán. Pokud je například podmnožina přirozených čísel , pak válec je . ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle \ mathbb {N}}$${\ displaystyle B}$${\ displaystyle B \ times \ mathbb {N}}$

Definice mimo teorii množin

Teorie kategorie

Ačkoli je karteziánský součin tradičně aplikován na množiny, teorie kategorií poskytuje obecnější interpretaci součinu matematických struktur. To se liší od pojmu karteziánského čtverce v teorii kategorií , i když to souvisí s tímto pojmem , což je zobecnění výrobku z vláken .

Umocňování je správným doplňkem karteziánského produktu; jakákoli kategorie s karteziánským produktem (a konečným předmětem ) je tedy karteziánskou uzavřenou kategorií .

Teorie grafů

V teorii grafů je karteziánský součin dvou grafů G a H graf označený G × H , jehož množinou vrcholů je (obyčejný) karteziánský součin V ( G ) × V ( H ) a takový, že dva vrcholy ( u , v ) a ( u ', v ') jsou přilehlé v G x H , a to pouze v případě, u = u ' a v je v sousedství s v ' v H , nebo v = v ' a u je v sousedství s u ' v G . Kartézský součin grafů není produktem ve smyslu teorie kategorií. Místo toho je kategorický součin známý jako tenzorový součin grafů .

Viz také

• Binární vztah
• Zřetězení množin řetězců
• Koprodukt
• Křížový produkt
• Přímý součin skupin
• Prázdný produkt
• Euklidovský prostor
• Exponenciální objekt
• Konečný vztah
• Připojte se (SQL) § Křížové spojení
• Objednávky na karteziánský produkt zcela objednaných sad
• Axiom mocenské sady (k prokázání existence karteziánského produktu)
• Produkt (teorie kategorií)
• Topologie produktu
• Typ výrobku
• Ultraprodukt

Reference

externí odkazy

• Cartesian Product ve společnosti ProvenMath
• „Přímý produkt“ , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Jak najít kartézský produkt, akademie vzdělávacího portálu