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

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

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

参照用 記事

集合と論理の練習問題: ツリー状の集合族

集合は、A, B など英字大文字で表します。集合の要素は英字小文字、a∈A とか。集合の集合を集合族とも呼びます。集合族は太字でTなどとします。

集合族Tが“ある条件”を満たすとき、ツリーとして絵に描けることを示します。また、要素aを含む一番小さな集合が一意に決まることも示します。ベン図などを描くと直感的に明らかな事なんですが、練習としてあえて論理式で書いてみます。

内容:

  1. disjoint-or-includedな集合族
  2. 「⊂⊂」と「∈∈」
  3. 関数を構成する
  4. ツリー状であること

disjoint-or-includedな集合族

Tは集合族だとします。次の条件を仮定します。

  1. Tは有限集合である。つまり、集合族Tに含まれる集合は有限個しかありません。ただし、Tの要素である集合が有限だとは仮定しませんのでご注意を。
  2. A∈T ならば、Aは空集合ではない。
  3. A, B∈T、A∩B ≠ 空集合 ならば、A⊆B または B⊆A 。

T自体が空であることを禁止してませんが、空では面白く無いので、以下、Tは空でないとします。

次の条件も付けますが、これを満たすようにすることは簡単にできます。

  1. U∈T があって、任意の A∈T に対して A⊆U
  2. 任意の a∈U に対して、a∈A となる A∈T が存在する。

このようなUがないなら、Tに属する集合すべての合併集合を作って、それをUとすればいいのです。Uを、集合族Tルート集合と呼びましょう。そう、ツリーのルートになる集合だからです。

以上の条件を満たす集合族をなんと呼びましょう? ツリー状集合族でもいいのですが、結論を先取りし過ぎているような。身も蓋もなくdisjoint-or-includedな集合族と言うことにします。Tに属する2つ(同一かもしれない)の集合は、disjointかincludedの関係になることが最も重要な条件だからです。

「⊂⊂」と「∈∈」

Tがdisjoint-or-includedな集合族として、A, B∈Tのあいだの関係「A⊂⊂B」と、a∈U と A∈T のあいだの関係「a∈∈A」を次のように定義します。

  • A⊂⊂B ⇔ A⊂B ∧ ∀X.(A⊂X ⊃ B⊆X)
  • a∈∈A ⇔ a∈A ∧ ∀X.(a∈X ⊃ A⊆X)

わかりますか? 記号「⇔」は左右が同値なことですが、ここでは特に、左辺を右辺により定義していることを示しています。記号「∧」は論理AND(連言)で、記号「⊃」は含意です。我々が使う古典論理では、P⊃Q は ¬P∨Q と同値です。ここで、「∨」は論理OR(選言)、「¬」は否定です。

含意の逆向きの「⊂」は論理記号ではなくて、「A⊂B ⇔ (A⊆B ∧ A≠B)」の意味ですから注意してください。

「∀X.…」は「任意の集合Xについて …」と読みます。任意とはいっても、X∈T なので、「∀X∈T.」と書くほうが正確です。ここではまだ出てきてませんが、「∃X.…」は「…である集合Xが存在する」です。

定義に基づいて次を示せます。

  1. Aに対して A⊂⊂B となるBは、存在するなら一意的である。
  2. aに対して a∈∈A となるAは、存在するなら一意的である。

一番目だけやってみると:

  1. A⊂⊂B、A⊂⊂B' とする。
  2. A⊂⊂B' から A⊂B'
  3. A⊂⊂B から、 ∀X.(A⊂X ⊃ B⊆X) 。
  4. XのところにB'を入れると (A⊂B' ⊃ B⊆B') だが、A⊂B' は成立しているので、B⊆B'
  5. 同様な議論で、B'⊆B
  6. B⊆B' かつ B'⊆B なので、B = B'

関数を構成する

ここで、イプシロン記号を思い出してください。

Pが変数xを含む命題として、εx.P は、「Pであるようなx」と読みます。∃!x.P は「Pであるようなxが一意的に存在する」ことを意味します。命題Pが変数yを含んでいて、もし ∀y.(∃!x.P) が証明できているなら、次の式で関数fを定義できます。

  • f(y) = εx.P

ただし、xやyが動く範囲は前もって明確にしておく必要があります。

我々は、disjoint-or-includedな集合族Tに対して、次のような関数を定義したいと思います。

  • F(A) = εX.(A⊂⊂X)
  • g(a) = εX.(a∈∈X)

ここで、Aの動く範囲はTですが、Uは除外します。aの動く範囲はUです。「\」を集合の差だとして、Fとgの域・余域を書くと、次のとおりです。

  • F:(T\{U})→T
  • g:U→T

これらの関数が定義できる条件は次のようになります。

  • ∀A.(A≠U ⊃ ∃!X.(A⊂⊂X))
  • ∀a.(∃!X.(a∈∈X))

もし存在するなら一意的は既に示したので、A, aをそれぞれ変域T、Uを走る自由変数として、次を示せばいいことになります。

  • A≠U ⊃ ∃X.(A⊂⊂X)
  • ∃X.(a∈∈X)

これは、形式的証明の練習問題にいいのではないでしょうか。

ツリー状であること

disjoint-or-includedな集合族Tを絵に描くとツリーになります。これはどういうことかと言うと; Tの要素(集合です)をノードとして描きます。Tは有限集合だったので、ノードは有限個です。ノードである集合Aに対して、F(A) を親とみなします。つまり、AからF(A)に向けて矢印を引きます。

ルートとなるU以外では、親が一意的に決まることはわかっています。しかし、サイクルが生じる可能性があります。「サイクルはない」と示すには、次を示せばいいでしょう。

  • 任意のA(≠U)に対して、適当な正整数kがあって、Fk(A) = U となる*1

Fkは、関数Fのk回の繰り返し適用です。F0(A) = A と約束すれば、F0(U) = U です。この命題から決まるkが、ノードAの高さ(あるいは深さ)となります。Uの高さは0です。


こんなことを考えたのは、単なる練習問題というわけじゃなくて、とあるリクエストディスパッチ手法が「扱いやすい」ことを示すためだったりします。

*1:あれ、論理式じゃなくて自然言語になってますね。