集合演算における双対原理

集合の双対

集合演算子として\(c,\cap,\cup ,\backslash ,\triangle \)を定義しましたが、先に示したように\(\backslash \)と\(\triangle \)はともに\(c,\cap ,\cup \)によって言い換え可能であるため、結局、集合演算子として\(c,\cap ,\cup \)だけ与えられれば任意の集合を表現することができます。具体的には、集合\(A,B\)がそれぞれ任意に与えられたとき、\begin{eqnarray*}&&\left( a\right) \ A\backslash B=A\cap B^{c} \\
&&\left( b\right) \ A\triangle B=\left( A\backslash B\right) \vee \left(
B\backslash A\right)
\end{eqnarray*}などの関係が成り立つため、これらの関係を適用することにより\(\backslash ,\triangle \)を\(c,\cap ,\cup \)に置き換えることができます。

以上を踏まえると、集合\(A\)を任意に選んだとき、そこに含まれる可能性のある集合演算子を\(c,\cap ,\cup \)に限定しても一般性は失われません。その上で、集合\(A\)に対して以下の操作を加えることにより得られる新たな集合を\(A\)の双対（dual）と呼びます。\begin{eqnarray*}&&\left( 1\right) \ A\text{中の}\cap \text{を}\cup \text{に入れ替え、}\cup \text{を}\cap
\text{に入れ替える。} \\
&&\left( 2\right) \ A\text{中の}U\text{を}\phi \text{に入れ替え、}\phi \text{を}U\text{に入れ替える。}
\end{eqnarray*}ただし、\(U\)は全体集合であり、\(\phi \)は空集合です。

第1双対原理

集合\(A_{1},\cdots ,A_{n}\)と全体集合\(U\)および空集合\(\phi \)を被演算子とする集合を、\begin{equation*}A\left( A_{1},\cdots ,A_{n},U,\phi \right)
\end{equation*}で表記します。集合\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)中の\(A_{1},\cdots,A_{n}\)を補集合\(A_{1}^{c},\cdots ,A_{n}^{c}\)に入れ替えることで得られる集合を、\begin{equation*}A\left( A_{1}^{c},\cdots ,A_{n}^{c},U,\phi \right)
\end{equation*}で表記し、さらにその補集合を、\begin{equation}
A^{c}\left( A_{1}^{c},\cdots ,A_{n}^{c},U,\phi \right) \quad \cdots (1)
\end{equation}で表記します。また、集合\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)の双対を、\begin{equation}A^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) \quad \cdots (2)
\end{equation}で表記します。実は、\(\left( 1\right) \)と\(\left( 2\right) \)は常に一致します。まずは例を通じて確認しましょう。

以上の2つの例が示唆するように、一般に、集合\(A_{1},\cdots ,A_{n}\)と全体集合\(U\)および空集合\(\phi \)を被演算子とする集合\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)が与えられたとき、その双対に関して、\begin{equation*}A^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) =A^{c}\left( A_{1}^{c},\cdots
,A_{n}^{c},U,\phi \right)
\end{equation*}という関係が成り立ちます。つまり、集合\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)の双対は、この集合中の\(A_{1},\cdots ,A_{n}\)を補集合\(A_{1}^{c},\cdots,A_{n}^{c}\)に置き換えて得られる集合の補集合と一致します。これを第1双対原理（first principleduality）や第1双対定理（first duality theorem）などと呼びます。証明では論理演算に関する第1双対原理を利用します。

第2双対原理

集合\(A_{1},\cdots ,A_{n}\)と全体集合\(U\)および空集合\(\phi \)を被演算子とする集合である\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)と\(B\left( A_{1},\cdots ,A_{n},U,\phi \right) \)の間に、\begin{equation*}A\left( A_{1},\cdots ,A_{n},U,\phi \right) \subset B\left( A_{1},\cdots
,A_{n},U,\phi \right)
\end{equation*}という関係が成り立つものとします。このとき、これらの集合の双対の間に、\begin{equation*}
B^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) \subset A^{D}\left(
A_{1},\cdots ,A_{n},U,\phi \right)
\end{equation*}が成り立つことが示されます。つまり、双対をとると包含関係が逆転するということです。これを第2双対原理（second principle duality）や第2双対定理（second duality theorem）などと呼びます。証明では先に示した第1双対原理を利用します。

第3双対原理

集合\(A_{1},\cdots ,A_{n}\)と全体集合\(U\)および空集合\(\phi \)を被演算子とする集合である\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)と\(B\left( A_{1},\cdots ,A_{n},U,\phi \right) \)の間に、\begin{equation*}A\left( A_{1},\cdots ,A_{n},U,\phi \right) =B\left( A_{1},\cdots
,A_{n},U,\phi \right)
\end{equation*}という関係が成り立つものとします。これは、\begin{eqnarray*}
A\left( A_{1},\cdots ,A_{n},U,\phi \right) &\subset &B\left( A_{1},\cdots
,A_{n},U,\phi \right) \\
B\left( A_{1},\cdots ,A_{n},U,\phi \right) &\subset &A\left( A_{1},\cdots
,A_{n},U,\phi \right)
\end{eqnarray*}がともに成り立つことを意味するため、第2双対原理より、\begin{eqnarray*}
B^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) &\subset &A^{D}\left(
A_{1},\cdots ,A_{n},U,\phi \right) \\
A^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) &\subset &B^{D}\left(
A_{1},\cdots ,A_{n},U,\phi \right)
\end{eqnarray*}を得ます。これは、\begin{equation*}
A^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) =B^{D}\left( A_{1},\cdots
,A_{n},U,\phi \right)
\end{equation*}であることを意味します。これを第3双対原理（third principle duality）や第3双対定理（third duality theorem）などと呼びます。つまり、集合\(A,B\)が等しいとき、それらの双対どうしも等しいことが保証されます。