Multisett - Multiset

I matematikk er et multisett (eller bag eller mset ) en modifikasjon av konseptet til et sett som, i motsetning til et sett, tillater flere forekomster for hvert av elementene . Antall forekomster gitt for hvert element kalles multiplisiteten til det elementet i multisettet. Som en konsekvens eksisterer et uendelig antall multisett som bare inneholder elementene $a$ og $b$ , men varierer i mangfoldet av elementene:

Settet ${a, b}$ inneholder bare elementene $a$ og $b$ , som hver har multiplisitet 1 når ${a, b}$ blir sett på som et multisett.
I multisettet ${a, a, b}$ har elementet $a$ multiplisitet 2, og $b$ har multiplicity 1.
I multisettet ${a, a, a, b, b, b}$ har $a$ og $b$ begge multiplisitet 3.

Disse objektene er alle forskjellige når de blir sett på som multisett, selv om de er det samme settet , siden de alle består av de samme elementene. Som med sett, og i motsetning til tupler , spiller orden ingen rolle ved diskriminering av flere nett, så ${a, a, b}$ og ${a, b, a}$ betegner det samme multisettet. For å skille mellom sett og multisett brukes noen ganger en notasjon som inneholder firkantede parenteser: multisettet ${a, a, b}$ kan betegnes som $[a, a, b]$ .

Den Kardinaliteten av en multiset er konstruert ved å summere opp multiplisitetene av alle dens elementer. For eksempel, i multisettet ${a, a, b, b, b, c}$ er multiplikasjonene til medlemmene $a$ , $b$ og $c$ henholdsvis 2, 3 og 1, og derfor er kardinaliteten til dette multisettet 6.

Nicolaas Govert de Bruijn skapte ordet multiset på 1970 -tallet , ifølge Donald Knuth . Imidlertid er bruken av begrepet multisett forut for myntingen av ordet multiset med mange århundrer. Knuth selv tilskriver den første studien av multisett til den indiske matematikeren Bhāskarāchārya , som beskrev permutasjoner av multisett rundt 1150. Andre navn har blitt foreslått eller brukt for dette konseptet, inkludert liste , haug , pose , haug , prøve , vektet sett , samling og suite .

Historie

Wayne Blizard sporet flere sett tilbake til tallets opprinnelse, og hevdet at "i antikken var tallet n ofte representert med en samling av n slag, tellemerker eller enheter." Disse og lignende objektsamlinger er flersett, fordi streker, tellermerker eller enheter anses som ikke skillbare. Dette viser at folk implisitt brukte multisett allerede før matematikk dukket opp.

Praktiske behov for denne strukturen har ført til at multisett har blitt gjenoppdaget flere ganger, og som har vist seg i litteratur under forskjellige navn. For eksempel var de viktige på tidlige AI -språk, for eksempel QA4, der de ble omtalt som poser, et begrep som tilskrives Peter Deutsch. Et multisett har også blitt kalt et aggregat, en haug, en haug, en prøve, et vektet sett, et forekomstssett og et brannsett (endelig gjentatt elementsett).

Selv om multisett ble brukt implisitt fra gammel tid, skjedde deres eksplisitte utforskning mye senere. Den første kjente studien av multisett tilskrives den indiske matematikeren Bhāskarāchārya rundt 1150, som beskrev permutasjoner av multisett. Verket til Marius Nizolius (1498–1576) inneholder en annen tidlig referanse til begrepet multisett. Athanasius Kircher fant antall multiset -permutasjoner når ett element kan gjentas. Jean Prestet publiserte en generell regel for multiset -permutasjoner i 1675. John Wallis forklarte denne regelen mer detaljert i 1685.

Multisett dukket opp eksplisitt i arbeidet til Richard Dedekind .

Andre matematikere formaliserte flersett og begynte å studere dem som presise matematiske strukturer på 1900 -tallet. For eksempel beskrev Whitney (1933) generaliserte sett ("sett" hvis karakteristiske funksjoner kan ta hvilken som helst heltall - positiv, negativ eller null). Monro (1987) undersøkte kategorien Mul av multisett og deres morfisme, og definerte et multisett som et sett med et ekvivalensforhold mellom elementer "av samme type ", og en morfisme mellom multisett som en funksjon som respekterer sorter . Han introduserte også en multinumber : en funksjon f ( x ) fra et multisett til de naturlige tallene , noe som gir mangfoldet av element x i multisettet. Monro hevdet at begrepene multiset og multinumber ofte blandes vilkårlig, selv om begge er nyttige.

Eksempler

Et av de enkleste og mest naturlige eksemplene er flersettet av primfaktorer for et naturlig tall $n$ . Her er det underliggende settet med elementer settet med primfaktorer til $n$ . For eksempel er antallet 120 har Primtallfaktorisering

{\ displaystyle 120 = 2^{3} 3^{1} 5^{1}}

som gir multisettet ${2, 2, 2, 3, 5}$ .

Et beslektet eksempel er flersettet av løsninger av en algebraisk ligning. En kvadratisk ligning har for eksempel to løsninger. I noen tilfeller er de imidlertid like mange. Dermed kan flersettet av løsningene i ligningen være ${3, 5}$ , eller det kan være ${4, 4}$ . I sistnevnte tilfelle har den en løsning av multiplisitet 2. Mer generelt hevder den grunnleggende teoremet om algebra at de komplekse løsningene til en polynomligning av grad $d$ alltid danner et multisett med kardinalitet $d$ .

Et spesielt tilfelle av det ovennevnte er egenverdiene til en matrise , hvis mangfoldighet vanligvis er definert som deres mangfoldighet som røtter til det karakteristiske polynomet . Imidlertid er to andre multiplikasjoner naturlig definert for egenverdier, deres multiplisiteter som røtter til det minimale polynomet , og den geometriske multiplisiteten , som er definert som dimensjonen til kjernen til $A - λI$ (hvor $λ$ er en egenverdi av matrisen $A$ ). Disse tre multiplikasjonene definerer tre multisett med egenverdier, som alle kan være forskjellige: La $A$ være en $n \times n$ -matrise i Jordans normale form som har en egen egenverdi. Dens mangfoldighet er $n$ , dens mangfoldighet som en rot av det minimale polynomet er størrelsen på den største Jordanblokken, og dens geometriske multiplisitet er antall Jordanblokker.

Definisjon

Et multisett kan formelt defineres som en 2- tupel $(A, m)$ hvor $A$ er det underliggende settet til multisettet, dannet av dets forskjellige elementer, og er en funksjon fra $A$ til settet med de positive heltallene , noe som gir multiplisiteten , det vil si antall forekomster av elementet $a$ i multisettet som tallet $m$ $($ $a$ $)$ . ${\ displaystyle m \ colon A \ to \ mathbb {Z} ^{+}}$

Ved å representere funksjonen $m$ ved grafen (settet med ordnede par ) kan du skrive multisettet ${$ $a$ $,$ $a$ $,$ $b$ $}$ som $({$ $a$ $,$ $b$ $}, {($ $a$ $, 2), ($ $b$ $, 1)})$ og multisettet ${$ $a$ $,$ $b$ $}$ som $({$ $a$ $,$ $b$ $}, {($ $a$ $, 1), ($ $b$ $, 1)})$ . Denne notasjonen er imidlertid ikke vanlig og mer kompakte notasjoner brukes. ${\ displaystyle \ left \ {\ left (a, m \ left (a \ right) \ right): a \ in A \ right \}}$

Hvis er et begrenset sett , blir multisettet $($ $A$ $,$ $m$ $)$ ofte representert som ${\ displaystyle A = \ {a_ {1}, \ ldots, a_ {n} \}}$

{\ displaystyle \ left \ {a_ {1}^{m (a_ {1})}, \ ldots, a_ {n}^{m (a_ {n})} \ right \}, \ quad}

noen ganger forenklet til

{\ displaystyle \ quad a_ {1}^{m (a_ {1})} \ cdots a_ {n}^{m (a_ {n})},}

der øvre indekser lik 1 er utelatt. For eksempel kan multisettet { a , a , b } skrives eller Hvis elementene i multisettet er tall, er det mulig å forveksle med vanlige aritmetiske operasjoner , de kan vanligvis utelukkes fra konteksten. På den annen side er sistnevnte notasjon i samsvar med det faktum at primfaktoriseringen av et positivt heltall er et unikt definert multisett, slik det blir hevdet av aritmetikkens grunnleggende teorem . Et monomial er også et multisett med ubestemte ; for eksempel tilsvarer monomialet x ³y ² multisettet { x , x , x , y , y }. ${\ displaystyle \ {a^{2}, b \}}$ ${\ displaystyle a^{2} b.}$

Et multisett tilsvarer et vanlig sett hvis mangfoldet av hvert element er ett (i motsetning til et større positivt heltall). En indeksert familie , $(a i) i \in I$ , hvor $jeg$ varierer over noen indekssett I , kan definere et multisett, noen ganger skrevet ${a i}$ . I denne visningen er det underliggende settet til multisettet gitt av bildet av familien, og mangfoldet av et hvilket som helst element $x$ er antallet indeksverdier $i$ slik at . I denne artikkelen anses multiplikasjonene å være begrensede, det vil si at ingen elementer forekommer uendelig mange ganger i familien: selv i et uendelig multisett er multiplikasjonene endelige tall. ${\ displaystyle a_ {i} = x}$

Det er mulig å utvide definisjonen av et multisett ved å la multiplisiteter av individuelle elementer være uendelige kardinaler i stedet for positive heltall, men ikke alle egenskaper går videre til denne generaliseringen.

Grunnleggende egenskaper og drift

Elementer av et multisett er vanligvis tatt i et fast sett $U$ , noen ganger kalt et univers , som ofte er settet med naturlige tall . Et element av $U$ som ikke tilhører et gitt multisett sies å ha en mangfoldighet 0 i dette multisettet. Dette utvider flerfunksjonsfunksjonen til multisettet til en funksjon fra $U$ til settet med ikke -negative heltall . Dette definerer et en-til-en korrespondanse mellom disse funksjonene og multisets som har sine elementer i $U$ . ${\ displaystyle \ mathbb {N}}$

Denne utvidede multiplisitetsfunksjonen kalles vanligvis ganske enkelt multiplisitetsfunksjonen , og er tilstrekkelig til å definere multisett når universet som inneholder elementene er fikset. Denne multiplisitetsfunksjonen er en generalisering av indikatorfunksjonen til et delsett, og deler noen egenskaper med den.

Den støtte av en MultiSet i et univers $U$ er den underliggende sett av multiset. Ved å bruke multiplisitetsfunksjonen , karakteriseres den som ${\ displaystyle A}$ ${\ displaystyle m}$

{\ displaystyle \ operatorname {Supp} (A): = \ left \ {x \ in U \ mid m_ {A} (x)> 0 \ right \}}

.

Et multisett er begrenset hvis støtten er begrenset, eller, tilsvarende, hvis den er kardinal

{\ displaystyle | A | = \ sum _ {x \ in \ operatorname {Supp} (A)} m_ {A} (x) = \ sum _ {x \ i U} m_ {A} (x)}

er begrenset. Det tomme multisettet er det unike multisettet med en tom støtte (underliggende sett), og dermed en kardinalitet 0.

De vanlige operasjonene til sett kan utvides til multisett ved å bruke multiplisitetsfunksjonen, på samme måte som å bruke indikatorfunksjonen for delsett. I det følgende er $A$ og $B$ multisett i et gitt univers $U$ , med flerhetsfunksjoner og ${\ displaystyle m_ {A}}$ ${\ displaystyle m_ {B}.}$

Inkludering: $A$ er inkludert i $B$ , betegnet $A \subseteq B$ , hvis

{\ displaystyle m_ {A} (x) \ leq m_ {B} (x) \ quad \ forall x \ i U.}

Union: den union (kalt, i noen sammenhenger, den høyeste eller laveste felles multiplum ) av $A$ og $B$ er det multiset $C$ med multiplisitet funksjon

{\ displaystyle m_ {C} (x) = \ max (m_ {A} (x), m_ {B} (x)) \ quad \ forall x \ i U.}

Kryss: det kryss (kalt, i noen sammenhenger, den infimum eller største felles divisor ) av $A$ og $B$ er det multiset $C$ med multiplisitet funksjon

{\ displaystyle m_ {C} (x) = \ min (m_ {A} (x), m_ {B} (x)) \ quad \ forall x \ i U.}

Sum: det summen av $A$ og $B$ er det multiset $C$ med multiplisitet funksjon

{\ displaystyle m_ {C} (x) = m_ {A} (x)+m_ {B} (x) \ quad \ forall x \ i U.}

Det kan sees på som en generalisering av den usammenhengende sammensetningen av sett. Den definerer en kommutativ monoid struktur på de endelige multisettene i et gitt univers. Denne monoiden er en fri kommutativ monoid , med universet som grunnlag.

Forskjell: den forskjell av $A$ og $B$ er det multiset $C$ med multiplisitet funksjon

{\ displaystyle m_ {C} (x) = \ max (m_ {A} (x) -m_ {B} (x), 0) \ quad \ forall x \ i U.}

To multisett er disjoint hvis støttene er disjoint -sett . Dette tilsvarer å si at skjæringspunktet deres er det tomme multisettet, eller at summen deres er lik deres forening.

Det er et inkluderings -ekskluderingsprinsipp for begrensede multisett (lik det for sett), som sier at en endelig forening av endelige multisett er forskjellen på to summer av multisett: i den første summen vurderer vi alle mulige kryss av et oddetall av de gitte multisettene, mens vi i den andre summen vurderer alle mulige kryss av et partall av de gitte multisettene.

Teller multisett

Tilknytning mellom 3-delsett av et 7-sett (venstre)
og 3-multisett med elementer fra et 5-sett (høyre)
Så dette illustrerer det .

{\ displaystyle \ textstyle {7 \ velg 3} = \ venstre (\! \! {5 \ velg 3} \! \! \ høyre)}

Antallet multisett med kardinalitet $k$ , med elementer hentet fra et begrenset sett med kardinalitet $n$ , kalles multiset -koeffisienten eller multiset -tallet . Dette tallet er skrevet av noen forfattere som en notasjon som er ment å ligne binomiske koeffisienter ; den brukes for eksempel i (Stanley, 1997), og kan uttales " $n$ multichoose $k$ " for å ligne " $n$ velge $k$ " for . I motsetning til for binomiske koeffisienter, er det ingen "multiset -setning" der multiset -koeffisienter ville forekomme, og de bør ikke forveksles med de ikke -relaterte multinomial -koeffisientene som forekommer i multinomial -setningen . ${\ displaystyle \ textstyle \ left (\! \! {n \ velg k} \! \! \ høyre)}$ ${\ displaystyle {\ tbinom {n} {k}}}$

Verdien av multiset -koeffisienter kan eksplisitt angis som

{\ displaystyle \ left (\! \! {n \ velg k} \! \! \ høyre) = {n+k-1 \ velg k} = {\ frac {(n+k-1)!} {k ! \, (n-1)!}} = {n (n+1) (n+2) \ cdots (n+k-1) \ over k!},}

hvor det andre uttrykket er som en binomial koeffisient; mange forfattere unngår faktisk separat notasjon og skriver bare binomiske koeffisienter. Så antallet av slike multisett er det samme som antall undersett av kardinalitet $k$ i et sett med kardinalitet $n + k - 1$ . Analogien med binomiske koeffisienter kan understrekes ved å skrive telleren i uttrykket ovenfor som en stigende faktoriell kraft

{\ displaystyle \ left (\! \! {n \ velg k} \! \! \ right) = {n^{\ overline {k}} \ over k!},}

for å matche uttrykket av binomiske koeffisienter ved å bruke en fallende faktoriell kraft:

{\ displaystyle {n \ velg k} = {n^{\ understrekning {k}} \ over k!}.}

Det er for eksempel 4 multisett av kardinalitet 3 med elementer hentet fra settet ${1, 2}$ av kardinalitet 2 ( $n = 2$ , $k = 3$ ), nemlig ${1, 1, 1}$ , ${1, 1, 2}$ , ${1, 2, 2}$ , ${2, 2, 2}$ . Det er også 4 undersett av kardinalitet 3 i settet ${1, 2, 3, 4}$ av kardinalitet 4 ( $n + k - 1$ ), nemlig ${1, 2, 3}$ , ${1, 2, 4}$ , ${1 , 3, 4}$ , ${2, 3, 4}$ .

En enkel måte å bevise likheten mellom multiset -koeffisienter og binomiske koeffisienter gitt ovenfor, innebærer å representere multisett på følgende måte. Vurder først notasjonen for multisett som representerer ${a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d}$ (6 $a$ s, 2 $b$ s, 3 $c$ s, 7 $d$ s) i dette skjemaet:

• • • • • • | • • | • • • | • • • • • • • •

Dette er et multisett med kardinalitet $k$ = 18 laget av elementer i et sett med kardinalitet $n$ = 4. Antall tegn inkludert både prikker og vertikale linjer som brukes i denne notasjonen er 18 + 4 - 1. Antallet vertikale linjer er 4 - 1. Antallet multisett av kardinalitet 18 er da antall måter å ordne de 4 - 1 vertikale linjene blant de 18 + 4 - 1 tegnene, og er dermed antall undersett av kardinalitet 4 - 1 i et sett med kardinalitet 18 + 4 - 1. Tilsvarende er det antall måter å ordne de 18 prikkene blant de 18 + 4 - 1 tegnene, som er antall undersett av kardinalitet 18 i et sett med kardinalitet 18 + 4 - 1. Dette er

{\ displaystyle {4+18-1 \ velg 4-1} = {4+18-1 \ velg 18} = 1330,}

dermed er verdien av multiset -koeffisienten og dens ekvivalenser:

{\ displaystyle \ left (\! \! {4 \ velg 18} \! \! \ høyre) = {21 \ velg 18} = {\ frac {21!} {18! \, 3!}} = {21 \ velg 3} = \ venstre (\! \! {19 \ velg 3} \! \! \ høyre),}

{\ displaystyle = {\ frac {{\ color {red} {\ mathfrak {4 \ cdot 5 \ cdot 6 \ cdot 7 \ cdot 8 \ cdot 9 \ cdot 10 \ cdot 11 \ cdot 12 \ cdot 13 \ cdot 14 \ cdot 15 \ cdot 16 \ cdot 17 \ cdot 18}}} \ cdot \ mathbf {19 \ cdot 20 \ cdot 21}} {\ mathbf {1 \ cdot 2 \ cdot 3} \ cdot {\ color {red} {\ mathfrak {4 \ cdot 5 \ cdot 6 \ cdot 7 \ cdot 8 \ cdot 9 \ cdot 10 \ cdot 11 \ cdot 12 \ cdot 13 \ cdot 14 \ cdot 15 \ cdot 16 \ cdot 17 \ cdot 18}}}}}}}} ,}

{\ displaystyle = {\ frac {1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5 \ cdots 16 \ cdot 17 \ cdot 18 \; \ mathbf {\ cdot \; 19 \ cdot 20 \ cdot 21}} {\ , 1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5 \ cdots 16 \ cdot 17 \ cdot 18 \, \ times \, \ mathbf {1 \ cdot 2 \ cdot 3 \ quad}}},}

{\ displaystyle = {\ frac {19 \ cdot 20 \ cdot 21} {1 \ cdot 2 \ cdot 3}}.}

Man kan definere en generalisert binomial koeffisient

{\ displaystyle {n \ velg k} = {n (n-1) (n-2) \ cdots (n-k+1) \ over k!}}

der $n$ ikke trenger å være et ikke-negativt heltall, men kan være negativt eller et ikke-heltall, eller et ikke-reelt komplekst tall . (Dersom $k$ = 0, vil verdien av denne koeffisient er 1 fordi det er den tom produkt .) Deretter antall multisets av cardinality $k$ i et sett av kardinalitet $n$ er

{\ displaystyle \ left (\! \! {n \ velg k} \! \! \ høyre) = (-1)^{k} {-n \ velg k}.}

Gjentagelsesforhold

En gjentakelsesrelasjon for multiset -koeffisienter kan gis som

{\ displaystyle \ venstre (\! \! {n \ velg k} \! \! \ høyre) = \ venstre (\! \! {n \ velg k-1} \! \! \ høyre)+\ venstre ( \! \! {n-1 \ velg k} \! \! \ høyre) \ quad {\ mbox {for}} n, k> 0}

med

{\ displaystyle \ left (\! \! {n \ velg 0} \! \! \ right) = 1, \ quad n \ in \ mathbb {N}, \ quad {\ mbox {og}} \ quad \ left (\! \! {0 \ velg k} \! \! \ Høyre) = 0, \ quad k> 0.}

Ovenstående tilbakefall kan tolkes som følger. La $[n]$ : = være kildesettet. Det er alltid nøyaktig ett (tomt) multisett med størrelse 0, og hvis $n$ $= 0 er$ det ingen større multisett, noe som gir de første betingelsene. ${\ displaystyle \ {1, \ dots, n \}}$

Vurder nå saken der $n, k > 0$ . Et multisett med kardinalitet $k$ med elementer fra $[n]$ kan inneholde noen forekomst av det siste elementet $n$ . Hvis det vises, ved å fjerne $n$ en gang, sitter man igjen med et multisett med kardinalitet $k - 1$ av elementer fra $[n]$ , og hvert slikt multisett kan oppstå, noe som gir totalt

{\ displaystyle \ left (\! \! {n \ velg k-1} \! \! \ right)}

muligheter.

Hvis $n$ ikke vises, er vårt originale multisett lik et multisett med kardinalitet $k$ med elementer fra $[n - 1]$ , som det er

{\ displaystyle \ left (\! \! {n-1 \ velg k} \! \! \ right).}

Og dermed,

{\ displaystyle \ venstre (\! \! {n \ velg k} \! \! \ høyre) = \ venstre (\! \! {n \ velg k-1} \! \! \ høyre)+\ venstre ( \! \! {n-1 \ velg k} \! \! \ høyre).}

Genererer serier

Den genererende funksjonen til multiset -koeffisientene er veldig enkel

{\ displaystyle \ sum _ {d = 0}^{\ infty} \ venstre (\! \! {n \ velg d} \! \! \ høyre) t^{d} = {\ frac {1} {( 1-t)^{n}}}.}

Ettersom multisett er i en-til-en-korrespondanse med monomialer, er også antallet monomialer av grad $d$ i $n$ ubestemte. Dermed er serien ovenfor også Hilbert -serien til polynomringen ${\ displaystyle \ left (\! \! {n \ velg d} \! \! \ right)}$ ${\ displaystyle k [x_ {1}, \ ldots, x_ {n}].}$

Som et polynom i $n$ , er det definert for enhver kompleks verdi av $n$ . ${\ displaystyle \ left (\! \! {n \ velg d} \! \! \ right)}$

Generalisering og tilkobling til den negative binomiale serien

Multiplikasjonsformelen gjør at definisjonen av multiset -koeffisienter kan utvides ved å erstatte n med et vilkårlig tall α (negativt, reelt, komplekst):

{\ displaystyle \ left (\! \! {\ alpha \ select k} \! \! \ right) = {\ frac {\ alpha ^{\ overline {k}}} {k!}} = {\ frac { \ alpha (\ alpha +1) (\ alpha +2) \ cdots (\ alpha +k-1)} {k (k-1) (k-2) \ cdots 1}} \ quad {\ text {for} } k \ in \ mathbb {N} {\ text {og vilkårlig}} \ alfa.}

Med denne definisjonen har man en generalisering av den negative binomiske formelen (med en av variablene satt til 1), som begrunner å kalle de negative binomiske koeffisientene: ${\ displaystyle \ venstre (\! \! {\ alpha \ velg k} \! \! \ høyre)}$

{\ displaystyle (1-X)^{-\ alpha} = \ sum _ {k = 0}^{\ infty} \ venstre (\! \! {\ alpha \ velg k} \! \! \ høyre) X ^{k}.}

Denne Taylor -serien formelen er gyldig for alle komplekse tall α og X med | X | <1. Det kan også tolkes som en identitet av formelle kraftserier i X , der det faktisk kan tjene som definisjon av vilkårlige krefter i serier med konstant koeffisient lik 1; poenget er at med denne definisjonen holder alle identiteter som man forventer for eksponentiering , spesielt

{\ displaystyle (1-X)^{-\ alpha} (1-X)^{-\ beta} = (1-X)^{-(\ alpha +\ beta)} \ quad {\ text {og} } \ quad ((1-X)^{-\ alpha})^{-\ beta} = (1-X)^{-(-\ alpha \ beta)}}

,

og formler som disse kan brukes til å bevise identiteter for multiset -koeffisientene.

Hvis α er et ikke -positivt heltall n , er alle termer med k > - n null, og den uendelige serien blir en endelig sum. For andre verdier av α , inkludert positive heltall og rasjonelle tall , er serien imidlertid uendelig.

applikasjoner

Multisett har forskjellige applikasjoner. De begynner å bli grunnleggende i kombinatorikk . Multisets har blitt et viktig verktøy i teorien om relasjonsdatabaser , som ofte benytter synonym posen . For eksempel brukes multisett ofte for å implementere relasjoner i databasesystemer. Spesielt fungerer en tabell (uten en primærnøkkel) som et multisett, fordi den kan ha flere identiske poster. På samme måte opererer SQL på multisett og returnerer identiske poster. Vurder for eksempel "VELG navn fra student". I tilfelle det er flere poster med navnet "sara" i studenttabellen, vises alle. Det betyr at resultatsettet av SQL er et multisett. Hvis det var et sett, ble de repeterende rekordene i resultatsettet eliminert. En annen anvendelse av multiset er i modellering av multigrafer . I multigrafer kan det være flere kanter mellom to gitte hjørner. Som sådan er enheten som viser kanter et flersett, og ikke et sett.

Det er også andre applikasjoner. For eksempel brukte Richard Rado multisett som en enhet for å undersøke egenskapene til settfamilier. Han skrev: "Forestillingen om et sett tar ikke hensyn til flere forekomster av noen av dets medlemmer, og likevel er det nettopp denne typen informasjon som ofte er viktig. Vi trenger bare tenke på settet med røtter til et polynom f ( x ) eller spekteret til en lineær operatør. "

Generaliseringer

Ulike generaliseringer av multisett har blitt introdusert, studert og brukt for å løse problemer.

Virkelig verdsatte multisett (der mangfoldet av et element kan være et hvilket som helst reelt tall)

Dette virker greit, ettersom mange definisjoner for uklare sett og flersett er veldig like og kan overtas for virkelig verdifulle multisett ved å bare erstatte verdiområdet for den karakteristiske funksjonen [[0, 1] eller ℕ = {0, 1, 2 , 3, ...}) med ℝ ₀⁺ = [0, ∞). Imidlertid kan denne tilnærmingen ikke lett utvides for generaliserte uklare sett som bruker poset eller gitter i stedet for en enkel grad av medlemskap. Flere andre tilnærminger for uklare multisett har blitt utviklet som ikke har denne begrensningen.

Uklare multisett
Grove multisett
Hybridsett
Multisett hvis mangfold er en hvilken som helst virkelig verdsatt trinnfunksjon
Myke multisett
Myke uklare multisett
Navngitte sett (forening av alle generaliseringer av sett)

Se også

Frekvens (statistikk) som multiplisitet analog
Kvasi-sett
Settteori
Læringsmateriell relatert til Partitions of multisets på Wikiversity

Referanser

^ Hein, James L. (2003). Diskret matematikk . Jones & Bartlett Publishers. s. 29 -30. ISBN 0-7637-2210-3.
^ ^a ^b ^c Knuth, Donald E. (1998). Seminumeriske algoritmer . The Computer of Computer Programming . 2 (3. utg.). Addison Wesley . ISBN 0-201-89684-2.
^ Blizard, Wayne D (1989). "Multiset -teori" . Notre Dame Journal of Formal Logic . 30 (1): 36–66. doi : 10.1305/ndjfl/1093634995 .
^ ^a ^b ^c ^d ^e Blizard, Wayne D. (1991). "Utviklingen av multiset -teori" . Moderne logikk . 1 (4): 319–352.
^ Rulifson, JF; Derkson, JA; Waldinger, RJ (november 1972). QA4: En prosedyreberegning for intuitivt resonnement (teknisk rapport). SRI International. 73.
^ ^a ^b Singh, D .; Ibrahim, AM; Yohanna, T .; Singh, JN (2007). "En oversikt over applikasjonene til multisett". Novi Sad Journal of Mathematics . 37 (2): 73–92.
^ Angelelli, I. (1965). "Leibniz's misforståelse av Nizolius 'forestilling om' multitudo ' ". Notre Dame Journal of Formal Logic (6): 319–322.
^ Kircher, Athanasius (1650). Musurgia Universalis . Roma: Corbelletti.
^ Prestet, Jean (1675). Elemens des Mathematiques . Paris: André Pralard.
^ Wallis, John (1685). En avhandling om algebra . London: John Playford.
^ Dedekind, Richard (1888). Was sind und was sollen die Zahlen? . Braunschweig: Vieweg.
^ Syropoulos, Apostolos (2001). "Mathematics of Multisets". I Calude, CS; et al. (red.). Multiset -behandling: Synspunkter i matematikk, informatikk og molekylær databehandling . Springer-Verlag. s. 347–358.
^ Whitney, H. (1933). "Karakteristiske funksjoner og logikkens algebra". Annals of Mathematics . 34 : 405–414. doi : 10.2307/1968168 .
^ Monro, GP (1987). "Konseptet med Multiset". Zeitschrift für Mathematische Logik und Grundlagen der Mathematik . 33 : 171–178. doi : 10.1002/malq.19870330212 .
^ Syropoulos, Apostolos (2000). "Mathematics of Multisets" . Forelesningsnotater i informatikk . 2235 : 347--358. doi : 10.1007/3-540-45523-X_17 . Hentet 16. februar 2021 .
^ Aigner, M. (1979). Kombinatorisk teori . New York/Berlin: Springer Verlag.
^ Anderson, I. (1987). Kombinatorikk av endelige sett . Oxford: Clarendon Press.
^ Stanley, Richard P. (1997). Enumerative Combinatorics . 1 . Cambridge University Press. ISBN 0-521-55309-1.
^ Stanley, Richard P. (1999). Enumerative Combinatorics . 2 . Cambridge University Press. ISBN 0-521-56069-1.
^ Grumbach, S .; Milo, T (1996). "Mot håndterbare algebraer for poser" . Journal of Computer and System Sciences . 52 (3): 570–588. doi : 10.1006/jcss.1996.0042 .
^ Libkin, L .; Wong, L. (1994). "Noen egenskaper for spørrespråk for poser". Arbeidet med workshopen om databaseprogrammeringsspråk . Springer Verlag. s. 97–114.
^ Libkin, L .; Wong, L. (1995). "Om representasjon og spørring av ufullstendig informasjon i databaser med poser". Informasjonsbehandlingsbrev . 56 (4): 209–214. doi : 10.1016/0020-0190 (95) 00154-5 .
^ Blizard, Wayne D. (1989). "Ekte verdsatte multisett og uklare sett". Uklare sett og systemer . 33 : 77–97. doi : 10.1016/0165-0114 (89) 90218-2 .
^ Blizard, Wayne D. (1990). "Negativt medlemskap". Notre Dame Journal of Formal Logic . 31 (1): 346–368.
^ Yager, RR (1986). "Om teorien om poser". International Journal of General Systems . 13 : 23–37. doi : 10.1080/03081078608934952 .
^ Grzymala-Busse, J. (1987). "Lære av eksempler basert på grove multisett". Prosedyrer fra det andre internasjonale symposiet om metoder for intelligente systemer . Charlotte, North Carolina. s. 325–332.
^ Loeb, D. (1992). "Sett med et negativt antall elementer" . Fremskritt innen matematikk . 91 : 64–74. doi : 10.1016/0001-8708 (92) 90011-9 .
^ Miyamoto, S. (2001). "Uklar multisett og deres generaliseringer". Flersettbehandling . 2235 : 225–235.
^ Alkhazaleh, S .; Salleh, AR; Hassan, N. (2011). "Soft Multisets Theory". Anvendt matematisk vitenskap . 5 (72): 3561–3573.
^ Alkhazaleh, S .; Salleh, AR (2012). "Fuzzy Soft Multiset Theory". Abstrakt og anvendt analyse .
^ Burgin, Mark (1990). "Teori om navngitte sett som grunnlag for matematikk" . Strukturer i matematiske teorier . San Sebastian. s. 417–420.
^ Burgin, Mark (1992). "Om konseptet med et multisett innen kybernetikk". Kybernetikk og systemanalyse . 3 : 165–167.
^ Burgin, Mark (2004). "Unified Foundations of Mathematics". arXiv : matematikk/0403186 .
^ Burgin, Mark (2011). Teori om navngitte sett . Matematikkforskningsutvikling. Nova Science Pub Inc. ISBN 978-1-61122-788-8.

[1] Hein, James L. (2003). Diskret matematikk . Jones & Bartlett Publishers. s. 29 -30. ISBN 0-7637-2210-3.

[Knuth1998-2] Knuth, Donald E. (1998). Seminumeriske algoritmer . The Computer of Computer Programming . 2 (3. utg.). Addison Wesley . ISBN 0-201-89684-2.

[Blizard1989-3] Blizard, Wayne D (1989). "Multiset -teori" . Notre Dame Journal of Formal Logic . 30 (1): 36–66. doi : 10.1305/ndjfl/1093634995 .

[Blizard1991-4] Blizard, Wayne D. (1991). "Utviklingen av multiset -teori" . Moderne logikk . 1 (4): 319–352.

[Rulifson1972-5] Rulifson, JF; Derkson, JA; Waldinger, RJ (november 1972). QA4: En prosedyreberegning for intuitivt resonnement (teknisk rapport). SRI International. 73.

[Singh2007-6] Singh, D .; Ibrahim, AM; Yohanna, T .; Singh, JN (2007). "En oversikt over applikasjonene til multisett". Novi Sad Journal of Mathematics . 37 (2): 73–92.

[Angelelli1965-7] Angelelli, I. (1965). "Leibniz's misforståelse av Nizolius 'forestilling om' multitudo ' ". Notre Dame Journal of Formal Logic (6): 319–322.

[8] Kircher, Athanasius (1650). Musurgia Universalis . Roma: Corbelletti.

[9] Prestet, Jean (1675). Elemens des Mathematiques . Paris: André Pralard.

[10] Wallis, John (1685). En avhandling om algebra . London: John Playford.

[11] Dedekind, Richard (1888). Was sind und was sollen die Zahlen? . Braunschweig: Vieweg.

[12] Syropoulos, Apostolos (2001). "Mathematics of Multisets". I Calude, CS; et al. (red.). Multiset -behandling: Synspunkter i matematikk, informatikk og molekylær databehandling . Springer-Verlag. s. 347–358.

[Whitney-13] Whitney, H. (1933). "Karakteristiske funksjoner og logikkens algebra". Annals of Mathematics . 34 : 405–414. doi : 10.2307/1968168 .

[14] Monro, GP (1987). "Konseptet med Multiset". Zeitschrift für Mathematische Logik und Grundlagen der Mathematik . 33 : 171–178. doi : 10.1002/malq.19870330212 .

[15] Syropoulos, Apostolos (2000). "Mathematics of Multisets" . Forelesningsnotater i informatikk . 2235 : 347--358. doi : 10.1007/3-540-45523-X_17 . Hentet 16. februar 2021 .

[Aigner1979-16] Aigner, M. (1979). Kombinatorisk teori . New York/Berlin: Springer Verlag.

[Anderson1987-17] Anderson, I. (1987). Kombinatorikk av endelige sett . Oxford: Clarendon Press.

[Stanley1997-18] Stanley, Richard P. (1997). Enumerative Combinatorics . 1 . Cambridge University Press. ISBN 0-521-55309-1.

[Stanley1999-19] Stanley, Richard P. (1999). Enumerative Combinatorics . 2 . Cambridge University Press. ISBN 0-521-56069-1.

[GrumbachMilo1996-20] Grumbach, S .; Milo, T (1996). "Mot håndterbare algebraer for poser" . Journal of Computer and System Sciences . 52 (3): 570–588. doi : 10.1006/jcss.1996.0042 .

[LibkinWong1994-21] Libkin, L .; Wong, L. (1994). "Noen egenskaper for spørrespråk for poser". Arbeidet med workshopen om databaseprogrammeringsspråk . Springer Verlag. s. 97–114.

[LibkingWong1995-22] Libkin, L .; Wong, L. (1995). "Om representasjon og spørring av ufullstendig informasjon i databaser med poser". Informasjonsbehandlingsbrev . 56 (4): 209–214. doi : 10.1016/0020-0190 (95) 00154-5 .

[23] Blizard, Wayne D. (1989). "Ekte verdsatte multisett og uklare sett". Uklare sett og systemer . 33 : 77–97. doi : 10.1016/0165-0114 (89) 90218-2 .

[Blizard1990-24] Blizard, Wayne D. (1990). "Negativt medlemskap". Notre Dame Journal of Formal Logic . 31 (1): 346–368.

[Yager1986-25] Yager, RR (1986). "Om teorien om poser". International Journal of General Systems . 13 : 23–37. doi : 10.1080/03081078608934952 .

[Grzymala-Busse1987-26] Grzymala-Busse, J. (1987). "Lære av eksempler basert på grove multisett". Prosedyrer fra det andre internasjonale symposiet om metoder for intelligente systemer . Charlotte, North Carolina. s. 325–332.

[Loeb1992-27] Loeb, D. (1992). "Sett med et negativt antall elementer" . Fremskritt innen matematikk . 91 : 64–74. doi : 10.1016/0001-8708 (92) 90011-9 .

[Miyamoto2001-28] Miyamoto, S. (2001). "Uklar multisett og deres generaliseringer". Flersettbehandling . 2235 : 225–235.

[Alkhazaleh2011-29] Alkhazaleh, S .; Salleh, AR; Hassan, N. (2011). "Soft Multisets Theory". Anvendt matematisk vitenskap . 5 (72): 3561–3573.

[Alkhazaleh2012-30] Alkhazaleh, S .; Salleh, AR (2012). "Fuzzy Soft Multiset Theory". Abstrakt og anvendt analyse .

[31] Burgin, Mark (1990). "Teori om navngitte sett som grunnlag for matematikk" . Strukturer i matematiske teorier . San Sebastian. s. 417–420.

[32] Burgin, Mark (1992). "Om konseptet med et multisett innen kybernetikk". Kybernetikk og systemanalyse . 3 : 165–167.

[33] Burgin, Mark (2004). "Unified Foundations of Mathematics". arXiv : matematikk/0403186 .

[34] Burgin, Mark (2011). Teori om navngitte sett . Matematikkforskningsutvikling. Nova Science Pub Inc. ISBN 978-1-61122-788-8.

Languages

In other projects