有限集合の基本性質の証明は意外と複雑

2020/06/26

今日の目標

有限集合の基本的な性質を示す。

この記事で使う記号や用語
  • $\NN$ を非負整数全体の集合とする。
  • $n \in \NN$ に対し $[n]$${} = \iset{i \in \NN}{1 \leq i \leq n}$ とする。
  • 写像 $f: X \rightarrow Y$ と $A \subseteq X$ に対し、$f$ の $A$ への制限写像を $f|_A$ と書く。

「有限集合の部分集合は有限集合」って本当に自明?

命題 有限集合の部分集合は有限集合である。
mizuha
これはもちろん成り立つわけだけど
証明できる?
kureha
え 何か証明することあるのこれ
mizuha
有限集合の定義は?
kureha
あー……
ある自然数 $n$ に対して
$[n]$ との全単射が存在する集合
mizuha
つまりこの命題を示すには
・集合 $A$
・自然数 $n$
・全単射 $f: [n] \rightarrow A$
・$A$ の部分集合 $B$
が与えられたときに
自然数 $m$ と全単射 $[m] \rightarrow B$ が
存在することを示さないといけない
kureha
ああ 意外と厄介だねこれ
kureha
鳩の巣原理も証明長かったし
これも似たような感じか
mizuha
今日は有限集合の基本性質をいろいろ示してくよ

有限集合の基本性質

mizuha
まずは肩慣らし
命題1

集合 $A$ と有限集合 $B$ に対し、以下は同値。

(1)

$A$ は有限集合で $\abs{A} = \abs{B}$

(2)

$A$ から $B$ への全単射が存在する

証明
(1) ${}\implies{}$ (2)

$n = \abs{A} = \abs{B}$ とし、全単射 $f: [n] \rightarrow A$ と全単射 $g: [n] \rightarrow B$ を取ると、全単射 $$g \circ f^{\minus 1}: A \rightarrow B$$ を構成できる。

(1) ${}\impliedby{}$ (2)

$n = \abs{B}$ とし、全単射 $f: [n] \rightarrow B$ を取る。全単射 $g: A \rightarrow B$ を一つ取ると、 $$g^{\minus 1} \circ f: [n] \rightarrow A$$ も全単射なので、$A$ は有限集合で $\abs{A} = n = \abs B$。


mizuha
「有限集合の部分集合は有限集合」以外にも
いろいろ示しておきたいことがあるから
mizuha
集合が有限であるかどうかを判定する
便利な道具を作っておこう
補題2

自然数 $n$ と空でない集合 $A$ に対し、以下は同値。

$\text{(I)}$

$A$ は要素数 $n$ 以下の有限集合

$\text{(II)}$

全射 $[n] \rightarrow A$ が存在する

$\text{(III)}$

単射 $A \rightarrow [n]$ が存在する

また $A$ が空集合であるか否かに関わらず $\text{(I)} \iff \text{(III)} \impliedby \text{(II)}$ は常に成立。

証明

まず $A \neq \varnothing$ のときを考える。

$\text{(I)} \implies{} \text{(III)}$

$m = \abs A \leq n$ とし、全単射 $f: A \rightarrow [m]$ を取ると、包含写像 $\iota: [m] \rightarrow [n]$ は単射なので、単射 $\iota \circ f: A \rightarrow [n]$ を構成できる。

$\text{(III)} {}\implies{} \text{(II)}$

空でない集合 $A$ から $[n]$ への単射が存在するので、始域と終域が逆の全射 $[n] \rightarrow A$ も存在する。

$\text{(II)}$ ${}\implies{}$ $\text{(I)}$

$n$ についての数学的帰納法で示す。

Base Case

全射 $\varnothing \rightarrow A$ が存在するので $A = \varnothing$ であり、これは要素数 $0$ の有限集合。

Induction Step

全射 $f: [n+1] \rightarrow A$ が存在するとする。$f$ の $[n]$ への制限写像 $f|_{[n]}$ を $[n]$ から $f([n])$ への全射とみなすと、帰納法の仮定より

$f([n])$ は要素数 $n$ 以下の有限集合

である。$f([n]) = A$ のときは自明。以下 $f([n]) \neq A$ とする。$f$ の全射性より $$A = f([n]) \cup \cbr{f(n+1)}$$ は非交叉和である。 $m = \abs{f([n])} \leq n$ とし、全単射 $g: [m] \rightarrow f([n])$ を取る。このとき、写像 $h: [m + 1] \rightarrow A$ を $$ h(i) = \begin{cases} g(i) & \text{($i \in [m]$ のとき)} \\ f(n+1) & \text{($i = m+1$ のとき)} \end{cases} $$ で定めると $h$ は全単射。よって $A$ は有限集合で $\abs A = m + 1 \leq n + 1$ である。

$A = \varnothing$ のときは $\text{(I)}$ も $\text{(III)}$ も真なので、$\text{(I)} \iff \text{(III)} \impliedby \text{(II)}$ が成立。

注意

$n \geq 1$ かつ $A = \varnothing$ のとき、$\text{(I)}$ と $\text{(III)}$ は真だが、$\text{(II)}$ は偽である。

mizuha
いま示した補題を一般化しよう
命題3

空でない集合 $A$ と有限集合 $B$ に対し、以下は同値。

$\text{(I)’}$

$A$ は要素数 $\abs B$ 以下の有限集合である

$\text{(II)’}$

全射 $B \rightarrow A$ が存在する

$\text{(III)’}$

単射 $A \rightarrow B$ が存在する

また $A$ が空集合であるかどうかに関係なく $\text{(I)’} \iff \text{(III)’} \impliedby \text{(II)’}$ は常に成立。

証明

$n = \abs B$ とする。補題2より

全射 $[n] \rightarrow A$ が存在する ${}\iff{}$ 全射 $B \rightarrow A$ が存在する

単射 $A \rightarrow [n]$ が存在する ${}\iff{}$ 単射 $A \rightarrow B$ が存在する

を示せばよい。全単射 $f: [n] \rightarrow B$ を取る。

全射 $[n] \rightarrow A$ が存在する ${}\iff{}$ $\text{(II)}$ 全射 $B \rightarrow A$ が存在する

全射 $g: [n] \rightarrow A$ が存在すれば $g \circ f^{\minus 1}: B \rightarrow A$ が全射。

全射 $h: B \rightarrow A$ が存在すれば $h \circ f: [n] \rightarrow A$ が全射。

単射 $A \rightarrow [n]$ が存在する ${}\iff{}$ $\text{(III)}$ 単射 $A \rightarrow B$ が存在する

単射 $g: A \rightarrow [n]$ が存在すれば $f \circ g: A \rightarrow B$ が全射。

単射 $h: A \rightarrow B$ が存在すれば $f^{\minus 1} \circ h: A \rightarrow [n]$ が単射。

kureha
集合 $A$ が有限であることを示したいなら
「有限集合を $A$ に写す全射」か
「 $A$ を有限集合に写す単射」の
どっちかを作ればいいってことね
mizuha
集合 $A$ の有限性を示すときは
$A$ が空集合かどうかは気にしなくていいけど
「$A$ が有限集合」という事実を使って
全射 $B \rightarrow A$ を作ろうとするときは
$A \neq \varnothing$ のチェックを忘れないこと
kureha
ゼロ除算みたいなもんか

mizuha
便利な道具を作ったから
いろいろ示してみよう
命題4(有限集合の像は有限集合)

写像 $f: X \rightarrow Y$ と有限集合 $A \subseteq X$ に対し、$f(A)$ は有限集合であり、$\abs{f(A)} \leq \abs{A}$ である。特に $f$ が単射ならば $\abs{f(A)} = \abs{A}$ である。

証明

$f$ の $A$ への制限写像 $f|_A$を $A$ から $f(A)$ への全射とみなすと、命題3より $f(A)$ は要素数 $\abs{A}$ 以下の有限集合。

特に $f$ が単射のときは $f|_A$ は $A$ から $f(A)$ への全単射とみなせるので、命題1より $f(A)$ は要素数 $\abs{A}$ の有限集合。

命題5(有限集合の部分集合は有限集合)

有限集合 $A$ の部分集合 $A’$ は有限集合であり、$\abs{A’} \leq \abs A$ である。

証明

包含写像 $\iota: A’ \rightarrow A$ が単射なので、命題3より $A’$ は要素数 $\abs A$ 以下の有限集合。

命題6(有限集合との交叉は有限集合)

有限集合 $A$ と集合 $B$ に対し交叉 $A \cap B$ は有限集合であり、$\abs{A \cap B} \leq \abs A$ である。

証明

$A\cap B$ は $A$ の部分集合なので命題5より従う。

命題7(有限集合の和集合は有限集合)

有限集合 $A, B$ に対し、和集合 $A \cup B$ は要素数 $\abs A + \abs B$ 以下の有限集合。更に次が成り立つ。

$A \cap B = \varnothing$ ${}\iff{}$ $\abs{A \cup B} = \abs A + \abs B$

証明

$n = \abs A, m = \abs B$ とし、$f: A \rightarrow [n]$ と $g: B \rightarrow [m]$ を全単射とする。ここで写像 $h: A \cup B \rightarrow [n + m]$ を $$h(x) = \begin{cases} f(x) & (\text{$x \in A$ のとき}) \\ g(x) + n & (\text{$x \in B \setminus A$ のとき}) \end{cases} $$ で定めると $h$ は単射。よって命題3より $A \cup B$ は要素数 $n + m$ 以下の有限集合。

$A \cap B = \varnothing$ ${}\implies{}$ $\abs{A \cup B} = \abs A + \abs B$

$B \setminus A = B$ なので $h$ は全単射になり、$A \cup B$ は要素数 $n + m$ の有限集合。

$A \cap B = \varnothing$ ${}\impliedby{}$ $\abs{A \cup B} = \abs A + \abs B$

上で示したことにより非交差和の要素数はそれぞれの要素数の和なので、 \begin{align} \abs A &= \abs{A \setminus B} + \abs{A \cap B} \\ \abs B &= \abs{B \setminus A} + \abs{A \cap B} \\ \abs{A \cup B} &= \abs{A \setminus B} + \abs{A \cap B} + \abs{B \setminus A} \end{align} となる。これらを仮定の $\abs{A \cup B} = \abs A + \abs B$ に代入して $2 \abs{A \cap B} = \abs{A \cap B}$ すなわち $\abs{A \cap B} = 0$ となり、 $A \cap B = \varnothing$ を得る。

命題8

有限集合 $A$ とその部分集合 $B$ に対し、$A$ から $B$ への全単射が存在すれば $A = B$ である。

証明

$A$ から $B$ への全単射が存在するので、命題1より $\abs A = \abs B$ であり、一方命題7より $\abs A = \abs{A \setminus B} + \abs B$ である。よって $\abs{A \setminus B} = 0$ となり $A \setminus B = \varnothing$ なので $A = B$。

命題9

有限集合 $A$ に対し、写像 $f: A \rightarrow A$ が単射 ならば $f$ は全単射。

証明

$f$ が単射なので $f$ は $A$ から $f(A)$ への全単射とみなせる。$f(A) \subseteq A$ なので命題8より $A = f(A)$ となり、よって $f$ は全射。

命題10

有限集合 $A$ に対し、写像 $f: A \rightarrow A$ が全射 ならば $f$ は全単射。

証明

$b, c \in A$ で $b \neq c$ なるものを取り、$f(b) \neq f(c)$ を示す。いま

$A = B \cup C$ $\quad$ $B \cap C = \varnothing$ $\quad$ $b \in B$ $\quad$ $c \in C$

を満たす集合 $B, C$ を取る(例えば $B = \cbr{b}, C = A \setminus \cbr{b}$)。このとき $B, C$ は $$\abs A = \abs B + \abs C$$ なる有限集合であり(命題7)、また $f(B), f(C)$ は

$\abs{f(B)} \leq \abs{B}$ $\quad$ $\abs{f(C)} \leq \abs{C}$

なる有限集合(命題4)。よって、$f(A) = f(B) \cup f(C)$ より $$\abs{f(A)} = \abs{f(B) \cup f(C)} \leq \abs{f(B)} + \abs{f(C)} \leq \abs B + \abs C = \abs{A}$$ となる(命題7)が、$f$ の全射性より $f(A) = A$ なので、この不等式は等号が成立する。よって $$\abs{f(B) \cup f(C)} = \abs{f(B)} + \abs{f(C)}$$ であり、命題7より $f(B) \cap f(C) = \varnothing$ である。よって $f(b) \neq f(c)$ が得られた。