多重集合

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

数学における多重集合(たじゅうしゅうごう、multiset)あるいはバッグbag; かばん)は、集合に同じ値の元がいくつも含まれるとき、各元がそれぞれいくつ含まれるかという重複度(じゅうふくど、multiplicity)を考え合わせた集合概念である。非順序対、非順序組 (unordered tuple) ともいう[! 1]

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

導入[編集]

集合と多重集合と順序対(あるいは組)は例えば次のような点で差異が認められる。ab として、

  • 順序対: (a, a, b) と (a, b, a) とは順序三つ組として異なる(各成分の現れる順番を変えてはいけない)。これらはもちろん (a, b) とも異なる。
  • 多重集合: {a, a, b} と {a, b, a} は多重集合として一致する(元の現れる順番は関係無い)が、{a, a, b} と {a, b} は多重集合として異なる(重複度が異なるなら多重集合としては異なる)。
  • 集合: {a, a, b} と {a, b, a} と {a, b} はいずれも同じ集合である(元の現れる順番は関係なく、また同じ元は何度現われてもひとつあることと同じ)[! 2]

建前上は基本的に集合のみを扱い多重集合を扱わないというような(しばしば初等的な)文脈でも、「重複度を込めて」という注釈とともに一時的に多重集合が扱われることがある。たとえば、二次式 x² + ax + b に対して、Δ := a² − 4b とおき、そのの集合

\lbrace x\mid x^2 + ax + b = 0\rbrace

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

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

n = 2^{m(2)}3^{m(3)}5^{m(5)}\cdots p^{m(p)}\cdots

(実際には n ごとに右辺に現れる素因子は有限個、つまり殆どの m(p) が 0 となる実質有限積である)は、自然数 n を素数全体の成す集合 P を台とする多重集合 (P, m) として表示する方法を与えるものと解釈することができる(素因数分解が積の順番の違いを除いて一意であるということが多重集合の性質に対応する)。置換の巡回置換分解あるいは巡回置換型も同様である。

もう少し複雑な例として、自然数の分割を考える。自然数nのある分割をDとし、分割Dにおける整数k(≦n)の重複度をmD,n(k)とすると、n

n = 1 \cdot m_{D,n}(1) + 2 \cdot m_{D,n}(2) + \cdots + n \cdot m_{D,n}(n)

と表現できる。この表現を、重複度関数の方を主体として考えてみる。nを固定したとき、自然数全体の成す集合 N を台とするある多重集合 (N, m)であって、重複度関数 mが次の2条件

 m(k) =0 \ (k > n)
 1 \cdot m(1) + 2 \cdot m(2) + \cdots + k \cdot m(k) + \cdots + n \cdot m(n) = n

を満たすようなものを1つ定めれば、多重集合 (N, m)はnのある分割を定めていることになる。 n を固定すると、nの分割を与えるような重複度関数 m のとり方は複数ある(その総数は分割関数 p(n) で与えられる)から、このような多重集合(N, m)もp(n) 個存在し、それらの多重集合による集合族nの分割に対応する。

言い換えれば、N を台集合とする多重集合全体から自然数全体の成す集合 N へのある種の写像 P による nN の逆像 P−1(n) として自然数 n の分割を解釈することができる。

定義[編集]

X を全体集合とし、その任意の部分集合 AA から非負整数全体の集合 N への写像 m: AN で、Aに属さないの元 x に対しては恒等的に m(x) = 0 を満たすものの組 (A, m) を、A を台集合とする(非負整数値の重複度関数 (multiplicity function) m を持つ)多重集合といい、台集合 A の各元 a に対してその m による像 m(a) を a重複度という。紛れのおそれの無い場合、多重集合 (A, m) をその台集合 A で表す。

非負整数値の重複度を持つ多重集合 (A, m) は、項の値に重複のあるの集合として

\{(\overbrace{a_1,a_1,\ldots,a_1}^{m(a_1){\rm\ times}}),(
\overbrace{a_2,a_2,\ldots,a_2}^{m(a_2){\rm\ times}}),\ldots\}

のようにも記される(パーレンはしばしば省略される)。

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

新たに添字を導入して

\{a_1^{(1)},a_1^{(2)},\ldots,a_1^{(m(a_1))},
 a_2^{(1)},a_2^{(2)},\ldots,a_2^{(m(a_2))},\ldots\}

などのように同じ元を区別すれば、通常の集合として扱うこともできる。また、各値に対して、同じ値を持つ項は有限個であるような (bi)iI に対して、同じ元からなる多重集合を {bi}iI で表すことがある[! 4]

多重集合の構成[編集]

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

長さ n の有限列(n-組)に n-次対称群を成分の(番号の)入れ替えとして作用させるとき、この作用で割って得られる同値類(軌道)あるいはその任意の代表元を(重複度まで込めた濃度が n の)多重集合と見做すことができる。

多重集合の演算と重複度函数[編集]

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

m_B(b) \leq m_A(b)

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

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

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

m_{A\cap B}(x) = \min\{m_A(x),m_B(x)\}(=: (m_A \wedge m_B)(x)),
m_{A\cup B}(x) = \max\{m_A(x),m_B(x)\}(=: (m_A \vee m_B)(x)),
m_{A\triangle B}(x) = |m_A(x) - m_B(x)|

に従う。また重複度函数の和 mA + mB を重複度函数に持つ多重集合を AB との結合 (join) あるいは直和(非交和、sum)と呼び

A\sqcup B, A\uplus B

などで表す(非交和と呼ぶことがあるにもかかわらず、台集合として AB = ∅ であることは必要でないことに注意。これは台集合の交わりに属する元であっても、それらはその重複度のために、何れの台集合に由来する元であるかの区別を受けるためである)。すなわち

m_{A\sqcup B}(x) = m_A(x) + m_B(x)

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

m_{A\sqcup B}(x) = \max\{m_A(x),m_B(x)\} = \begin{cases}m_A(x) & (x\in A)\\ m_B(x) & (x\in B)\end{cases}

と書ける。

一般化[編集]

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

たとえば、ファジィ集合(曖昧集合、確率的集合)は、区間 [0, 1] に値をとる重複度函数を備えた多重集合と考えることもできる。この場合、ファジィ集合の帰属率函数(メンバシップ函数)が重複度函数に相当する。ただし、ある集合 X を全体集合として固定して、その部分集合となっているようなものだけにファジィ集合だけを考えるときは、(確率的な解釈を与えるため)X の任意の分割

X = \sum_{\lambda\in\Lambda}A_\lambda

に対して、

(\mu_X =) \sum_{\lambda\in\Lambda}\mu_{A_\lambda} \equiv 1

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

注釈[編集]

  1. ^ 文脈によっては集合のことを非順序対 (unordered pair) などと呼ぶこともある。特に、xy のときの {x, y} を非順序対と呼ぶときは、これが集合であると理解しても多重集合であると理解しても論理的には同じである(x = y のときは差異が認められる)。
  2. ^ このような外延的記法での例を挙げると、集合なのになぜか多重集合のようではないか、不自然だといったようなことを考える向きもあるだろうが、内包的記法が多用される数学の文脈では(それを外延的に書き直すと)このような例は実際に頻繁に遭遇することであり、このように規約を設けることには便宜上も意味のあることである。簡単な例で言えば、偶数の集合 2Z = {2n | n は整数} と 4 の倍数の集合 4Z = {4n | n は整数} の和集合はもちろん偶数の集合だが、2Z ∪ 4Z = {x | x = 2n または x = 4m (n, m は整数)} の右辺には 4 の倍数が 2-回ずつ現れている。
  3. ^ 文脈によっては、「解(の個数)」と言ったときは集合として、「根(の個数)」と言ったときは多重集合として、それぞれ考えるといったような便宜上の規約が設けられていることがあるので注意。
  4. ^ この記法は(特に添字集合が明らかであるとして省略するとき)数列を表す慣習的な記法 {an} と紛らわしい。

出典と参考文献[編集]

  1. ^ Knuth, Donald E. (1998). The Art of Computer Programming – Vol. 2: Seminumerical Algorithms (3rd edition ed.). Addison Wesley. pp. 694. ISBN 0201896842.  クヌースは同書で、多重集合に対して提案された他の名前(例えば,リスト(list)、まとまり(bunch)、バッグ(bag)、堆積(heap)、標本(sample)、重みつき集合(weighted set)、コレクション(collection)、組(suite).など)も提示している。
  2. ^ a b Wayne D. Blizard (1991). “The development of multiset theory” (PDF). The Review of Modern Logic 1 (4): 319-352. MathSciNet: MR1112352, Zbl: 0744.03054. http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.rml/1204834739 2010年11月26日閲覧。.  多重集合の歴史に関するサーベイ論文である。
  3. ^ デーデキント; 河野伊三郎 (訳) (1967). 数について. 岩波書店. pp. 139. ISBN 4003392418. 
  4. ^ Syropoulos, Apostolos (2001). C. S. Calude et al.. ed. “Mathematics of Multisets” (PDF). WMP '00 Proceedings of the Workshop on Multiset Processing: Mathematical, Multiset Processing, Mathematical, Computer Science, and Molecular Computing Points of View (Springer-Verlag): 347–358. ISBN: 3-540-43063-6. http://citeseerx.ksu.edu.sa/viewdoc/summary?doi=10.1.1.58.5406 2010年11月26日閲覧。. 

関連項目[編集]