補集合

同義語：絶対補集合complement

概要

前提知識: 集合, 部分集合, 差集合

補集合（complement）とは、固定した全体集合 $U$ の部分集合 $A$ に対し、$U$ の元で $A$ に属さないもの全体の集合 $A^c=U\setminus A$ である。
補集合は「$A$ でないもの」を集める操作で、論理の否定に対応する。二回とるともとに戻り、包含の向きを逆にし、和集合と共通部分を入れ替える。ただし「何の中で $A$ でないのか」という全体集合を決めなければ定まらない。

定義

集合を扱うときは、考察の対象となる範囲を一つの集合 $U$ に限定し、その部分集合について議論することが多い。この $U$ を全体集合（universal set、基準集合）という。

補集合

全体集合 $U$ とその部分集合 $A\subset U$ に対し、$U$ の要素であって $A$ に属さないもの全体の集合
$$ A^c:=\{x\in U\mid x\notin A\} $$
を、$U$ における $A$ の補集合（complement）という。全体集合に対する補集合であることを強調して絶対補集合（absolute complement）ともいう。記号は $A^c$ のほか、$\overline{A}$、$A'$、$\complement_U A$、$U\setminus A$ などが用いられる。

相対補集合

二つの集合 $A$、$B$ に対し、$B$ の要素であって $A$ に属さないもの全体の集合
$$ B\setminus A:=\{x\in B\mid x\notin A\} $$
を、$B$ における $A$ の相対補集合（relative complement）という。これは $B$ から $A$ を引いた差集合にほかならず、$B-A$ とも書かれる。相対補集合は全体集合を前提としない。

絶対補集合 $A^c$ は、全体集合 $U$ における $A$ の相対補集合 $U\setminus A$ である（差集合を「$A$ に対する $B$ の補集合」と呼ぶ流儀は Mun00 §1, p. 10 にある）。逆に、$A,B\subset U$ のとき相対補集合は $B\setminus A=B\cap A^c$ と絶対補集合と共通部分で書ける（prop-complement-relative-formulas）。記号 $A^c$ は全体集合 $U$ を省略しているので、これを書く前には $U$ が文脈で固定されていなければならない。全体集合を固定しないと何が起こるかは、次の命題が示す。

全体集合なしの補集合は存在しない

どんな集合 $A$ についても、「$x\notin A$ を満たすすべての $x$」を元とする集合は存在しない。

そのような集合 $C$ があるとする。任意の集合 $x$ は $x\in A$ か $x\notin A$ のどちらかを満たすので、$x\in A\cup C$ である。よって $A\cup C$ はすべての集合を元にもつ集合になり、集合の命題「Russell の議論と全体集合の非存在」に反する。$\square$

この命題は HJ99 Chapter 1 §4, Exercise 4.4（p. 15）の主張である。全体集合とは議論ごとに選んだ一つの集合 $U$ であって、文脈から独立に定まる「すべてのもの」ではない。全体集合を取り替えたときの補集合の関係は次のとおりである。

全体集合の取り替え

$A\subset U\subset U'$ とする。$U$ における補集合と $U'$ における補集合について
$$ U\setminus A=U\cap(U'\setminus A),\qquad (U'\setminus A)\setminus(U\setminus A)=U'\setminus U $$
が成り立つ。とくに $U\subsetneq U'$ なら二つの補集合は異なる。

第一式：$x\in U\setminus A$ は「$x\in U$ かつ $x\notin A$」と同値である。$U\subset U'$ なので、これは「$x\in U$ かつ $x\in U'$ かつ $x\notin A$」、すなわち $x\in U\cap(U'\setminus A)$ と同値である。
第二式：$x$ が左辺に属するとは、$x\in U'$、$x\notin A$ であって、$x\in U$ かつ $x\notin A$ ではないこと、すなわち $x\in U'$、$x\notin A$、$x\notin U$ であることである。$A\subset U$ なので $x\notin U$ から $x\notin A$ が従い、条件は「$x\in U'$ かつ $x\notin U$」、すなわち $x\in U'\setminus U$ と同値である。
最後に、$U\subsetneq U'$ なら $U'\setminus U\neq\emptyset$ なので、第二式から $U'\setminus A\neq U\setminus A$ である。$\square$

直感

補集合は「$A$ でないもの全体」を集合として表す操作であり、命題論理の否定 $\neg$ に対応する。しかし「すべてのもの」の範囲を決めなければ「$A$ でないもの」は定まらないので、全体集合 $U$ を固定する必要がある。全体集合を白黒に塗り分ける操作と思えば、$A$ の点を黒としたとき $A^c$ は白い点の全体であり、もう一度反転すれば元に戻る。この操作は和集合と共通部分を入れ替え、包含の向きを反転させる。この構造は、確率論の余事象や位相空間における開集合と閉集合の双対性としてそのまま現れる。

例と反例

数の集合における補集合

全体集合を整数全体 $U=\mathbb{Z}$ とし、$A=2\mathbb{Z}$ を偶数全体とすると、$A^c=\{2k+1\mid k\in\mathbb{Z}\}$ は奇数全体である。
全体集合を実数全体 $U=\mathbb{R}$ とし、$A=\mathbb{Q}$ を有理数全体とすると、$A^c=\mathbb{R}\setminus\mathbb{Q}$ は無理数全体である。
$U=\mathbb{R}$ において、$x\ge 5$ を満たす実数の集合 $A=[5,\infty)$ の補集合は $A^c=(-\infty,5)$ である。閉端点 $5$ は $A$ に属するので補集合には入らない。

確率論における余事象

ある試行の標本空間を $\Omega$ とし、事象を $\Omega$ の部分集合とみなす。事象 $A\subset\Omega$ に対し、その補集合 $A^c$ は「$A$ が起こらない」という事象であり、$A$ の余事象という。確率 $P$ について $P(A^c)=1-P(A)$ が成り立つ（prop-complement-probability）。たとえばさいころを 3 回振って少なくとも 1 回 6 が出る確率は、余事象「一度も 6 が出ない」の確率 $(5/6)^3=125/216$ を $1$ から引いて $91/216$ と求まる。

全体集合による補集合の違い

同じ条件で定めた集合でも、全体集合が変われば補集合は変わる。条件「$x< 3$」を満たす数の集合の補集合は、$U=\mathbb{N}$ ならば $\{3,4,5,\dots\}$ であり、$U=\mathbb{R}$ ならば $[3,\infty)$ である。同様に、偶数全体 $2\mathbb{Z}$ の補集合は、$U=\mathbb{Z}$ ならば奇数全体だが、$U=\mathbb{R}$ ならば「偶数でないすべての実数」であり、はるかに大きい。二つの補集合の差は prop-complement-change-universe の第二式のとおり $\mathbb R\setminus\mathbb Z$ である。

反例：全体集合を途中で変えると二重補集合が戻らない

$A=\{0\}$、$U=\{0,1\}$、$U'=\{0,1,2\}$ とする。$U$ で補集合をとると $\{1\}$、それを $U'$ で補集合にとると $\{0,2\}$ であり、$A$ に戻らない。二重補集合がもとに戻る法則（prop-complement-basic-laws の 1）は、二回とも同じ全体集合で補集合をとることを仮定している。

反例：像は補集合を保たない

写像 $f\colon X\to Y$ による逆像は補集合を保つ（逆像の命題「逆像と集合の演算」の 4）が、像(写像)は一般に保たない。$f\colon\mathbb{R}\to\mathbb{R}$、$f(x)=x^2$ とし、$A=[0,\infty)$ とおく。このとき $f(A)=[0,\infty)$ であり、$\mathbb{R}$ における補集合は $\mathbb{R}\setminus f(A)=(-\infty,0)$ である。一方 $A^c=(-\infty,0)$ の像は $f(A^c)=(0,\infty)$ である。ゆえに $f(A^c)\neq\mathbb{R}\setminus f(A)$ である。この $f$ は単射でなく（$f(-1)=f(1)$）、$A$ の外の点 $-1$ と内の点 $1$ が同じ値に送られることが原因である。また $f$ は全射でもなく、負の数はどちらの側の像にも入らない。等号が成り立つための条件は prop-complement-image で述べる。

反例：差集合の向き

$A\setminus B$ と $B\setminus A$ は一般に異なる。$A=\{1,2\}$、$B=\{2,3\}$ とすると $A\setminus B=\{1\}$、$B\setminus A=\{3\}$ である。$A\setminus B$ と $B\setminus A$ の和集合が対称差である。相対補集合を「$B$ における $A$ の」と言うときは、$B$ から $A$ を引くという向きを確認する必要がある。

性質

以下では全体集合 $U$ を固定し、すべての集合を $U$ の部分集合とする。

補集合の基本法則

任意の $A,B\subset U$ について次が成り立つ。

$(A^c)^c=A$（二重補集合）。
$U^c=\emptyset$、$\emptyset^c=U$。
$A\cup A^c=U$、$A\cap A^c=\emptyset$。
$A\subset B$ ならば $B^c\subset A^c$（包含の反転）。

任意の $x\in U$ について、$x\in(A^c)^c\iff x\notin A^c\iff\neg(x\notin A)\iff x\in A$ である。
$U$ の要素で $U$ に属さないものはないので $U^c=\emptyset$。$U$ のどの要素も空集合には属さないので $\emptyset^c=U$。
各 $x\in U$ は $A$ に属するか属さないかのちょうど一方なので、$x\in A$ または $x\in A^c$ が成り立ち、両方が同時に成り立つことはない。
$A\subset B$ とし、$x\in B^c$ とする。もし $x\in A$ ならば $x\in B$ となり $x\in B^c$ に反する。よって $x\notin A$、すなわち $x\in A^c$ である。$\square$

3 の二つの等式は補集合を特徴づける。$B\subset U$ が $A\cup B=U$ と $A\cap B=\emptyset$ をともに満たせば $B=A^c$ である。これは Boolean代数の命題「補元の一意性と基本法則」を冪集合 $\mathcal P(U)$ に当てはめたものである。1 と 4 を合わせると、$A\subset B$ と $B^c\subset A^c$ は同値である（逆向きは 4 を $B^c\subset A^c$ に使い、1 で戻す）。

和集合と共通部分の補集合

$U$ の部分集合の族 $(A_i)_{i\in I}$ に対し
$$ \Bigl(\bigcup_{i\in I}A_i\Bigr)^c=\bigcap_{i\in I}A_i^c,\qquad \Bigl(\bigcap_{i\in I}A_i\Bigr)^c=\bigcup_{i\in I}A_i^c $$
が成り立つ。特に $A,B\subset U$ について $(A\cup B)^c=A^c\cap B^c$、$(A\cap B)^c=A^c\cup B^c$ である。

任意の $x\in U$ について
$$ \begin{aligned} x\in\Bigl(\bigcup_{i\in I}A_i\Bigr)^c &\iff x\notin\bigcup_{i\in I}A_i \iff \text{すべての } i\in I \text{ について } x\notin A_i\\ &\iff \text{すべての } i\in I \text{ について } x\in A_i^c \iff x\in\bigcap_{i\in I}A_i^c \end{aligned} $$
であるから第一式を得る。同様に、$x\notin\bigcap_{i}A_i$ はある $i\in I$ について $x\notin A_i$ であることと同値であり、これは $x\in\bigcup_i A_i^c$ と同値なので第二式を得る。有限個の場合は $I=\{1,2\}$ とすればよい。$\square$

これらの等式をDe Morganの法則という。添字集合 $I$ が空のときも、約束 $\bigcup_{i\in\emptyset}A_i=\emptyset$、$\bigcap_{i\in\emptyset}A_i=U$ のもとで両式は成り立つ。全体集合を使わない相対形 $C\setminus(A\cup B)=(C\setminus A)\cap(C\setminus B)$、$C\setminus(A\cap B)=(C\setminus A)\cup(C\setminus B)$ は HJ99 Chapter 1 §4（p. 14）と Mun00 §1（p. 11）に、任意の族の場合は Mun00 §1, Exercise 9（p. 15）にある。

相対補集合と包含の書き換え

任意の $A,B\subset U$ について次が成り立つ。

$B\setminus A=B\cap A^c$。
$(B\setminus A)^c=B^c\cup A$。
$A\subset B$ であることと $A\cap B^c=\emptyset$ であることは同値である。

$x\in B\setminus A\iff x\in B$ かつ $x\notin A\iff x\in B$ かつ $x\in A^c\iff x\in B\cap A^c$。
1. と prop-complement-de-morgan により $(B\setminus A)^c=(B\cap A^c)^c=B^c\cup(A^c)^c=B^c\cup A$。最後の等号は prop-complement-basic-laws (1) による。
$A\cap B^c=A\setminus B$ である。$A\subset B$ ならば $A$ の要素はすべて $B$ に属するので $A\setminus B=\emptyset$。逆に $A\setminus B=\emptyset$ ならば、$x\in A$ に対し $x\notin B$ とすると $x\in A\setminus B$ となって矛盾するので $x\in B$ であり、$A\subset B$ である。$\square$

3 は「$A$ が $B$ に含まれる」ことを「$A$ と $B$ の外が交わらない」ことに言い換える。背理法で包含を示すとき（$A$ の元で $B$ に入らないものがあると仮定して矛盾を導くとき）に使っているのはこの形である。

写像と補集合

写像 $f\colon X\to Y$ の逆像は補集合を保つ。$f^{-1}(Y\setminus B)=X\setminus f^{-1}(B)$ であり、これは逆像の命題「逆像と集合の演算」の 4 である。逆像は和集合・共通部分・補集合をすべて保つので、連続写像や可測写像の定義は像ではなく逆像で書かれる。像については、補集合を保つのは次の場合に限る。

像が補集合を保つ条件

写像 $f\colon X\to Y$ について、次は同値である。

すべての $A\subset X$ について $f(X\setminus A)=Y\setminus f(A)$。
$f$ は全単射である。

（2 ⇒ 1）$f$ が単射なので、差集合の命題「像と差集合」の 2 により $f(X\setminus A)=f(X)\setminus f(A)$ である。$f$ が全射なので $f(X)=Y$ であり、$f(X\setminus A)=Y\setminus f(A)$ を得る。
（1 ⇒ 2）$A=\emptyset$ とおくと $f(X)=Y\setminus f(\emptyset)=Y$ なので、$f$ は全射である。次に $f(x)=f(x')$ とし、$x\neq x'$ と仮定する。$A=\{x\}$ とおくと $x'\in X\setminus A$ なので $f(x')\in f(X\setminus A)$ である。1 により $f(X\setminus A)=Y\setminus\{f(x)\}$ だから $f(x')\neq f(x)$ となり、仮定に反する。よって $x=x'$ であり、$f$ は単射である。$\square$

証明から、崩れ方は二通りに分かれる。$f(X\setminus A)$ が $Y\setminus f(A)$ からはみ出すのは、$A$ の外の点と内の点が同じ値をとるとき（単射でないとき）であり、$Y\setminus f(A)$ が $f(X\setminus A)$ に収まらないのは、どの点の値にもならない $Y$ の点があるとき（全射でないとき）である。一方、差集合の命題「像と差集合」の 1 から、包含 $f(X)\setminus f(A)\subset f(X\setminus A)$ はつねに成り立つ。

数え上げと確率

$U$ が有限集合なら、$U$ は交わらない二つの集合 $A$ と $A^c$ の和なので $\lvert A^c\rvert=\lvert U\rvert-\lvert A\rvert$ である（和集合の命題「二集合の包除原理」で $A\cap A^c=\emptyset$ とした場合）。特性関数では $\chi_{A^c}=1-\chi_A$ である（特性関数の命題「集合演算と特性関数」）。「少なくとも一つ」を数えるより「一つもない」を数えて全体から引く方が易しいことが多いのは、この等式による。確率でも同じ形になる。

余事象の確率

確率空間 $(\Omega,\mathcal{F},P)$（$\mathcal{F}$ は $\Omega$ 上のσ-加法族）の事象 $A\in\mathcal{F}$ に対し、$A^c=\Omega\setminus A$ は $\mathcal{F}$ に属し、$P(A^c)=1-P(A)$ が成り立つ。

$\mathcal{F}$ は補集合について閉じているので $A^c\in\mathcal{F}$ である。prop-complement-basic-laws (3) により $\Omega=A\cup A^c$ かつ $A\cap A^c=\emptyset$ であるから、確率の加法性と $P(\Omega)=1$ により $1=P(\Omega)=P(A)+P(A^c)$ を得る。$\square$

全体の測度が有限な測度では、加法性から $\mu(A^c)=\mu(\Omega)-\mu(A)$ と書ける。全体の測度が無限大でも $\mu(A)$ が有限なら右辺は $\infty$ と定められるが、$\mu(A)$ も無限大なら $\infty-\infty$ となり、この引き算は定まらない。たとえば実数直線のLebesgue測度 $\mu$ と $A=[0,\infty)$ では、$\mu(\mathbb R)=\mu(A)=\mu(A^c)=\infty$ であり、右辺は $\infty-\infty$ になる。

補足

補集合は冪集合 $\mathcal{P}(U)$ 上の写像 $A\mapsto A^c$ とみなせば、prop-complement-basic-laws により、二回合成すると恒等写像になり（対合）、包含順序を反転させる。和集合・共通部分・補集合を備えた $\mathcal{P}(U)$ はBoolean代数の基本例であり、補集合はその否定演算にあたる。命題論理の否定 $\neg$、論理和 $\vee$、論理積 $\wedge$ に対する De Morgan の法則 $\neg(P\vee Q)\iff\neg P\wedge\neg Q$ などは、prop-complement-de-morgan の論理版である。
位相空間 $X$ では、閉集合を「補集合が開集合である集合」として定義する。prop-complement-de-morgan により、開集合の族に課される「任意個の和集合と有限個の共通部分で閉じる」という条件は、閉集合の族の「任意個の共通部分と有限個の和集合で閉じる」という条件に反転する。内部と閉包も
$$ \operatorname{int}(A)=X\setminus\overline{X\setminus A},\qquad \overline{A}=X\setminus\operatorname{int}(X\setminus A) $$
と補集合で互いに移り合う。可算個の開集合の共通部分であるG_δ-集合と可算個の閉集合の和集合であるF_σ-集合も、補集合をとることで互いに移り合う。
記号については次の点に注意する。$\overline{A}$ は補集合を表すこともあれば閉包を表すこともあり、位相空間では混同しやすいので、$A^c$ または $X\setminus A$ と書く方が安全である。
集合の補集合を特定の構造に合わせて取ったものとして、グラフの補グラフ（可能な辺全体の中での辺集合の補集合）や、内積空間の直交補空間がある。いずれも本記事の補集合そのものではなく、それぞれの記事で扱う。

反例の表

外す条件	反例	成り立たなくなること
全体集合を固定する	$2\mathbb Z$ の補集合を $\mathbb Z$ と $\mathbb R$ の中でとる	補集合が一つに定まる
全体集合を決める	$\{x\mid x\notin A\}$	補集合が集合として存在する
二回とも同じ全体集合	$A=\{0\}$、$U=\{0,1\}$、$U'=\{0,1,2\}$	二重補集合がもとに戻る
写像の単射性	$f(x)=x^2$、$A=[0,\infty)$	$f(X\setminus A)\subset Y\setminus f(A)$
写像の全射性	包含 $\{0\}\to\{0,1\}$、$A=\{0\}$	$Y\setminus f(A)\subset f(X\setminus A)$
全体の測度が有限	$\mathbb R$ の Lebesgue 測度、$A=[0,\infty)$	右辺を引き算で定める式 $\mu(A^c)=\mu(\Omega)-\mu(A)$
差をとる向き	$\{1,2\}\setminus\{2,3\}$ と $\{2,3\}\setminus\{1,2\}$	$A\setminus B=B\setminus A$

5 行目では $f(X\setminus A)=f(\emptyset)=\emptyset$ だが $Y\setminus f(A)=\{1\}$ である。4 行目では $f(X\setminus A)=(0,\infty)$ が $Y\setminus f(A)=(-\infty,0)$ に含まれない。