補集合

補集合

集合\(A\)に集合演算子\(c\)を作用することで得られる、\begin{equation*}A^{c}
\end{equation*}もまた集合です。\(c\)は補集合（complement）と呼ばれる集合演算子であり、集合\(A^{c}\)を\(A\)の補集合（complement of \(A\)）と呼びます。

全体集合が\(U\)であるものとします。集合\(A\)が与えられたとき、その補集合\(A^{c}\)とは、\(U\)の要素の中でも\(A\)の要素ではないものからなる集合\begin{equation*}A^{c}=\left\{ x\in U\ |\ x\not\in A\right\}
\end{equation*}として定義されます。定義より、以下の関係\begin{equation*}
\forall x\in U:\left( x\in A^{c}\Leftrightarrow x\not\in A\right)
\end{equation*}が成り立ちます。つまり、\(x\)が\(A\)の補集合の要素であることと、\(x\)が\(A\)の要素ではないことは必要十分です。このとき、\begin{equation*}\forall x\in U:\left( x\not\in A^{c}\Leftrightarrow x\in A\right)
\end{equation*}もまた成り立ちます。つまり、\(x\)が\(A\)の補集合の要素ではないことと、\(x\)が\(A\)の要素であることは必要十分です。

同一の集合\(A\)を対象としていても、全体集合\(U\)が変われば補集合\(A^{c}\)もまた変化し得ることに注意してください。以下が具体例です。

上の例が示唆するように、補集合は全体集合に応じて変化するため、補集合をとる際には全体集合が何であるかをきちんと確認する必要があります。

補集合の内包的表現

全体集合が\(U\)である状況を想定します。集合\(A\)は以下の条件\begin{equation*}\forall x\in U:\left[ x\in A\Leftrightarrow P\left( x\right) \right] \end{equation*}を満たす命題関数\(P\left(x\right) \)の真理集合として表現可能です。つまり、全体集合\(U\)に属する要素の中でも命題\(P\left( x\right) \)が真になるような要素\(x\)からなる集合が\(A\)であり、\begin{equation*}A=\left\{ x\in U\ |\ P\left( x\right) \right\}
\end{equation*}と表現できるということです。

集合\(A\)が命題関数\(P\left( x\right) \)を用いて内包的に表現されている場合、その補集合\(A^{c}\)はどのような命題関数を用いて内包的に表現されるでしょうか。集合\(A\)が、\begin{equation}A=\left\{ x\in U\ |\ P\left( x\right) \right\} \quad \cdots (1)
\end{equation}と定義されているものとします。補集合の定義より、任意の\(x\in U\)について、\begin{equation}x\in A^{c}\Leftrightarrow x\not\in A \quad \cdots (2)
\end{equation}が成り立ちます。以上を踏まえると、任意の\(x\in U\)について、\begin{eqnarray*}x\in A^{c} &\Leftrightarrow &x\not\in A\quad \because \left( 2\right) \\
&\Leftrightarrow &\lnot P\left( x\right) \quad \because \left( 1\right)
\end{eqnarray*}となるため、以下の命題\begin{equation*}
\forall x\in U:\left[ x\in A^{c}\Leftrightarrow \lnot P\left( x\right) \right] \end{equation*}が成り立つことが明らかになりました。したがって、補集合\(A^{c}\)は否定\(\lnot P\left( x\right) \)の真理集合として表現されるため、\begin{equation*}A^{c}=\left\{ x\in U\ |\ \lnot P\left( x\right) \right\}
\end{equation*}となります。全体集合\(U\)に属する要素の中でも命題\(\lnot P\left( x\right) \)が真、すなわち命題\(P\left( x\right) \)が偽になるような要素\(x\)からなる集合が\(A^{c}\)です。補集合\(c\)という集合演算は否定\(\lnot \)から間接的に定義可能であるということです。

つまり、集合\(A\)が命題関数\(P\left( x\right) \)を用いて表現されている場合、その否定\(\lnot P\left( x\right) \)をとれば、補集合\(A^{c}\)を特定できるということです。

上の命題の主張を視覚的に表現したものが以下の図です。

全体集合\(U\)が上の長方形の領域として描かれているものとします。集合\(A\)が命題関数\(P\left( x\right) \)から内包的に定義されているとき、\(A\)は命題\(P\left( x\right) \)が真になるような値\(x\in U\)からなる集合、すなわち命題関数\(P\left( x\right) \)の真理集合\(\phi \left( P\right) \)と一致します。これは上図において白い領域として描かれています。一方、補集合\(A^{c}\)は命題関数\(\lnot P\left( x\right) \)の真理集合\(\phi \left( \lnot P\right) \)と一致し、これは上図においてグレーの領域として描かれています。

全体集合や空集合の補集合

全体集合\(U\)は恒真式\(\top \)を用いて内包的に表現され、空集合\(\phi \)は恒偽式\(\bot \)を用いて内包的に表現されます。つまり、\begin{eqnarray*}U &=&\left\{ x\in U\ |\ \top \right\} \\
\phi &=&\left\{ x\in U\ |\ \bot \right\}
\end{eqnarray*}です。以上の事実を用いると、全体集合や空集合の補集合に関する以下の命題が導かれます。つまり、全体集合の補集合は空集合であり、空集合の補集合は全体集合です。

補集合と包含関係

全体集合を\(U\)とします。集合\(A,B\)を任意に選んだとき、以下の関係\begin{equation*}A\subset B\Leftrightarrow B^{c}\subset A^{c}
\end{equation*}が成り立つことが保証されます。つまり、\(A\)が\(B\)の部分集合であることと、\(B\)の補集合が\(A\)の補集合の部分集合であることは必要十分です。つまり、包含関係が成立する2つの集合の補集合をそれぞれとると、包含関係が逆転します。

補集合の要素の個数

集合\(A\)の要素の個数を、\begin{equation*}\left\vert A\right\vert
\end{equation*}で表記します。\(A\)が有限集合であるならば、すなわち\(A\)の要素の個数が有限であるならば\(\left\vert A\right\vert \)は非負の整数です。全体集合\(U\)が有限集合である場合、その任意の部分集合\(A\)もまた有限集合です。補集合\(A^{c}\)は全体集合\(U\)の要素の中でも\(A\)の要素ではないものからなる集合であるため、以下の関係\begin{equation*}\left\vert A^{c}\right\vert =\left\vert U\right\vert -\left\vert
A\right\vert
\end{equation*}が成り立ちます。つまり、全体集合\(U\)が有限集合である場合、その部分集合\(A\)を任意に選んだとき、補集合\(A^{c}\)の要素の個数は\(U\)の要素の個数から\(A\)の要素の個数を引くことにより得られます。

演習問題