WIIS

教材一覧
教材一覧
教材検索
CARDINALITY OF SET

有限集合の和集合の濃度(包除原理)

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

互いに素な2つの有限集合の和集合の濃度

2つの集合\(A,B\)がともに有限集合であるとともに互いに素である場合、すなわち、\begin{equation*}A\cap B=\phi
\end{equation*}が成り立つ場合、和集合\(A\cup B\)もまた有限集合になるとともに、これらの集合の濃度の間には、\begin{equation*}\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert
\end{equation*}という関係が成り立つことが保証されます。つまり、互いに素な有限集合どうしの和集合の濃度は、個々の集合の濃度の和に等しいということです。

命題(互いに素な2つの有限集合の和集合の濃度)
集合\(A,B\)がともに有限集合であるとともに互いに素であるならば、和集合\(A\cup B\)もまた有限集合であるとともに、\begin{equation*}\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert
\end{equation*}という関係が成り立つ。

証明

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

 

2つの有限集合の和集合の濃度(包除原理)

2つの有限集合\(A,B\)が互いに素であるとは限らない場合、和集合\(A\cup B\)の濃度についてどのようなことが言えるでしょうか。互いに素であるとは限らない集合\(A,B\)の和集合に関して以下の集合変形\begin{equation*}A\cup B=\left( A\backslash B\right) \cup \left( B\backslash A\right) \cup
\left( A\cap B\right)
\end{equation*}が可能であることと先の命題を踏まえると以下を得ます。これを包除原理(inclusion-exclusion principle)と呼びます。

命題(2つの有限集合の和集合の濃度)
集合\(A,B\)がともに有限集合であるならば、和集合\(A\cup B\)もまた有限集合であるとともに、\begin{equation*}\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cap B\right\vert
\end{equation*}という関係が成り立つ。

証明

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

例(包除原理)
\(1\)以上\(100\)以下の整数の中に\(2\)もしくは\(3\)の倍数はいくつ存在するでしょうか。\(1\)以上\(100\)以下の整数の中でも\(2\)で割れるものからなる集合を\(A\)で表記するのであれば、\begin{equation}\left\vert A\right\vert =50 \quad \cdots (1)
\end{equation}が成り立ちます。また、\(1\)以上\(100\)以下の整数の中でも\(3\)で割れるものからなる集合を\(B\)で表記するのであれば、\begin{equation}\left\vert B\right\vert =33 \quad \cdots (2)
\end{equation}が成り立ちます。\(1\)以上\(100\)以下の整数の中でも\(2\)と\(3\)で割り切れるもの、すなわち\(6\)で割り切れるものからなる集合は\(A\cap B\)であり、\begin{equation}\left\vert A\cap B\right\vert =16 \quad \cdots (3)
\end{equation}となります。問題としているのは和集合\(A\cup B\)の濃度であるため、\begin{eqnarray*}\left\vert A\cup B\right\vert &=&\left\vert A\right\vert +\left\vert
B\right\vert -\left\vert A\cap B\right\vert \quad \because \text{除法原理} \\
&=&50+33-16 \\
&=&67
\end{eqnarray*}となります。したがって答えは\(67\)個です。

 

有限個の有限集合の和集合の濃度(包除原理の一般化)

先の命題は3個以上の有限集合の和集合に関しても拡張可能です。証明では集合の個数\(n\)に関する数学的帰納法を利用します。

命題(有限個の有限集合の和集合の濃度)
有限\(n\)個の集合\(A_{1},A_{2},\cdots ,A_{n}\)がいずれも有限集合であるならば、和集合\(A_{1}\cup A_{2}\cup \cdots \cup A_{n}\)もまた有限集合であるとともに、\begin{eqnarray*}\left\vert A_{1}\cup A_{2}\cup \cdots \cup A_{n}\right\vert &=&\left\vert
A_{1}\right\vert +\left\vert A_{2}\right\vert +\cdots +\left\vert
A_{n}\right\vert \\
&&-\left\vert A_{1}\cap A_{2}\right\vert -\left\vert A_{1}\cap
A_{3}\right\vert -\cdots -\left\vert A_{n-1}\cap A_{n}\right\vert \\
&&+\left\vert A_{1}\cap A_{2}\cap A_{3}\right\vert +\cdots +\left\vert
A_{n-2}\cap A_{n-1}\cap A_{n}\right\vert \\
&&\vdots \\
&&+\left( -1\right) ^{n-1}\left\vert A_{1}\cap A_{2}\cap \cdots \cap
A_{n}\right\vert
\end{eqnarray*}という関係が成り立つ。

このままでは分かりづらいため、上の命題中の\(n\)に具体的な数を入れてみます。

例(3個の有限集合の和集合の濃度)
\(3\)個の集合\(A_{1},A_{2},A_{3}\)がいずれも有限集合であるならば、上の命題より和集合\(A_{1}\cup A_{2}\cup A_{3}\)もまた有限集合であるとともに、\begin{eqnarray*}\left\vert A_{1}\cup A_{2}\cup A_{3}\right\vert &=&\left\vert
A_{1}\right\vert +\left\vert A_{2}\right\vert +\left\vert A_{3}\right\vert
\\
&&-\left\vert A_{1}\cap A_{2}\right\vert -\left\vert A_{1}\cap
A_{3}\right\vert -\left\vert A_{2}\cap A_{3}\right\vert \\
&&+\left\vert A_{1}\cap A_{2}\cap A_{3}\right\vert
\end{eqnarray*}という関係が成り立ちます。

例(4個の有限集合の和集合の濃度)
\(4\)個の集合\(A_{1},A_{2},A_{3},A_{4}\)がいずれも有限集合であるならば、上の命題より和集合\(A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\)もまた有限集合であるとともに、\begin{eqnarray*}\left\vert A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\right\vert &=&\left\vert
A_{1}\right\vert +\left\vert A_{2}\right\vert +\left\vert A_{3}\right\vert
+\left\vert A_{4}\right\vert \\
&&-\left\vert A_{1}\cap A_{2}\right\vert -\left\vert A_{1}\cap
A_{3}\right\vert -\left\vert A_{1}\cap A_{4}\right\vert -\left\vert
A_{2}\cap A_{3}\right\vert -\left\vert A_{2}\cap A_{4}\right\vert
-\left\vert A_{3}\cap A_{4}\right\vert \\
&&+\left\vert A_{1}\cap A_{2}\cap A_{3}\right\vert +\left\vert A_{1}\cap
A_{2}\cap A_{4}\right\vert +\left\vert A_{2}\cap A_{3}\cap A_{4}\right\vert
\\
&&-\left\vert A_{1}\cap A_{2}\cap A_{3}\cap A_{4}\right\vert
\end{eqnarray*}という関係が成り立ちます。

つまり、有限\(n\)個の集合\(A_{1},A_{2},\cdots ,A_{n}\)の和集合の濃度を求めるためには、まず、\(n\)個の集合の濃度を足し、次に、\(n\)個の集合から\(2\)個を選んでできる共通部分(このような共通部分は\(\binom{n}{2}\)通り存在する)の濃度の総和を引き、次に、\(n\)個の集合から\(3\)個を選んでできる共通部分(このような共通部分は\(\binom{n}{3}\)通り存在する)の濃度の総和を足し、次に、\(n\)個の集合から\(4\)個を選んでできる共通部分(このような共通部分は\(\binom{n}{4}\)通り存在する)の濃度の総和を引き、\(\cdots \)という作業を続け、最終的に、\(n\)が奇数ならば\(n\)個の集合の共通部分の濃度を足し、\(n\)が偶数ならば\(n\)個の集合の共通部分の濃度を引けばよいということです。

例(包除原理)
\(1\)以上\(60\)以下の整数の中に\(3\)または\(4\)または\(5\)の中の少なくとも1つで割り切れる数はいくつ存在するでしょうか。\(1\)以上\(60\)以下の整数の中でも\(3\)で割れるものからなる集合を\(A\)で表記するのであれば、\begin{equation*}\left\vert A\right\vert =20
\end{equation*}が成り立ちます。また、\(1\)以上\(60\)以下の整数の中でも\(4\)で割れるものからなる集合を\(B\)で表記するのであれば、\begin{equation*}\left\vert B\right\vert =15
\end{equation*}が成り立ちます。さらに、\(1\)以上\(60\)以下の整数の中でも\(5\)で割れるものからなる集合を\(C\)で表記するのであれば、\begin{equation*}\left\vert C\right\vert =12
\end{equation*}が成り立ちます。\(1\)以上\(60\)以下の整数の中でも\(3\)と\(4\)で割り切れるもの、すなわち\(12\)で割り切れるものからなる集合は\(A\cap B\)であり、\begin{equation*}\left\vert A\cap B\right\vert =5
\end{equation*}となります。\(1\)以上\(60\)以下の整数の中でも\(3\)と\(5\)で割り切れるもの、すなわち\(15\)で割り切れるものからなる集合は\(A\cap C\)であり、\begin{equation*}\left\vert A\cap C\right\vert =4
\end{equation*}となります。\(1\)以上\(60\)以下の整数の中でも\(4\)と\(5\)で割り切れるもの、すなわち\(20\)で割り切れるものからなる集合は\(B\cap C\)であり、\begin{equation*}\left\vert B\cap C\right\vert =3
\end{equation*}となります。\(1\)以上\(60\)以下の整数の中でも\(3\)と\(4\)と\(5\)で割り切れるもの、すなわち\(60\)で割り切れるものからなる集合は\(A\cap B\cap C\)であり、\begin{equation*}\left\vert A\cap B\cap C\right\vert =1
\end{equation*}となります。問題としているのは和集合\(A\cup B\cup C\)の濃度ですが、\begin{eqnarray*}\left\vert A\cup B\cup C\right\vert &=&\left\vert A\right\vert +\left\vert
B\right\vert +\left\vert C\right\vert -\left\vert A\cap B\right\vert
-\left\vert A\cap C\right\vert -\left\vert B\cap C\right\vert +\left\vert
A\cap B\cap C\right\vert \quad \because \text{除法原理} \\
&=&20+15+12-5-4-3+1 \\
&=&36
\end{eqnarray*}となります。したがって答えは\(36\)個です。

 

演習問題

問題(包除原理)
期末試験を実施したところ、全受験者の\(80\)パーセントは国語の試験に合格し、全受験者の\(85\)パーセントが数学の試験に合格しました。また、\(75\)パーセントが国語と数学の両方の試験に合格しました。加えて、国語と数学の両方の試験で不合格であった受験者の数が\(45\)人でした。全受験者の人数を求めてください。
証明

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

問題(包除原理)
ある会社には\(1000\)人の社員がおり、それぞれの社員は日本語・英語・中国語の中の少なくとも1つを話すことができるものとします。以下の条件が与えられているとき、三か国語をすべて話すことができる社員の人数を明らかにしてください。

  1. 日本語を話せるのは\(310\)人
  2. 英語を話せるのは\(650\)人
  3. 中国語を話せるのは\(440\)人
  4. 日本語を英語の両方を話せるのは\(170\)人
  5. 日本語と中国語の両方を話せるのは\(150\)人
  6. 英語と中国語の両方を話せるのは\(180\)人
解答を見る

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

Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

有限濃度
有限集合

有限個の要素を持つ集合を有限集合と呼びます。有限集合の濃度を有限濃度と呼びます。有限集合どうしの濃度が等しいことと、それらの集合に含まれる要素の個数が等しいことは必要十分です。

有限集合
有限集合の部分集合の濃度

有限集合Aの部分集合Bもまた有限集合であるとともに、Bの濃度はAの濃度以下です。また、有限集合Aの真部分集合Bもまた有限集合であるとともに、Bの濃度はAの濃度よりも小さいです。

有限集合
有限集合の直積集合の濃度

有限個の有限集合の直積集合もまた有限集合であることを示すとともに、その濃度を具体的に求める方法について解説します。

有限集合
鳩の巣原理(ディリクレの箱入れ原理)

集合A,Bがともに有限集合であるとともにAの濃度がBの濃度よりも大きい場合にはAからBへの単射は存在しません。これを鳩の巣原理やディリクレの箱入れ原理などと呼びます。

可算集合
可算集合の和集合の濃度

2つの可算集合の和集合、有限個の可算集合の和集合、可算個の可算集合の和集合はいずれも可算集合になります。

和事象
和事象

事象 A と事象 B の和集合として定義される事象を A と B の和事象と呼びます。これは「A と B の少なくとも一方が起こる」という現象に相当する事象です。

和集合
述語論理における論理和

論理式 A,B に論理演算子 ∨ を作用させることで得られる A∨B もまた論理式です。∨ は論理和と呼ばれる論理演算子であり、論理式 A∨B )を A と B の論理和と呼びます。

和集合
和集合

集合 A,B の少なくとも一方に属する要素からなる集合を A と B の和集合と呼びます。 A が命題関数 P(x) から、集合 B が命題関数 Q(x) からそれぞれ内包的に定義されるとき、A と B の和集合は 2 つの命題 P(x),Q(x) の少なくとも一方が真になるような要素 x からなる集合です。

有限集合
有限型確率空間

標本空間が有限集合であるとき、その任意の部分集合を事象として考察対象に含めることができます。その上で、標本空間のベキ集合上に集合関数を定義した上で、それが確率論の公理と呼ばれる性質を満たすものと定めます。こうして得られる概念を有限確率空間と呼びます。

和集合
命題論理における選言導入

論理式 A,B を任意に選んだとき、「Aである」(もしくは「Bである」)という前提から「AまたはB」という結論を導く推論規則を選言導入と呼びます。

和集合
集合族の和集合

集合族の要素である少なくとも1つの集合に含まれる要素からなる集合を集合族の和集合と定義します。集合族の和集合は、その集合族の要素である任意の集合を部分集合として含む集合の中でも最小のものです。

DISCUSSION

質問とコメント

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