2020年度「離散数学」のページ
資料
集合の濃度 — ???
■
\(A\subset B\) ならば \(\sharp A\le\sharp B\) が成り立つ。
証明
\(f:A\rightarrow B\) を
\[
f(x)=x
\]
で定めれば、\(f\) は単射。
なぜならば、\(f\) の定義より、
\[
f(x)=f(x')\;\Rightarrow\;x=x'
\]
系
\(\sharp(A\cap B)\le\sharp A\)
系
\(\sharp(A\setminus B)\le\sharp A\)
系
\(A\subset B\) かつ \(B\) が有限集合ならば \(A\) も有限集合。
証明
\[
\text{$A\subset B$ かつ $B$ が有限集合}
\;\Rightarrow\;
\sharp A\le\sharp B \text{ かつ } \sharp B<\aleph_0
\;\Rightarrow\;
\sharp A<\aleph_0
\]
系
\(A\subset B\) かつ \(A\) が無限集合ならば \(B\) も無限集合。
証明
\[
\text{$A\subset B$ かつ $A$ が無限集合}
\;\Rightarrow\;
\sharp A\le\sharp B \text{ かつ } \sharp A\ge\aleph_0
\;\Rightarrow\;
\sharp B\ge\aleph_0
\]
■
\(A\) と \(B\) が有限集合ならば、\(A\cup B\) も有限集合。
証明
\(A\cap B=\varnothing\) の場合、
\(f:A\rightarrow\{0,\dots,m-1\}\),
\(g:B\rightarrow\{0,\dots,n-1\}\)
ともに全単射とする。
\(h:A\cup B\rightarrow\{0,\dots,m+n-1\}\) を
\[
h(x)=
\begin{cases}
f(x) & x\in A\text{ のとき}
\\
g(x)+m & x\in B\text{ のとき}
\end{cases}
\]
で定めると、\(h\) は全単射である。
一般の場合、\(B'=B\setminus A\) とおくと、\(A\cup B'=A\cup B\) かつ \(A\cap B'=\varnothing\) なので、さきほどの場合に帰着できる。
■
\(\sharp A=\aleph_0\) かつ \(\sharp B\le\aleph_0\) ならば、\(\sharp(A\cup B)=\aleph_0\) である。
■
\(\sharp A=2^{\aleph_0}\) かつ \(\sharp B\le2^{\aleph_0}\) ならば、\(\sharp(A\cup B)=2^{\aleph_0}\) である。
戻る