練習問題

整列原理を使う練習として、整列原理を使った証明のテンプレートを利用して次の簡単な事実を証明してみよう:

整数 \(j\) が整数 \(k\) を割り切ることを \(j \; | \; k\) と表記する。また、述語 \(S(n)\) を「\(10\) セント切手と \(15\) セント切手だけを使って \(n\) セントの郵便料金をちょうど支払える」と定める。このとき、示すべき命題は次のように表せる:

次の証明に含まれる \((\,\cdots)\) を埋めることで、命題 \(\text{(2.2)}\) の証明を完成させよ。

証明 命題 \(\text{(2.2)}\) の反例全体の集合を \(C\) とする。具体的に言えば、\(C\) を次のように定める:

矛盾を導くために \(C\) が非空だと仮定する。このとき整列原理より \(C\) には最小要素 \(m\) が存在する。この \(m\) は正である。なぜなら \((\,\cdots)\ \)

\(S(m)\) が成り立って \(m\) が正なので、\(S(m-10)\) または \(S(m-15)\) が成り立つ。なぜなら \((\,\cdots)\ \)

\(S(m-10)\) が成り立つと仮定する。このとき \(5 \; | \; (m - 10)\) である。なぜなら \((\,\cdots)\ \)

しかし、もし \(5 \; | \; (m - 10)\) なら明らかに \(5 \; | \; m\) であり、\(m\) が反例である事実と矛盾する。

\(S(m -15)\) が成り立つ場合も、同様に矛盾が導ける。

両方の場合で矛盾が導けたので、\((\,\cdots)\) と結論できる。つまり命題 \(\text{(2.2)}\) は成り立つ。 ■

Fibonacciフィボナッチ 数 (Fibonacci number) \(F(0)\), \(F(1)\), \(F(2)\), \(\ldots\) は次のように定義される:

次の誤った証明に含まれる正しくない箇所 (一つとは限らない) を正確に指摘し、なぜ誤っているか説明せよ。

誤った主張 全ての Fibonacci 数は偶数である。

誤った証明 以降で使われる \(m\), \(n\), \(k\) は全て非負整数を表す。

1. 整列原理を使って示す。

2. \(\operatorname{EF}(n)\) を述語「\(F(n)\) は偶数である」と定める。

3. 命題「全ての \(n \in \mathbb{N}\) で \(\operatorname{EF}(n)\) が成り立つ」の反例全体の集合を \(C\) とする。具体的に言えば、次のように \(C\) を定める:

   \[ C ::= \left\{n \in \mathbb{N} \; | \; \operatorname{\text{\footnotesize NOT}} (\operatorname{EF}(n))\right\} \]

4. 背理法で \(C\) が空だと示す。そのために \(C\) が非空だと仮定する。

5. 整列原理より、\(C\) には最小要素 \(m\) が存在する。

6. \(F(0) = 0\) は偶数より \(m > 0\) が分かる。

7. \(m\) は最小の反例なので、任意の \(k < m\) で \(F(k)\) は偶数である。

8. 特に、\(F(m-1)\) と \(F(m-2)\) はどちらも偶数である。

9. Fibonacci 数の定義より、\(F(m)\) は \(F(m-1) + F(m-2)\) に等しい。つまり \(F(m)\) は二つの偶数の和だから、偶数である。

10. よって \(\operatorname{EF}(m)\) は正しい。

11. これは \(\operatorname{\text{\footnotesize NOT}} (\operatorname{EF}(m))\) が成り立つという \(m\) の定義と矛盾する。

12. 矛盾が得られたので、\(C\) は空だと分かる。つまり、任意の \(n \in \mathbb{N}\) で \(F(n)\) は偶数である。

■

第 2.1 節では、全ての正の有理数は既約分数として ── 共通の素因数を持たない二整数の比として ── 表現できることを整列原理を使って証明した。次に示すのは同じ結論を示す別証明であるものの、誤りを含んでいる。正当化されていない論理的推論を行っている箇所を指摘せよ。

誤った証明 背理法で示す。既約分数として表現できない正の有理数 \(q\) が存在すると仮定する。既約分数として表現できない正の有理数全体の集合を \(C\) と定める。\(q \in C\) より \(C\) は非空だから、\(C\) には最小要素 \(q_{0}\) が存在する。

\(q_{0} / 2 < q_{0}\) だから、\(q_{0} / 2\) は既約分数として表現できる。つまり、共通の素因数を持たない正整数 \(m\), \(n\) であって次の等式を満たすものが存在する:

以降の議論は二つの場合に分かれる:

\(C\) が非空という仮定から矛盾が得られたので、\(C\) は空だと分かる ── つまり反例は存在しない。 ■

整列原理を使って¹、全ての非負整数 \(n\) に対して次の等式が成り立つことを示せ:

整列原理を使って、次の等式を満たす正整数 \(a\), \(b\), \(c\) が存在しないことを示せ:

\(m + 1\) 個の封筒があり、それぞれ \(1\), \(2\), \(4\), \(\ldots\), \(2^{m}\) ドルが入っている。性質 \(m\) を次のように定める:

性質 \(m\) が全ての非負整数 \(m\) で成り立つことを整列原理を使って証明せよ。

ヒント: 「目標金額が \(2^{m}\) より小さいとき」と「目標金額が \(2^{m}\) 以上のとき」を分けて考える。

整列原理を使って、\(8\) 以上の任意の整数は \(3\) の非負整数倍と \(5\) の非負整数倍の和として書けることを示せ。

整列原理を使って、\(50\) 以上の任意の整数は \(7\) の非負整数倍と \(11\) の非負整数倍と \(13\) の非負整数倍の和として書けることを示せ。

1796 年、Eulerオイラー は次の等式を満たす整数 \(a\), \(b\), \(c\), \(d\) は存在しないと予想した:

この等式を満たす整数 \(a\), \(b\), \(c\), \(d\) は 1986 年に初めて発見された。つまり Euler は間違っていたものの、その間違いが判明するまでには二世紀以上の時間を要した。

この問題では Lehmanリーマン が考案した等式を考える。これは上記の Euler の等式に似ているものの、いくつか係数が付いている:

等式 \(\text{(2.5)}\) は整数解を持たないことを示せ。

ヒント: 等式 \(\text{(2.5)}\) の解を全て考えたときの \(a\) の最小値を考える。

整列原理を使って、非負整数 \(n\) に対する次の不等式を示せ:

ヒント: \(n \leq 4\) に対しては手計算で不等式 \((\ast)\) を示す。

ミニテトリスと呼ばれるゲームでは、\(2 \times n\) のボードを次の \(3\) 種類のタイルで隙間無く配置することを目指す:

隙間無くタイルを配置する方法を勝利配置 (winning configuration) と呼ぶ。\(2 \times 5\) のボードを使うときの勝利配置の例を次に示す:

1. \(2 \times n\) のボードを使うときの異なる勝利配置の個数を \(T_{n}\) とする。\(T_{1}\), \(T_{2}\), \(T_{3}\) を求めよ。

2. \(n > 2\) に対する \(T_{n}\) を \(T_{n-1}\) と \(T_{n-2}\) を使って表せ。

3. 整列原理を使って、\(2 \times n\) のボードを使うミニテトリスの異なる勝利配置の個数 \(T_{n}\) は次の式²で表せると示せ:

   \[ T_{n} = \frac{2^{n+1} + (-1)^{n}}{3} \tag{\(\ast\)} \]

ミニテトリスは \(n \times 2\) のボードに指定されたタイルを隙間無く配置するゲームである。この問題では次の \(5\) 種類のタイルを使ったミニテトリスを考える:

例えば、\(1 \times 2\) のボードに隙間無くタイルを配置する方法は \(2\) 通りある:

また、次に示すのは \(2 \times 2\) のボードに隙間無くタイルを配置する \(3\) 通りの方法である:

タイルを回転させてはいけないことに注意してほしい。そのため、最後に示した \(3\) 通りの配置の \(2\) 番目と \(3\) 番目は互いに \(180^{\circ}\) 回転させた形をしているものの、異なる配置とみなされる。また、両者を \(90^{\circ}\) だけ回転させた図形はそもそもタイルの正しい配置を表さない。

1. \(2 \times 2\) のボードにタイルを隙間無く配置する方法は上に示したもの以外に \(4\) 通りある。全て示せ。

\(n \times 2\) のボードにタイルを隙間無く配置する異なる方法の個数を \(T_{n}\) とする。これまでに \(T_{1} = 2\) と \(T_{2} = 7\) は判明した。また、\(0 \times 2\) のボードにはタイルを一切配置できないので \(T_{0} = 1\) が分かる。

2. \(n \geq 2\) のとき、\(T_{n}\) は \(T_{n-1}\) と \(T_{n-2}\) を使って次のように表せる:

   \[ T_{n} = 2 T_{n-1} + 3 T_{n-2} \tag{2.6}\]

   この式が正しい理由を簡単に説明せよ。

3. 整列原理を使って、\(n \geq 0\) で次の等式が成り立つと示せ:

   \[ T_{n} = \frac{3^{n+1} + (-1)^{n}}{4} \]

次に示すのは、命題「\(10\) セント切手と \(15\) セント切手だけを使ってちょうど支払える郵便料金は \(5\) で割り切れる」の整列原理を使った証明である。簡単に埋められる詳細は省略してある。

整数 \(j\) が整数 \(k\) を割り切ることを \(j \; | \; k\) と表記する。また、述語 \(S(n)\) を「\(10\) セント切手と \(15\) セント切手だけを使って \(n\) セントの郵便料金をちょうど支払える」と定める。このとき、証明が示すのは次の命題である:

次に示す命題 \(\text{(2.7)}\) の証明で省略されている \((\,\cdots)\) の部分を埋める文章を答えよ。また、最後にあるように証明には小さな誤りが含まれるので、それを指摘して修正せよ。

この証明は \(m\) の値に関して暗黙の仮定をしている。その仮定は何かを述べ、一行で正当化せよ。

1. 整列原理を使って、命題「\(6 ¢\), \(14 ¢\), \(21 ¢\) の切手を使うことで、\(50 ¢\) 以上のどんな郵便料金もちょうど支払うことができる」を示せ。面倒な議論を省くため、\(50 ¢\), \(51 ¢\), \(\ldots\), \(100 ¢\) はちょうど支払えると「証明なしに仮定」して構わない。ただし、ちょうど支払えると証明なしに仮定する料金が具体的にどれかを明確に表明すること。

2. \(49 ¢\) はちょうど支払えないことを示せ。

\(n\) を正整数とする。整列原理を使って、最初の \(n\) 個の奇数の和が \(n^{2}\) に等しいと示そう。つまり、整数 \(n > 0\) に対する次の等式を示す:

矛盾を導くために、等式 \(\text{(2.8)}\) が特定の正整数 \(n\) で成り立たないと仮定する。そのような正整数の中で最小のものを \(m\) とする。

1. \(m\) が必ず存在すると言えるのはなぜか？

2. \(m \geq 2\) である理由を説明せよ。

3. 前問が次の等式を意味する理由を説明せよ:

   \[ \sum_{i=1}^{m-1} (2 (i - 1) + 1) = (m - 1)^{2} \tag{2.9}\]

4. 等式 \(\text{(2.9)}\) の左辺を

   \[ \sum_{i=1}^{m} (2 (i - 1) + 1) \]

   とするには、どのような項を両辺に足すべきか？

5. 全ての正整数 \(n\) で等式 \(\text{(2.8)}\) が成り立つと結論付けよ。

整列原理を使って、全ての正整数 \(n\) で次の等式が成り立つと示せ:

整列原理を使って、全ての非負整数 \(n\) で次の等式が成り立つと示せ:

整列原理を使って、\(1\) 以上の全ての整数 \(n\) で次の等式が成り立つと示せ:

\(6 ¢\) と \(16 ¢\) の切手だけを使ってちょうど支払える郵便料金を支払い可能 (makeable) と呼ぶことにする。整列原理を使って、\(12\) 以上の \(3\) の倍数は全て支払い可能だと示せ。

補題 2.4.6 の証明を完成させよ。つまり、\(n_{S} + f_{S}\) が \(S\) の最小要素だと示せ。

次に示す実数の集合のそれぞれについて、最小要素を持つかどうか、そして整列かどうかを答えよ。整列でない集合に対しては、最小要素を持たない部分集合の例を答えよ。

1. \(- \sqrt{2}\) 以上の整数全体の集合

2. \(- \sqrt{2}\) 以上の有理数全体の集合

3. 正整数 \(n\) を使って \(1/n\) と書ける有理数全体の集合

4. \(g\) をグーゴル (googol) と呼ばれる値 \(10^{100}\) としたとき、\(m, n > 0\) と \(n \leq g\) を満たす整数 \(m\), \(n\) を使って \(m/n\) と書ける有理数全体の集合 \(G\)

5. 非負整数 \(n\) を使って \(n/(n+1)\) の形で書ける有理数全体の集合 \(\mathbb{F}\):

   \[ \mathbb{F} ::= \left\{\frac{0}{1},\ \frac{1}{2},\ \frac{2}{3},\ \frac{3}{4},\ \ldots,\ \frac{n}{n+1},\ \ldots \right\} \]

6. 非負整数 \(n\) を使って \(n/(n+1)\) と表せる有理数と非負整数を全て集めた集合を \(W ::= \mathbb{N} \cup \mathbb{F}\) とする。\(W\) の要素で構成される、\(1\) から始まる長さ \(5\) の減少列を答えよ。同じ条件で長さ \(50\)、そして長さ \(500\) の減少列を答えよ。

整列原理を使って、空でない実数の有限集合は全て最小要素を持つと示せ。

「実数の集合 \(R\) が整列」と「\(R\) の要素からなる無限減少列が存在しない」が同値だと示せ。「\(R\) の要素からなる無限減少列が存在する」とは、次の条件を満たす \(r_{i} \in R\) が取れることを意味する: