20180513集合と位相ゼミの補足

\(\mathcal{P}\)を集合\(X\)の分割とし、\(X\)上の二項関係\(x\sim y\)を\(\exists S\in\mathcal{P}[x\in S\wedge y\in S]\)と定義すると、\(\sim\)は同値関係である(証明略)。\(a\in X\)に対し同値類\(\{x\in X\mid x\sim a\}\)を\(C_a\)と略記する。

補題】\(a\in A\)を満たす任意の\(a\in X\)および\(A\in\mathcal{P}\)に対し、\(A=C_a\)が成り立つ。
(証明)\(A\subseteq C_a\)について:任意の\(x\in A\)をとると、\(a\in A\)であったので\(x\sim a\)すなわち\(x\in C_a\)を得る。
\(A\supseteq C_a\)について:任意の\(x\in C_a\)をとると、\(x\sim a\)により、\(x\in S\)かつ\(a\in S\)を満たす\(S\in\mathcal{P}\)がとれる。すると\(a\in S\cap A\neq\varnothing\)であり、\(\mathcal{P}\)が分割であること(条件3.)から\(S=A\)、したがって\(x\in A\)である。■

【本題】\(\mathcal{P}=\{C_a:\ a\in X\}\)である。
(証明)右辺を\(\mathcal{Q}\)とおく。
\(\mathcal{P}\subseteq\mathcal{Q}\)について:任意の\(A\in\mathcal{P}\)をとると、\(\mathcal{P}\)が分割であること(条件1.)から\(a\in A\)なる\(a\in X\)がとれる。すると補題により\(A=C_a\in\mathcal{Q}\)である。
\(\mathcal{P}\supseteq\mathcal{Q}\)について:任意の\(a\in X\)をとると、\(\mathcal{P}\)が分割であること(条件2.)から\(a\in A\)なる\(A\in\mathcal{P}\)がとれる。すると補題により\(C_a=A\in\mathcal{P}\)である。■

20180506集合と位相ゼミの補足

\(f\)が単射とは限らないときの、\(f[\bigcap A_i]=\bigcap f[A_i]\)の反例。

各\(A_i\)の、\(\bigcap A_i\)以外の点\(a_i\)たちから一斉に同じ点\(b\)に飛ぶ場合、像の共通部分をとっても\(b\)が「異物」として混入することがありうる。

\(f\)を\(\mathbb{N}\)から2点集合\(\{p,q\}\)(ただし\(p\neq q\))への写像とし、\[f(x)=\left\{\begin{array}{c}p\quad({\rm if}\ x=0)\\q\quad({\rm if}\ x\neq 0)\end{array}\right.\]と定義する。\(i\)は\(1,2,3,\ldots\)に渡るとして\(f[\bigcap\{0,i\}]=f[\{0\}]=\{p\}\)、いっぽう任意の\(i=1,2,3,\ldots\)に対して\(f[\{0,i\}]=\{p,q\}\)なので\(\bigcap f[\{0,i\}]=\{p,q\}\)となり、\(q\)が排除できずに残る。

20180429集合と位相ゼミの補足

(※内輪向けのメモです。)

特性関数および「集合から特性関数への写像」が初めはイメージしにくいと思うので、解説を書いてみました。

aさん、bさん、cさん、dさん、eさんという5人のグループがあって、とある勉強会に出席するかどうかを調査したところ、aさん、cさん、dさんが出席、bさん、eさんが欠席することが分かった。このとき、出欠に関する情報を書き記す方法はいくつか考えられる。例えば\[\{a,c,d\}\]のように出席者だけをすべて書き並べてもよいし、

a b c d e
1 0 1 1 0

と、全員の出欠を表にしてもよい。後者の出欠表は、\(X=\{a,b,c,d,e\}\)から\(\{0,1\}\)への写像になっている。この写像を「\(\{a,c,d\}\)の特性関数」と呼び、\(\chi_{\{a,c,d\}}\)と書く。\(X\)の部分集合\(A\)をいろいろ変えてとれば、その\(A\)ごとに特性関数\(\chi_A\)がひとつ定まる。そこで、\(A\)に\(\chi_A\)を対応させる写像を考えることもできる。いわば、「『出席者のみのリスト』を『出欠表』のフォーマットに変換する写像」である。\(A\)は\(X\)の部分集合、すなわち\(X\)の冪集合の要素であり、いっぽう\(\chi_A\)は「\(X\)から\(\{0,1\}\)への写像の(ひとつひとつをすべて集めた)集合」の要素である。つまり、この写像は\[\chi:\mathcal{P}(X)\to{\rm Map}(X,\{0,1\}),\quad\chi(A)=\chi_A\]と書ける。「写像でうつる個々の値が再び写像になっている」という、非常に「荷物の重い」ものを想像しないといけないのが初心者には辛いところ(私は今でも辛い)。

さて、出欠表のイメージを持っていれば、逆に出欠表から出席者リストを復元するのは容易に見える。実際、出欠表の値が「1」になっているメンバーだけを漏れなく集めればよい。しかし、\(X\)が無限集合の場合なども考慮に入れると、これは決して自明なことではない。\({\rm Map}(X,\{0,1\})\)の要素(個々の写像)のなかには、\(X\)のいかなる部分集合の特性関数にもなっていないような、得体の知れない写像があるかもしれないし、よしんば何らかの特性関数になっていたとしても、ただひとつに復元できるという保証もない。\(\chi\)の全射性・単射性をきちんと証明することによって、これらの「いっけん自明なこと」が確認される。
全射性の証明)任意の\(f\in{\rm Map}(X,\{0,1\})\)をとり、\(X\)の部分集合に\(f\)を特性関数とするものがあることを導く。\(f^{-1}[\{1\}]\)を考えると、実は\(f\)はこの集合の特性関数になっているので、そのことを示す。任意の\(x\in X\)をとる。(1)\(x\in f^{-1}[\{1\}]\)のとき、逆像の定義から\(f(x)=1\)である。(2)\(x\notin f^{-1}[\{1\}]\)のとき、やはり逆像の定義から\(f(x)\neq1\)すなわち\(f(x)=0\)である。(1)(2)により、\(f\)は\(f^{-1}[\{1\}]\)の特性関数の定義を満たしている。■

※この証明を見ると、結局のところ\(f^{-1}[\{1\}]\)という集合の存在が決め手になっている。これは集合論的には裏付けることのできる話であるが、そこを避けて通ってしまっているので、「結局、わざわざ証明した意義が分からない」と感じる人がいても不思議ではない。

単射性の証明)\(X\)の部分集合\(A,B\)を任意にとり、\(\chi(A)=\chi(B)\)を仮定して\(A=B\)を導く。任意の\(a\in A\)をとると\(\chi_A(a)=1\)である。仮定により\(A,B\)の特性関数\(\chi_A,\chi_B\)が写像として等しいから\(\chi_B(a)\)の値も\(1\)であり、したがって\(a\in B\)である。全く同様にして、\(b\in B\)をとると\(b\in A\)が導かれる。■

※ゼミでは\(A\neq B\)から\(\chi(A)\neq\chi(B)\)を導いたが、ここでは対偶を示した。

20180422集合と位相ゼミの補足

(※内輪向けのメモです。)
二項関係を初めて理解する際は、まずは最も素朴に二次元の表をイメージしておくのが良いと思います。
例えば\(X=\{グー,チョキ,パー\}\)として、関係\(aRb\)を「\(a\)が\(b\)に勝つ」とすると、その実体は\(R=\{(グー,チョキ),(チョキ,パー),(パー,グー)\}\)という、\(X\times X\)の部分集合です。こう定めておくことにより、\(aRb\Leftrightarrow (a,b)\in R\)と考えることができます。

a \ b グー チョキ パー
グー
チョキ
パー

この例では\(X\)のサイズが\(3\)なので表のマスは\(3\times 3=9\)個あり、●の付け方は\(2^9=512\)通りあります。それらの中には「\(a\)が\(b\)に勝つ」のように、●の付け方のルールが簡単に表現できるものもありますが、ワケの分からないところに●が付いているものもたくさんあります。それらのひとつひとつはいずれも二項関係と呼んでよい、ということに注意してください。すべてのマスに●が付いているものも、●が全く付いていないものも、\(X\)上の二項関係のひとつです。

・「前提を伴った定義文」の実例について考えてみました。たとえば「\(X,Y\)をベクトル空間とする。\(X\)から\(Y\)への写像\(f\)が(略)を満たすとき、\(f\)を『\(X\)から\(Y\)への線形写像』という。」という定義があって、その後で\(U,V\)に関する前置きなく「\(g\)を\(U\)から\(V\)への線形写像とする」という仮定が書いてあったとします。このときは「\(U,V\)はベクトル空間なのだな」と補って読んでやるしかありませんが、あまり良くない書き方だと思います。やはり、文脈上すでに\(U,V\)がベクトル空間として登場しているとか、直前に「\(U,V\)をベクトル空間とし、」といった文言を書くのが通例です。

・「\(f\)を\(X\times Y\)の部分集合と思ったとき」というのは、いま読んでもやはり「『思ったとき』も何も、まさに部分集合として定義しているじゃないか」と感じてしまいますが、誰もがそのような集合論的コーディングを意識するわけではないので、ここは「部分集合であることを強調したいとき」というくらいの意味で捉えればよいと思います。実際、集合論ではわざわざ\(\Gamma_f\)など導入せずに\( (x,y)\in f\)と書いているものを普通に見かけますが、著者にとっては違和感があったのでしょう。

・p19の問5(2)に対して、「結局\(h(g(f(x)))\)と書くのなら、グラフを用いてもたいして説明は変わらないのでは」という話が出ました。(1)は\(\{(x,z)\in X\times Z\mid\exists y\in Y[(x,y)\in\Gamma_f\wedge(y,z)\in\Gamma_g]\}\)と書くこともできます。(2)も同様に書けば\((h\circ g)\circ f\)と\(h\circ (g\circ f)\)が一致するので両写像は等しい、というのが著者の意図だったのではないでしょうか。

・みんなで少し詰まった「単射\(f:X\to Y\)において\(x\notin A\)ならば\(f(x)\notin f[A]\)」の証明、次のように書くのはどうでしょうか。
「\(x\notin A\)と仮定する。任意の\(x'\in A\)に対し、\(x\neq x'\)と\(f\)の単射性から\(f(x)\neq f(x')\)である。すなわち、\(f(x)\)は\(f[A]\)のどの要素とも等しくならない。したがって\(f(x)\notin f[A]\)である。」

20180414集合と位相ゼミの補足

(※内輪向けのメモです。)
発表者の証明を聞いて「ふんふん」と納得することと、実際に自分で証明を書いてみることの間には大きな壁があります。全部やるのは大変ですが、いくつかでも自分で書いてみることを勧めます。

今日取り上げられていた、補題1.3.2の2の逆を例に挙げると:

(問)「\(A\cup B\subset C\)ならば『\(A\subset C\)かつ\(B\subset C\)』」を証明せよ。
(証明)\(A\cup B\subset C\)を仮定し、\(A\subset C\)および\(B\subset C\)をそれぞれ導く。
まず\(A\subset C\)を示すためには、\(x\in A\)を満たす任意の\(x\)をとり、\(x\in C\)を導けばよい。
いま\(x\)は\(x\in A\vee x\in B\)を満たしているので、\(x\in A\cup B\)である。
これと\(A\cup B\subset C\)から、\(x\in C\)である。以上により\(A\subset C\)が示された。
同様にして\(B\subset C\)も示される。■

(別証)以下の補題を先に示す。
・\(P\subset P\cup Q\)および\(Q\subset P\cup Q\)
(証明)前者を示すために、\(x\in P\)を満たす任意の\(x\)をとり、\(x\in P\cup Q\)を導く。\(x\in P\)から、\(x\in P\vee x\in Q\)が成り立っている。したがって\(x\in P\cup Q\)である。後者も同様に示される。■
・「\(X\subset Y\)かつ\(Y\subset Z\)」ならば\(X\subset Z\)
(証明)\(X\subset Y,Y\subset Z\)を仮定し、さらに\(a\in X\)を満たす任意の\(a\)をとって\(a\in Z\)を導く。\(a\in X\)と\(X\subset Y\)から、\(a\in Y\)である。これと\(Y\subset Z\)から、\(a\in Z\)である。■
(本題の証明)\(A\cup B\subset C\)を仮定すると、上の補題により\(A\subset A\cup B\subset C\)から\(A\subset C\)が導かれる。同様に\(B\subset A\cup B\subset C\)から\(B\subset C\)となる。■

Nにおける∈の整礎性

\(N\)における∈の整礎性を、通常の帰納法で示す。\(N\)が順序をなす議論から独立して話を進めたいので、「\(\in\)極小元」といった語の代わりに、下のような語を用いる。
【定義】\(S\)が\(\neg\exists x\in S[x\in t]\)なる要素\(t\)を持つとき、\(t\)を\(S\)の左\(\in\)ターミナルと呼ぶ。

【定理】\(N\)の非空部分集合は左\(\in\)ターミナルを持つ。
(証明)\[\alpha(n):n\in S\subseteq Nを満たす任意のSが左\inターミナルを持つ\]とおき、\(\forall n\in N[\alpha(n)]\)を示せばよい。さらに\[\beta(n):\forall k\in n'[\alpha(k)]\]とおく。\(n\in n'\)により、各\(\beta(n)\)は\(\alpha(n)\)を含意するので、\(\forall n\in N[\beta(n)]\)を帰納法で証明することにする。まず\(\beta(\varnothing)\)は\(\alpha(\varnothing)\)のことであるが、\(\varnothing\in S\subseteq N\)を満たす任意の\(S\)は\(\varnothing\)を左\(\in\)ターミナルに持つことから、これは成立する。次に\(\beta(n)\)を仮定して\(\beta(n')\)を導くが、\(n''=n'\cup\{n'\}\)により、\(\alpha(n')\)さえ導ければよい。そこで、\(n'\in S\subseteq N\)を満たす任意の\(S\)をとる。\(r\in n'\)かつ\(r\in S\)なる\(r\)が存在するとき、\(\beta(n)\)により\(\alpha(r)\)が成立するので、\(S\)は左\(\in\)ターミナルを持つ。そのような\(r\)が存在しないときは、\(n'\)が\(S\)の左\(\in\)ターミナルとなる。■

最小の帰納的集合は狭義順序をなす

対の公理と和集合の公理により、任意の\(n\)の各々に対して\(n\cup\{n\}\)なる集合が存在するので、これを\(n'\)と書く。すなわち\[m\in n'\Leftrightarrow (m\in n\vee m=n)\]が成り立つ。
【定義】\(y\)が次の条件\(\varphi(y)\)を満たすことを、「\(y\)は帰納的集合である」という。\[\varphi(y):\varnothing\in y\wedge\forall z[z\in y\rightarrow z'\in y]\]

(無限公理)帰納的集合が存在する。

無限公理により存在が保証された帰納的集合のひとつを\(I\)とすると、分出公理により\[\{x\in I\mid\forall y[\varphi(y)\rightarrow x\in y]\}\] という集合が存在し、これは\(I\)のとり方によらない。この集合を\(N\)と名付ける。

【定理】\(N\)は最小の帰納的集合である。
(証明)\(N\)が任意の帰納的集合に包含されること:任意の帰納的集合\(J\)と任意の\(x\in N\)をとれば\(x\in J\)、したがって\(N\subseteq J\)である。
\(N\)自身が帰納的集合であること:\(\varphi(y)\)を満たす任意の\(y\)をとると\(\varnothing\in y\)、特に\(\varnothing\in I\)。したがって\(\varnothing\in N\)である。次に\(z\in N\)を仮定し\(z'\in N\)を導く。\(\varphi(y)\)を満たす任意の\(y\)をとると、\(z\in N\)から\(z\in y\)、これと\(\varphi(y)\)から\(z'\in y\)、特に\(z'\in I\)。したがって\(z'\in N\)である。

この定理により、\(N\)上で数学的帰納法が使えるようになる。

【定義】集合\(n\)が「\(k\in n\)ならば\(k\subseteq n\)」を満たすとき、「\(n\)は推移的集合である」という。以下では推移的集合のことをtransetと記す。

【系】\(n\)がtransetであるとき、「\(k\in n'\)ならば\(k\subseteq n\)」が成り立つ。
(証明)\(k\in n'\)と仮定すると、\(k=n\)または\(k\in n\)が成り立つが、\(n\)がtransetであることから、いずれにせよ\(k\subseteq n\)となる。■

【定理】\(N\)の各要素はtransetである。
(証明)帰納法による。まず\(\varnothing\)はtransetである。\(n\in N\)がtransetであると仮定する。任意の\(k\in n'\)をとると、上の系により\(k\subseteq n\subseteq n'\)となる。したがって\(n'\)もtransetである。■

【定理】\(N\)自身もtransetである。
(証明)帰納法による。まず\(\varnothing\subseteq N\)である。\(n\subseteq N\)を仮定し、\(n'\subseteq N\)を導く。任意の\(k\in n'\)をとると、\(k=n\)または\(k\in n\)が成り立つが、前者ならば\(k=n\in N\)、後者ならば仮定により\(k\in n\subseteq N\)であり、いずれにせよ\(k\in N\)となる。■

\(N\)における「\('\)」の性質についての補題を得ておく。

補題】任意の\(p,q\in N\)に対し、次が成り立つ。
(1)\(p'\neq\varnothing\)
(2)\(\varnothing\in p'\)
(3)\(p=q\Leftrightarrow p'=q'\)
(4)\(p\in q\Leftrightarrow p'\in q'\)
(証明)(1)\(p\notin\varnothing\)および\(p\in p'\)による。
(2)\(p\)についての帰納法による。まず\(\varnothing\in\varnothing'\)は成り立つ。\(\varnothing\in p'\)は\(\varnothing\in p''\)を含意する。
(3)「→」は等号公理により直ちに示される。「←」を示すため、\(p'=q’\)と仮定する。\(p\in p'=q'\)であり、\(q\)がtransetであることから、上の系により\(p\subseteq q\)である。まったく同様にして\(q\subseteq p\)が導かれるので、\(p=q\)となる。
(4)任意の\(p\in N\)を選んで固定し、\(q\)についての帰納法で示す。まず\(p\in\varnothing\Leftrightarrow p'\in\varnothing'\)は両辺とも偽になるので成立する。\(p\in q\Leftrightarrow p'\in q'\)と仮定すると、(3)と辺々「\(\vee\)」で結ぶことにより\(p\in q'\Leftrightarrow p'\in q''\)となる。■

【定理】\(N\)上の二項関係\(\in\)は狭義全順序をなす。
(証明)推移性:\(N\)の任意の要素\(l,m,n\)をとり、\(l\in m\in n\)と仮定すると、\(n\)がtransetであることから\(l\in n\)である。
無反射性:帰納法による。まず\(\varnothing\notin\varnothing\)である。\(n\notin n\)と仮定すると、「\('\)」の性質(4)により\(n'\notin n'\)となる。

一般に推移的かつ無反射的な二項関係は反対称的でもある。したがって\(N\)における\(\in\)も反対称的である。

弱い三分性:\(m\in N\)を任意にとって固定し、\(\psi(n):m\in n\vee m=n\vee n\in m\)とおいて、\(n\)についての帰納法を用いる。\(\psi(n)\)は\[\psi_1(n):m \in n'\vee n\in m\]とも\[\psi_2(n):m\in n\vee n\in m'\]とも書けるので、そのつど便利なものを用いる。まず、「\('\)」の性質(2)により、\(\psi_2(\varnothing)\)の後件が成り立つ。次に、\(\psi_1(n)\)を仮定して\(\psi_2(n')\)を導く。\(m\in n'\)のとき、これは\(\psi_2(n')\)の前件にほかならない。\(n\in m\)のとき、「\('\)」の性質(4)から\(n'\in m'\)、これは\(\psi_2(n')\)の後件に当たる。■

「反対称性」「無反射性」「弱い三分性」をまとめたものが「強い三分性」(\(m\in n,m=n,n\in m\)のうち、ちょうどひとつが成り立つ)に相当する。