多重集合

数学における多重集合あるいはバッグは、集合に同じ値の元がいくつも含まれるとき、各元がそれぞれいくつ含まれるかという重複度を考え合わせた集合概念である。非順序対、非順序組 en ともいう文脈によっては集合のことを非順序対  などと呼ぶこともある。特に、math。

クヌースによれば、1970年代に最初に多重集合  という言葉を提案したのは、オランダ人数学者のニコラース・ホーバート・ド・ブラン  であるという。しかし、数学における多重集合の概念は、"multiset" という名称がつけられる90年以上も前にすでに使用が認められる。実際、1888年に発表されたリヒャルト・デデキントの有名な論文 "Was sind und was sollen die Zahlen?" において、実質的に多重集合の概念が用いられている。

1. 導入
-----

集合と多重集合の峻別のために、集合のように 波括弧 msetで囲む代わりに、二重波括弧 braces [[黒板太字 や角括弧 bracket あるいは中抜き波括弧 unicode. などで囲むこともある。

集合と多重集合と順序対は例えば次のような点で差異が認められる。//a// ≠ //b//}} として、

順序対: }} と }} とは順序三つ組として異なる。これらはもちろん }} とも異なる。
多重集合: unicode と unicode は多重集合として一致するが、unicode と unicode は多重集合として異なる。
集合: mset と mset と mset はいずれも同じ集合であるこのような外延的記法での例を挙げると、集合なのになぜか多重集合のようではないか、不自然だといったようなことを考える向きもあるだろうが、内包的記法が多用される数学の文脈ではこのような例は実際に頻繁に遭遇することであり、このように規約を設けることには便宜上も意味のあることである。簡単な例で言えば、偶数の集合 math。建前上は基本的に集合のみを扱い多重集合を扱わないというような文脈でも、「重複度を込めて」という注釈とともに一時的に多重集合が扱われることがある。たとえば、二次式 //x//² + //ax// + //b//}} に対して、1=Δ := //a//² − 4//b//}} とおき、その根の集合

を考えると、この集合の濃度は Δ ≠ 0}} のとき 2}} だが、1=Δ = 0}} のときは退化して 1}} になってしまう。これを 1=Δ = 0}} のときは 2 つの根がたまたま重なったものと考えて重複度 2}} を与えることにより、根は 1=Δ = 0}} のときも含めて常に 2}} 個であると考えることができる。この例は一般に、代数方程式論の基本定理の一つの表現「n}}-次方程式は必ず重複度まで込めてちょうど n}} 個の根を持つ」として述べることができる。同様の例として、複素解析函数に対する零点や極の位数あるいは曲線の接触の位数なども挙げられる。

またたとえば、自然数 n}} の素因数分解

は、自然数 n}} を素数全体の成す集合 P}} を台とする多重集合 }} として表示する方法を与えるものと解釈することができる。置換の巡回置換分解あるいは巡回置換型も同様である。

同様に、自然数 n}} の分割を考えることは、分割に現れる各整数 //k// }} の個数を重複度 //m//}} ととれば、自然数全体の成す集合 N}} を台とする多重集合 }} であって、重複度関数 m}} が次の二条件

を満たすようなものを一つ定めることに他ならない。ゆえに、分割数は、各自然数 n}} に対してこのような重複度関数 m}} のとり方が //p//}} 通りあることを示している。

2. 歴史
-----

Wayne Blizard は、“in ancient times, the number n was often represented by a collection of n strokes, tally marks, or units.”なる論法を以って、多重集合の起源はまさに数の起源にまで遡れるとする。これら、あるいは同様の対象の集まりは、棒・画線・単位が各々区別できないもの  と考えて多重集合になる。これは多重集合の概念が数学に取り入れられる以前から人々に暗に用いられていたことを示している。

そのような理由により多重集合は、この構造が必要とされるたびに何度も再発見され、異なる名称を以って文献に現れることとなる。例えば、Peterson はこれを bag と呼んでおり、その語は Cerf の影響によるものである。多重集合は他にも aggregate, heap, bunch, sample, weighted set, occurrence set, and fireset  などと呼ばれている。

ただ多重集合の概念が古代より暗に用いられていたと言っても、それらが明示的に調べられるようになるのはずっと後になってからのことである。多重集合の最初の研究として知られるのは1150年ごろ、インドの数学者バースカラ2世による、多重集合の順列に関するものである694}}。マリウス・ニゾリウス  の業績には多重集合の概念に関する別の先駆的言及が含まれる。Kircher は一つの元のみ重複する場合の多重集合の順列の数を求めた。ジャン・プルステは1675年に多重集合の順列に関する一般法則を著した。Wallis はこの法則をより詳細に説明している

明確な形で多重集合が現れるのはリヒャルト・デーデキントの手によるが、数学者が多重集合を定式化して明確な数学的対象としてその研究を始めたのは20世紀に入ってからである。

3. 定義
-----

X}} を全体集合とし、その任意の部分集合 A}} と X}} から非負整数全体の集合 N}} への写像 //m//: //X// → N}} で、[[関数の台 すなわち A}} に属さない元 x}} に対しては恒等的に 1=//m// = 0}} を満たすものの組 }} を、A}} を台集合とする多重集合といい、台集合 A}} の各元 a}} に対してその m}} による像 //m//}} を a}} の重複度という。紛れのおそれの無い場合、多重集合 }} をその台集合 A}} で表す。

非負整数値の重複度を持つ多重集合 }} は、項の値に重複のある列の集合として

のようにも記される。

たとえば、二つの文字 a, b}} について a}} を 2 個、b}} を 1 個含むような多重集合を考えると、この台集合は mset であり、各元の重複度 1= = 2),  = 1)}} を合わせた (mset が、同じ多重集合を台集合とその上の重複度という構造によって表したものとなる。またこれは簡単に mset とも記す。

新たに添字を導入して

などのように同じ元を区別すれば、通常の集合として扱うこともできる。また、各値に対して、同じ値を持つ項は有限個であるような族 (//bind に対して、同じ元からなる多重集合を mset で表すことがあるこの記法は数列を表す慣習的な記法 math。//

4. 多重集合の構成
----------

文字集合 Ω}} を固定したとき、Ω}} 上の有限多重集合は、Ω}} 上の文字列で文字の順番を自由に取り替えたものと同一視できるから、Ω}} 上の有限文字列全体が文字列の連接を演算として空文字列を単位元とする Ω}} の生成する自由モノイドとなるのと並行して、Ω}} の生成する自由可換モノイドと Ω}} 上の有限多重集合の全体とが同一視される。すなわち、Ω}} の元からなる有限多重集合は、Ω}} 上の自由モノイドのアーベル化の元である。

長さ n}} の有限列に n}}-次対称群を成分の入れ替えとして作用させるとき、この作用で割って得られる同値類あるいはその任意の代表元を多重集合と見做すことができる。

5. 多重集合の演算と重複度函数
----------------

多重集合 (//A//, //mind に対し、台集合 A}} の部分集合 B}} を台集合とする多重集合 (//B//, //mind で B}} の各元 b}} の重複度について

が成り立つとき、多重集合 (//B//, //mind は多重集合 (//A//, //mind の部分多重集合であるといい、(//B//, //mind で表す。//

また、多重集合に対する和、差、積、対称差などの概念が、通常の集合に関する和、差、積、対称差などに従って定義される。例えば、多重集合 A, B}} の和 //A// ∪ //B//}} は包含関係 ⊂}} を順序とする上限、積 //A// ∩ //B//}} は ⊂}} に関する下限である。多重集合の演算は台集合に対しては通常の集合演算として作用するが、その元の重複度については多少の注意を要する。

集合 X}} の各元の重複度を 1}} としたときの重複度関数は集合 X}} の指示関数である。有限集合の指示関数を数え上げ測度で積分したものは集合の基数をあたえるから、多重集合の元 a}} の重複度は、同じ値 a}} を持つ元を全てあわせた集合の指示関数の積分で得られる。指示関数が集合を定義するのと同様に、多重集合は重複度関数によって定義されると考えることができる。特に、多重集合の和、積、対称差などの重複度関数は、集合の指示関数が満たすのと同様の算術

に従う。また重複度函数の和 //m//ind を重複度函数に持つ多重集合を A}} と B}} との結合  あるいは直和と呼び

などで表す。すなわち

が成り立つ。特に台集合が交わりを持たないときは

と書ける。

6. 多重集合の数え上げ
------------

濃度 n}} の有限集合から元をとって作られる濃度 k}} の多重集合の総数は多重集合数  と呼ばれる。この数はしばしば二項係数と似せて ((su と書かれる

多重集合係数の値は

で明示的に与えることができる。ただし、二番目の式は二項係数としての表示であるであり、このような多重集合の総数は濃度 //n// + //k// − 1}} の集合内の k}}-元部分集合の総数に等しい。二項係数との類似性を見るために、上記の式の分子に上昇階乗冪を用いて ((su と書けば、二項係数が下降階乗冪を用いて (su と書かれることとの対比は明瞭である。

一般化された二項係数を

において n}} が非負整数とは限らず、負の整数、整数でない実数、実数でない複素数などとすることによって定義することができる。この意味において、n}}-元集合から得られる k}}-元部分多重集合の総数は

と書ける。

6.1. 漸化式
--------

多重集合係数に対して漸化式

を初期条件 ((su および ((su の下で与えることができる。この漸化式は以下のように組合せ論的に解釈することができる。

以下 bracketと書く。位数 0}} の多重集合は常にただ一つであり、また //n// =}} 0}} のときそれより位数の大きな多重集合は存在しないから、初期条件はこの解釈に適合する。さて //n//,//k// > 0}} のとき、集合 bracket の元からなる位数 k}} の多重集合が末尾の元 n}} を含むか含まないかに分けて考える。含むならば、n}} の一つはさておいて残りの//k// − 1}} 個の元を [//n//]}} から選んで多重集合を作りそこに n}} を加えればよいから、そのようなものは ((su 通りある。他方、含まないときは、末尾を除いた集合 bracket から k}}-元多重集合をつくることになるから、そのようなものは ((su 通りである。従って ((su が得られた。

7. 多項式表現
--------

集合 mset を単項式 //x//}} で表すと、その冪集合 mset は二項式 1 + //x//}} で表すことができる。集合 mset を単項式 xy}} に対応させればその冪集合 mset は多項式  =}} 1 + //x// + //y// + //xy//}} が対応する。同様に多重集合 mset を単項式 //x//exp に対応させれば、その冪多重集合mset は多項式 exp に対応する。単項式 xexp で表される多重集合の冪多重集合が

で表されることは、二項係数 (su が n}}-元集合から選んだ k}}-元の組合せの総数を数え上げることになる理由を説明するものである。

集合 mset に元をとる有限多重集合全体の成す無限集合 mset は形式冪級数 //S// =}} 1 + //x// + //x//exp で表され、形式解 //S// =}} exp に多重集合の集合としての意味を与えることができるが、中間表現である 1 − //x//}} は多重集合の集合として意味を成さない。同様に、単項式 xy}} で表される集合に値を持つ有限多重集合全体の成す無限集合は

で表され、単項式 //x//exp で表される多重集合から元をとって作られる有限多重集合全体の成す無限多重集合は //x// =}} //y//}} なる特別の場合として exp で表される。さらに進めて単項式 xexp に対応する多重集合に値をとる有限多重集合全体の成す無限多重集合は

である。これを「多重集合は濃度が負の集合」と形式的に説明することができる。負の二項係数 (su は n}}-元集合から元をとって得られる k}}-元多重集合の総数を数えるものである。

8. 累積母函数
--------

8.1. 非負整数の多重集合
--------------

非負整数 n}} を単項式 xexp で表すと、同様にして非負整数からなる有限多重集合を多項式 //f//}} で表すことができる。

これには累積母函数 1=//g// = log //f//(//e//exp を考えるのが簡便である。

多重集合の濃度は //e//exp.
累積母函数の導函数は .
多重集合の平均値 .
多重集合の分散 .例えば非負整数の多重集合 mset に対応する多項式は //f// =}} 3//x//exp であり、その累積母函数 //g// =}} log =}} exp などと計算できる。

ここに現れる数 (μ,σexp は各次数の累積率と呼ばれる。

非負整数全体の成す無限集合 mset は形式冪級数 1 + //x// + //x//exp で表され、平均値や標準偏差は定義されないが、累積母函数 //g// =}} −log =}} (//e//exp である。

8.2. 実数の多重集合
------------

実数からなる有限多重集合 //A// =}} mset は累積母函数

で表される。この表現は一意である。平均 μ}}, 標準偏差 σ}} を持つ n}} 個の実数からなる多重集合の累積母函数は //g// =}} log //n// + //μt// + 2exp で与えられ、その導函数は //g'}}// =}} μ + σexpとなる。

ただ一つの実数 k}} からなる集合 //k//}}} の累積母函数は //g// =}} //kt//}} であり、その導函数 //g'}}// =}} //k//}} はその数自身に一致する。この意味において、「実数からなる多重集合の累積母函数の導函数」は実数の概念を一般化するものである。

一つの実数 k}} のみを含む n}} 元の定値多重集合 mset は //g// =}} log //n// + //kt//}} が対応し、導函数は n}} に無関係に //g'}}// =}} //k//}} である。

8.3. 性質
-------

実数からなる二つの多重集合の元ごとの和の成す多重集合の累積母函数は、各々の多重集合の累積母函数の和に等しい:

元ごとの積の累積母函数

を計算する一般式は存在しないが、その特別の場合として定数倍は

となる。多重集合 1=2⋅//A// =}} mset は多重集合 1=2 × //A// =}} //A// + //A// =}} mset とは異なることに注意せよ。例えば、1=2 ⋅mset に対し、1=2 × mset である。//k// × //A//}} の累積母函数は

となる。標準正規分布は実数からなる巨大な多重集合の極限

と看做せる。この極限は実数の多重集合として意味を成すものではないが、極限をとる多重集合の累積母函数の導函数には意味を持たせることができて、その極限は

と矛盾なく定義される。定数項 //k//exp は微分で消え、省略した後続の項は極限をとれば消える。ゆえに平均 0}}, 標準偏差 1}} を持つ標準正規分布に対して、その累積母函数の導函数は //g'}}// =}} //t//}} となる。平均 μ}}, 標準偏差 σ}} の正規分布の累積母函数の導函数は //g'}}// =}} μ + σexp で与えられる。

9. 応用
-----

多重集合は様々な応用を持つ。多重集合はそのより高度な厳密さが希求されたことの結果として、組合せ論における主要な構造となり、現代組合せ論は集合ではなく多重集合に対する理論として発展した。多重集合はデータベースにおいて重要な道具となった。例えば多重集合はデータベースシステムにおける重要な関係としてしばしば用いられる。多重集合は計算機科学においても重要な役割を務める。

他にも応用はある。例えば、リチャード・ラドは多重集合を集合族の性質を調べる仕掛けとして用いた。ラドは「集合の概念はその各元がいくつ現れるかを考慮しないものだが、そうは言ってもこの手の情報はたびたび重要になる。多項式 f の根全体の成す集合とか線型作用素のスペクトルとかを考えるだけでもそれは分かるだろう。」と書いている。

10. 一般化
-------

重複度関数の値域を変更することにより、重複度を負の値も含めた整数値や実数値などに拡張して考えることができる。拡張された意味での多重集合に関する多重集合演算は、大抵の場合には非負整数値の場合の重複度関数の算術がそのまま成立するものとして演算後の重複度関数を定め、それによって特徴付けられる多重集合として定義される。

たとえば、ファジィ集合は、区間 0, 1}} に値をとる重複度函数を備えた多重集合と考えることもできる。この場合、ファジィ集合の帰属率函数が重複度函数に相当する。ただし、ある集合 //X// を全体集合として固定して、その部分集合となっているようなものだけにファジィ集合だけを考えるときは、//X// の任意の分割

に対して、

となるように帰属率函数に制限を加えて考えることも多い。

各種問題の研究と解法に応じて様々に異なる多重集合の一般化が存在する:

Fuzzy multisets
Rough multisets
Real-valued multisets 
Hybrid sets
where multiplicity is any real-valued step function
Soft multisets
Soft fuzzy multisets
Named set 

11. 注釈
------

12. 出典と参考文献
-----------

13. 関連項目
--------

集合
族 

14. 外部リンク
---------