等しい 2 つの集合が与えられたとき、それらの双対をとるとそれらもまた等しくなります。これを双対原理と呼びます。
< 前のページ

集合の双対

集合演算子として\(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\)に対して以下の操作を加えることで得られる新たな集合を\(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) ^{c}\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( U\cup C^{c}\right) ^{c}\)です。

 

第1双対原理

集合\(A_{1},\cdots ,A_{n}\)と全体集合\(U\)および空集合\(\phi \)を被演算子とする集合を\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)と表記します。ただし、\(A\)に含まれる集合演算子は\(c,\cap ,\cup \)だけであり、\(\backslash ,\triangle \)はいずれも先の要領で\(c,\cap ,\cup \)に変換されているものとします。また、集合\(A_{1},\cdots ,A_{n},U,\phi \)はそれぞれ、\begin{eqnarray*}
A_{1} &=&\left\{ x\in U\ |\ P_{1}\left( x\right) \right\} \\
&&\vdots \\
A_{n} &=&\left\{ x\in U\ |\ P_{n}\left( x\right) \right\} \\
U &=&\left\{ x\in U\ |\ T\right\} \\
\phi &=&\left\{ x\in U\ |\ F\right\}
\end{eqnarray*}という形で内包的に定義されているものとします。ただし、\(P_{1}\left( x\right) ,\cdots ,P_{n}\left( x\right) \)は命題関数であり、\(T\)と\(F\)は命題定数です。その上で、集合\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)を内包的に定義する論理式を\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)で表します。この論理式の双対を\(A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \)で表すとき、第1双対定理より、\begin{equation*}
A^{D}\left( P_{1},\cdots ,P_{n},T,F\right) =\lnot A\left( \lnot P_{1},\cdots
,\lnot P_{n},T,F\right)
\end{equation*}という関係が成り立ちます。もとの集合\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)の双対を\(A^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) \)で表すとき、上の関係は、\begin{equation*}
A^{D}\left( A_{1},\cdots ,A_{n},U,\phi \right) =\left( A\left(
A_{1}^{c},\cdots ,A_{n}^{c},U,\phi \right) \right) ^{c}
\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 principle duality)や第1双対定理(first duality theorem)などと呼びます。

命題(第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) =\left( A\left(
A_{1}^{c},\cdots ,A_{n}^{c},U,\phi \right) \right) ^{c}
\end{equation*}という関係が成り立つ。
証明を見る(プレミアム会員限定)
例(第1双対原理)
集合\(B,C\)を被演算子とする集合を、\begin{equation}
A\left( B,C\right) =B\cap C \tag{1}
\end{equation}と定義すると、その双対は、\begin{equation}
A^{D}\left( B,C\right) =B\cup C \tag{2}
\end{equation}となります。このとき、\begin{eqnarray*}
\left( A\left( B^{c},C^{c}\right) \right) ^{c} &=&\left( B^{c}\cap
C^{c}\right) ^{c}\quad \because \left( 1\right) \\
&=&B\cup C\quad \because \text{ド・モルガンの法則} \\
&=&A^{D}\left( B,C\right) \quad \because \left( 2\right)
\end{eqnarray*}となりますが、この結果は第1双対原理と整合的です。
例(第1双対原理)
集合\(B,C,D\)と全体集合\(U\)を被演算子とする集合を、\begin{equation}
A\left( B,C,D,U\right) =\left( B\cap C^{c}\right) \cup \left( D^{c}\cap
U\right) \tag{1}
\end{equation}と定義すると、その双対は、\begin{equation}
A^{D}\left( B,C,D,U\right) =\left( B\cup C^{c}\right) \cap \left( D^{c}\cup
\phi \right) \tag{2}
\end{equation}となります。このとき、\begin{eqnarray*}
\left( A\left( B^{c},C^{c},D^{c},U\right) \right) ^{c} &=&\left( \left(
B^{c}\cap C^{cc}\right) \cup \left( D^{cc}\cap U\right) \right) ^{c}\quad
\because \left( 1\right) \\
&=&\left( \left( B^{c}\cap C\right) \cup \left( D\cap U\right) \right)
^{c}\quad \because \text{反射律} \\
&=&\left( B^{c}\cap C\right) ^{c}\cap \left( D\cap U\right) ^{c}\quad
\because \text{ド・モルガンの法則} \\
&=&\left( B^{cc}\cup C^{c}\right) \cap \left( D^{c}\cup U^{c}\right) \quad
\because \text{ド・モルガンの法則} \\
&=&\left( B\cup C^{c}\right) \cap \left( D^{c}\cup \phi \right) \quad
\because \text{反射律} \\
&=&A^{D}\left( B,C,D,U\right) \quad \because \left( 2\right)
\end{eqnarray*}となりますが、この結果は第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) \tag{1}
\end{equation}という関係が成り立つものとします。\(A\left( A_{1},\cdots ,A_{n},U,\phi \right) \)を内包的に定義する論理式\(A\left( P_{1},\cdots ,P_{n},T,F\right) \)で、\(B\left( A_{1},\cdots ,A_{n},U,\phi \right) \)を内包的に定義する論理式を\(B\left( P_{1},\cdots ,P_{n},T,F\right) \)でそれぞれ表すとき、\(\left( 1\right) \)のもとでは、\begin{equation*}
A\left( P_{1},\cdots ,P_{n},T,F\right) \Rightarrow B\left( P_{1},\cdots
,P_{n},T,F\right)
\end{equation*}という関係が成り立ちます。すると、第2双対原理より、この2つの論理式の双対の間には、\begin{equation*}
B^{D}\left( P_{1},\cdots ,P_{n},T,F\right) \Rightarrow A^{D}\left(
P_{1},\cdots ,P_{n},T,F\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*}を得ます。つまり、集合\(A,B\)の間に\(A\subset B\)が成り立つとき、それらの双対\(A^{D},B^{D}\)の間に\(B^{D}\subset A^{D}\)が成り立つと言うことです。これを集合演算に関する第2双対原理(second principle duality)や第2双対定理(second duality theorem)などと呼びます。

命題(第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*}という関係が成り立つ。
証明を見る(プレミアム会員限定)

 

第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*}であることを意味します。つまり、集合\(A,B\)の間に\(A=B\)が成り立つとき、それらの双対\(A^{D},B^{D}\)の間に\(A^{D}=B^{D}\)が成り立つと言うことです。これを集合演算に関する第3双対原理(third principle duality)や第3双対定理(third duality theorem)などと呼びます。

命題(第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) \)を得ます。

次回からは集合族について学びます。

次へ進む 質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
< 前のページ

プレミアム会員サービス

ユーザー名とメールアドレスを入力して有料(500円/月)のプレミアム会員へアップグレードすることにより、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題、解答など)へのアクセスが可能に。
会員サービス
ログイン

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

アカウント
ログイン