このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

有限集合とは何だろう(ストーリー付き練習問題集)

「Xは有限集合である」とか「Xは有限集合でない」とかの表現はよく出てきますが、この有限性ってのはいったい何なんでしょう? 少しマジメに考えてみることにします。これといった予備知識を要求しませんが、マジメに考える態度は必要です。

実は、有限性を調べるのは目的じゃなくて手段です。証明の“お膳立て”シリーズとか、自然演繹ダメじゃんシリーズ(って、そんなシリーズねえけど、「存在記号の除去規則について考える」とか)に対して、例題を提供するのが、この記事の主たる目的です。この記事を読みながら、ハッキリとは書いてない証明を全部書いていくことが練習問題になります。内容的には超カンタン(当たり前)なので、明示的な証明は逆にハードです。

内容:

自然数についてよく知っているとする

公理的集合論では、集合ありき/集合しかない世界で考えるので、自然数集合論のなかで組み立てたりします。しかし我々は、集合を習うはるか前に自然数を習います。集合についてあまり知らなくても、自然数についてはけっこうよく知っています。

という事情から、自然数についてはよく知っているとします。「よく知っている」とは次のような事だとします。

  1. 0, 1, 2などの個々の自然数を知っている。
  2. 自然数の全体が集合Nを形成することを知っている。
  3. 自然数加減乗除について知っている。引き算は部分演算(n ≦ m のときだけ m - n を定義)、割り算は整除を使う。
  4. 自然数の大小関係について知っている。また、加減乗除と大小関係の“関係”についても知っている。例えば、n ≦ n', m ≦ m' ならば n + m ≦ n' + m' など。

これらの知識は、だいたい小学校で習います(集合概念は小学校で習わないかな)。小学校では習わない重要な事として、数学的帰納法の原理があります。

  • 自然数の変数(集合N上を走る変数)を含む命題Pに対して、P(0) と ∀k∈N.P(k)⊃P(k + 1) が成立するなら、∀n∈N.P(n) が成立する。

記号'⊃'は「ならば」です。'⇒'を使う人が多いかも知れませんが、僕は'⊃'を使う('⇒'や'→'は他の意味で使う)ことが多いので、今回は'⊃'にします(気分によって使う記号は変わるんだけどね)。

数学的帰納法の原理は、しばしばドミノ倒しに喩えられます。最初の(0番目の)ドミノが確実に倒れ、k番目のドミノが倒れたなら(k + 1)番目も倒れることが保証されているなら、全部のドミノが倒れるはずだ、ってことです。P(0) を数学的帰納法ベース〈the base case〉、∀k∈N.P(k)⊃P(k + 1) を数学的帰納法ステップ〈the inductive/induction step〉と呼ぶことがあります。

*1

論理記号など

既に前節で論理記号を使っています。ここで使う論理記号を列挙すると:

  1. ∧ :論理AND、連言〈れんげん〉
  2. ∨ :論理OR、選言〈せんげん〉
  3. ⊃ :含意〈がんい〉
  4. ¬ :論理NOT、否定
  5. ∀ :全称限量子〈ぜんしょう・げんりょうし〉
  6. ∃ :存在限量子〈そんざい・げんりょうし〉

変数の型宣言は x:X の形にします。ここでの型は集合のことなので、Xは集合です。例えば、n:N と宣言されていれば、それ以降nは自然数の変数です。原則としては(サボらないならば)、宣言されてない変数は使えません。ただし、文脈から暗黙に宣言される(とみなす)変数を使うことはしばしばあります。

限量子∀, ∃の直後に書く変数(束縛変数)には、その場で型を指定します。∀n:N.P のような形です。ただし、∀n∈N.P のように、所属記号'∈'を使うこともあります。'∈'より':'が望ましいと思うのですが、僕はついつい'∈'で書いてしまいます。

型の指定には'∈'より':'が望ましいと書いたのは、'∈'は命題(述語論理の論理式)のなかで述語記号(関係記号)として使われるものだからです。もちろん'∈'は本来の意味 -- 要素と集合のあいだの所属関係として使います。

'∈'が出てくるってことは、常識的な集合概念は仮定するってことです。公理的集合論ではなくて、素朴集合論です。素朴集合論って何だ? ってことは、次の記事で扱っています。

有限性の定義

自然数nに対して、

  • [n] = {k∈N | k < n}

と定義します。特に、

  • [0] = {}
  • [1] = {0}

準備が出来たので、Xが有限集合であることを定義します。基本的に論理式で書きますが、すぐ下に自然言語の記述も併記します。

  • 論理式: Xは有限集合 :⇔ ∃n∈N.( X \stackrel{\sim}{=} [n] ) ---(有限集合の定義)
  • 自然言語: Xは有限集合だとは、自然数nが存在して、X \stackrel{\sim}{=} [n] となること。

ここで使った'\stackrel{\sim}{=}'は、集合として同型という意味です。その定義は:

  • 論理式: X \stackrel{\sim}{=} Y :⇔ ∃f:X→Y, g:Y→X.(f;g = idX ∧ g;f = idY ) ---(集合として同型の定義)
  • 自然言語: X \stackrel{\sim}{=} Y だとは、写像 f:X→Y と 写像 g:Y→X があって、f;g = idX かつ g;f = idY が成立すること。

';'は写像の図式順結合〈diagrammatic order composition〉記号、idXはXの恒等写像です。論理式の後のハイフン3つは、論理式に名前を付けるためのものです。

Xが有限集合だとは、適当な [n] = {0, 1, ..., n - 1} と1:1に対応することです。この定義は、納得しやすいものでしょう。

自然数nは、Xの要素の個数になります。しかし、上記の定義だけだと、有限集合Xに対してnが一意的に決まる保証がありません。次の定理が必要になります。

  • 論理式: (X \stackrel{\sim}{=} [n] ∧ X \stackrel{\sim}{=} [m]) ⊃ (n = m)
  • 自然言語: X \stackrel{\sim}{=} [n] かつ X \stackrel{\sim}{=} [m] ならば n = m である。

もし上の定理(今はまだ願望)が証明されれば、有限集合Xは(定義により)適当な[n]と同型で、そのようなnは一意的に決まるので、要素の個数が決まります。要素の個数を、有限集合Xの基数〈cardinality〉とか濃度と呼びます。有限でないXに対する基数は、今は考えません。

個数勘定の原理

前節で述べた定理は、我々が有限個のモノの集まりに対して、モノの個数を勘定できることを保証するものなので、個数勘定の原理と呼んでおきましょう。

すぐ後で使うので、集合の同型 \stackrel{\sim}{=} に関して、次の法則を確認しましょう。

  1. X \stackrel{\sim}{=} X
  2. X \stackrel{\sim}{=} Y ⊃ Y \stackrel{\sim}{=} X
  3. (X \stackrel{\sim}{=} Y ∧ Y \stackrel{\sim}{=} Z) ⊃ X \stackrel{\sim}{=} Z

もう'∧'(かつ)と'⊃'(ならば)の記号には慣れましたか。

これらの法則は任意の集合に対して成立するので、全称記号を明示すると次のようになります。

  1. ∀X:Set.( X \stackrel{\sim}{=} X ) ---(同型の反射律)
  2. ∀X, Y:Set.( X \stackrel{\sim}{=} Y ⊃ Y \stackrel{\sim}{=} X ) ---(同型の対称律)
  3. ∀X, Y, Z:Set.( (X \stackrel{\sim}{=} Y ∧ Y \stackrel{\sim}{=} Z) ⊃ X \stackrel{\sim}{=} Z ) ---(同型の推移律)

変数X, Y, Zの型はSetです(僕の気分により X∈Set とは書きませんでした)。Setは普通の型とは違って、Set自体は集合ではありません。類〈class〉とか大きな集合〈{large | huge} set〉とか呼びます。普通の集合よりデカイので取り扱い注意です。が、ここではSetの正体に深入りしないでおきましょう。気にしない気にしない。

先の3つの法則は、\stackrel{\sim}{=} が同値関係(正確には“大きな”同値関係)であることですが、\stackrel{\sim}{=} の定義に従って証明すべきことです。これは練習問題 -- 証明要求の形に書いておきます。証明要求については証明の“お膳立て”シリーズを参照してください。

  1. Γ |-? ∀X:Set.( X \stackrel{\sim}{=} X ) ---(同型の反射律)
  2. Γ |-? ∀X, Y:Set.( X \stackrel{\sim}{=} Y ⊃ Y \stackrel{\sim}{=} X ) ---(同型の対称律)
  3. Γ |-? ∀X, Y, Z:Set.( (X \stackrel{\sim}{=} Y ∧ Y \stackrel{\sim}{=} Z) ⊃ X \stackrel{\sim}{=} Z ) ---(同型の推移律)

Γは、\stackrel{\sim}{=} の定義などを含む文脈(背景知識、予備知識)です。Γを具体的に書き下すことはしませんが、けっこう色々な知識が含まれます。僕が想定しているΓとあなたの実際のΓに不一致がると、証明はできない可能性があります。Γを合意・確認する作業は、けっこう困難なものです。

個数勘定の原理を再掲します。全称限量子を付けた論理式で書きます。

  • ∀X:Set.∀n, m∈N.( (X \stackrel{\sim}{=} [n] ∧ X \stackrel{\sim}{=} [m]) ⊃ (n = m) ) ---(個数勘定の原理)

これを示すために、次の補題があればいいことは分かるでしょう。

  • ∀n, m∈N.( ([n] \stackrel{\sim}{=} [m]) ⊃ (n = m) ) ---(個数勘定の補題)

個数勘定の補題と鳩の巣原理

前節最後の個数勘定の補題の対偶を取ってみます(全称限量子は省略)。

  • (n ≠ m) ⊃ ([n] \stackrel{\sim}{=} [m] ではない)

n ≠ m は、n < m か n > m のどちらかで、どっちでも話は同じなので、n < m としましょう。すると:

  • (n < m) ⊃ ([n] \stackrel{\sim}{=} [m] ではない)

自然言語で言えば:

  • n < m ならば、[n] と [m] は同型ではない。

これは非常に当たり前です。ここまで当たり前だと証明の必要性を感じないし、どうやって証明していいかも分かりません。当たり前のことを別な当たり前のことに帰着するくらいしか出来そうにありません。「気休め」感が否めませんが、まーでも、ジタバタしてみましょう。(あるいは、練習としてジタバタしてみましょう。)

モノの個数に関する原理で割と有名なものに「鳩の巣原理」があります。

本物の鳩の画像で説明しましょう。

*2

画像の鳩の巣には9個の箱があります。よく見ると鳩は10羽います。左上の箱に2羽入っているのです。9羽を超える鳩を9箱の鳩小屋に入れると、2羽以上入る箱が必ず生じる -- これが鳩の巣原理〈pigeonhole principle〉です。

一般に、n < m であるとき、m個のモノをn個の箱に入れると、2個以上入る箱が必ず生じます。これは次のように表現できます。

  • n < m ならば、写像 f:[m]→[n] は単射ではない。

論理式で書けば(外側の全称限量子は省略):

  • (n < m) ⊃ ∀f:[m]→[n].( ¬(fは単射) )

お好みにより、ド・モルガンの法則で書き換えると:

  • (n < m) ⊃ ¬∃f:[m]→[n].( fは単射 )

鳩の巣原理を仮定して、個数勘定の補題を証明することはできます。鳩の巣原理と似た(双対っぽい)次の命題からも個数勘定の補題を証明できます。この命題は、鳩の数より箱の数が多いときは必ず空き箱が生じることを主張しています。

  • (n < m) ⊃ ¬∃f:[n]→[m].( fは全射 )

個数勘定の補題数学的帰納法

  • ∀n, m∈N.( ([n] \stackrel{\sim}{=} [m]) ⊃ (n = m) ) ---(個数勘定の補題)

この命題に n = 0 を代入してみると、次が得られます。

  • ∀m∈N.( ([0] \stackrel{\sim}{=} [m]) ⊃ (0 = m) )

これは、「空集合と同型な[m]は[0]に限る」という意味です。空集合の定義、空集合からの/への写像の定義などを使えば、普通に証明できそうです。(でも、空集合写像に関する予備知識はけっこう必要です。)

個数勘定の補題に出現する変数nを自然数の上で走らせるとすると、上記の命題は最初の状態 n = 0 での事実です。残りのnも全部倒すには、数学的帰納法を使えばよさそうです。数学的帰納法は思いの外強烈で、当たり前過ぎて証明できそうにないような命題が数学的帰納法で証明できるときがあります。やってみます。

変数nに注目して数学的帰納法の原理にうったえるならば、次の2つの命題を示せばいいことになります。

  1. ∀m∈N.( ([0] \stackrel{\sim}{=} [m]) ⊃ (0 = m) ) ---(個数勘定の補題 帰納のベース)
  2. ∀k∈N.( ∀m∈N.( ([k] \stackrel{\sim}{=} [m]) ⊃ (k = m) ) ⊃ ∀m∈N.( ([k + 1] \stackrel{\sim}{=} [m]) ⊃ (k + 1 = m) ) ) ---(個数勘定の補題 帰納のステップ)

話の筋を見失わないようにここで注意しておくと; 我々のターゲット命題は個数勘定の原理でした。個数勘定の原理を示すには、自然数だけに関係する補題を示せばいいと分かりました。ターゲットに至るために、より“手前”のサブターゲットを設定したのです。こんな考え方をバックワード・リーズニングと呼びます。さらなるバックワード・リーズニングで、数学的帰納法を成立させる2つの命題に至ったのでした。

「個数勘定の補題 帰納のベース」はいいとして、「個数勘定の補題 帰納のステップ」のほうをなんとかします。これもバックワード・リーズニングでより攻略しやすい形に変形します。そういった変形を、証明の“お膳立て”と呼んだのでした(証明の“お膳立て”シリーズ)。

まず、証明要求を書いてみます。

  • Γ |-? ∀k∈N.( ∀m∈N.( ([k] \stackrel{\sim}{=} [m]) ⊃ (k = m) ) ⊃ ∀m∈N.( ([k + 1] \stackrel{\sim}{=} [m]) ⊃ (k + 1 = m) ) ) ---(個数勘定の補題 帰納のステップ)

お決まりのお膳立てを実行しましょう。論理式が長いので複数行で書きます。

 Γ |-? ∀k∈N.(
          ∀m∈N.( ([k] \stackrel{\sim}{=} [m]) ⊃ (k = m) )
          ⊃
          ∀m∈N.( ([k + 1] \stackrel{\sim}{=} [m]) ⊃ (k + 1 = m) )
         )
 -------------------------------------------------------------[∀の変形]
 Γ/ k:N |-?
          ∀m∈N.( ([k] \stackrel{\sim}{=} [m]) ⊃ (k = m) )
          ⊃
          ∀m∈N.( ([k + 1] \stackrel{\sim}{=} [m]) ⊃ (k + 1 = m) )
 -------------------------------------------------------------[⊃の変形]
 Γ/ k:N,
    ∀m∈N.( ([k] \stackrel{\sim}{=} [m]) ⊃ (k = m) )
     |-?
    ∀m∈N.( ([k + 1] \stackrel{\sim}{=} [m]) ⊃ (k + 1 = m) )
 -------------------------------------------------------------[∀の変形]
 Γ/ k:N,
    ∀m∈N.( ([k] \stackrel{\sim}{=} [m]) ⊃ (k = m) ),
    m:N
     |-?
    ([k + 1] \stackrel{\sim}{=} [m]) ⊃ (k + 1 = m)
 -------------------------------------------------------------[⊃の変形]
 Γ/ k:N,
    ∀m∈N.( ([k] \stackrel{\sim}{=} [m]) ⊃ (k = m) ),
    m:N,
    [k + 1] \stackrel{\sim}{=} [m]
   |-?
    k + 1 = m

もう少し数学的帰納法のためのお膳立て

前節一番下段の仮定 ∀m∈N.( ([k] \stackrel{\sim}{=} [m]) ⊃ (k = m) ) で、束縛変数が直後の自由変数と同じmです。混乱を招きやすいので、束縛変数をℓに変えておきましょう。そのうえで、使っていい宣言・仮定を箇条書きにすると:

  1. k:N (変数kは自然数を表す)
  2. このkに対して、∀ℓ∈N.( ([k] \stackrel{\sim}{=} [ℓ]) ⊃ (k = ℓ) ) ---(仮定1)
  3. m:N (変数mは自然数を表す)
  4. 上記kとこのmに対して、[k + 1] \stackrel{\sim}{=} [m] ---(仮定2)

これらの変数宣言(変数導入)と仮定命題のもとで、ターゲット命題 k + 1 = m を示したいわけです。ここで、ターゲット命題の代わりに次の命題を考えます。

  • [k] \stackrel{\sim}{=} [m - 1] ---(代替ターゲット)

もし、代替ターゲットが示せれば、仮定1を使って k = m - 1 が出て、両辺に1を足してもとのターゲット k + 1 = m が得られます。よって、上記の仮定のもとで代替ターゲットを目指せばいいわけです。このとき、仮定1は使わないので削り落としてもかまいません。以上のことを証明要求に書いてみれば:

  • Γ/ (k, m:N), [k + 1] \stackrel{\sim}{=} [m] |-? [k] \stackrel{\sim}{=} [m - 1] ---(代替ターゲット)

この証明要求では、Nの部分集合に関する同型しか出てきません。証明要求に応えるには、N上で作業して、求められている同型(可逆写像)を作り出せばいいのです。

ただ、少し気になることがあります。代替ターゲットのなかで m - 1 が出てきますが、自然数の引き算は部分的にしか定義されてないので、m - 1 が意味を持つには 1 ≦ m が事前に分かっている必要があります。次のように、仮定に 1 ≦ m が欲しいのです。

  • Γ/ (k, m:N), [k + 1] \stackrel{\sim}{=} [m], 1 ≦ m |-? [k] \stackrel{\sim}{=} [m - 1] ---(代替ターゲット)

証明要求の仮定に好き勝手に命題を加えていいわけではありません。「証明の“お膳立て”のやり方 2: 証明の顧客・業者モデル」で述べた「定義・補題の追加」の手順に従えば、仮定への命題追加ができます。

  Γ/ Δ |-? Q   Γ/ Δ |- R
 -----------------------------[定義・補題の追加]
      Γ/ Δ, R |-? Q

もともとの前提から 1 ≦ m が証明できれば、それを仮定に追加できます。つまり、次の補助的な証明要求が発生します。

  • Γ/ (k, m:N), [k + 1] \stackrel{\sim}{=} [m] |-? 1 ≦ m

証明要求を順方向に並べてみる

今までバックワード・リーズニング、つまりターゲットからの逆方向の推論でサブターゲットを探ってきました。これを順方向に並べ替えて列挙してみます。

  1. Γ |-? ∀m∈N.( ([0] \stackrel{\sim}{=} [m]) ⊃ (0 = m) ) ---(個数勘定の補題 帰納のベース)
  2. Γ/ (k, m:N), [k + 1] \stackrel{\sim}{=} [m] |-? 1 ≦ m
  3. Γ/ (k, m:N), [k + 1] \stackrel{\sim}{=} [m], 1 ≦ m |-? [k] \stackrel{\sim}{=} [m - 1]
  4. Γ/ k:N, ∀m∈N.( ([k] \stackrel{\sim}{=} [m]) ⊃ (k = m) ), m:N, [k + 1] \stackrel{\sim}{=} [m] |-? k + 1 = m
  5. Γ |-? ∀k∈N.( ∀m∈N.( ([k] \stackrel{\sim}{=} [m]) ⊃ (k = m) ) ⊃ ∀m∈N.( ([k + 1] \stackrel{\sim}{=} [m]) ⊃ (k + 1 = m) ) ) ---(個数勘定の補題 帰納のステップ)
  6. Γ |-? ∀n, m∈N.( ([n] \stackrel{\sim}{=} [m]) ⊃ (n = m) ) ---(個数勘定の補題)
  7. Γ |-? ∀X:Set.( X \stackrel{\sim}{=} X ) ---(同型の反射律)
  8. Γ |-? ∀X, Y:Set.( X \stackrel{\sim}{=} Y ⊃ Y \stackrel{\sim}{=} X ) ---(同型の対称律)
  9. Γ |-? ∀X, Y, Z:Set.( (X \stackrel{\sim}{=} Y ∧ Y \stackrel{\sim}{=} Z) ⊃ X \stackrel{\sim}{=} Z ) ---(同型の推移律)
  10. Γ |-? ∀X:Set.∀n, m∈N.( (X \stackrel{\sim}{=} [n] ∧ X \stackrel{\sim}{=} [m]) ⊃ (n = m) ) ---(個数勘定の原理)

このように書くと、証明(リーズニング)の順方向の流れが分かりやすくなります。しかし、証明全体の構造は、直線状ではなくて有向グラフになります。直線上ではない依存関係を頑張ってテキストで書く例は、「証明の“お膳立て”のやり方 3: さらに事例」の「“お膳立て”の全体像」にあります。まー、無理してテキストで書く必要もなくて、マルと矢印線の手描きで十分です。

自然数の部分集合で有限なもの

今までやったことは、有限集合とは何かを定義して、有限集合の基数が一意に決まることを示しただけです。もうひとつくらい、有限集合に関する話題を入れておきましょう。

SをNの部分集合とします。Sが有界〈bounded〉であることを次のように定義します。

  • Sは有界 :⇔ ∃n∈N.∀k∈N.( k∈S ⊃ k ≦ n)

自然数の部分集合に限れば、有限性と有界性は同じことになります。つまり、次の命題が成立します。

  • (Sは有限 ⊃ Sは有界) ∧ (Sは有界 ⊃ Sは有限)

これは、少し一般化した次のような命題につながります。

  1. 有限集合からの写像の像は有限集合
  2. 有限集合の部分集合は有限集合

いずれも当たり前ですが、ジタバタしてみてください。