集合族
概要
集合族（family of sets）とは、添字集合 $I$ の各元 $i$ に集合 $A_i$ を対応させた集まり $(A_i)_{i\in I}$、すなわち $I$ を定義域とする写像である。写像として扱うので、同じ集合が異なる添字に重複して現れる情報を保持でき、冪集合の部分集合としての部分集合系と区別される。和 $\bigcup_{i\in I}A_i$ と交叉 $\bigcap_{i\in I}A_i$ は De Morgan の法則や逆像と両立し、全射による添字の付け替えで変わらない。各 $i$ から添字を一つずつ選ぶ写像で和と交叉を入れ替える一般分配律は、選択公理と同値である。
定義
多数の集合を一度に扱うには、それぞれを区別する添字を付ける。有限個の集合、集合の列、開被覆、部分群の集まりなどは、すべて同じ「集合族」の記法で表せる。
集合 $I$ の各元 $i$ に集合 $A_i$ を対応させたもの
$$
(A_i)_{i\in I}
$$
を集合族(family of sets)という。$I$ を添字集合、$i$ を添字という。厳密には、集合族は $i\mapsto A_i$ という写像である。
すべての $A_i$ が一つの集合 $X$ の部分集合であるとき、$(A_i)_{i\in I}$ を $X$ の部分集合族という。この場合、集合族は写像 $I\to\mathcal{P}(X)$ と同じデータである。
集合 $X$ に対し、冪集合 $\mathcal{P}(X)$ の部分集合
$$
\mathcal{A}\subset\mathcal{P}(X)
$$
を $X$ 上の部分集合系(set system)という。
文献によっては部分集合系も集合族と呼び、二つを区別しない。本記事では、集合族を写像 $I\to\mathcal{P}(X)$、部分集合系をその値の集合 $\{A_i\mid i\in I\}$ として区別する。重複や添字を保持するときは $(A_i)_{i\in I}$、値だけを見るときは $\{A_i\mid i\in I\}$ と書く。どの部分集合系 $\mathcal A$ も、$\mathcal A$ 自身を添字集合とし $A\mapsto A$ とする族 $(A)_{A\in\mathcal A}$ として表せる（HJ99 Chapter 2, Exercise 3.8, p. 28）。
集合族 $(A_i)_{i\in I}$ に対して
$$
\bigcup_{i\in I}A_i
=\{x\mid \text{ある }i\in I\text{ について }x\in A_i\}
$$
をその和または合併という。
さらに各 $A_i$ が共通の全体集合 $X$ の部分集合であるとき
$$
\bigcap_{i\in I}A_i
=\{x\in X\mid \text{すべての }i\in I\text{ について }x\in A_i\}
$$
をその交叉または共通部分という。
$I=\emptyset$ の場合、和は $\emptyset$ である。交叉は全体集合を指定しなければ一意に定まらないが、$A_i\subset X$ という文脈では空な族の交叉を $X$ とする。和の存在は、集合の集まりの和を保証する和集合の公理から従う（HJ99 Chapter 1 §3, p. 9、族の和の記法は Chapter 2 §3, p. 27）。
直感
集合族を写像として定義する理由は、値が同じでも添字が違えば別の項として記録できるからである。たとえば $A_1=A_2$ であっても、列 $(A_1,A_2,A_3)$ では二つの段階が存在する。一方、値の集合 $\{A_1,A_2,A_3\}$ では重複が消える。
和の定義に現れるのは存在量化「ある $i$」であり、交叉の定義に現れるのは全称量化「すべての $i$」である。この違いから、空な添字集合に対する和は空集合、固定した $X$ の中での交叉は $X$ になる。以下の性質の多くは、この二つの量化の性質を集合の言葉に写したものである。
二つの集合の和と共通部分そのものの性質は 和集合 と 共通部分 で扱う。本記事では、添字を保持した族としての扱い、すなわち添字の付け替え、二重の添字、選択関数を使う分配律、互いに素な族を中心に述べる。
例と反例
$X=\{1,2,3,4\}$ とし
$$
A_1=\{1,2\},\qquad A_2=\{2,3\},\qquad A_3=\{2,4\}
$$
とする。すると
$$
\bigcup_{i=1}^{3}A_i=X,\qquad
\bigcap_{i=1}^{3}A_i=\{2\}
$$
である。
$n\geq1$ に対して $A_n=(-1/n,1/n)$ とおくと、$(A_n)_{n\geq1}$ は $A_{n+1}\subset A_n$ を満たす減少する集合族である。このとき
$$
\bigcup_{n\geq1}A_n=(-1,1),\qquad
\bigcap_{n\geq1}A_n=\{0\}
$$
である。各 $A_n$ は通常の位相空間 $\mathbb{R}$ で開集合だが、無限交叉は開集合とは限らない。
位相空間 $X$ の開集合族 $(U_i)_{i\in I}$ が
$$
X=\bigcup_{i\in I}U_i
$$
を満たすとき、これを $X$ の開被覆という。同じ開集合が異なる添字で現れてもよい。有限部分被覆を選べるかどうかを論じるとき、添字集合を保持する見方が便利である。
$I=\{1,2\}$、$J_1=J_2=\{1,2\}$ とし、$\mathbb R$ の部分集合を
$$
A_{1,1}=[0,1],\quad A_{1,2}=[2,3],\quad A_{2,1}=[0,2],\quad A_{2,2}=[5,6]
$$
とする。$\bigcup_{j}A_{1,j}=[0,1]\cup[2,3]$、$\bigcup_jA_{2,j}=[0,2]\cup[5,6]$ だから、その交叉は $[0,1]\cup\{2\}$ である。一方、各 $i$ に $j$ を一つずつ選ぶ写像 $\varphi\colon\{1,2\}\to\{1,2\}$ は 4 通りあり、$A_{1,\varphi(1)}\cap A_{2,\varphi(2)}$ は順に $[0,1]$、$\emptyset$、$\{2\}$、$\emptyset$ である。その和も $[0,1]\cup\{2\}$ になり、下の定理「一般分配律」の等式の小さな場合になっている。
$I=\{1,2,3\}$、$A_1=A_2=\emptyset$、$A_3=\{0\}$ とする。添字付き族 $(A_i)_{i\in I}$ には三つの項があるが、値の集合は
$$
\{A_i\mid i\in I\}=\{\emptyset,\{0\}\}
$$
という二元集合である。「添字付き族には $|I|$ 個の相異なる集合が現れる」という含意は成り立たない。破れているのは写像 $i\mapsto A_i$ の単射性である。
基本性質
$X$ の部分集合族 $(A_i)_{i\in I}$ に対し
$$
X\setminus\bigcup_{i\in I}A_i
=\bigcap_{i\in I}(X\setminus A_i),
$$
$$
X\setminus\bigcap_{i\in I}A_i
=\bigcup_{i\in I}(X\setminus A_i)
$$
が成り立つ。
$x\in X$ を取る。$x\notin\bigcup_iA_i$ であることは、$x\in A_i$ となる $i$ が存在しないこと、すなわちすべての $i\in I$ について $x\notin A_i$ であることと同値である。これは $x\in\bigcap_i(X\setminus A_i)$ と同値なので第一式を得る。
また $x\notin\bigcap_iA_i$ であることは、すべての $i$ について $x\in A_i$ であることが成り立たないこと、すなわちある $i\in I$ について $x\notin A_i$ であることと同値である。これは $x\in\bigcup_i(X\setminus A_i)$ と同値なので第二式を得る。$I=\emptyset$ のときも、左辺は $X\setminus\emptyset=X$ と $X\setminus X=\emptyset$、右辺は空な族の交叉 $X$ と和 $\emptyset$ で一致する。$\blacksquare$
各 $i\in I$ に対して添字集合 $J_i$ と集合族 $(A_{i,j})_{j\in J_i}$ があるとき
$$
\bigcup_{i\in I}\left(\bigcup_{j\in J_i}A_{i,j}\right)
=
\bigcup_{(i,j)\in K}A_{i,j},
\qquad
K=\{(i,j)\mid i\in I,\ j\in J_i\}
$$
が成り立つ。
左辺に $x$ が属することは、ある $i\in I$ が存在して $x\in\bigcup_{j\in J_i}A_{i,j}$ となることと同値である。さらにこれは、ある $i\in I$ とある $j\in J_i$ が存在して $x\in A_{i,j}$ となることと同値である。この条件は、ある $(i,j)\in K$ について $x\in A_{i,j}$ となること、すなわち右辺に $x$ が属することそのものである。外延性により両辺は等しい。$\blacksquare$
交叉についても、すべての $A_{i,j}$ が $X$ の部分集合なら、同じ論法で $\bigcap_{i\in I}\bigcap_{j\in J_i}A_{i,j}=\bigcap_{(i,j)\in K}A_{i,j}$ が成り立つ。これは結合律の一般形である（HJ99 Chapter 2, Exercise 3.10, p. 28）。
写像 $f\colon X\to Y$ の逆像が $Y$ の部分集合族の和と交叉を保つこと（空な族では両辺 $\emptyset$ と $X$）は 逆像 の命題「逆像は任意の和と共通部分を保存する」にある。像は任意和を保つが、一般に交叉を保たない。たとえば定値写像 $f\colon\{1,2\}\to\{0\}$ と $A_1=\{1\}$、$A_2=\{2\}$ に対して、$f(A_1\cap A_2)=\emptyset$ だが $f(A_1)\cap f(A_2)=\{0\}$ である。$f$ が単射なら、任意の空でない族について $f(\bigcap_iA_i)=\bigcap_if(A_i)$ が成り立つ（HJ99 Chapter 2, Exercise 3.12, p. 29）。実際、$y\in\bigcap_if(A_i)$ なら各 $i$ について $f(x_i)=y$ となる $x_i\in A_i$ があり、単射性からこれらはすべて同じ元 $x$ に等しいので、$x\in\bigcap_iA_i$ かつ $y=f(x)$ である。逆の包含は単射性なしに成り立つ。
添字の付け替え
同じ集合の集まりを別の添字集合で数え直すことはよくある。たとえば開被覆の添字を部分集合に制限したり、列を並べ替えたりする。和と交叉がどこまで変わらないかは、付け替えの写像が全射かどうかで決まる。
$(A_i)_{i\in I}$ を $X$ の部分集合族、$\sigma\colon J\to I$ を写像とし、付け替えた族 $(A_{\sigma(j)})_{j\in J}$ を考える。
- $\bigcup_{j\in J}A_{\sigma(j)}\subset\bigcup_{i\in I}A_i$ かつ $\bigcap_{j\in J}A_{\sigma(j)}\supset\bigcap_{i\in I}A_i$ である。
- $\sigma$ が全射なら、どちらも等号が成り立つ。
- $x\in\bigcup_jA_{\sigma(j)}$ なら、ある $j$ について $x\in A_{\sigma(j)}$ であり、$i=\sigma(j)$ とおけば $x\in A_i$ である。また $x\in\bigcap_iA_i$ なら、任意の $j$ について $\sigma(j)\in I$ だから $x\in A_{\sigma(j)}$ である。
- $\sigma$ が全射とする。$x\in\bigcup_iA_i$ なら、ある $i$ について $x\in A_i$ であり、$\sigma(j)=i$ となる $j$ があるので $x\in A_{\sigma(j)}$ である。また $x\in\bigcap_jA_{\sigma(j)}$ とし $i\in I$ を任意にとると、$\sigma(j)=i$ となる $j$ について $x\in A_{\sigma(j)}=A_i$ である。よって 1 の包含は逆向きにも成り立つ。$\blacksquare$
全射は十分条件であって必要条件ではない。$\sigma$ の像に入らない添字 $i$ の $A_i$ が、ほかの項の和に含まれていれば和は変わらない。一方、$I=\{1,2\}$、$J=\{1\}$、$\sigma(1)=1$、$A_1=\emptyset$、$A_2=\{0\}$ とすると、付け替えた族の和は $\emptyset$ で、もとの族の和 $\{0\}$ と異なる。これが全射性を外したときの反例である。
とくに $\sigma$ が全単射なら、和と交叉は添字の並べ方によらない。有限個の和 $A_1\cup\cdots\cup A_n$ で項の順番を入れ替えてよいのは、この特別な場合である。
一般分配律と選択公理
二重の添字をもつ族について、「各 $i$ ごとに和をとってから交叉をとる」ことと、「各 $i$ に $j$ を一つずつ選んで交叉をとってから、選び方全体で和をとる」ことは一致する。選び方は写像 $\varphi$ で表され、そのような写像全体は直積 $\prod_{i\in I}J_i$ である。
$(A_{i,j})_{i\in I,\,j\in J_i}$ を $X$ の部分集合からなる二重の添字の族とし、
$$
\Phi=\prod_{i\in I}J_i=\{\varphi\mid \varphi\text{ は }I\text{ 上の写像で、各 }i\text{ について }\varphi(i)\in J_i\}
$$
とおく。
- つねに $\displaystyle\bigcup_{\varphi\in\Phi}\bigcap_{i\in I}A_{i,\varphi(i)}\subset\bigcap_{i\in I}\bigcup_{j\in J_i}A_{i,j}$ である。
- 選択公理を仮定すると、1 の包含は等号になる。
- 各 $i$ について族 $(A_{i,j})_{j\in J_i}$ が互いに素なら、選択公理を使わずに等号が成り立つ。
- 逆に、あらゆる二重の添字の族について 1 が等号になるなら、空でない集合の任意の族 $(J_i)_{i\in I}$ について $\prod_{i\in I}J_i\neq\emptyset$ である。
- $x$ が左辺に属するとし、$x\in\bigcap_iA_{i,\varphi(i)}$ となる $\varphi\in\Phi$ をとる。各 $i$ について $j=\varphi(i)\in J_i$ とすれば $x\in A_{i,j}\subset\bigcup_{j'}A_{i,j'}$ だから、$x$ は右辺に属する。$I=\emptyset$ のときは $\Phi$ は空写像だけからなり、両辺とも $X$ である。
- $x$ が右辺に属するとする。各 $i\in I$ について
$$ J_i^x=\{j\in J_i\mid x\in A_{i,j}\} $$
は空でない。選択公理により、各 $i$ について $\varphi(i)\in J_i^x$ となる写像 $\varphi$ がある。$\varphi\in\Phi$ で、すべての $i$ について $x\in A_{i,\varphi(i)}$ だから、$x$ は左辺に属する。 - 各 $i$ で $(A_{i,j})_j$ が互いに素なら、2 の $J_i^x$ はちょうど一つの元からなる。そこで $\varphi=\{(i,j)\mid i\in I,\ j\in J_i,\ x\in A_{i,j}\}$ とおくと、これは各 $i$ にただ一つの $j$ を対応させる写像であり、条件を満たす元を集める操作だけで作れるので選択公理は要らない。あとは 2 と同じである。
- $(J_i)_{i\in I}$ を空でない集合の族とし、$X=\{0\}$、すべての $i,j$ について $A_{i,j}=\{0\}$ とおく。各 $J_i$ が空でないので $\bigcup_{j\in J_i}A_{i,j}=\{0\}$ であり、右辺は $\{0\}$ である（$I=\emptyset$ でも $X=\{0\}$）。等号が成り立つなら左辺も $\{0\}$ で、とくに空でない。空な集合族の和は空だから $\Phi\neq\emptyset$ である。$\blacksquare$
4 の結論「空でない集合の族の直積は空でない」は選択公理と同値である（直積集合 の定理「選択公理との同値」）。したがって 2 と 4 を合わせると、一般分配律がつねに成り立つことは選択公理と同値である。3 のように互いに素な場合は、元 $x$ が選ぶべき $j$ を一つに決めてくれるので、選択が要らない（HJ99 Chapter 2, Exercise 3.13, p. 29）。選択公理を使う 2 と下の系の形は同書 Chapter 8, Exercise 1.11（p. 144）にある。
選択公理のもとで、$X$ の部分集合からなる二重の添字の族について
$$
\bigcup_{i\in I}\bigcap_{j\in J_i}A_{i,j}=\bigcap_{\varphi\in\Phi}\bigcup_{i\in I}A_{i,\varphi(i)}
$$
が成り立つ。
補集合の族 $B_{i,j}=X\setminus A_{i,j}$ に thm-family-general-distributive を使うと $\bigcap_i\bigcup_jB_{i,j}=\bigcup_\varphi\bigcap_iB_{i,\varphi(i)}$ である。両辺の $X$ での補集合をとり、prop-family-de-morgan を二回ずつ使うと、左辺は $\bigcup_i\bigcap_jA_{i,j}$、右辺は $\bigcap_\varphi\bigcup_iA_{i,\varphi(i)}$ になる。$\blacksquare$
互いに素な族と分割
集合族 $(A_i)_{i\in I}$ が互いに素(pairwise disjoint)であるとは、$i\neq k$ ならば $A_i\cap A_k=\emptyset$ であることをいう。集合 $X$ の部分集合族 $(A_i)_{i\in I}$ が互いに素で、各 $A_i$ が空でなく、$\bigcup_iA_i=X$ であるとき、これを $X$ の分割という。
族として互いに素であることは、値の集合 $\{A_i\mid i\in I\}$ の相異なる二元が交わらないことより強い。たとえば $A\neq\emptyset$ のとき、族 $(A,A)$（添字 $1,2$）は互いに素でないが、値の集合 $\{A\}$ には相異なる二元がない。
集合族 $(A_i)_{i\in I}$ について次が成り立つ。
- $(A_i)$ が互いに素であることと、$\bigcup_iA_i$ の各元 $x$ について $x\in A_i$ となる $i$ がちょうど一つであることは同値である。
- $(A_i)$ が互いに素で各 $A_i$ が空でなければ、写像 $i\mapsto A_i$ は単射である。
- 互いに素とし、$x\in A_i$ かつ $x\in A_k$ とすると $A_i\cap A_k\neq\emptyset$ だから $i=k$ である。$x$ が和に属するので少なくとも一つの $i$ はある。逆に、和の各元を含む項がただ一つなら、$i\neq k$ で $x\in A_i\cap A_k$ となる $x$ はなく、$A_i\cap A_k=\emptyset$ である。
- $A_i=A_k$ とする。$A_i$ が空でないので元 $x\in A_i$ をとると $x\in A_i\cap A_k$ であり、互いに素だから $i=k$ である。$\blacksquare$
2 により、分割は値の集合 $\{A_i\mid i\in I\}$ と同じ情報をもつ。分割と同値関係の対応は 同値関係 の定理「同値関係と分割の対応」で扱う。互いに素な有限個の有限集合の和の元の個数が各項の元の個数の和になることは 非交和集合 の命題「非交和の濃度」で、任意の集合の列を互いに素な列に直す方法は 差集合 の命題「互いに素な列への分解」で扱う。
反例の表
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 付け替え $\sigma$ の全射性 | $\sigma\colon\{1\}\to\{1,2\}$、$A_1=\emptyset$、$A_2=\{0\}$ | 付け替えた族の和がもとの族の和に等しい |
| 写像の単射性 | 定値写像 $\{1,2\}\to\{0\}$ と $A_1=\{1\}$、$A_2=\{2\}$ | 像が交叉を保つ |
| 族として互いに素 | 族 $(\{0\},\{0\})$ | 和の各元を含む項がただ一つ |
| 各項が空でない | 互いに素な族 $(\emptyset,\emptyset)$ | $i\mapsto A_i$ が単射 |
| 各 $i$ での互いに素（選択公理を使わない場合） | $A_{1,1}=A_{1,2}=\{0\}$ | 等号を満たす $\varphi$ が一つに決まる |
最後の行では等号そのものは成り立つ（$\varphi$ は 2 通りある）が、$x=0$ から $\varphi$ が一つに定まらないため、thm-family-general-distributive の 3 の証明の作り方が使えなくなる。
記法と扱う範囲
$\{A_i\}_{i\in I}$ という波括弧つき記法も集合族に広く使われる。ただし、重複を保持する写像としての族か、値だけからなる集合かが曖昧になり得る。重複・順序・添字写像が重要な場面では $(A_i)_{i\in I}$ と書くのが安全である。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
