集合位相 証明テク (1)

松坂和夫先生の「集合・位相入門」を読んだ.証明においてよく使われる議論の流れをまとめておく.

随時更新

一般論

最強のテク
前に出てきた定理や演習問題を使うこと

あまりふざけていない.これは大事.特に演習問題の答えを使うという発想は最初は出ないがち.

自明

「自明」「明らか」を調子に乗って多用していると,痛い目にあう
たまに非自明な反例があって死ぬ.これらの言葉はかなり慎重に使わなければならない.

\(p \Rightarrow q\) の証明
1. 直接示す.\(p\)を仮定して\(q\)を示す.
2. 対偶を示す.\(\neg q\)を仮定して\(\neg p\)を示す.つまり,\(\neg q \Rightarrow \neg p\)を示す.
3. 背理法.\(p\)と\(\neg q\)を仮定して矛盾を示す.つまり,\(p \land \neg q \Rightarrow \bot\)を示す.

対偶と背理法は\(\neg q\)を仮定しているという点で似ているが,背理法は加えて\(p\)も仮定できるので,対偶による証明よりもやりやすいことが多い.なので証明は基本的に直接示すか背理法で示すかで考えておけば良さそう.結局\(p\)の仮定が不要だとわかれば対偶にすればいい.

\(p \Leftrightarrow q\)の証明
わざわざ書くほどのことでもないが,
1. \(p \Rightarrow q\)と\(q \Rightarrow p\)を示す.これが最も素直なやり方.
2. \(\neg p \Rightarrow \neg q\)と\(\neg q \Rightarrow \neg p\)を示す.両方の向きの対偶を取るとこうなる.
3. \(p \Rightarrow q\)と\(\neg p \Rightarrow \neg q\)を示す.片方の向きだけ対偶を取るとこうなる.

\(p \Leftrightarrow q \Leftrightarrow r\)
1. \(p \Leftrightarrow q\)と\(q \Leftrightarrow r\)を示す.素直.
2. \(p \Rightarrow q\)と\(q \Rightarrow r\)と\(r \Rightarrow p\)を示す.これ面白いと思う.

2のやり方は,この本を読むまで見たことがなかった.要するに,グラフ理論の言葉で言えば,命題間に辺を張ったとき,同じ強連結成分に属している命題は同値であるということ.このことは条件が4つになっても5つになっても同じことが言える.

「〜は存在しない」の証明
これはほとんど背理法(か対偶).一般に,何かが存在しないことを表現するのは難しいが,存在することを表現するのは簡単であることが多い.「〜は存在する」と仮定して矛盾を示す.

第1章 集合と写像

§1 集合の概念

\(A \subset B\)の証明

\(x \in A \Rightarrow x \in B\)を示す.

\(A = B\)の証明

\(A \subset B\)かつ\(B \subset A\)を示す.

§2 集合の間の演算

基本的には要素ベースで考えるのがやりやすい.

例えば,「\(A-(B \cup C) = (A-B)\cup(A-C)\)を示せ」というような問題があった時に,直接式変形して解くんじゃなくて(もちろんこれで解けることもある),\(x \in A - (B\cup C)\)を変形して\(x \in (A-B)\cup(A-C)\)を示すのがやりやすい.

要素ベースで考えるのはこれから先もずっとやることになる.

よく使う性質(というか定義)

  • \(x \in A \cup B \Leftrightarrow x \in A \lor x \in B\)
  • \(x \in A \cap B \Leftrightarrow x \in A \land x \in B\)
  • \(x \in A^\mathsf{c} \Leftrightarrow x \notin A\)
  • \(x \in A - B \Leftrightarrow x \in A \land x \in B^\mathsf{c}\)
  • \(x \in \bigcup \mathfrak{A} \Leftrightarrow \)ある\(A \in \mathfrak{A}\)があって,\(x \in A\)
  • \(x \in \bigcap \mathfrak{A} \Leftrightarrow \)すべての\(A \in \mathfrak{A}\)に対して,\(x \in A\)

§3 写像と対応

§4 写像に関する諸概念

集合の像や逆像に関する相等や包含関係の証明
§1や§2で言ったことと,

  • \(x \in A \Rightarrow f(x) \in f(A)\)
  • \(y \in f(A) \Leftrightarrow \exists x \in A\ (f(x)=y)\)
  • \(x \in f^{-1}(A) \Leftrightarrow f(x) \in A\)

を組み合わせれば大体解ける.

以下\(f : A \to B\)について考える.
全射の証明
各\(b \in B\)について,ある\(a \in A\)が存在し,\(f(a) = b\)なることを示す

具体的に\(a\)を構成することが多い.別の写像の全射性を利用することも多い.

単射の証明
1. 任意の\(a, a' \in A\)に対し,\(a \neq a' \Rightarrow f(a) \neq f(a')\)
2. 任意の\(a, a' \in A\)に対し,\(f(a) = f(a') \Rightarrow a = a'\)

まあ対偶なので同じこと.どちらもよく見ると思う.

全単射の証明
全射かつ単射を示す

§5 添数づけられた族,一般の直積

§6 同値関係

同値関係の証明

  • 反射律 \(\forall a \in A\ (aRa)\)
  • 対称律 \(\forall a, b \in A\ (aRb \Rightarrow bRa)\)
  • 推移律 \(\forall a, b, c \in A\ (aRb,\ bRc \Rightarrow aRc)\)

この3つを示す.というかこれ以外にない.

第2章 集合の濃度

§1 集合の対等と濃度

集合\(A, B\)が対等であることの証明
1. \(A\)から\(B\)への全単射が存在することを示す.
定義.具体的に全単射を構成することが多い.

2. \(A\)から\(B\)への単射と,\(B\)から\(A\)への単射が存在することを示す.
Bernsteinの定理.これも具体的に単射を構成することが多い.
「\(A\)から\(B\)への単射が存在 \(\Leftrightarrow\) \(B\)から\(A\)への全射が存在」(第1章定理7系)より,単射を全射に置き換えてもOK.

濃度の大小の証明 \(\mathfrak{m} \leq \mathfrak{n}\)
\(\mathrm{card}A = \mathfrak{m},\ \mathrm{card}B = \mathfrak{n}\)なる集合\(A, B\)を取り,\(A\)から\(B\)への単射(または,\(B\)から\(A\)への全射)が存在することを示す.具体的に写像を構成することが多い.

\(\mathfrak{m} = \mathfrak{n}\)の証明は対等性の証明と同じ.

§2 可算集合,非可算集合

集合\(A\)が(高々)可算であることの証明

1. 素直に\(\mathrm{card}A \leq \aleph_0\)を示す.
前節のテクが使える.

2. 「高々可算な集合の有限個の直積は高々可算」「高々可算な集合の,高々可算個の和集合は,高々可算」(定理5)を使う.
基本これな気がする.この事実自体は,\(\mathbb{N} \times \mathbb{N}\)が可算であることから証明される.\(\mathbb{N} \times \mathbb{N}\)が可算であることは,具体的に\(\mathbb{N} \times \mathbb{N}\)から\(\mathbb{N}\)への単射を作れることから示される.

その他
「\(A\)が無限集合,\(B \subset A\)が高々可算のとき,\(A-B\)が無限集合 \(\Rightarrow\) \(A-B\)は\(A\)と対等」(定理6)を使う.

部分集合に関して示したいときは有用.もちろんこれはある集合が高々可算であることを示すのにも使える.

§3 濃度の演算

\(\aleph_0, \aleph\)に関する演算
§1, 2のことに加え,無限の濃度が絡んでくるときによく使う手法としては,はさみうちにすることが上げられる.
例えば,ある濃度が\(\aleph_0\)で下から,\(\aleph_0 \aleph_0\)で上から抑えられれば,\(\aleph_0 \aleph_0 = \aleph_0\)よりその濃度は\(\aleph_0\)と等しいことがわかる.
前節の定理6も無限集合の対等に関する定理なので有用.
あとはCantorの定理\(\mathfrak{m} < 2^\mathfrak{m}\)も使うことがある.

つづく

長くなりそうなので今回はここで切る.そのうち続きを書く.