キューネン基礎論定理II.7.15(1)(2)の同値性(コンパクト性定理)

\(\Sigma,\Theta\)を語彙\(\mathcal{L}\)の文の集合とする。次の(1)が任意の\(\Sigma\)で成り立つことと、(2)が任意の\(\Theta\)で成り立つことは同値。
(1)\(\Sigma\)のすべての有限部分集合がそれぞれモデルを持つとき、\(\Sigma\)もモデルを持つ。
(2)\(\Theta\models\psi\)のとき、ある有限の\(\Delta\subseteq\Theta\)について\(\Delta\models\psi\)となる。

(証明)(1)→(2)について:(1)および\(\Theta\models\psi\)を仮定する。\(\Theta\cup\{\neg\psi\}\)がモデルを持たないことから、(1)の対偶により\(\Theta\cup\{\neg\psi\}\)の有限部分集合\(\Omega\)でモデルを持たないものがとれる。\(\Delta=\Omega\cap\Theta\left(\subseteq\Theta\right)\)とおけば、これは有限集合であり、\(\Omega\subseteq\Delta\cup\{\neg\psi\}\)により、\(\Delta\cup\{\neg\psi\}\)もモデルを持たない。
(2)→(1)について:(2)の\(\psi\)として\(\perp\)を選ぶと、「\(\Theta\)がモデルを持たないとき、ある有限の\(\Delta\subseteq\Theta\)はモデルを持たない」となる。これは(1)の対偶である。■

原始的な帰納法のみでNにおける∈の無反射性を示す

\(\forall n\in\mathbb{N}[n\notin n]\)を、原始的な数学的帰納法のみを用いて示す。以下、\(n'\)は\({\rm Suc}(n)=n\cup\{n\}\)を意味する。
\(\beta(n):\forall k\in n'[k\notin k]\)と置くと、\(n\in n'\)により、各\(\beta(n)\)は\(n\notin n\)を含意する。そこで、\(\forall n\in\mathbb{N}[\beta(n)]\)を帰納法によって示せばよい。
まず\(\beta(\varnothing)\)は\(\varnothing\notin\varnothing\)により成立する。
\(\beta(n)\)を仮定し、\(k\)として\(n'\)を選べば\[n'\in n'\rightarrow n'\notin n'\]が得られるが、これは\(n'\notin n'\)のことである。したがって\(\beta(n')\)すなわち\(\beta(n)\wedge n'\notin n'\)も成立する。■

20180610集合と位相ゼミの補足(上限の定義について)

上限の定義に登場した、\[\forall y\in X[yはAの上界である\rightarrow a\leq y]\]と\[\forall x\in X[x < a\rightarrow\exists b\in A[x < b]]\]の同値性を納得しておきたい。記号を揃えるために前者の\(y\)を\(x\)と書き直す:\[\forall x\in X[xはAの上界である\rightarrow a\leq x]\]いっぽう、後者の\(\exists\)以降は「\(x\)は\(A\)の上界でない」と書ける:\[\forall x\in X[x < a\rightarrow xはAの上界でない]\]両者を見比べると互いに対偶になっている。ただし、
・「\(x\)は\(A\)の上界でない」は\(\exists b\in A[\neg b\leq x]\)だが、この\(\neg b\leq x\)を\(x < b\)と書いてよい
・\(a\leq x\)と\(x < a\)とが互いの否定になる
のは、「全順序で考えている」という前提のもとなので、一般の半順序では後者の定義は正しくない。

20180527集合と位相ゼミの補足(ハミング距離)

命題\(P\)の真理値\(V(P)\)は\(1\)(真)あるいは\(0\)(偽)という値をとるものとする。すると\(P\rightarrow Q\)は\(V(P)\leq V(Q)\)と言い換えられる。また\(V(PとQの真偽が異なる)=|V(P)-V(Q)|\)である。

\(V(a\neq b)\)のことを\(d(a,b)\)と書くことにする。

等号の対称性と推移性から\(x=y\rightarrow(x=z\Leftrightarrow y=z)\)である。これにより、「\(x\neq z\)と\(y\neq z\)の真偽が異なるならば\(x\neq y\)である」ということがわかる。このことを冒頭の準備を用いて書き直すと\(|d(x,z)-d(y,z)|\leq d(x,y)\)が得られるが、これは1次元のハミング距離の三角不等式にほかならない。

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)\)を導いたが、ここでは対偶を示した。