有限集合の基本性質の証明は意外と複雑
有限集合の基本的な性質を示す。
- $\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$ と書く。
「有限集合の部分集合は有限集合」って本当に自明？
証明できる？
ある自然数 $n$ に対して
$[n]$ との全単射が存在する集合
・集合 $A$
・自然数 $n$
・全単射 $f: [n] \rightarrow A$
・$A$ の部分集合 $B$
が与えられたときに
自然数 $m$ と全単射 $[m] \rightarrow B$ が
存在することを示さないといけない
これも似たような感じか
https://sorai-note.com/math/pigeonhole/有限集合の基本性質
集合 $A$ と有限集合 $B$ に対し、以下は同値。
$A$ は有限集合で $\abs{A} = \abs{B}$
$A$ から $B$ への全単射が存在する
$n = \abs{A} = \abs{B}$ とし、全単射 $f: [n] \rightarrow A$ と全単射 $g: [n] \rightarrow B$ を取ると、全単射 $$g \circ f^{\minus 1}: A \rightarrow B$$ を構成できる。
$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$。
いろいろ示しておきたいことがあるから
便利な道具を作っておこう
自然数 $n$ と空でない集合 $A$ に対し、以下は同値。
$A$ は要素数 $n$ 以下の有限集合
全射 $[n] \rightarrow A$ が存在する
単射 $A \rightarrow [n]$ が存在する
また $A$ が空集合であるか否かに関わらず $\text{(I)} \iff \text{(III)} \impliedby \text{(II)}$ は常に成立。
まず $A \neq \varnothing$ のときを考える。
$m = \abs A \leq n$ とし、全単射 $f: A \rightarrow [m]$ を取ると、包含写像 $\iota: [m] \rightarrow [n]$ は単射なので、単射 $\iota \circ f: A \rightarrow [n]$ を構成できる。
空でない集合 $A$ から $[n]$ への単射が存在するので、始域と終域が逆の全射 $[n] \rightarrow A$ も存在する。
$n$ についての数学的帰納法で示す。
全射 $\varnothing \rightarrow A$ が存在するので $A = \varnothing$ であり、これは要素数 $0$ の有限集合。
全射 $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)}$ は偽である。
空でない集合 $A$ と有限集合 $B$ に対し、以下は同値。
$A$ は要素数 $\abs B$ 以下の有限集合である
全射 $B \rightarrow A$ が存在する
単射 $A \rightarrow B$ が存在する
また $A$ が空集合であるかどうかに関係なく $\text{(I)’} \iff \text{(III)’} \impliedby \text{(II)’}$ は常に成立。
$n = \abs B$ とする。補題２より
全射 $[n] \rightarrow A$ が存在する ${}\iff{}$ 全射 $B \rightarrow A$ が存在する
単射 $A \rightarrow [n]$ が存在する ${}\iff{}$ 単射 $A \rightarrow B$ が存在する
を示せばよい。全単射 $f: [n] \rightarrow B$ を取る。全射 $g: [n] \rightarrow A$ が存在すれば $g \circ f^{\minus 1}: B \rightarrow A$ が全射。
全射 $h: B \rightarrow A$ が存在すれば $h \circ f: [n] \rightarrow A$ が全射。
単射 $g: A \rightarrow [n]$ が存在すれば $f \circ g: A \rightarrow B$ が全射。
単射 $h: A \rightarrow B$ が存在すれば $f^{\minus 1} \circ h: A \rightarrow [n]$ が単射。
「有限集合を $A$ に写す全射」か
「 $A$ を有限集合に写す単射」の
どっちかを作ればいいってことね
$A$ が空集合かどうかは気にしなくていいけど
「$A$ が有限集合」という事実を使って
全射 $B \rightarrow A$ を作ろうとするときは
$A \neq \varnothing$ のチェックを忘れないこと
いろいろ示してみよう
写像 $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)$ への全射とみなすと、命題３より $f(A)$ は要素数 $\abs{A}$ 以下の有限集合。
特に $f$ が単射のときは $f|_A$ は $A$ から $f(A)$ への全単射とみなせるので、命題１より $f(A)$ は要素数 $\abs{A}$ の有限集合。
有限集合 $A$ の部分集合 $A’$ は有限集合であり、$\abs{A’} \leq \abs A$ である。
包含写像 $\iota: A’ \rightarrow A$ が単射なので、命題３より $A’$ は要素数 $\abs A$ 以下の有限集合。
有限集合 $A$ と集合 $B$ に対し交叉 $A \cap B$ は有限集合であり、$\abs{A \cap B} \leq \abs A$ である。
$A\cap B$ は $A$ の部分集合なので命題５より従う。
有限集合 $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$ は単射。よって命題３より $A \cup B$ は要素数 $n + m$ 以下の有限集合。
$B \setminus A = B$ なので $h$ は全単射になり、$A \cup B$ は要素数 $n + m$ の有限集合。
上で示したことにより非交差和の要素数はそれぞれの要素数の和なので、 \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$ を得る。
有限集合 $A$ とその部分集合 $B$ に対し、$A$ から $B$ への全単射が存在すれば $A = B$ である。
$A$ から $B$ への全単射が存在するので、命題１より $\abs A = \abs B$ であり、一方命題７より $\abs A = \abs{A \setminus B} + \abs B$ である。よって $\abs{A \setminus B} = 0$ となり $A \setminus B = \varnothing$ なので $A = B$。
有限集合 $A$ に対し、写像 $f: A \rightarrow A$ が単射 ならば $f$ は全単射。
$f$ が単射なので $f$ は $A$ から $f(A)$ への全単射とみなせる。$f(A) \subseteq A$ なので命題８より $A = f(A)$ となり、よって $f$ は全射。
有限集合 $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$$ なる有限集合であり（命題７）、また $f(B), f(C)$ は$\abs{f(B)} \leq \abs{B}$ $\quad$ $\abs{f(C)} \leq \abs{C}$
なる有限集合（命題４）。よって、$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}$$ となる（命題７）が、$f$ の全射性より $f(A) = A$ なので、この不等式は等号が成立する。よって $$\abs{f(B) \cup f(C)} = \abs{f(B)} + \abs{f(C)}$$ であり、命題７より $f(B) \cap f(C) = \varnothing$ である。よって $f(b) \neq f(c)$ が得られた。