教材一覧
CARDINALITY OF SET

有限集合

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

有限集合の濃度が等しいことの意味

集合\(A,B\)が与えられたとき、\(A\)から\(B\)への全単射が存在する場合には\(A\)と\(B\)は等しい濃度を持つと言い、このことを、\begin{equation*}\left\vert A\right\vert =\left\vert B\right\vert
\end{equation*}と表記するものと定めましたが、直感的には、これは何を意味しているのでしょうか。

有限個の要素を持つ集合を有限集合(finite set)と呼びますが、有限集合に話の対象を限定すると、2つの集合の濃度が等しいことと、それらの集合に含まれる要素の個数が等しいことが必要十分になります。このことを以下で示しましょう。

集合\(A,B\)がともに有限\(n\)個の要素を持つものとし、そのことを、\begin{eqnarray*}A &=&\left\{ a_{1},a_{2},\cdots ,a_{n}\right\} \\
B &=&\left\{ b_{1},b_{2},\cdots ,b_{n}\right\}
\end{eqnarray*}と表記します。その上で、写像\(f:A\rightarrow B\)を、\begin{eqnarray*}f\left( a_{1}\right) &=&b_{1} \\
f\left( a_{2}\right) &=&b_{2} \\
&&\vdots \\
f\left( a_{n}\right) &=&b_{n}
\end{eqnarray*}と定義します。この写像\(f\)は全単射です。実際、始集合の要素\(a_{i},a_{j}\in A\)を任意に選んだとき、\begin{equation*}a_{i}\not=a_{j}\Rightarrow f\left( a_{i}\right) \not=f\left( a_{j}\right)
\end{equation*}が成り立つため\(f\)は単射であり、終集合の要素\(b_{i}\in B\)を任意に選んだとき、それに対して、\begin{equation*}f\left( a_{i}\right) =b_{i}
\end{equation*}を満たす\(a_{i}\in A\)が存在するため\(f\)は全射です。したがって\(f\)は全単射であるため、\begin{equation*}\left\vert A\right\vert =\left\vert B\right\vert
\end{equation*}であることが示されました。

逆に、有限集合\(A,B\)について\(\left\vert A\right\vert =\left\vert B\right\vert \)が成り立つものとします。つまり、全単射\(f:A\rightarrow B\)が存在するということです。このとき、\(A\)と\(B\)の要素の個数が異なるものと仮定して矛盾を導きます。\(A\)の要素の個数が\(B\)の要素の個数よりも多いと仮定しても一般性は失われません。写像の定義より、\(f\)は\(A\)のそれぞれの要素\(a\in A\)に対して\(B\)の要素\(f\left(a\right) \in B\)を1つずつ定めます。したがって、\(A\)の要素の個数が\(B\)の要素の個数よりも多い場合には、少なくとも2つの異なる要素\(a,a^{\prime }\in A\)に対して、\begin{equation*}f\left( a\right) =f\left( a^{\prime }\right) \in B
\end{equation*}が成り立ちますが、これは\(f\)が単射ではないことを意味します。したがって\(f\)は全単射ではありません。\(A\)から\(B\)への任意の写像について同様の議論が成立するため、\(A\)から\(B\)への全単射が存在しないことが明らかになりました。これは\(\left\vert A\right\vert =\left\vert B\right\vert \)と矛盾するため、背理法より、\(A\)と\(B\)の要素の個数が等しいことが示されました。

命題(有限集合の濃度が等しいことの意味)
有限集合\(A,B\)が任意に与えられたとき、\(A\)の要素の個数と\(B\)の要素の個数が等しいことと、\(\left\vert A\right\vert =\left\vert B\right\vert \)が成り立つことは必要十分である。

 

有限濃度

すべての有限集合を要素として持つ集合族を\(\mathfrak{A}\)で表記します。先に示したように、有限集合\(A,B\in \mathfrak{A}\)を任意に選んだとき、\begin{equation}\left\vert A\right\vert =\left\vert B\right\vert \Leftrightarrow A\text{と}B\text{の要素の個数は等しい} \quad \cdots (1)
\end{equation}という関係が成り立ちます。濃度の相等関係\(=\)は同値関係であるため、有限集合\(A\in \mathfrak{A}\)を任意に選んだとき、それを代表元とする同値類\(\left[ A\right] \)が定義されますが、集合\(A\)の要素の個数が有限\(n\)個である場合には、\begin{eqnarray*}\left[ A\right] &=&\left\{ B\in \mathfrak{A}\ |\ \left\vert A\right\vert
=\left\vert B\right\vert \right\} \quad \because \text{同値類の定義} \\
&=&\left\{ B\in \mathfrak{A}\ |\ A\text{と}B\text{の要素の個数は等しい}\right\}
\quad \because \left( 1\right) \\
&=&\left\{ B\in \mathfrak{A}\ |\ B\text{の要素の個数は}n\right\} \quad \because A\text{の要素の個数は}n
\end{eqnarray*}となります。つまり、この同値類\(\left[ A\right] \)に属するすべての集合は集合\(A\)と同様に\(n\)個の要素を持っています。言い換えると、この同値類\(\left[ A\right] \)に属するすべての集合は要素の個数に相当する自然数\(n\)を共有しています。そこで、この自然数を有限濃度(finite potency)や濃度(potency)などと呼び、有限集合\(A\)の濃度を、\begin{equation*}\left\vert A\right\vert ,\quad \#A,\quad \mathrm{card}A
\end{equation*}などで表記します。有限濃度は要素の個数と一致するため、集合\(A\)が有限\(n\)個の要素を持つ場合には、\begin{equation*}\left\vert A\right\vert =n
\end{equation*}となります。ちなみに、空集合\(\phi \)は要素を持たないため、その濃度を、\begin{equation*}\left\vert \phi \right\vert =0
\end{equation*}と定めます。

加えて、\(\mathfrak{A}\)の\(=\)による商集合は、\begin{equation*}\mathfrak{A}\backslash ==\left\{ \left[ A\right] \ |\ A\in \mathfrak{A}\right\}
\end{equation*}と定義されますが、商集合の性質より、これは\(\mathfrak{A}\)の分割です。つまり、濃度の大きさ(すなわち要素の個数)を基準に有限集合を分類したとき、それぞれの有限集合は何らかの濃度を持ち、なおかつ、異なる濃度を同時に持つ有限集合は存在しません。言い換えると、それぞれの有限集合には濃度すなわち要素の個数を表す自然数が必ず1つずつ定まるということです。

例(有限濃度)
集合\(A,B,C\)がそれぞれ、\begin{eqnarray*}A &=&\left\{ 1,2,3\right\} \\
B &=&\left\{ a,b,c\right\} \\
C &=&\left\{ c_{1},c_{2},c_{3}\right\}
\end{eqnarray*}で与えられているものとします。これらはいずれも有限集合であり、濃度に関して、\begin{equation*}
\left\vert A\right\vert =\left\vert B\right\vert =\left\vert C\right\vert =3
\end{equation*}が成り立ちます。
例(有限濃度)
集合\(A,B,C\)がそれぞれ、\begin{eqnarray*}A &=&\left\{ 1,2,\cdots ,n\right\} \\
B &=&\left\{ 1,\frac{1}{2},\cdots ,\frac{1}{n}\right\} \\
C &=&\left\{ c_{1},c_{2},\cdots ,c_{n}\right\}
\end{eqnarray*}で与えられているものとします。ただし、\(n\in \mathbb{N} \)です。これらはいずれも有限集合であり、濃度に関して、\begin{equation*}\left\vert A\right\vert =\left\vert B\right\vert =\left\vert C\right\vert =n
\end{equation*}が成り立ちます。
例(有限濃度)
集合\(A,B\)がそれぞれ、\begin{eqnarray*}A &=&\phi \\
B &=&\left\{ x\in \mathbb{R} \ |\ x^{2}=-1\right\}
\end{eqnarray*}で与えられているとき、これらの濃度に関して、\begin{equation*}
\left\vert A\right\vert =\left\vert B\right\vert =0
\end{equation*}が成り立ちます。

 

有限集合

有限個の要素を持つ集合を有限集合と呼んできましたが、以上の議論を踏まえた上で、有限濃度を持つ集合として有限集合(finite set)を定義します。つまり、集合\(A\)が有限集合であることとは、それが空集合であるか、もしくは何らかの自然数\(n\in \mathbb{N} \)が存在して、\begin{equation}\left\vert A\right\vert =n \quad \cdots (1)
\end{equation}が成り立つことを意味します。また、\begin{equation*}\mathbb{N} _{n}=\left\{ 1,\cdots ,n\right\}
\end{equation*}という表記を導入するのであれば、\(\left( 1\right) \)が成り立つことは、全単射\begin{equation*}f:\mathbb{N} _{n}\rightarrow A
\end{equation*}が存在することとして表現することもできます。

例(有限集合)
集合\(A\)が、\begin{equation*}A=\left\{ 11,12,\cdots ,20\right\}
\end{equation*}として与えられています。これは有限個の要素を持つ集合であるため有限集合です。実際、\begin{equation*}\mathbb{N} _{10}=\left\{ 1,2,\cdots ,10\right\}
\end{equation*}と定めた上で、写像\(f:\mathbb{N} _{10}\rightarrow A\)を、それぞれの\(x\in \mathbb{N} _{10}\)に対して、\begin{equation*}f\left( x\right) =x+10
\end{equation*}を定めるものとして定義すると、この\(f\)は全単射です(確認してください)。したがって\(f\)は有限集合であり、その濃度は、\begin{equation*}\left\vert A\right\vert =10
\end{equation*}となります。

 

有限集合の性質

有限集合の濃度は要素の個数と等しいため、有限集合に要素を1つ加えれば、濃度は\(1\)だけ大きくなるはずです。

命題(要素を1つ増やすと濃度が1増える)
有限集合\(A\)と\(x\not\in A\)がそれぞれ任意に与えられたとき、\begin{equation*}\left\vert A\cup \left\{ x\right\} \right\vert =\left\vert A\right\vert +1
\end{equation*}が成り立つ。
証明

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

有限集合の濃度は要素の個数と等しいため、有限集合が\(\mathbb{N} _{n}\)の部分集合であるならば、その濃度は\(n\)以下であるはずです。

命題(包含関係と有限濃度)
集合\(A\)に対してある\(n\in \mathbb{N} \)が存在して\(A\subset \mathbb{N} _{n}\)が成り立つ場合には\(A\)は有限集合であるとともに、\begin{equation*}\left\vert A\right\vert \leq n
\end{equation*}が成り立つ。ただし、\begin{equation*}\mathbb{N} _{n}=\left\{ 1,\cdots ,n\right\}
\end{equation*}である。
証明

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

有限集合の濃度は要素の個数と等しいため、有限集合\(A\)の部分集合\(B\)もまた有限集合であるとともに、\(A\)の濃度は\(B\)の濃度以下であるはずです。

命題(包含関係と有限濃度)
有限集合\(A\)の部分集合\(B\)を任意に選んだとき、\(B\)もまた有限集合であるととともに、\begin{equation*}\left\vert B\right\vert \leq \left\vert A\right\vert
\end{equation*}が成り立つ。
解答を見る

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

有限集合の濃度は要素の個数と等しいため、有限集合から要素を1つ除けば、濃度は\(1\)だけ小さくなるはずです。

命題(要素を1つ減らすと濃度が1減る)
有限集合\(A\)と\(x\in A\)がそれぞれ任意に与えられたとき、\begin{equation*}\left\vert A\backslash \left\{ x\right\} \right\vert =\left\vert
A\right\vert -1
\end{equation*}が成り立つ。
証明

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

有限集合の濃度は要素の個数と等しいため、有限集合の濃度はその任意の真部分集合の濃度よりも大きいはずです。

命題(有限集合の濃度は真部分集合の濃度よりも大きい)
有限集合\(A\)の真部分集合\(B\)を任意に選んだとき、\(B\)は有限集合であるとともに、\begin{equation*}\left\vert B\right\vert <\left\vert A\right\vert
\end{equation*}が成り立つ。
証明

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

 

演習問題

問題(有限集合)
集合\(A\)が、\begin{equation*}A=\left\{ 2,4,6,\cdots ,2n\right\}
\end{equation*}で与えられているとき、\begin{equation*}
\left\vert A\right\vert =n
\end{equation*}が成り立つことを証明してください。
解答を見る

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

次回は無限集合について学びます。

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

事象

標本空間と事象

起こり得るすべての結果は分かっていても、その中のどの結果が実際に起こるかはランダムネスによって支配されている実験や観察を試行と呼びます。試行によって起こり得る個々の結果を標本点と呼び、すべての標本点からなる集合を標本集合と呼びます。試行によって起こり得る現象は標本空間の部分集合として定式化され、それを事象と呼びます。

可算集合

可算集合

すべての自然数からなる集合と等しい濃度を持つ集合を可算集合や可付番集合と呼びます。可算集合には無限個の要素が含まれるため、すべての要素を数え尽くすことはできませんが、要素を1番目から順番に数えることはできます。

標本空間

非可算集合

可算集合ではない無限集合を非可算集合と呼びます。非可算集合の具体例を提示します。

有限集合

有限型確率空間

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

DISCUSSION

質問とコメント

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