WIIS

集合

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

目次

関連知識

前のページ:

二重補集合の法則

次のページ:

集合族(集合系)

Mailで保存
Xで共有

集合の双対

集合演算子として\(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 \)は空集合です。

例(双対)
集合\(A,B\)を被演算子とする集合\((A\cap B)\cup A\)の双対は\((A\cup B)\cap A\)です。
例(双対)
集合\(A,B\)を被演算子とする集合\(\left( A\cap B\right) \cup \left( A^{c}\cap B^{c}\right) \)の双対は\(\left( A\cup B\right)\cap \left( A^{c}\cup B^{c}\right) \)です。
例(双対)
集合\(A,B,C\)と全体集合\(U\)を被演算子とする集合\(\left( A^{c}\cap B\right) \cup \left( U\cap C^{c}\right) ^{c}\)の双対は\(\left( A^{c}\cup B\right) \cap \left( \phi \cup C^{c}\right) ^{c}\)です。

 

第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) \)は常に一致します。まずは例を通じて確認しましょう。

例(第1双対原理)
集合\(A_{1},A_{2}\)と全体集合\(U\)および空集合\(\phi \)に関する集合が、\begin{equation}A\left( A_{1},A_{2},U,\phi \right) =A_{1}\cap A_{2} \quad \cdots (1)
\end{equation}で与えられているとき、その双対は、\begin{equation}
A^{D}\left( A_{1},A_{2},U,\phi \right) =A_{1}\cup A_{2} \quad \cdots (2)
\end{equation}となります。さて、\begin{eqnarray*}
A^{c}\left( A_{1}^{c},A_{2}^{c},U,\phi \right) &=&\left( A_{1}^{c}\cap
A_{2}^{c}\right) ^{c}\quad \because \left( 1\right) \\
&=&A_{1}\cup A_{2}\quad \because \text{ド・モルガンの法則} \\
&=&A^{D}\left( A_{1},A_{2},U,\phi \right) \quad \because \left( 2\right)
\end{eqnarray*}となるため、\begin{equation*}
A^{D}\left( A_{1},A_{2},U,\phi \right) =A^{c}\left(
A_{1}^{c},A_{2}^{c},U,\phi \right)
\end{equation*}という関係が成り立つことが示されました。つまり、集合\(A\left(A_{1},A_{2},U,\phi \right) \)の双対は、この集合中の集合\(A_{1},A_{2}\)を補集合\(A_{1}^{c},A_{2}^{c}\)に入れ替えることで得られる集合の補集合と一致します。
例(第1双対原理)
集合\(A_{1},A_{2},A_{3}\)と全体集合\(U\)および空集合\(\phi \)に関する集合が、\begin{equation}A\left( A_{1},A_{2},A_{3},U,\phi \right) =\left( A_{1}\cap A_{2}^{c}\right)
\cup \left( A_{3}^{c}\cap U\right) \quad \cdots (1)
\end{equation}で与えられているとき、その双対は、\begin{equation}
A^{D}\left( A_{1},A_{2},A_{3},U,\phi \right) =\left( A_{1}\cup
A_{2}^{c}\right) \cap \left( A_{3}^{c}\cup \phi \right) \quad \cdots (2)
\end{equation}となります。さて、\begin{eqnarray*}
A^{c}\left( A_{1}^{c},A_{2}^{c},A_{3}^{c},U,\phi \right) &=&\left( \left(
A_{1}^{c}\cap A_{2}\right) \cup \left( A_{3}\cap U\right) \right) ^{c}\quad
\because \left( 1\right) \\
&=&\left( A_{1}^{c}\cap A_{2}\right) ^{c}\cap \left( A_{3}\cap U\right)
^{c}\quad \because \text{ド・モルガンの法則} \\
&=&\left( A_{1}\cup A_{2}^{c}\right) \cap \left( A_{3}^{c}\cup \phi \right)
\quad \because \text{ド・モルガンの法則} \\
&=&A^{D}\left( A_{1},A_{2},A_{3},U,\phi \right) \quad \because \left(
2\right)
\end{eqnarray*}となるため、\begin{equation*}
A^{D}\left( A_{1},A_{2},A_{3},U,\phi \right) =A^{c}\left(
A_{1}^{c},A_{2}^{c},A_{3}^{c},U,\phi \right)
\end{equation*}という関係が成り立つことが示されました。つまり、集合\(A\left(A_{1},A_{2},A_{3},U,\phi \right) \)の双対は、この集合中の集合\(A_{1},A_{2},A_{3}\)を補集合\(A_{1}^{c},A_{2}^{c},A_{3}^{c}\)に入れ替えて得られる集合の補集合と一致します。

以上の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双対原理を利用します。

命題(第1双対原理)
集合\(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*}という関係が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(第1双対原理)
集合\(A,B\)を被演算子とする集合\(A\cap B\)が与えられたとき、第1双対原理より、その双対である\(A\cup B\)について、\begin{equation*}A\cup B=\left( A^{c}\cap B^{c}\right) ^{c}
\end{equation*}という関係が成り立ちます。これはド・モルガンの法則に他なりません。

例(第1双対原理)
集合\(A,B\)および全体集合\(U\)を被演算子とする集合\(A\cap \left( B^{c}\cup U\right) \)が与えられたとき、第1双対原理より、その双対である\(A\cup \left( B^{c}\cap \phi \right) \)について、\begin{equation*}A\cup \left( B^{c}\cap \phi \right) =\left( A^{c}\cap \left( B\cup U\right)
\right) ^{c}
\end{equation*}という関係が成り立ちます。実際、\begin{eqnarray*}
\left( A^{c}\cap \left( B\cup U\right) \right) ^{c} &=&A\cup \left( B\cup
U\right) ^{c}\quad \because \text{ド・モルガンの法則} \\
&=&A\cup \left( B^{c}\cap \phi \right) \quad \because \text{ド・モルガンの法則}
\end{eqnarray*}であることから確認できます。

例(第1双対原理)
集合\(A,B,C\)と全体集合\(U\)を被演算子とする集合\(\left( B\cap C^{c}\right) \cup \left( D^{c}\cap U\right) \)が与えられたとき、第1双対原理より、その双対である\(\left( B\cup C^{c}\right) \cap \left(D^{c}\cup \phi \right) \)について、\begin{equation*}\left( B\cup C^{c}\right) \cap \left( D^{c}\cup \phi \right) =\left( \left(
B^{c}\cap C\right) \cup \left( D\cap U\right) \right) ^{c}
\end{equation*}という関係が成り立ちます。実際、\begin{eqnarray*}
\left( \left( B^{c}\cap C\right) \cup \left( D\cap U\right) \right) ^{c}
&=&\left( B^{c}\cap C\right) ^{c}\cap \left( D\cap U\right) ^{c}\quad
\because \text{ド・モルガンの法則} \\
&=&\left( B\cup C^{c}\right) \cap \left( D^{c}\cup \phi \right) \quad
\because \text{ド・モルガンの法則}
\end{eqnarray*}であることから確認できます。

 

第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双対原理を利用します。

命題(第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双対原理)
集合\(A,B\)に関して、\begin{equation*}A\cap B\subset A
\end{equation*}が成り立ちますが(確認してください)、このとき、第2双対原理より、\begin{equation*}
A\subset A\cup B
\end{equation*}もまた成り立つことが保証されます。実際、これは正しい主張です(確認してください)。

例(第2双対原理)
集合\(A,B\)に関して、\begin{equation*}\left( A\cap B\right) ^{c}\subset A^{c}\cup B^{c}
\end{equation*}が成り立ちますが(確認してください)、このとき、第2双対原理より、\begin{equation*}
A^{c}\cap B^{c}\subset \left( A\cup B\right) ^{c}
\end{equation*}もまた成り立つことが保証されます。実際、これは正しい主張です(確認してください)。

 

第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\)が等しいとき、それらの双対どうしも等しいことが保証されます。

命題(第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{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*}という関係が成り立つ。

例(双対原理)
ベキ等律とは、任意の集合\(A\)に対して、\begin{eqnarray*}\left( a\right) \ A\cap A &=&A \\
\left( b\right) \ A\cup A &=&A
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
交換律とは、任意の集合\(A,B\)に対して、\begin{eqnarray*}\left( a\right) \ A\cap B &=&B\cap A \\
\left( b\right) \ A\cup B &=&B\cup A
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
結合律とは、任意の集合\(A,B,C\)に対して、\begin{eqnarray*}\left( a\right) \ (A\cap B)\cap C &=&A\cap (B\cap C) \\
\left( b\right) \ (A\cup B)\cup C &=&A\cup (B\cup C)
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
分配律とは、任意の集合\(A,B,C\)について、\begin{eqnarray*}\left( a\right) \ A\cap (B\cup C) &=&(A\cap B)\cup (A\cap C) \\
\left( b\right) \ A\cup (B\cap C) &=&(A\cup B)\cap (A\cup C)
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
吸収律とは、任意の集合\(A,B\)について、\begin{eqnarray*}\left( a\right) \ A\cap \left( A\cup B\right) &=&A \\
\left( b\right) \ A\cup \left( A\cap B\right) &=&A
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
ド・モルガンの法則とは、任意の集合\(A,B\)について、\begin{eqnarray*}\left( a\right) \ \left( A\cap B\right) ^{c} &=&A^{c}\cup B^{c} \\
\left( b\right) \ \left( A\cup B\right) ^{c} &=&A^{c}\cap B^{c}
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。
例(双対原理)
補集合法則とは、空集合\(\phi \)と全体集合\(U\)について、\begin{eqnarray*}&&\left( a\right) \ \phi ^{c}=U \\
&&\left( b\right) \ U^{c}=\phi
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。もう一つの補集合法則とは、任意の集合\(A\)について、\begin{eqnarray*}&&\left( c\right) \ A\cap A^{c}=\phi \\
&&\left( d\right) \ A\cup A^{c}=U
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(c\right) \)に双対原理を適用すれば\(\left( d\right) \)を得て、逆に、\(\left( d\right) \)に双対原理を適用すれば\(\left( c\right) \)を得ます。
例(双対原理)
恒等法則とは、任意の集合\(A\)について、\begin{eqnarray*}&&\left( a\right) \ A\cap \phi =\phi \\
&&\left( b\right) \ A\cup U=U
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(a\right) \)に双対原理を適用すれば\(\left( b\right) \)を得て、逆に、\(\left( b\right) \)に双対原理を適用すれば\(\left( a\right) \)を得ます。もう一つの補集合法則とは、任意の集合\(A\)について、\begin{eqnarray*}&&\left( c\right) \ A\cup \phi =A \\
&&\left( d\right) \ A\cap U=A
\end{eqnarray*}がともに成り立つという命題ですが、\(\left(c\right) \)に双対原理を適用すれば\(\left( d\right) \)を得て、逆に、\(\left( d\right) \)に双対原理を適用すれば\(\left( c\right) \)を得ます。

関連知識

前のページ:

二重補集合の法則

次のページ:

集合族(集合系)

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員専用コンテンツです
ログイン】【会員登録