練習問題

有限長ビット列全体の集合 \(\left\{ 0, 1 \right\}^{\ast}\) が加算だと示せ。

一方からもう一方への全単射が存在しないような二つの非加算集合 \(A\), \(B\) の例を示せ。

次に示す命題の中で

と同値なものを全て答えよ:

1. \(|A|\) が定義されない。

2. \(A\) が加算無限である。

3. \(A\) が非加算である。

4. \(A\) が有限である。

5. \(\mathbb{N} \mathrel{\text{\small surj}} A\)
6. \(\forall n \in \mathbb{N}.\ |A| \leq n\)
7. \(\forall n \in \mathbb{N}.\ |A| \geq n\)
8. \(\exists n \in \mathbb{N}.\ |A| \leq n\)
9. \(\exists n \in \mathbb{N}.\ |A| \geq n\)

集合 \(S\) から \(\mathbb{N}\) への全域単射 (「外 \(\geq 1\)」かつ「内 \(\leq 1\)」) な関係が存在するとき \(S\) は加算だと示せ。

\(S\) が無限集合のとき \(\operatorname{pow}(S)\) は非加算だと示せ。

正の実数値を取る全域関数 \(f_{k}\colon \mathbb{N} \to \mathbb{R}^{+}\) の無限列

が与えられたとする。

1. 関数 \(g \colon \mathbb{N} \to \mathbb{R}\) が十分大きい任意の整数 \(n\) で任意の \(f_{k}(n)\) より大きくなるとき、\(g\) は \(f_{k}\) の集合を majorize すると言う。\(f_{k}\) の集合を majorize する関数を見つけるには、\(f_{k}\) のいずれとも異なる関数を見つける対角線論法とは異なるアプローチが必要になる。

   \(f_{k}\) の集合を majorize する関数 \(g \colon \mathbb{N} \to \mathbb{R}\) の例を示し、その \(g\) で \(g(n) > f_{k}(n)\) を保証するには \(n\) をどこまで大きくする必要があるか答えよ。

2. 必要なら \(\text{(a)}\) の解答を改変し、\(f_{k}\) の集合を majorize する関数 \(h \colon \mathbb{N} \to \mathbb{R}\) であって、任意の \(k \in \mathbb{N}\) に対して \(f_{k}\) より速く大きくなるものを答えよ。つまり、\(h\) は任意の \(k\) に対して次の等式を満たす必要がある:

   \[ \lim_{n \to \infty} \frac{f_{k}(n)}{h(n)} = 0 \]

   \(h\) が条件を満たす理由を説明せよ。

非負実数値を取る全域関数 \(f_{k} \colon \mathbb{N} \to \mathbb{R}^{\geq 0}\) の無限列

が与えられたとする (全て異なるとは限らない)。関数 \(s\colon \mathbb{N} \to \mathbb{R}^{\geq 0}\) を次の規則で定義する:

1. \(b(k)\) を「任意の \(k\) で、\(n\) が \(b(k)\) 以上なら \(s\) は \(f_{k}\) 以上である」を満たすような関数とする。つまり \(b(k)\) に関して次の命題が成り立つ:

   \[ \forall k\, \forall n \geq b(k).\ s(n) \geq f_{k}(n) \]

   \(b(k)\) として可能な関数を次の中から全て選べ:

   1. \(k\)
   2. \(\sqrt{k}\)
   3. \(n^{2}\)
   4. \(k^{2}\)
   5. \(k^{3}\)
   6. \(2^{k}\)

2. 次に示す性質の中で、\(s\) が \(f_{k}\) の列に現れないことを保証するのはどれか？

   1. \(f_{7}\) が正である (\(\forall n.\ f_{7}(n) > 0\))。

   2. \(f_{7}\) は無限回正になる (\(\forall k\, \exists n > k.\ f_{7}(n) > 0\))。

   3. \(f(7)\) が上界を持たない。

   4. \(f_{7}\) と \(f_{8}\) が正である。

   5. \(f_{7}\) と \(f_{8}\) は無限回正になる (両者が同じ \(n\) で正になる必要はない)。

   6. \(f_{7}\) と \(f_{8}\) がどちらも上界を持たない。

\(A\) を何らかの無限集合とする。補題 8.1.7 より、任意の \(b_{0}\) に対して

が成り立つ。簡単な数学帰納法による証明を使えば、任意の有限集合 \(\left\{ b_{0}, b_{1}, \ldots, b_{n} \right\}\) に対して

が成り立つと示せる。

ここから、任意の集合 \(B\) に対して

が成り立つと思ってしまう学生がいる。しかし、これは正しくない: 例えば \(A\) が \(\mathbb{N}\) で \(B\) が \(\mathbb{R}\) のとき \(\text{(AuB)}\) は成り立たない¹。

集合の集まり \(\mathcal{C}\) が鎖 (chain) とは、\(\mathcal{C}\) に含まれる任意の二つの集合について一方がもう一方を含むことを言う。述語 \(P(C)\) が有限連続 (finitely continuous) とは、有限集合からなる任意の鎖 \(\mathcal{F}\) に対して、全ての \(F \in \mathcal{F}\) で \(P(F)\) が成り立つなら \(P(\bigcup \mathcal{F})\) が成り立つことを言う。\((\text{AuB}_{i})\) が \(\text{(AuB)}\) を意味すると主張するのは、次の述語 \(P_{A}(C)\) が有限連続だと主張するのに等しい:

\(A = \mathbb{N}\) および \(B = \mathbb{R}\) としたとき \(\text{(AuB)}\) は成り立たないので、\(P_{A}(C)\) は有限連続でない。

次の述語 \(P(C)\) の中で、有限連続なものを全て答えよ:

1. \(C\) は有限集合である。

2. \(C\) は非加算である。

3. \(C = \varnothing\)

4. 最小要素 \(b \in C \cap \mathbb{N}\) が存在する。

5. 最小要素 \(b \in C \cap \mathbb{Z}\) が存在する。

6. \(\pi / 2 \in C\)
7. \(\exists \varepsilon > 0 \ \forall a,b \in C \cap \mathbb{R}.\ |a - b| > \varepsilon\)

8. \(C \cup \mathbb{N}\) が有限である。

9. \(C \subseteq \mathbb{N}\)
10. \(C \subset \mathbb{N}\)

11. \(C\) が加算である。

正整数の有限集合全体の集合は加算だと示せ。

ヒント: 部分集合をその和で分類する。

集合の集まり \(\mathcal{C}\) が鎖 (chain) とは、\(\mathcal{C}\) に含まれる任意の二つの集合について一方がもう一方を含むことを言う。\(\mathcal{F}\) が有限集合からなる鎖なら \(\bigcup \mathcal{F}\) は加算だと示せ (鎖の条件がないとき、任意の集合は常に有限部分集合の和集合として表せる)。

非負整数の有限列全体の集合 \(\mathbb{N}^{\ast}\) が加算だと示せ。

1. 補題 8.1.7 の証明は循環論法ではないかと指摘してきた学生が何人かいた。これについてどう思うか？

2. 補題 8.1.7 の証明を利用して、\(A\) が無限集合なら \(A \mathrel{\text{\small surj}} \mathbb{N}\) だと示せ。言い換えれば、全ての無限集合は非負整数全体の集合「以上に大きい」と示せ。

有理数は整数の間をギッシリ埋めるので、直感的には整数より多く存在するように思える。しかし、その直感は正しくない。この問題では正有理数が正整数と「同じだけ」存在すること、言い換えれば有理数全体の集合が加算であることを証明する。

1. 正整数全体の集合 \(\mathbb{Z}^{+}\) から正整数の組全体の集合 \(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\) への全単射を定義せよ。次の図を利用してもよい:

   \[ \def\arraystretch{1.2}\begin{array}{cccccc} (1,1), & (1,2), & (1,3), & (1,4), & (1,5), & \ldots \\ (2,1), & (2,2), & (2,3), & (2,4), & (2,5), & \ldots \\ (3,1), & (3,2), & (3,3), & (3,4), & (3,5), & \ldots \\ (4,1), & (4,2), & (4,3), & (4,4), & (4,5), & \ldots \\ (5,1), & (5,2), & (5,3), & (5,4), & (5,5), & \ldots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array} \]

2. 正有理数全体の集合 \(Q^{\ast}\) が加算だと結論付けよ。

この問題では Schröder–Bernstein の定理 (定理 8.1.4) と同値な次の命題を証明する:

\(A \mathrel{\text{\small inj}} B\) かつ \(B \mathrel{\text{\small inj}} A\) より、全域単射関数 \(f\colon A \to B\) と \(g\colon B \to A\) が存在する。

議論を簡単にするため、\(A\) と \(B\) は共通要素を持たないとする。次のように \(A\), \(B\), \(f\), \(g\) を表す図を作成する。\(A\) の各要素を縦一列に並ぶ点として左側に描き、\(B\) の要素を縦一列に並ぶ点として右側に描く。その上で、\(a \in A\) のそれぞれに対して \(a\) から \(f(a)\) に向かう矢印を書き、さらに \(b \in B\) のそれぞれに対して \(b\) から \(g(a)\) に向かう矢印を書く。\(f\) と \(g\) は全域関数だから、この図の任意の点はちょうど一本の矢印の始点となる。また、\(f\) と \(g\) は単射だから、任意の点は最大で一本の矢印の終点となる。

よって、任意の要素から始めて矢印を順方向にたどる操作を繰り返し行うと、\(A\) の要素と \(B\) の要素が交互に並んだ無限パスが得られる (同じパスが反復する可能性はある)。同様に、任意の要素から始めて矢印を逆方向にたどる操作を繰り返し行うと、\(A\) の要素と \(B\) の要素が交互に並んだ無限パスまたは有限パスが得られる。これらのパスは全く交わらない: もし複数のパスに属する要素があるなら、その要素は異なる二本の矢印の始点または終点となっている。

このとき、任意の要素は次の四種類のパスのいずれかに属する:

1. 両方向に無限に伸びるパス

2. \(A\) の要素から始まり無限に伸びるパス

3. \(B\) の要素から始まり無限に伸びるパス

4. 終わりを持たない有限パス

次の設問に答えよ:

1. \(\text{(iv)}\) の状況を表す図を書け。

2. それぞれのパスについて、次のいずれかが成り立つと示せ:

   1. \(f\) の定める矢印が、パス上の \(A\) の要素から \(B\) の要素への全単射を定義する。

   2. \(g\) の定める矢印が、パス上の \(B\) の要素から \(A\) の要素への全単射を定義する。

   3. \(f\) の定める矢印と \(g\) の定める矢印の両方が全単射を定義する。

   どの種類のパスが \(\text{(iii)}\) に対応するか？

3. これらの全単射を組み合わせて \(A\) から \(B\) への全単射を構築する方法を説明せよ。

4. \(A\) と \(B\) が共通要素を持たないという仮定を正当化せよ。

1. 非空集合 \(C\) が加算なら、全域全射関数 \(f\colon \mathbb{N} \to C\) が存在すると示せ。

2. 逆に、全域全射関数 \(f\colon \mathbb{N} \to D\) の存在が言えなくても \(\mathbb{N} \mathrel{\text{\small surj}} D\) なら \(D\) が加算だと示せ。

無限集合には様々な「大きさ」を持つものが存在する。例えば、非負整数を全て集めた無限集合 \(\mathbb{N}\) から始めて、冪集合を繰り返し取ることで無限集合の無限列

を作成すると、この列の任意の要素は次の要素より「真に小さい」ことが定理 8.1.12 より分かる。この列の第 \(n\) 要素を \(\operatorname{pow}^{n}(\mathbb{N})\) として、集合 \(U\) を次のように定める:

1. 全ての \(n \in \mathbb{N}\) で次の関係が成り立つと示せ:

   \[ U\ \mathrel{\text{\small surj}}\ \operatorname{pow}^{n}(\mathbb{N}) \]

2. 全ての \(n \in \mathbb{N}\) で次の関係が成り立つと示せ:

   \[ \operatorname{pow}^{n}(\mathbb{N})\ \mathrel{\text{strict}}\ U \]

\(\left\{ 0, 1 \right\}^{\omega}\) は無限長ビット列全体の集合を表す。\(\left\{ 0, 1 \right\}^{\omega}\) の要素が孤独 (lonely) とは、\(1\) が連続しないことを言う。例えば、\((0,1)\) が繰り返される次の文字列は孤独である:

一方、次の列には \(1\) が二つ連続する部分があるので孤独でない:

孤独な無限長ビット列全体の集合を \(F\) とする。\(F\) が非加算だと示せ。

ヒント: 問題 8.20 と同様の「非対角線論法」を使う。

\(A\) が無限集合で \(B\) が加算集合なら、次の関係が成り立つと示せ:

ヒント: \(A\) が無限集合なので、補題 8.1.7 の証明と同様に \(A\) の要素からなる無限列 \(a_{0}\), \(a_{1}\), \(\ldots\) を取れる。

この問題では驚くべき事実を証明する ── 集合論では直感が信用できないとさらに納得できることだろう: 単位半開区間²は複素平面の第一象限と「同じ大きさ」を持つ！ 具体的には、\((0, 1]\) から \([0, \infty) \times [0, \infty)\) への全単射が存在する。

1. \((0, 1]\) から \([0, \infty)\) への全単射を示せ。

   ヒント: \(1/x\) が解答に非常に近い。

2. 一桁の数字 \(\left\{ \texttt{0}, \texttt{1}, \ldots, \texttt{9}\right\}\) を並べた無限列がロング (long) とは、接尾部に含まれるのが \(0\) だけでないことを言う。言い換えれば、\(\texttt{0}\) でない数字が無限に多く現れる列はロングである。ロングな列全体の集合を \(L\) とする。\(L\) から半開区間 \((0, 1]\) への全単射を示せ。

   ヒント:列の先頭に小数点を書く。

3. \(L\) から \(L^{2}\) への全射関数を示せ。一つのロングな列から桁を互い違いに取ることで二つのロングな列を作成するアプローチを用いよ。

   ヒント: 解答が全域関数である必要はない。

4. 次の補題を示し、それを使って \(L^{2}\) から \((0, 1]^{2}\) への全単射を示せ。

   補題

   \(A\), \(B\) を非空集合とする。\(A\) から \(B\) への全単射が存在するなら、\(A \times A\) から \(B \times B\) への全単射が存在する。

5. ここまでの結果を使って、\((0, 1]\) から \((0, 1]^{2}\) への全射が存在することを証明せよ。Schröder–Bernstein の定理 (定理 8.1.4) を使って、\((0, 1]\) から \((0, 1]^{2}\) への全単射が存在すると結論付けよ。

6. \((0,1]\) から \([0, \infty)^{2}\) への全単射が存在することの証明を完成させよ。

対角線論法で「対角線」をたどる必要は必ずしもない。

歴史的に重要な対角線論法の応用を見よう。次の単方向無限列を考える:

山括弧は列が集合でない事実を強調するためにある。列の要素は順序を持ち、同じ要素を複数回持っていても構わない³。

典型的な対角線論法の設定では、単方向無限列が並んだ単方向無限列 \(S\) が登場する。この列を \(S = \langle s_{0},\ s_{1},\ \ldots,\ \rangle\) とする。\(S\) の各要素を縦に並べ、\(s_{k} \in S\) の各要素を横に並べると \(S\) を図示できる。ここで \(s_{k}\) の要素は次のように表記する:

\(S\) を表す二次元の表を示す。この表は下方向および右方向に無限に広がる:

対角線論法では、ここから \(S\) に含まれない列を新しく構築する。具体的には、上記の表で対角線上にある要素のそれぞれに対して、それと異なる要素を並べた列を作成する。この新しい列 \(D_{S}\) は次のように表現できる:

ここで \(\overline{x}\) は \(x\) と異なる何らかの要素を表す。このとき \(D_{S}\) は \(S\) に含まれる任意の列と異なるので、\(S\) に含まれない。具体的には、\(S\) の要素 \(s_{k}\) と \(D_{S}\) は第 \(k\) 要素が異なる。

簡単のため、次のように定めておく:

このとき \(D_{S}\) は \(1\) と \(2\) だけからなる単方向無限列であり、かつ \(S\) に含まれない。

しかし冒頭で書いたように、どの \(s_{k}\) とも異なる列は対角線をたどらなくても構築できる。例えば、傾きが \(-1/4\) の直線上にある要素を利用する次の列を \(D_{S}\) の代わりに使うこともできる:

ここで \(t_{i}\) はどんな値でも構わない。この形をした任意の列 \(T_{S}\) と \(s_{k}\) は、第 \(4k\) 要素が必ず異なる。

1. 全ての正整数 \(i\) で \(t_{i} = 2\) と定めれば、\(1\) と \(2\) だけからなる単方向無限列 \(T_{S}\) であって、(極限において) 要素の少なくとも \(3/4\) が \(2\) に等しいものが得られる。この条件を満たす列を非加算個構築する方法を説明せよ。

   ヒント: 傾き \(1/8\) の直線を使って、\(8\) 個の空間の中に \(6\) 個の \(2\) を入れる。次の略記法を使うとよい:

   \[ 2^{(n)} ::= \underbrace{2, 2, \ldots, 2}_{n \text{ 個}} \]

   これは \(n\) 個の \(2\) が並ぶ列を表す。\(2^{(6)}\) を使うことになるだろう。

2. 条件「任意の \(\varepsilon > 0\) に対して、極限における \(2\) でない要素の割合が \(\varepsilon\) 以下である⁴」を満たし、かつ \(S\) に含まれない単方向無限列を構築する方法を説明せよ。

3. \(S\) に含まれる任意の列と無限個の箇所で異なる列を構築する方法を説明せよ。

   ヒント: \(\mathbb{N}\) を無限個の無限集合に分割する。

Cantor の定理 (定理 8.1.12) からは、任意の集合 \(A\) に対して全射関数 \(g\colon A \to \operatorname{pow}(A)\) が存在しないと分かる。特に、この定理の証明では次の「対角線」集合 \(A_{g}\) を利用した:

どんな \(g\) を考えたとしても、この \(A_{g}\) は \(g\) の値域に含まれない: なぜなら、任意の \(a\) に対して、\(g\) の値域に含まれる集合 \(g(a)\) と \(A_{g}\) は \(a\) を含むかどうかが異なるからである。

ただ、対角線が本質的な意味を持っているわけではない。\(p \colon A \to A\) を何らかの全域関数として、「対角線」上にある \(a\) ではなく \(p(a)\) で \(g(a)\) と異なる集合を作ることもできる。つまり、\(A_{g,\, p}\) を次のように定める:

この \(A_{g,\, p}\) は \(\operatorname{pow}(A)\) の要素である。このとき任意の \(a\) に対して、\(g\) の値域に含まれる集合 \(g(a)\) と 集合 \(A_{g,\, p}\) は \(p(a)\) を含むかどうかが異なり、次の主張が成り立つ...ように思える:

1. \(A ::= \left\{ 0, 1 \right\}\), \(\,g(n) = \left\{ n \right\}\), \(\,p(n) = 0\) (\(n \in \mathbb{N}\)) の場合を考えることで、上記の主張が誤りだと示せ。

2. 上記の議論に含まれる誤りを特定し、\(p\) の単射性を要求することで証明を修正せよ。

\(\mathcal{S} = \left\{ S_{0}, S_{1}, \ldots \right\}\) を非負整数の無限集合 \(S_{n}\) の加算集合とする。対角線論法を使うと、\(S\) に含まれない非負整数の無限集合 \(U\) を「新しく」構築できる。

この問題では、\(\mathcal{S}\) に含まれないだけでなく \(\mathcal{S}\) に含まれる集合を部分集合としてさえ持たないような非負整数の無限集合 \(U\) を構築する。

直接 \(U\) を構築するよりも、その補集合 \(C\) を考えた方が少し簡単になる。\(C\) が定義できれば、\(U\) は \(U ::= \overline{\mathstrut C} = \mathbb{N} - C\) と定義できる。

関数 \(f\colon \mathbb{N} \to \mathbb{N}\) を次のように定める:

さらに、次の通り \(C\) を定義する:

1. \(U\) の任意の部分集合は \(\mathcal{S}\) に含まれないと示せ。

2. \(U\) の極限における密度が \(1\) だと示せ。つまり次の等式が成り立つと証明せよ:

   \[ \lim_{k \to \infty}\frac{|U \cap [0, k]|}{k} = 1 \]

1. 次に示す集合が有限・加算無限・非加算無限のどれかをそれぞれ答えよ:

   1. \(10^{100}\) より大きい偶数全体の集合

   2. \(0\) でない実数 \(r\) を使って \(ri\) と表せる純虚数全体の集合

   3. \([10, 10^{10}]\) に含まれる整数全体の集合の冪集合

   4. 整数係数二次方程式の根であるような複素数 \(c\) 全体の集合: 言い換えれば、次の条件を満たす複素数 \(c\) 全体の集合:

      \[ \exists m, n, p \in \mathbb{Z},\, m \neq 0.\ mc^{2} + nc + p = 0 \]

   \(\mathcal{U}\) を非加算集合、\(\mathcal{C}\) を \(\mathcal{U}\) の加算無限部分集合、\(\mathcal{D}\) を加算無限集合とする。

   5. \(\mathcal{U} \cup \mathcal{D}\)
   6. \(\mathcal{U} \cap \mathcal{C}\)
   7. \(\mathcal{U} - \mathcal{D}\)

2. 次の条件を満たす集合 \(A\), \(B\) の例を示せ:

   \[ \mathbb{R} \mathrel{\text{strict}} A \mathrel{\text{strict}} B \]

\(A_{0}, A_{1}, \ldots, A_{n}, \ldots\) が加算集合の無限列のとき、次の集合も加算集合だと示せ:

\(A\), \(B\) を次の加算無限集合とする:

このとき \(A \times B\) も加算無限集合だと示せ。\(A \times B\) の要素を並べる方法を示すことで証明せよ。

\(1\), \(2\), \(3\) だけからなる無限列全体の集合は \(\left\{ 1, 2, 3 \right\}^{\omega}\) と表される。この集合に含まれる列の例を示す:

\(\left\{ 1, 2, 3 \right\}^{\omega}\) が非加算であることを二通りの方法で証明せよ:

1. 既知の非加算集合 \(S\) に対して \(\left\{ 1, 2, 3 \right\}^{\omega} \mathrel{\text{\small surj}} S\)が成り立つことを示す。

2. 対角線論法で直接示す。

無限長ビット列 \(b ::= b_{0}b_{1}b_{2} \ldots b_{n} \ldots\) が OK とは、\(\texttt{1}\) が完全平方数の位置にだけ存在することを言う。つまり \(b\) は次の条件を満たすとき OK である:

1. OK な文字列全体の集合が非加算だと示せ。

2. 非加算な部分集合を持つ集合は非加算だと示せ。

3. \(\texttt{1}\) の割合が極限において \(0\) になる無限長ビット列全体の集合を \(\text{Sparse}\) とする。\(\text{Sparse}\) が非加算だと示せ。

非負整数全体の集合の部分集合が孤独 (lonely) とは、隣り合う二つの非負整数が含まれないことを言う。例えば \(5\) の冪全体の集合 \(\left\{ 1, 5, 25, 125, \ldots \right\}\) は孤独である。また、素数全体の集合 \(\left\{ 2, 3, 5, 7, 11, \ldots \right\}\) は \(2\) と \(3\) を含むので孤独でない。

\(\mathbb{N}\) の孤独な部分集合全体の集合を \(L\) とする。\(L\) が非加算だと示せ。

関数 \(f\colon \mathbb{N} \to \mathbb{N}\) が全ての \(n \in \mathbb{N}\) に対して次の条件を満たすとき、高速増加 (rapidly increasing) と言うことにする:

高速増加な関数全体の集合を \(\text{Rapid}\) とする。

対角線論法を使って、\(\text{Rapid}\) が非加算だと示せ。

整数係数二次方程式の根である実数を二次的 (quadratic) と呼ぶことにする。加算個の二次的実数が存在する理由を説明せよ。

次に \(12\) 個の集合を示す。全単射が存在する集合の組を全て答えよ。

1. \(\mathbb{Z}\) (整数全体の集合)

2. \(\mathbb{Q}\) (有理数全体の集合)

3. \(\mathbb{R}\) (実数全体の集合)

4. \(\mathbb{C}\) (複素数全体の集合)

5. \(\operatorname{pow}(\mathbb{Z})\) (整数の集合全体の集合)

6. \(\operatorname{pow}(\varnothing)\)
7. \(\operatorname{pow}(\operatorname{pow}(\varnothing))\)

8. \(\left\{ 0, 1 \right\}^{\ast}\) (有限長ビット列全体の集合)

9. \(\left\{ 0, 1 \right\}^{\omega}\) (無限長ビット列全体の集合)

10. \(\left\{ \textbf{T}, \textbf{F} \right\}\) (真理値全体の集合)

11. \(\operatorname{pow}(\left\{ \textbf{T}, \textbf{F} \right\})\)
12. \(\operatorname{pow}(\left\{ 0, 1 \right\}^{\omega})\)

正整数の有限列全体の集合 \((\mathbb{Z}^{+})^{\ast}\) が加算だと示せ。

ヒント: \(s \in (\mathbb{Z}^{+})^{\ast}\) に対して、\(s\) に含まれる正整数の和を \(\operatorname{sum}(s)\) とする。

\(\mathbb{N}^{\omega}\) は非負整数の無限列全体の集合を表す。\(\mathbb{N}^{\omega}\) に含まれる列の例を次に示す:

\(\mathbb{N}^{\omega}\) が非加算だと示せ。

任意の集合 \(A\), \(B\) に対して、\(A\) から \(B\) への全域関数全体の集合を \([A \to B]\) と表記する。\(A\) が非空集合であり、\(B\) が二つ以上の要素を持つなら \(A \mathrel{\text{strict}} [A \to B]\) だと示せ。

ヒント: 任意の要素 \(a \in A\) を関数 \(\sigma_{a}\colon A \to B\) に結び付ける関数を \(\sigma\colon A \to [A \to B]\) とする。\(b \neq c\) を満たす \(b, c \in B\) を取って、次の関数を考える:

文字列手続き (string procedure) とは、ASCII アルファベットからなる文字列を一つ入力に受け取る手続きである。文字列手続き \(P\) に文字列 \(s\) を入力したとき計算がいずれ停止するなら、\(P\) は \(s\) を認識 (recognize) すると言う。この文脈では文字列の集合を言語 (language) と呼ぶ。\(P\) が認識する文字列全体の言語を \(\operatorname{lang}(P)\) と表記する:

言語 \(L\) が認識可能 (recognizable) とは、\(L = \operatorname{lang}(P)\) が成り立つ文字列手続き \(P\) が存在することを言う。

プログラムの文法規則に従う文字列 \(s \in \text{ASCII}^{\ast}\) が定義する文字列手続きを \(P_{s}\) と表記する (文字列 \(s\) をコンパイルした結果が \(P_{s}\) だと考えることができる)。もし \(s \in \text{ASCII}^{\ast}\) がプログラムの文法規則に従っていないなら、任意の入力に対して停止しない手続きを \(P_{s}\) と定める。このとき、任意の文字列は何らかの文字列手続きを定義し、任意の文字列手続きは何らかの文字列 \(s \in \text{ASCII}^{\ast}\) に対する \(P_{s}\) である。

第 8.2 節で見たように、簡単な対角線論法を使うと次の集合が認識可能でないと示せる:

「\(P_{s}\) に \(s\) を入力する」のは奇妙な操作に思える。もう少し常識的な例は作れないだろうか？ 答えは「たくさん作れる」である。この問題では、次の三つの集合が認識可能でないと示す:

最初に、\(\text{No-halt-}\lambda\) を認識する手続きを使うと \(\text{No-halt}\) を認識する手続きを定義できることを示す。つまり、\(\text{No-halt}\) の認識という奇妙な問題を \(\text{No-halt-}\lambda\) の認識という理解しやすい問題に帰着 (reduce) させる。\(\text{No-halt}\) は認識可能でないので、このとき \(\text{No-halt-}\lambda\) も認識可能でないと分かる。

具体的な帰着は次の通りである。与えられた文字列 \(s\) が \(\text{No-halt}\) に属するかどうかを判定したいとする。\(s\) を使って、次の手続き \(P_{s^{\prime}}\) を表す文字列 \(s^{\prime}\) を作成する:

もし \(P_{s}\) に \(s\) を入力したとき停止するなら、\(P_{s^{\prime}}\) は全ての文字列に対して停止する。逆に、もし \(P_{s}\) に \(s\) を入力したとき停止しないなら、\(P_{s^{\prime}}\) は全ての文字列に対して停止しない。つまり次の関係分かる:

これを言い換えれば

である。つまり \(s \in \text{No-halt}\) かどうかを判定するには、\(s^{\prime} \in \text{No-halt-}\lambda\) かどうかを判定すればよい。上述したように、これは \(\text{No-halt-}\lambda\) が認識可能なら \(\text{No-halt}\) が認識可能であることを意味する (学生から何回か質問を受けたので繰り返しておく)。\(\text{No-halt}\) が認識可能でないことは既知なので、\(\text{No-halt-}\lambda\) は認識可能でないと結論できる。

1. \(\text{Finite-halt}\) が認識可能でないと結論付けよ。

   ヒント: 同じ \(s^{\prime}\) が利用できる。

続いて、\(\text{No-halt}\) を \(\text{Always-halt}\) に帰着させる方法を見よう。与えられた文字列 \(s\) が \(\text{No-halt}\) に属するかどうかを判定したいとする。\(s\) を使って、次の手続き \(P_{s^{\prime\prime}}\) を表す文字列 \(s^{\prime\prime}\) を作成する:

2. \(\text{Always-halt}\) が認識可能でないと結論付けよ。

   ヒント: \(s \in \text{No-halt} \ \ \longleftrightarrow \ \ s^{\prime\prime} \in \text{Always-halt}\) である理由を説明する。

3. \(\overline{\text{Finite-halt}}\) が認識可能でない理由を説明せよ。

   ヒント: 同じ \(s^{\prime\prime}\) が利用できる。

\(P_{s}\) に \(s\) を入力したとき停止するかどうかは簡単に判定できる: \(P_{s}\) に \(s\) を入力したときの動作を停止するまでシミュレートすればよい。ここから \(\overline{\text{No-halt}}\) は認識可能だと分かる。この問題では \(\text{Finite-halt}\) が \(\text{No-halt}\) より厄介な言語だと証明した: \(\text{Finite-halt}\) と \(\overline{\text{Finite-halt}}\) は両方とも認識可能でない。

集合に関する任意の述語 \(P\) に対して、\(P\) を満たす全ての集合の集まりを \(\mathcal{S}_{P}\) と定める:

1. \(\mathcal{S}_{P}\) が集合とならない \(P\) の例を示せ。

2. \(\mathcal{S}_{P}\) が集合となる \(P\) の例を示せ。

3. \(\mathcal{S}_{P}\) が集合なら \(P(\mathcal{S}_{P})\) は偽だと示せ。

定理 8.3.2 より、全ての純粋集合は再帰集合 \(\text{RecSet}\) の要素で、その逆も成り立つと分かる。それなのに、どうして集合論の公理 (ZFC) を放棄して \(\text{RecSet}\) の再帰的定義で集合を定義しないのだろうか？

数学的オブジェクト \(a\), \(b\) から組 \((a, b)\) を構築する操作は、当たり前に可能なものとして証明なしに用いられる数学的操作の一つである。しかし、全ての数学的概念が集合論に帰着できると示すには、組 \((a, b)\) を集合で表現する方法が必要になる。

1. 組 \((a, b)\) を集合 \(\left\{ a, b \right\}\) で表現する方法では問題が発生する理由を説明せよ。

2. 組 \((a, b)\) を集合 \(\left\{ a, \left\{ b \right\} \right\}\) で表現する方法でも問題が発生する理由を説明せよ。

   ヒント: \(\left\{ \left\{ 1 \right\}, \left\{ 2 \right\} \right\}\) は何を表すか？

3. 次の規則で定義される \(\operatorname{pair}(a, b)\) で組 \((a, b)\) を表現するとき、\(a\) と \(b\) が一意に決定する理由を説明せよ:

   \[ \operatorname{pair}(a, b) ::= \left\{ a, \left\{ a, b \right\} \right\} \]

   ヒント: 任意の集合は自身を間接的な要素に持つことができない。つまり、任意の集合 \(a\) に対して \(a \in a\) は成り立たず、任意の集合 \(a\), \(b\) に対して \(a \in b \in a\) も成り立たない。

選択公理は「\(s\) が組ごとの交わりを持たない (pairwise disjoint) ── つまり、任意の二集合が共通要素を持たない ── 非空集合の集合なら、\(s\) の各要素からちょうど一つずつ要素を集めた集合 \(c\) が存在する」と定める。

\(s\) が満たす条件は次のように論理式で表せる:

同様に、\(c\) が満たす条件は次の論理式で表せる:

ここで \(\exists! z.\) は「以下の条件を満たす \(z\) が一つだけ存在する」を表す非常に標準的な記号である。

これらの述語を使えば、形式的な定義が可能になる:

この定義に関する唯一の問題は、集合論の公理は集合の言葉を使った純粋論理式で定義する必要がある点である。つまり、集合間の要素関係を表す記号 \(\in\)、命題論理式の論理結合子、二つの量化子 \(\forall\), \(\exists\)、そして集合の値を取る変数だけが含まれる論理式で定義しなければならない。上述した定義に含まれる純粋でない部分論理式を同値な純粋論理式に置き換える方法を説明し、選択公理が純粋論理式で表現できることを確かめよ。

例えば、論理式 \(x = y\) は純粋論理式 \(\forall z.\ z \in x \ \operatorname{\text{\footnotesize IFF}}\ z \in y\) で置き換えられる。

\(A\) を集合、\(R \colon A \to A\) を \(A\) 上の二項関係とする。\(a_{1} \mathrel{R} a_{0}\) のとき、\(a_{1}\) は \(a_{0}\) より「\(R\)-小 (\(R\)-smaller)」と言うことにする。次の条件を満たす「\(R\)-減少」な無限列が存在しないとき、\(R\) を整礎 (well-founded) と呼ぶ:

ここで \(a_{i}\) は \(A\) の要素を表す。

例えば、\(A = \mathbb{N}\) で \(R\) が \(<\) 関係なら、\(R\) は整礎である。なぜなら非負整数の狭義減少列を伸ばしていくと必ず \(0\) で止まるからである:

一方で、狭義増加列はどこまでも長くできるので、\(>\) 関係は整礎でない:

また、\(\leq \) 関係は整礎でない: 定数を並べた無限列は「\(\leq\)-減少」となる:

1. \(A\) の部分集合 \(B\) の要素 \(b \in B\) が \(R\)-最小 (\(R\)-minimal) とは、\(b\) より \(R\)-小な \(B\) の要素が存在しないことを言う。「\(R\colon A \to A\) が整礎」と「\(A\) の任意の非空部分集合が \(R\)-最小な要素を持つ」が同値だと示せ。

集合論の論理式 (formula of set theory) は、集合を表す変数 \(x\), \(y\) 間の要素関係を表す述語 \(x \in y\) と論理結合子と量化子だけを持つ。例えば

は「\(x\) は空集合」を表す集合論の論理式である。

2. 集合 \(v\) に含まれる集合の中で \(u\) が \(\in\)-最小であることを表現する集合論の論理式 \(\text{member-minimal}(u, v)\) を書け。

3. 基礎の公理 (axiom of foundation) は \(\in\) が集合に関する整礎関係だと主張する。他の資料を参照せずに、基礎の公理を集合論の論理式で表現せよ。解答では上記の \(\text{member-minimal}\) と \(\operatorname{isempty}\) を使って構わない。

4. 基礎の公理が「自身を要素に持つ集合は存在しない」を意味する理由を説明せよ。

この問題の解答では、以前の設問で定義された略記を使って構わない。また \(=\) は最初から使ってよい。

1. \(y \subseteq \left\{ y_{1}, y_{2}, \ldots y_{n} \right\}\) を意味する集合論の論理式⁵ \(\text{Subset}_{n}(x, y_{1}, y_{2}, \ldots, y_{n})\) を書け。

2. \(\text{Subset}_{n}\) を使って「\(x\) の要素数が \(n\) 以下」を意味する集合論の論理式 \(\text{Atmost}_{n}(x)\) を書け。

3. 「\(x\) の要素数が \(n\)」を意味する集合論の論理式 \(\text{Exactly}_{n}(x)\) を示せ。解答は長さが \(\text{Atmost}_{n}\) の二倍程度である必要がある。

4. 「\(y_{1}\), \(\ldots\), \(y_{n}\) は相異なる」を意味する集合論の論理式 \(D_{n}(y_{1}, \ldots, y_{n})\) を得る簡単な方法として、\(1 \leq i < j \leq n\) に対する \(y_{i} \neq y_{j}\) を \(\operatorname{\text{\footnotesize AND}}\) で結ぶ方法がある。このとき \(n(n - 1)\) 個の部分論理式が \(\operatorname{\text{\footnotesize AND}}\) で結ばれるので、\(D_{n}\) の長さは \(n^{2}\) に比例する。\(n\) に比例する長さしか持たない集合論の論理式で \(D_{n}\) を表現する方法を説明せよ。

   ヒント: \(\text{Subset}_{n}\) と \(\text{Exactly}_{n}\) を使う。

この問題では、途方もなく無限にあるオブジェクトに関する性質の単純な証明が構造的帰納法によって提供される。

任意の純粋集合は二人ゲームを定義すると理解できる: 集合の要素がプレイヤーによる操作の結果を表す。二人のプレイヤーは交互に操作を行い、操作ができなくなったプレイヤーの敗北と定める。言い換えれば、空集合を選択したプレイヤーの勝利である。

この「集合ゲーム (set game)」の初期盤面を集合 \(R\) とする。\(R\) から最初に操作するプレイヤーを \(\text{Next}\) と呼び、もう一人のプレイヤーを \(\text{Previous}\) と呼ぶ。\(\text{Next}\) が \(S \in R\) を選択すると、ゲームは \(S\) を初期盤面として \(\text{Previous}\) が最初に操作する新しいゲームに進行する。

再帰集合 \(\text{RecSet}\) の定義 (8.3.1) に関する構造的帰納法を使って、任意の集合ゲームにおいて \(\text{Next}\) または \(\text{Previous}\) に必勝戦略が存在すると示せ⁶。

1. \(p = \left\{ a, b \right\}\) を意味する集合論の論理式⁷ \(\operatorname{Member}(p, a, b)\) を書け。

   ヒント: 「\(p\) の任意の要素は \(a\) または \(b\) である」を表現する。\(x = y\) の形をした部分式を使って構わない (集合論の論理式の略記とみなせるため)。

組 \((a, b)\) は長さ \(2\) の列であり、第 \(1\) 要素 \(a\) を、第 \(2\) 要素に \(b\) を持つ。組は基礎的な数学的データ型であり、当然のものとして証明や定義を示すことなく使われている。しかし、全ての数学が集合論に帰着できると示すには、組を集合で表現する手段が必要になる。集合を使った組 \((a, b)\) の表現であって問題が起こらないもの⁸を次に示す:

2. \(p = \operatorname{pair}(a, b)\) を意味する集合論の論理式 \(\text{Pair}(p, a, b)\) を書け。

   ヒント: \(\text{Members}(p, a, b)\) を部分式として使って構わない。

3. 「\(p\) は第 \(2\) 要素に \(b\) を持つ組である」を意味する集合論の論理式 \(\operatorname{Second}(p, b)\) を書け。