Cartesian produkt
Det kartesiske produkt eller produktmængde er i sætteorien en grundlæggende struktur fra givne mængder for at generere et nyt sæt. Lejlighedsvis bruges det tvetydige udtryk " krydsprodukt " om det kartesiske produkt . Det kartesiske produkt med to sæt er sættet med alle ordnede par af elementer i de to sæt, hvor den første komponent er et element i det første sæt, og den anden komponent er et element i det andet sæt. Mere generelt består det kartesiske produkt af flere sæt af sættet af alle tupper af sættets elementer, hvor rækkefølgen af sættene og dermed af de tilsvarende elementer er fastgjort. Resultatsættet for det kartesiske produkt er også produktmængde , krydsmængde eller mængde kaldet forbindelse . Det kartesiske produkt er opkaldt efter den franske matematiker René Descartes , der brugte det til at beskrive det kartesiske koordinatsystem og dermed etablerede analytisk geometri .
Produkt af to sæt
definition
Det kartesiske produkt (læs "A kryds B") med to sæt og defineres som sættet af alle ordnede par , hvor et element er ude og et element er ude. Hvert element er lavet med hvert element kombineret. Formelt er det kartesiske produkt igennem
Er defineret. Især er det også muligt at danne det kartesiske produkt af et sæt med sig selv og derefter skrive
- .
Lejlighedsvis bruges udtrykket "krydsprodukt" også om det kartesiske produkt, men dette har andre betydninger, se krydsprodukt .
Ovenstående definition er ethvert problem (reelt) på klasser og udvideligt. Især dannes par kun for elementer af og ; disse kan ikke være rigtige klasser og har ingen specielle krav til pardannelse.
Eksempler
Endelige mængder
Det kartesiske produkt af de to sæt og er
- .
Det kartesiske produkt er derimod et andet sæt, nemlig
- ,
fordi rækkefølgen af elementerne spiller en rolle i ordnede par. Det cartesianske produkt af sig selv er
- .
Reelle tal
Det reelle talplan stammer fra det kartesiske produkt af de reelle tal med sig selv:
- .
Intervaller
Tuplerne kaldes også kartesiske koordinater . Det kartesiske produkt med to reelle intervaller og giver rektanglet
- .
Spillekort
Spilkort , som dem, der bruges i Texas Hold'em , Canasta , " Doppelkopf " og Skat , er et eksempel på et kartesisk produkt. Det første sæt i dette tilfælde er sættet med kortværdier, for eksempel V = {A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2} , og det andet sæt er det sæt kortsymboler, for eksempel S = { ♣ , ♠ , ♥ , ♦ } . Sættet med spillekort er derefter det kartesiske produkt af disse to sæt: V × S = {(A, ♣ ), (A, ♠ ), (A, ♥ ), (A, ♦ ), (K, ♣ ), ..., (3, ♦ ), (2, ♣ ), (2, ♠ ), (2, ♥ ), (2, ♦ )} .
I dette eksempel er mængden har kortværdierne 13 elementer, dvs. mængden og de kortsymboler er en 4 elementer, dvs. . Det følger heraf, at sættet med spillekort har elementer.
Dette kartesiske produkt kan repræsenteres med en tabel:
Kartesisk produkt af kortværdier og kortsymboler | ||||
---|---|---|---|---|
♣ | ♠ | ♥ | ♦ | |
EN. | (A, ♣ ) | (A, ♠ ) | (A, ♥ ) | (A, ♦ ) |
K | (K, ♣ ) | (K, ♠ ) | (A, ♥ ) | (A, ♦ ) |
Q | (Q, ♣ ) | (Q, ♠ ) | (Q, ♥ ) | (Q, ♦ ) |
J | (J, ♣ ) | (J, ♠ ) | (J, ♥ ) | (J, ♦ ) |
10 | (10, ♣ ) | (10, ♠ ) | (10, ♥ ) | (10, ♦ ) |
... | ... | ... | ... | ... |
3 | (3, ♣ ) | (3, ♠ ) | (3, ♥ ) | (3, ♦ ) |
2 | (2, ♣ ) | (2, ♠ ) | (2, ♥ ) | (2, ♦ ) |
Metro linjer eller S-Bahn linjer
I tilfælde af transportnetværk, der består af metrolinjer og S-Bahn-linjer , er sættet med transportledninger et kartesisk produkt, som f.eks. Kan opnås fra sættet L = {U, S} af linjetyperne og den indstillede N = {1, 2, 3, 4, 5, 6, 7} af linjenumrene kan dannes. Her er .
Kartesisk produkt af linjetyper (U / S-Bahn-linjer) og linjenumre | |||||||
---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4. plads | 5 | 6. | 7. | |
U1 | U2 | U3 | U4 | U5 | U6 | U7 | |
S1 | S2 | S3 | S4 | S5 | S6 | S7 |
Tips:
Et (komplet) kartesisk produkt opnås kun, hvis antallet af underjordiske og S-Bahn-linjer er det samme. Ellers er resultatet et ufuldstændigt kartesisk produkt, der har fundamentalt forskellige egenskaber. Inden for datalogi og programmering kan dette emne f.eks . Findes under arraydimensioner .
ejendomme
Antal elementer
-en | b | c | d | e | f | G | H | ||
8. plads | 8. plads | ||||||||
7. | 7. | ||||||||
6. | 6. | ||||||||
5 | 5 | ||||||||
4. plads | 4. plads | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
-en | b | c | d | e | f | G | H |
Hvis sætene er og er endelige , så er deres kartesiske produkt et endeligt sæt bestilte par. Antallet af par svarer til produktet af antallet af elementerne i det oprindelige sæt, dvs.
I det særlige tilfælde, dvs., gælder
- .
Hvis mindst et af de to sæt indeholder et uendeligt antal elementer, og det andet ikke er tomt, består dets kartesiske produkt af et uendeligt antal par. Den kartesiske produkt af to tælleligt uendelige sæt er også tælleligt ifølge Cantor første diagonal argument . Hvis mindst et af de to sæt er utallige , er dets produktsæt også utallige.
Tomt sæt
Da intet element kan vælges fra det tomme sæt , resulterer det kartesiske produkt af det tomme sæt med et vilkårligt sæt i det tomme sæt. Mere generelt gælder
- ,
det vil sige, det kartesiske produkt med to sæt er tomt, hvis og kun hvis mindst et af de to sæt er tomt.
Ikke-kommutativitet
Det kartesiske produkt er ikke kommutativt , det vil sige for ikke-ukomplicerede sæt og med er
- ,
for i par af sættet er det første element slukket og det andet slukket , mens i paret af sættet er det første element slukket og det andet er slukket. Der er dog en kanonisk sammenhæng mellem de to sæt, nemlig
- ,
hvormed mængderne kan identificeres med hinanden.
Ikke-associativitet
Det kartesiske produkt er også ikke- associativ , der er, for ikke-tomme mængde , og holder i almindelighed
- ,
fordi sættet på venstre side indeholder par, hvis første element er et par off, og hvis andet element er et par off , mens sættet på højre side indeholder par, hvis første element er et par off, og hvis andet element er et par off . Også her er der en kanonisk sammenhæng mellem disse to sæt, nemlig
- .
Nogle forfattere identificerer parene og med den bestilte tredobbelt , hvilket også gør det kartesiske produkt associerende.
Distributivitet
Følgende distributionslove vedrørende union , skæringspunkt og subtraktion af sæt gælder for det kartesiske produkt :
Den fjerde lov kan bruges til at bevise fordelingen af de naturlige tal, hvis disse er defineret med hovedtal .
Monotoni og komplement
Det kartesiske produkt opfører sig monotont med hensyn til dannelsen af delmængder , det vil sige, hvis sætene og ikke er tomme, gælder følgende
- .
Især gælder lighed her
- .
Hvis man betragter sættet som basissættet af og sættet som basissættet af , så har komplementet af i repræsentationen
- .
Yderligere beregningsregler
Det er sandt
- ,
men generelt er det
- ,
fordi sættet til venstre indeholder par, og som ikke er inkluderet i sættet til højre.
Produkt af endeligt mange mængder
definition
Mere generelt, den kartesiske produkt af er sæt defineret som sættet af alle - tuples , hvor for hver enkelt element er fra sættet . Formelt er det flere kartesiske produkt igennem
Er defineret. Ved hjælp af produktsymbolet føres det flere kartesiske produkt også igennem
skrevet ned. Det foldede kartesiske produkt af et sæt med sig selv er også skrevet som
- .
Tomt produkt
Det kartesiske produkt med nul sæt er det sæt, der indeholder den tomme tupel som det eneste element , dvs.
Især er for ethvert sæt
- .
Dette gøres, når konstanter af en matematisk struktur ses som nulcifrede operationer.
Tilknytning af alle produkter
Med betegner foreningen af alle foldede kartesiske produkter af et sæt med sig selv (for alle ), dvs. sættet af alle tupler med elementer af A, inklusive den tomme tupel:
- .
Eksempler
Er så er
- .
Det euklidiske rum består af tre gange det kartesiske produkt af de reelle tal :
- .
De 3-tupler er de tredimensionelle kartesiske koordinater. Det kartesiske produkt med tre reelle intervaller , og giver kuboidet
- .
Generelt giver det foldede kartesiske produkt af de reelle tal plads, og det kartesiske produkt med reelle intervaller giver et hyperrektangel .
ejendomme
Antal elementer
Hvis sætene alle er endelige, er deres kartesiske produkt også et endeligt sæt, hvor antallet af elementer af er lig med produktet af elementnumrene i de oprindelige sæt , det vil sige
eller i en anden notation
- .
I det specielle tilfælde at alle sæt er lig med et sæt , gælder følgende
- .
Det kartesianske produkt af endelig mange utallige uendelige sæt kan også tælles, hvilket kan vises ved at gentage argumentet for det kartesiske produkt af to sæt ved hjælp af Cantors tupelfunktion .
monotoni
Hvis sætene og ikke er tomme, gælder monotoni, som med det kartesiske produkt af to sæt
og lighed
- .
Produkt med uendeligt mange mængder
definition
Det er også muligt at definere det kartesiske produkt af et uendeligt antal sæt. Hvis der er et indeks sæt og en familie af sæt, defineres det cartesianske produkt af sætene med
- .
Dette er mængden af alle billeder af foreningen af sættene , som billedet i løgne. Hvis de alle er lig med et sæt , er det det kartesiske produkt
sættet med alle funktioner fra til . Hvis mængderne er forskellige, er det kartesiske produkt dog langt mindre klart. Selv spørgsmålet om, hvorvidt et kartesisk produkt af ikke-tomme sæt er ikke-tomt, kan ikke afgøres med Zermelo-Fraenkel-sætteorien ZF; påstanden om, at den ikke er tom, er en formulering af det valgte aksiom , der føjes til ZF for at opnå sætteorien ZFC (“Zermelo-Fraenkel + Choice”).
Særlige tilfælde
Et vigtigt specialtilfælde for et uendeligt kartesisk produkt opstår ved valget af naturlige tal som indeksindstillingen. Den kartesiske produkt af en sekvens af sæt
svarer derefter til sættet med alle sekvenser, hvis -th sekvensmedlem er i sættet . For eksempel, hvis alle er , så er
sættet med alle reelle nummersekvenser. Det tællbare kartesiske produkt kan kortlægges ved hjælp af det generelt definerede kartesiske produkt, fordi hver sekvens definerer en funktion med, og omvendt, enhver sådan funktion kan skrives som en sekvens . Det cartesianske produkt af endeligt mange sæt kan også forstås som et specielt tilfælde af den generelle definition under anvendelse af endelige sekvenser.
Det cartesianske produkts universelle ejendom
Fremskrivningsfamilien tilhører det kartesiske produkt . Det cartesianske produkt sammen med familien har følgende egenskab: Hvis der er et vilkårligt sæt og er en familie af billeder, så er der nøjagtigt et billede med for alle . Det vil sige følgende diagram er kommutativ:
Hvis denne kvalitet også deles med familien , er der en bijektiv kortlægning .
Afledte udtryk
- Et binært forhold mellem to sæt er en delmængde af det kartesiske produkt af de to sæt. Især er hver kortlægning derfor en delmængde af det kartesiske produkt af definitionen og målsætningen for kortlægningen. Mere generelt er en -cifret relation en delmængde af det cartesiske produkt af sæt.
- En projektion er en kortlægning af det cartesianske produkt af to sæt tilbage til et af disse sæt. Mere generelt er en projektion en kortlægning fra det cartesianske produkt af en familie af sæt til det cartesiske produkt af en underfamilie af disse sæt, der vælger elementer med visse indekser.
- Et tocifret link er en kortlægning af det kartesiske produkt af to sæt til et andet sæt. Mere generelt er et cifret link en kortlægning af det kartesiske produkt af sæt til et andet sæt. Hvert -cifret link kan derfor også forstås som et -cifret forhold.
- Et direkte produkt er et produkt af algebraiske strukturer , såsom grupper eller vektorrum , der består af det kartesiske produkt fra bæresættene og derudover forsynes med en eller flere komponentvise forbindelser. En direkte sum er en delmængde af det direkte produkt, der kun adskiller sig fra det direkte produkt for produkter i uendeligt mange mængder. den består af alle tupler, der kun adskiller sig fra et bestemt element (normalt det neutrale element i et link) et begrænset antal steder .
- Det kategoriske produkt svarer til det kartesiske produkt i kategorien sæt og det direkte produkt i kategorien af grupper og i andre kategorier af algebraiske strukturer.
- I relationelle databaser bruges det kartesiske produkt af tabeller og sammenkædningsoperationer baseret på dem til at linke databasetabeller.
litteratur
- Oliver Deiser: Introduktion til sætteori. Georg Cantors sætteori og dens axiomatisering af Ernst Zermelo. 2. forbedret og udvidet udgave. Springer, Berlin et al. 2004, ISBN 3-540-20401-6 .
Weblinks
- M. Sh. Tsalenko: Direkte produkt . I: Michiel Hazewinkel (red.): Encyclopedia of Mathematics . Springer-Verlag og EMS Press, Berlin 2002, ISBN 978-1-55608-010-4 (engelsk, online ).
- Eric W. Weisstein : kartesisk produkt . På: MathWorld (engelsk).
- David Jao: kartesisk produkt . I: PlanetMath . (Engelsk)
- Thomas Foregger, David Jao, Andrew Archibald: Generaliseret kartesisk produkt . I: PlanetMath . (Engelsk)