集合 列 多重集合 違い
TL;DR
集合と列と多重集合は全て異なります。 これらみっつの差やそれぞれの記法について理解している人は、この記事を読む必要はありません。
- 集合は「何が含まれているか」のみを考慮し、「いくつ含まれているか」や「どのような順序で含まれているか」は無視します。$\lbrace 0, 1, 2, \dots \rbrace$ のように書きます。
- 列は「どのような順序で含まれているか」までのすべてを考慮します。$(0, 1, 2, \dots)$ のように書きます。
- 多重集合は「いくつ含まれているか」も考慮しますが、「どのような順序で含まれているか」については無視します。統一された記法はありません。
集合とは
集合とは、ものの集まりであって「何が所属しているのかが明確に定義されたもの」のことです12。 たとえば「整数全体からなる集まり」「$3$ 以上の自然数の全体からなる集まり」などは集合です。 「大きな整数の全体からなる集まり」などは何が所属しているのかが曖昧であるため集合ではありません。 「自然数の全体を昇順に並べたもの」は順序が重要なものであるため集合ではありません。
集合は「何が所属しているのか」だけを考えるものであり、「どういう順序で所属しているのか」「それぞれの要素が何個ずつ所属しているのか」などは考えません。たとえば「正整数全体からなる集合 $X$」と「$1$ の倍数の全体と $2$ の倍数の全体と $3$ の倍数の全体をすべて併せてできる集合 $Y$」「$3$ の倍数の全体と $2$ の倍数の全体と $1$ の倍数の全体をすべて併せてできる集合 $Y$」は同じ集合です。自然数 $6$ は $1$ の倍数でも $2$ の倍数でも $3$ の倍数でもありますが「$6$ は $Y$ に $3$ 回分だけ所属している」とは考えません。
集合は通常のプログラミングにおいても現われます。
C++ の std::set<T>
や Python の set
は集合を表現する型です。
記法について
数学では、集合は波括弧 $\lbrace, \rbrace$ を用いて書かれます。 集合の書き方には、所属する要素をすべて列挙して書き表す方法 (外延表記) と、どのような要素が所属するかの条件により書き表す方法 (内包表記) とがあります。
外延表記は、含まれる要素をカンマ $,$ で区切って並べて書きます。 たとえばみっつの要素 $a, b, c$ からなる集合は $\lbrace a, b, c \rbrace$ と書かれます。 無限個の要素を含む場合も同様です。 たとえばすべての自然数からなる集合は $\lbrace 0, 1, 2, \dots \rbrace$ と書かれます。 空集合 (要素をひとつも含まない集合) は $\lbrace \rbrace$ や $\emptyset$ や $\varnothing$ と書かれます。なおこの空集合の記号 $\emptyset$, $\varnothing$ はファイ $\phi, \varphi$ とは異なる記号です。
外延表記において、書かれる要素がすべて異なっている必要はありません。 たとえば $X = \lbrace x, y \rbrace$ という集合の要素数は、$x \ne y$ のときは $2$ ですが $x = y$ のときは $1$ です。 通常は $\lbrace 0, 0 \rbrace$ のように明らかに同じ要素が書かれることはありません ($\lbrace 0 \rbrace$ と書けば十分なので) が、記法としては間違いではありません。
内包表記は、含まれる要素を表す変数 $x$ (あるいは $y$ や $z$ など) を明記し、それが満たすべき条件 $\varphi(x)$ を縦棒 $\mid$ (あるいはコロン $:$) の横に書きます。 たとえば自然数であって $99$ より大きいもの全体からなる集合は $\lbrace x \in \mathbb{N} \mid x \gt 99 \rbrace$ と書かれます。 一般に「$A$ であるような $x$ であって条件 $\varphi(x)$ を満たすものの全体からなる集合」は $\lbrace x \in A \mid \varphi(x) \rbrace$ と書かれます。 より崩した書き方として、縦棒の左側に式が書かれることもあります。たとえば「$A$ に含まれる要素を $2$ 倍して得られるようなものの全体」は $\lbrace 2x \mid x \in A \rbrace$ と書かれます。
列とは
列とは、ものの集まりであって「ものを一直線上に並べてできるもの」のことです3。 たとえば「自然数を小さい方から大きい方へ順番に並べてできるもの」「$a$ を $7$ 個並べてできるもの」などは列です。 「自然数全体からなる集まり」などはどのような順番で並んでいるのかが曖昧であるため列ではありません。 「大きな整数の全体を昇順に並べたもの」などは何が並べられているのかが曖昧であるため列ではありません。
列はその要素が数の場合には数列とも呼ばれます。 列は長さが $2$ であるとき対とも呼ばれます4。 列は長さが $n$ であるとき $n$-組とも呼ばれます4。
列は通常のプログラミングにおいても現われます。
C++ の std::vector<T>
や Python の list
は列を表現する型です。
記法について
数学では、列は丸括弧 $(, )$ を用いて書かれます。 集合の場合と同様に、含まれる要素を順番に書いて表す方法 (外延表記) と、$i$ 番目の要素がどのようであるかの式を使って書き表す方法 (内包表記) とがあります。
外延表記は、含まれる要素をカンマ $,$ で区切って並べて書きます。 たとえば、みっつの要素 $a, b, c$ をこの順番で並べてできる列は $(a, b, c)$ と書かれます。 無限列 (長さが無限の列) は $(a_0, a_1, a_2, \dots)$ のように書かれます。 空列 (長さが $0$ の列) は $()$ と書かれます。イプシロン $\epsilon$ で書かれることもあります。
列そのものを対象として考える (たとえば、ある条件を満たす列の全体からなる集合を考えるなど) ことがない場合などにおいては、列は丸括弧を伴なわずに書かれることもあります。 しかし、文脈なしに単に「与えられた列 $A_1, A_2, A_3, \dots, A_K$ に対し……」などと書かれているときは、「長さ $K$ の列 $A = (A_1, A_2, A_3, \dots, A_K)$ が与えられる」のか「列 $A_1$ と列 $A_2$ と列 $A_3$ と……列 $A_K$ という $K$ 個の列が与えられる」のかが曖昧であることに注意する必要があります。
内包表記にはいろいろな書き方があります。 最も丁寧な場合は、集合と同様に $(a_i \mid i \in \mathbb{N})$ のように書かれます。 たとえば「それぞれの $i \ge 0$ について $i$ 番目の要素 $a_i$ が $3i + 2$ に等しいような列」は $(3i + 2 \mid i \in \mathbb{N})$ と書かれます。 しかしたいていはより省略され $(a_i) _ {i \in \mathbb{N}}$ や $(a_i) _ {i = 0, 1, 2, \dots}$ あるいは単に $(a_i) _ i$ や $(a_i)$ と書かれます。
列を内包的に表記する場合は、まれに $\lbrace a_i \rbrace$ と書かれることもあります。 しかし外延的に表記する場合に $\lbrace, \rbrace$ が使われることはほぼありません5。
多重集合とは
多重集合とは、要素がそれぞれ何個含まれるかの情報を含めて考える集合のような集まりです。 数学ではあまり出現しません。 たとえば「$a$ を $2$ 個と $b$ を $3$ 個含みそれ以外のものは含まないような集まり」は多重集合です。 たとえば「$a$ を $2$ 個と $b$ を $3$ 個を $b, a, b, a, b$ という順番で含みそれ以外は含まないようなもの」は並べられた順番が重要であるので多重集合ではありません。
多重集合は通常のプログラミングにおいても現われます。
C++ の std::multiset<T>
は多重集合を表現する型です。
記法について
数学では、多重集合の記法は統一されていません。 以下のような様々な記法が用いられているようです。 どれを用いる場合も「それが多重集合を表していること」を注意してから使うべきでしょう。
- (多重集合であることを明記した上で) 波括弧を使う (例: $\lbrace a, a, b, c \rbrace$)
- 角括弧を使う (例: $\lbrack a, a, b, c \rbrack$)
- 二重波括弧を使う (例: $\lbrace\mskip-6mu\lbrace a, a, b, c \rbrace\mskip-6mu\rbrace$)
- 中抜き波括弧を使う (例: $\lbrace\mskip-3mu\vert a, a, b, c \vert\mskip-3mu\rbrace$)
- 重複度をコロンを使って明記する (例: $\lbrace a: 2, b: 1, c: 1 \rbrace$)
- 重複度を上付き数字で明記する (例: $\lbrace a^2, b^1, c^1 \rbrace$)
- 重複度関数のグラフとして書く (例: $\lbrace (a, 2), (b, 1), (c, 1) \rbrace$)
これらみっつの関係について
- 要素に重複がなくソートされている列と集合は同一視できます。
- ソートされている列と多重集合は同一視できます。
- 要素を高々ひとつまでしか含まない多重集合は集合と同一視できます。
これらみっつと関数の関係について
- 関数 $f$ と関数 $f$ のグラフは同一視できます。関数のグラフは集合です。
- 全体集合が固定されているとき、与えられた要素 $x$ に対しそれが $A$ に含まれているかどうかの情報を計算する関数 $f$ (つまり $x \in A$ なら $f(x) = 1$ でそうでないなら $f(x) = 0$) と集合 $A$ は同一視できます。
- 添字 $i$ から要素 $a_i$ への関数 $f : i \mapsto a_i$ と列 $(a_i) _ i$ は同一視できます。
- 全体集合が固定されているとき、与えられた要素 $x$ に対しそれが $B$ に何個含まれているかを計算する関数 $f$ と多重集合 $B$ は同一視できます。
演習問題
Q. 以下の等式について、それぞれ真であるか偽であるかを判定せよ。ただし (7.), (8.) の $\lbrace\mskip-6mu\lbrace, \rbrace\mskip-6mu\rbrace$ は多重集合を意味する。
- $\lbrace 1, 2, 3 \rbrace = \lbrace 3, 2, 1 \rbrace$
- $\lbrace 1, 2, 3 \rbrace = \lbrace 1, 1, 2, 3 \rbrace$
- $\lbrace x \in \mathbb{N} \mid x \text{は偶数} \rbrace = \lbrace 2 y \mid y \in \mathbb{N} \rbrace$
- $(1, 2, 3) = (3, 2, 1)$
- $(1, 2, 3) = (1, 1, 2, 3)$
- $(1, 3, 5, 7, 9, 11, \dots, 99) = (2 i + 1 \mid i \in \mathbb{N})$
- $\lbrace\mskip-6mu\lbrace 1, 2, 3 \rbrace\mskip-6mu\rbrace = \lbrace\mskip-6mu\lbrace 3, 2, 1 \rbrace\mskip-6mu\rbrace$
- $\lbrace\mskip-6mu\lbrace 1, 2, 3 \rbrace\mskip-6mu\rbrace = \lbrace\mskip-6mu\lbrace 1, 1, 2, 3 \rbrace\mskip-6mu\rbrace$
A. それぞれ、真、真、真、偽、偽、偽、真、偽 (反転してください)
リンク
注釈
-
(あるひとつの) 厳密な定義を知りたい人は公理的集合論をやってください。 ↩
-
なお「自分自身を含まない集合の全体の集まり $R$」「すべての集合の集まり $V$」「すべての群の集まり」のような大きすぎる集まりは (通常は) 集合にはなりません。これらが集合だと仮定すると矛盾が示せてしまうためです。このあたりについて知りたければ “proper class” とかで調べてください。 ↩
-
列の長さが無限であるとき「一直線上に並べる」というのはすこし曖昧になります。整数の全体の順序 (両方向に無限に伸びている) とか有理数の全体の順序 (どの $2$ 点をとってもその間に点がある) などもある意味で「一直線上に並んでいる」と言えます。難しいので省略しますが、こういう場合に興味がある人は順序数について調べてみましょう。 ↩
-
C 言語では配列は
int ary[] = { 0, 1, 2 };
のように書かかれます。C 言語系列の言語しか使えないプログラマの書いた数学風の文章では、C 言語からの連想により列が $\lbrace 0, 1, 2 \rbrace$ と書かれていることがあります。 ↩