Multihulk

Multihulk on hulgateooria mõiste, mis üldistab hulga mõistet. Multihulga erinevus tavalisest hulgast seisneb selles, et selle elemendid võivad esineda mitu korda. Multihulga elementide arvu, arvestades ka korduvaid elemente, nimetatakse selle suuruseks või võimsuseks. Seetõttu defineeritakse ka hulgatehted (ühend, ühisosa, vahe jne) multihulkade puhul eraldi.

Multihulga ideed on kaudselt kasutatud juba ammustest aegadest (Donald Knuth toob näiteks Bhāskara II 12. sajandist, kes uuris multihulkade permutatsioone), kuid mõiste ja termini kasutuselevõttu seostatakse Nicolaas de Bruijniga (1970ndad). Seda kasutatakse nii kombinatoorikas ja algebras kui ka matemaatika rakendustes (informaatikas, tehisintellektis, otsustusteoorias). Petri võrkude teoorias nimetatakse multihulka komplektiks. Eri valdkondades kasutatakse erinevaid tähistusi.

Informaatikas kasutatakse multihulki andmestruktuurina; seal nimetatakse neid ka ingliskeelsete terminitega multiset ja bag. Näiteks käsitleb andmebaasikeel SQL päringu tulemusi multihulkadena, st korduvaid ridu ei eemaldata, kui just ei kasutata märksõna DISTINCT.^[viide?]

Definitsioon

Ühe käsituse järgi on multihulk ${\displaystyle M}$ üle hulga ${\displaystyle A}$ (põhihulga ehk universumi) järjestatud paar ${\displaystyle (A,m)}$, kus ${\displaystyle m\colon A\to \mathbb {N} _{0}}$ on kujutus, mis seab igale hulga ${\displaystyle A}$ elemendile ${\displaystyle a}$ vastavusse naturaalarvu ${\displaystyle m(a)}$, mida nimetatakse selle elemendi kordsuseks. Arv ${\displaystyle M(x)}$ iga ${\displaystyle x\in A}$ korral näitab, mitu korda element ${\displaystyle x}$ multihulgas ${\displaystyle M}$ esineb. Selles käsitluses on ${\displaystyle A}$ elementide varu: elemendi kordsus võib olla ka null, mis tähendab, et see element multihulgas ei esine. Kõigi hulga ${\displaystyle A}$ multihulkade hulka võib tähistada ${\displaystyle \mathbb {N} _{0}^{A}}$. Edaspidi kasutatakse selle asemel lühemat tähistust ${\displaystyle \operatorname {MS} (A)}$.

Multihulga ${\displaystyle M}$ üle hulga ${\displaystyle A}$ kandja on nende ${\displaystyle A}$ elementide hulk, mille kordsus on positiivne:

${\displaystyle \operatorname {supp} (M)=\{x\in A\mid M(x)>0\}}$.

Teise käsituse järgi on multihulk defineeritud nii, et põhihulk ${\displaystyle A}$ langeb kandjaga kokku, nii et sellesse ei kuulu elemente kordsusega 0. Sel juhul on iga elemendi kordsus positiivne täisarv ja multihulk on defineeritud järjestatud paarina ${\displaystyle (A,m)}$, kus ${\displaystyle m\colon A\to \mathbb {N} ^{+}}$.

Multihulga mõistet võib üldistada, lubades elemendi kordsuseks ka lõpmatu kardinaalarvu. Sel juhul võib kordsus olla mistahes nullist erinev kardinaalarv; kui multihulga kandjaks võetakse täpselt selle elementide hulk, on ${\displaystyle m\colon A\to \operatorname {Card} \setminus \{0\}}$.

Lõpliku multihulga võimsus on kõigi selle elementide kordsuste summa ${\displaystyle \sum _{a\in A}m(a)}$.

Näited

Üks lihtsamaid näiteid on positiivse täisarvu algtegurite multihulk. Näiteks on arvu 120 kanooniline lahutus algteguriteks ${\displaystyle 120=2^{3}\cdot 3^{1}\cdot 5^{1}}$, nii et selle algtegurite multihulk on ${\displaystyle \{2,2,2,3,5\}}$. Arvu 1 algtegurite multihulk on tühi.

Teine näide on algebralise võrrandi lahendite multihulk, kus iga lahendit arvestatakse koos kordsusega. Näiteks on võrrandi ${\displaystyle x^{3}-5x^{2}+8x-4=(x-1)(x-2)^{2}=0}$ lahendite multihulk ${\displaystyle \{1,2,2\}}$.

Viited

Kirjandus

• James L. Peterson. Petri Net Theory and the Modeling of Systems, Prentice-Hall 1981.
• Wayne D. Blizard. Multiset theory. – Notre Dame Journal of Formal Logic, 1989, 30(1), lk 36–66.
• Wayne D. Blizard. The development of multiset theory. – Modern Logic, 1991, 1(4), lk 319–352.
• Knuth, Donald E. The Art of Computer Programming, kd 2: Seminumerical Algorithms. 3. trükk, Addison-Wesley 1997, lLõik 4.6.3, harjutus 19.
• Calude, C. S., Păun, Gh., Rozenberg, G., Salomaa, A. (toim). Multiset Processing: Mathematical, Computer Science, and Molecular Computing Points of View, Springer 2001.
• Алексей Борисович Петровский. Основные понятия теории мультимножеств, Москва: Эдиториал УРСС, 2002, ISBN 5-354-00166-8.
• А. Б. Петровский. Пространства множеств и мультимножеств, М.: Эдиториал УРСС 2003, ISBN 5-7262-0633-9.
• Kenneth P. Bogart. Combinatorics Through Guided Discovery, 2. trükk, 2004.
• Donald E. Knuth. The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations, Upper Saddle River, N.J.: Addison-Wesley 2005, ISBN 0-201-85393-0.
• Singh, D., Ibrahim, A. M., Yohanna, T., Singh, J. N. An overview of the applications of multisets. – Novi Sad Journal of Mathematics, 2007, 37(2), lk 73–92.
• Donald E. Knuth. The Art of Computer Programming, vol. 4A: Combinatorial Algorithms, Part 1. Addison-Wesley 2011, lõigud 7.2.1.2 ja 7.2.1.3.

Välislingid

• Nipkow, Tobias; Wenzel, Markus; Paulson, Lawrence C.; Voelker, Norbert; Popescu, Andrei; Blanchette, Jasmin; Traytel, Dmitriy; Fleury, Mathias; Desharnais, Martin. Theory Multiset, Isabelle/HOL Library, HOL/Library/Multiset.thy.