集合，位相，論理など

(Set, Topology, Logic, etc.)

21th Oct. 2021 (Updated)
10th Oct. 2017 (First)
Akihiko Koga

トップページへ戻る
圏論を勉強しようへ
束論を勉強しようへ
半群論を勉強しようへ
このページは計算機科学の観点から，集合論，位相，論理などについて，いろいろ，考えたり，調べたり，お勉強したりしたことを書きます．

ここで参照している文献はインターネット上で ダウンロード可能なものが多いですが，リンクは張ってない場合が多いです．すみませんが， もし，ご興味があれば検索エンジンなどで調べてください．

  1. 集合論の基礎
    1. いろいろな集合論についてのおぼえ書き
      1. 公理的集合論
      2. 素朴集合論
      3. 圏論ベースの集合論
      4. 代替集合論 (Alternative Set Theories)
        某勉強会で発表してきたことを追加しました．(2019.06.22)
    2. 集合論の学習での重要なポイント
    3. Zorn の補題と選択公理のお話
    4. ZFA + ¬選択公理のモデルの作り方 New 2021.10.21
    5. フォーシングと連続体仮説の否定の無矛盾性
    6. 基礎的な集合論の教科書
    7. 集合論についての素朴な(かなり，おまぬけな)疑問集
  2. 位相空間の基礎
      テキストや計算機応用の文献など
  3. 論理学の基礎
    1. Hilbert の体系の例
    2. レーベンハイム・スコーレムの定理 (Löwenheim-Skolem Theorem)
      某勉強会での連続体仮説解説の顛末追記
    3. ゲーデルの不完全性定理について
      別のコーナーで書いた簡単な説明へのリンクです 2019.12.28
    4. 数理論理学の基礎を勉強するための参考になりそうな文献例

●集合論の基礎

- いろいろな集合論についてのおぼえ書き

注意 *「代替集合論」という用語はぐぐってもこの意味では見つけられなかったので， alternative set theories を見て，私が勝手に作った用語のような気がします． 「代替的な」集合論くらいにして，１つの用語にとられるの避けるべきなのかもしれません．

- 集合論の学習での重要なポイント

集合論には理論的な関心，基礎論的な関心，哲学的な関心もあると思うが， 計算機科学など応用分野の人間からみれば，自分の仕事の中で，この知識を 役立てたいという気持ちがあると思う．集合論の理論で支えられている世界を 直観的に感じ，慣れ，比較的効率的に思考できるようになりたい．

それにはきっと基礎的な部分をしっかり，図などを使いイメージを養いながら 習得するのがよいと思う．そういう目的で 集合論の学習での重要なポイント を書いてみた．ページの内容は


こんなところである．かなり基礎的な記述になっているので，このページとは 雰囲気が違うと思う．

- Zorn の補題と選択公理のお話


図. Zorn の補題

ここしばらく，選択公理からのZornの補題の証明に取り組んでいました．過去， テキストを見ながら何度も証明したはずなのに，独力で証明しようとすると なかなか証明できず，満足いく証明にたどりつくまでにとてつもない長い時間が 掛かってしまいました．ここらあたりの事情は 日記 に書きましたが，証明に取り組んでいる間に色々考えることが あったし，試行錯誤の過程を述べるのも他人の勉強の参考になるかなと思って，

Zorn の補題と選択公理のお話
のページを作りました．選択公理の不思議というよりは，Zorn の補題の方が 主役のページです．2018.08.01 (水)

P.S. やはり，Zermelo が整列可能定理を証明した当時，あれだけ論争になったんだから， 選択公理や整列可能定理，Zorn の補題は難しいんだと思う．私が証明に時間がかかったのも それほど無能という訳ではない（でもそこそこ無能のような気はする）．

- ZFA + ¬選択公理のモデルの作り方

アトム（要素を含まない空集合以外のもの）を持つ集合論として ZFA があります． ZFA に選択公理の否定を加えた公理系のモデルは比較的簡単に作ることができます．

最近，自分自身の復習のために，ZFC および ZFC の解説と，そのZFA + ¬選択公理のモデルの 作り方を

ZFA の思い出しと選択公理の独立性の証明への応用

A はアトムの集まり

に書いてみました．
（のですが，ちょっと勘違いがあったようで現在精査中．近日中に リンクを貼れると思います）
2021年10月21日（木）

- フォーシングと連続体仮説の否定の無矛盾性

ℵ0 ...... 2ℵ0

せっかくZFC までまとめたので，フォーシングと連続体仮説の否定のモデルを作る方法まで 勉強することにした．とりあえず，このトピックスに関する入門的な参考文献を挙げておく． これらは PDF で公開されているが，例によって直接リンクは張らないので，著者，タイトル等で検索してほしい．

2020年3月27日追記：私自身も某勉強会の発表でこの解説を試みたものがある．
「連続体仮説の解説 AGAIN」の資料

まず，種々の文献を読むにあたっての全体的な注意を書いておく．

  1. 前提知識
    次にあげた参考文献にあたる前に，数理論理学の基礎とその解釈構造とモデル， レーヴェンハイム-スコーレムの定理( Löwenheim-Skolem の定理)を勉強しておくことが（ほぼ）必要である．とりあえずは，Wikipedia でも良いかもしれない．それで読み進められれば，そのまま学習すればよい．もしくは，読み進められなくて挫折すれば， もう少しまとまったテキストでじっくりこれらを学べばよい．たぶん，どちらにしても，そこで やった努力は，周辺知識として役に立つと思う． レーヴェンハイム-スコーレムの定理は集合論と組み合わせると結構味わい深い． なお，連続体仮説のおおざっぱな解説を某勉強会で 2018 年10月17日にやった．このページの下の方に 某勉強会での連続体仮説の解説についての顛末を書いた．

  2. 文献に寄る微妙なアプローチの違い
    私が読んだ中では，Forcing において，完備ブール代数を使うもの（そして filter としては ultrafilter であることを課すもの）と generic filter を 使うもの(ultrafilter であることを特には課さない)がある．以下の参考文献では Kenny Easwaran のものと Timothy Y. Chow のものが完備ブール代数を 使っている．たぶん，フォーシングの説明は昔に比べると格段に易しくなっているの だろうが，やはり難しいところは多い．一つの文献で分からないところを，他の文献に あたってみるのも良い方法だが，この２つは微妙に違うということを認識して おかないと混乱するかもしれない．

  3. 連続体仮説の否定のモデルでキーとなる概念
    フォーシングでは，既存の ZFC モデル M に 新しい要素 G を加えて 新しいZFC モデル M[G] を作り，そこでの性質を古いモデル M の中で 記述する技術が大きな枠組みとなる．したがって，下記の参考文献の中でも， 話の途中までは，追加される要素 G は，ある poset (partially ordered set) P の generic filter というくらいの説明しかなされず，初心者はそのイメージを 持ちづらい．しかし，連続体仮説の否定のモデルを作る際は，これを使って， 十分大きな集合から集合 2ℵ0 の中への 1対1写像（injection）を作るので，こちらこそが主役である．したがって， 連続体仮説の否定のモデルを通してフォーシングを学習しようとしている学習者は 次の流れを予め意識しながら読んだ方がよい．あるいは，これだけ個別に読んで 確固たるイメージを掴んでおくとか．

    1. P := 集合 A × ℵ0 → {0, 1} への partial function f で |f| < ∞ のものの集合を，X ≤ Y iff Y ⊆ X で順序付けた poset と考える（つまり，A × ℵ0　の中の有限部分集合を定義域とする部分関数の集合．二つの関数は，定義域が広くて，共通部分では共通の値を取る関数の方が小さいと考える．このposet の中の順序で次第に小さい要素を取っていけば，部分関数としてはより広い範囲で定義された部分関数になる．定義域を段々全域になるように広げていく部分関数列を取れば，極限としては全域関数を近似することができる）

    2. P の部分集合 D について「稠密(dense)」という概念を導入する．これはPの中の 任意の部分関数 h を取って来ても，D の中に，それより定義域が広くて 引数 n が h の定義域内では h(n) と同じ値をとる関数が D に存在するということである．

    3. P のフィルターとなる部分集合 G で P の任意の稠密な部分集合と交わるものを generic filter という

    4. fG := ∪ G とすると fG は A × ℵ0 → {0, 1} の関数になる．これは
      f'(a) := {n ∈ ℵ0 | fG(a, x）= 1}
      と置けば，関数 f' : A → 2ℵ0 を定めているとも言える． さらに，この f' は A から2 ℵ0 の中への1対1関数（injection）になる．この f' が集合 ℵ0 と 2 ℵ0 の間の集合を作るための本質的な役割を果たす

それでは入門的な参考文献をリストアップする．

  1. SPENCER UNGER : FORCING SUMMER SCHOOL LECTURE NOTES, 2014, pp1-44

    一応，Self-contained の度合いが高い．数理論理学の話やZFC の公理的集合論の 話なども載っている．したがって，上に書いた注意に反して，これだけは そのまま読み進められるのだが，やはり，基礎知識の解説には限界がある． 読み進めている際に難しいと感じたら，じっくり考えたり，ほかの文献を 適宜探して補足学習するなど，あまり焦らずに読み進めるのが良いと思う．

  2. Kenny Easwaran : A Cheerful Introduction to Forcing and the Continuum Hypothesis, 2007, pp1-15

    注意に述べたように「ZFC+連続体仮説の否定」のモデルを作る際に完備ブール代数を使っている．比較的ストーリーは追いやすい．

  3. Timothy Y. Chow : A beginner's guide to forcing, 2007, pp1-16

    もともと USENET の sci.math.research に2001年に投稿された "Forcing for dummies"（「サルでもわかるフォーシング」？）から成長させていった解説らしい（ええ，どうせ私らはサルですよ．しかし，ただのサルではない．「この解説を読んでも理解できないサル」なのだ）．この参考文献は，少し，諸概念の意義に関するお話も多いように思う．完備ブール代数を使っている．

  4. Forcing/強制法 に関する英語・日本語の Wikipedia
    (forcing 強制法 wikipedia で検索すると出てくる)

    2018年 2月27日時点で日本語の wikipedia ページは出だしの「直観的意味合い」のところの

    が、このような議論は表面上不可能である。
    など，日本語が変（？）と思うような部分も あるが，ほかの入門書と合わせて読むと結構エッセンスだけが良くまとまっている．さらに 英語と日本語の ページも全く同じではなく，これも微妙に良く補い合っている．

  5. 日本語で利用可能なドキュメントとしては次の２つのもの(PDF)を見つけた．

    1. 鏡弘道 : 強制法入門, 2006年12月11日, pp1-16

    2. 渕野昌 : Forcing 入門, 2015年10月17日版, pp1-35

- 基礎的な集合論の教科書

集合論は数学あるいは計算機科学を学習するには，とても基本的と思います．基本的な概念や定理は抑えておく必要があります．そこで，ここでは集合論の基礎を学ぶのに良いと思われる教科書を列挙しておこうと 思います．具体的には，私が 読んでみてよいと感じた教科書や別の参考書に良いとして挙げられている教科書を列挙していこうと思います（なぜこのようなことをするか不思議に思われるかもしれませんが，私は，理論的な計算機科学を研究するための基礎学力をつける方法に興味があるので，どのような教科書があるかという知識も整理していきたいのです．
  1. つぎの２つの本は最近読んだ本です（2018年1月18日記載）．素朴な集合論の基礎を 習得するためには読みやすい本かなと思います．

    ●寺澤順 : 現代集合論の探検, 2013
    基数を集合の集まり（クラス）を bijection で類別したものと考えると， 集合論より先に，クラスの理論が必要になってしまう．そこで順序数から 入り，集合論の枠内で基数の定義までやるという方針で書かれた本のようです．

    ●福田 拓生 : 集合への入門―無限をかいま見る, 2012
    こちらは集合の基本的なことがらと基数（濃度）の理論までで，順序数は 章としてはありません．その代わり，無限集合についてのいろいろな不思議な ことについて紹介されています．今，目次を見直してみると， バナッハ-タルスキーのパラドックスについても証明まで 記載されているようです．バナッハ-タルスキーのパラドックスとは， ３次元空間の中の球体をいくつかの点集合に分割して，回転と平行移動だけで 元の球体と同じ大きさの球体を２つ作ることができるというやつですね．選択公理を 仮定するとそういうことが証明できると．

  2. 集合論のレクチャーノートの類 (Updated 6th May 2018)

    大学で先生方が作成されたレクチャーノートの類で公開されているものも 沢山あります（もしかしたら，もっぱら，自分の大学の学生向けかもしれませんが， とにかく外に見えているもの）．その中で私がぱらっとみて何となく良さそうだなと 思ったものを挙げておきます．興味があれば，例によってタイトル，著者，PDF というキーワードで 探してください．

    ●Frank Stephan : Set Theory, 2009-2010, pp. 0-94
    一応，書き方は一階述語論理を仮定しているわけでなく，自然語っぽい書き方ですが， 集合論の公理（ZFC）をきちんと押さえた形で書いてあるように思います．また， 後ろの方に連続体仮説のことが載っています．連続体仮説の否定のモデルがあるという フォーシングの話ではなく，実数の集合の部分集合をある種のものに限定すれば 有限，可算無限，連続体濃度のどれかになるということを示すみたいです．

    一応，通して読んでみました．およそ集合のイメージが分かっている初心者が 大学での少し公理的な集合論に入っていくときに良いテキストだと思います． 2018年8月28日（火）

    ●P.D. Welch : Axtiomatic Set Theory, 2017, pp. 1-76
    こちらは「公理的集合論」とタイトルから打ってありますね．一階述語論理を 使った記述になります．上のものより密度が濃いです．内容は，

    1. Axioms and Formal Systems
    2. Initial segments of the Universe
    3. Formalising semantics within ZF
    4. The Constructible Hierarchy
    5. Appendix A Logical Matters
    です．短いノートですが，集合論に関与した人の写真が沢山でてきます． 「あれ？， Mostowski さんって，結構，イケメンね」とか楽しめます．こちらは 連続体仮説が成立するモデルの作り方は出てくるみたいです．

    ●William A. R. Weiss : Introduction to SET THEORY, 2008, pp. 1-119
    最初に一階述語論理を導入して，公理的な立場から集合論を述べています．ただし， ただ，地の文では結構，背景や動機が書いてあります．この本が通常の ZFC の 解説でない部分は，最後の４章に，The Universe, Reflection, Elementary Submodels, Constructibity があることだと思います．また，列挙されているだけですが，Appendix の ２つめは，ZFC の公理系に追加可能な公理のリストがあります．

    ●An Open Logic Text (Remixed by Richard Zach): Sets, Logic, Computation, 2016 FALL, pp. 1-253
    こちらは集合論だけの本ではなく，集合論，ロジック，計算理論の本です． 集合論は１ページ目から５０ページまでです．集合論，ロジック，計算理論が 一緒になっているのでお得かなと思い，挙げてみました．上に挙げた P.D. Welch の本は色々な研究者の写真が載っていたのですが，こちらは，Cantor, Turing, Gödel, Noether, Skolem の似顔絵が載っています．また，付録には，Cantor, Church, Gentzen, Gödel, Noether, Russel, Tarski, Turing,Zermelo の 写真が載っています．集合論についてはごくごく初歩的な 部分だけしか触れられていません．例えば，計算機科学専攻の学部生が最低限知っておくべきこと くらいでしょうか．テキストの最後に，Open Logic Text って，協調的に formal meta-logic と formal methods の 中級のオープンなテキストを作る活動という説明がありましたので，今後，拡張されるのかも しれません．楽しみです．

- 集合論についての素朴な(かなり，おまぬけな)疑問集

日頃，浮かんでは，泡沫（うたかた）のように消えていく集合論についての疑問を書くことにしました．

疑問の意味を明確にしたり，考察を加えたりはしますが，解答は書きません．なぜなら，間違って いるかもしれず怖いからです（卑怯者ですから）．何かの本に答えが書いてあるのを見つけたら嬉々として書き込むかもしれません．

  1. すべての集合の集まりを集合と考えると矛盾が起こり，それは通常クラスとして扱うが，次のものはどうだろう？

    1. すべてのモノイドの集まり

      「モノイド」が分からなければ，群とか半群に置き換えてもよいですが，どうでしょう？

      あとの疑問にも関係しますが，モノイド（あるいは群，半群）って，集合論的には何だろうという疑問がでてきますよね．素朴な集合論で考えると，「モノイド」というなんらかの概念なんでしょうね（うっ，概念ってなんだろう？ 次から次に疑問がわいてきますね．私の知り合いの KNDHさんなら，これだけでご飯３杯はいけそうな）．

      すべてが集合と考える立場だと，モノイドを集合としてうまく定義することになるのでしょうね．その場合は，すべての集合より少ないことになりますが，どれくらい少ないかですよね．集合と考えてよいほど少なくなるかどうか？

      一方，モノイドの集まりの方が集合の集まりより多そうな気もしますよね．一つの集合からモノイドが作れれば，モノイドの方が多く（≥）なりそうですものね．実際，集合 X からフリーモノイド Free(X) が作れますから（計算機屋さんには X* と言った方が分かりやすいかもしれません）．

    2. すべての singleton sets (要素が１個の集合）の集まり

      これは上の問題より，考えることは少ないでしょうけど，上の問題と似ていますよね．

  2. モノイドは集合の要素たりえるか？

    これは，「何を言っているんだ．おまえは！」という疑問のような気もします．

    素朴に考えれば，モノイドという対象ははっきりしているので，集合に入るか入らないか 明確な判定基準があれば，モノイドの（小さい）集合は考えることができますよね．

    でも， これは「集合とは何か？」，「モノイドとは何か？」に対してどんな立場をとるかによるんでしょうね．空集合から始めて次々に集合を作っていく立場では，集合の要素としてモノイドという概念はない訳ですから，モノイドを集合の要素たる何かで表してやればよいんでしょうね．

    どちらにしても，モノイドを集合の要素として考えないと数学がやれないので， どういう理由をつけて集合の要素として考えるかということだけですね．すでに，上でモノイドとは何かを考察してあるので，それに従って理由付けをするだけだと思います．

  3. varieties の集まりは集合か？
    (容器の数は少ないのだけれど，それぞれの容器には集合となり得ないほどの要素が 入っている場合)
    variety は普遍代数の用語ですが，大まかに，同じ型の代数で，同じ等式の集合を みたすものの集まりと思ってください．ここで同じ型というのは，同じ関数の集合 があるということです．例えば，二項演算・がある代数系では，結合律を満たす 半群と呼ばれる代数系がありますが，このような代数をすべて集めたものを 半群のvarietyと言います．同様に，二項演算だけがある代数では，可換な半群の 集まりも {x・(y・z) = (x・y)・z, x・y = y・x} という等式の集合を満たす代数の集まりですから，variety をなします．variety 自身は通常は集合に収まり切りません． 例えば，半群の variety は，集合 X に対して，自由半群 X+が存在しますから すべての集合の集まりから中への１対１対応があり，集合と考えることはできません． で，この項目は，variety の集まりはどうでしょうという疑問です．これも集合とは 何かという定義によるのかもしれません．集合の中身も集合でなければならないという 立場では，集合と考えることはできないでしょう．一方，個数の多さから考えると 集合の集まりよりははるかに少なそうです． 等式の集合に対して variety が１つ定まり，等式は「項１=項２」という形をしていると します．変数や関数記号が可算無限 (ℵ0) 個とすると項も，項を２つ組み合わせた等式も加算無限個あります．ということは，等式の集合は2ℵ0個だけありますから，全varietiesの集まりも，これで抑えられる個数しかない訳です．したがって集合の範囲内に 収まります．どう扱うのがよいのでしょうか？

    補足：自分で書いておいて，上の文章を読む気力がないのですが，「真のクラスが別のクラスの 要素になりえるか？」という問題にすると，これは集合論の体系によるということに なりそうです．クラスを持つ集合論として有名なものとして，von Neumann, Gödel, Bernays の集合論， Kelley-Morse の集合論がありますが，これらは，真のクラスはクラスの要素にはなり得ないようです． それに対して，Ackermann 集合論と呼ばれる体系は，真のクラスが別のクラスの要素にも なり得る体系です．無条件にではないでしょうが．ここらあたりは，このページにも 書いた

    Alternative Set Theories
    に関連しています．しかし，上に書いたどの集合論も真のクラスは別の集合の要素に なることは許してないようです．2019.06.22 (土）追記

  4. （これは簡単な圏論の知識が要るかもしれません）
    自由モノイドを作る関手 Free : Sets -> Mon と忘却関手 U : Mon -> Sets の合成 Star(X) := U(Free(X)) は，idempotent, つまり Star(Star(X)) = Star(X) である．これはおかしくないか？    （注）

    これを読んだとき，逆に，どこにおかしいと感じる余地があるかが分からないかもしれません． 次のようなことです．

    X = { a, b } とします．

    Free(X) = { w | w は a あるいは b を0個以上有限個並べた語 }
    で，かつ，連接の演算があるもの
    となりますから，
    U(Free(X)) = { w | w は a あるいは b を0個以上有限個並べた語 }
    で，かつ，連接の演算を考えないもの
    で，もう一回 Free をとった，Free(U(Free(X))) では，U(Free(X)) は連接の演算を持っていませんから，例えば， ab と abb を並べたものは，ababb とはならず，(ab)(abb)になるはずではないだろうかという疑問です．つまり，U(Free(X))の中では ab はaとbを並べたものと言う構造は失っており，abb も同様なので，ab も abb もそれぞれ一つの記号としてとらえるのが正しいのではないだろうかという疑問です．そうすると，Free(U(Free(X)) は可算無限個の記号の集合から作られた自由モノイドで，U(Free(U(Free(X)))) はその台ですから，
    Star(Star(X)) = U(Free(U(Free(X)))) = U(Free(X)) = Star(X)
    と考えるのは虫が良すぎるのではないかということになります．

    要は集合 U(Free(X)) の要素は一体何だろうということに答えを出せば良いのですよね．くっつけると自然に中の括弧が消えるモナド的ななにか？

    （注）Star(X) は計算機屋さんには，記号の集合 X に対してクリーネ閉包 X* と言った方が分かりやすいですね．

  5. (Continue)

（ちょっと個人の覚書のような内容で申し訳ありません．次第に整理していきます． 圏論の方はここより整理ができていますので，ご興味のある方は

圏論 (Category Theory) のお勉強
もご参照ください． ）

●位相空間の基礎

計算機科学でも位相 (Topology) の考えは結構有用です．例えば，無限に動き続ける プロセスの挙動をとらえるには，近傍とか収束という概念が必要になってきますし， 形式言語の理論において言語間の近さ・遠さを考えるときは，言語の集合を距離空間と考えていることになります． しかし，残念ながら，計算機科学の中では，位相の扱いはまだそれほど盛んという わけではないように思います．実は，私も苦手ですが，やはりごく初歩的なところは抑えて おかねばと思い，勉強しはじめました．

ここでは，私自身が勉強しながら感じた，位相のごく基礎の部分の勉強に役立つ情報を 書くようにします．とりあえず，「集合と位相」とかいうようなタイトルの授業で 取り上げられそうなごく初歩の部分だけです（たぶん，大学の数学科の１年生か ２年生で習うような部分までです）．勉強が進んだら，また，書く内容も 増えるかもしれませんが．

  1. 教科書
    1. Tom Leinster : General Topology, 2014-15

      エディンバラ大学のレクチャーノートです．彼のホームページ

      Tom Leinster
      で general topology という文字列で検索してみてください．PDF が見つかります． 現時点 (2018.01.13) で 85ページの薄いテキストです．位相空間 (Topological space), コンパクト性 (Compactness), 連結性 (Connectedness) だけの内容です．定義の 裏の意図などについて親切に触れられていて，私は分かりやすかったです．

  2. 計算機科学での利用

    計算機への位相の利用でいくつか調べ，読もうと思っている参考文献をいくつか 挙げておきます． 所謂，積読です．リンクは張りませんが，PDF でダウンロードできるものばかりです． 興味があれば，タイトルと著者で検索してみてください．

    1. Mai Gehrke, Serge Grigorieff, and Jean-Éric Pin : A Topological Approach to Recognition, 2010, pp.151 - 162
      言語の集合をブール代数と考えて，トポロジーを使った形式言語の認識 (recognition) の新しいアプローチだそうです．

    2. JÉ Pin, Pedro V.Silva : A topological approach to transductions, 2005, pp 443-456
      ２つのモノイド M と N の間のトランスダクション τ で，L ⊆ N が認識可能 (recognizable) ならτ-1(L) ⊆ M も認識可能なものの位相的な特徴づけについて調べます．First author の Jean-Éric Pin は一つ上の論文の著者の中にも入っています． 形式言語の研究者としてはわりかし有名な方です．

    3. Cristian S. Calude, Helmut Jürgensen. Ludwig Staiger : Topology on Words, 2009, pp 2323-2335
      A∞ = A * ∪ Aω (つまり，アルファベット A の有限列と無限列すべての集合) に prefix relation で 位相を入れた空間の性質について調べます．次の図のような内容だと思います．

    4. N. Pippenger : Regular languages and stone duality, 1997, pp 121–134
      正規言語がなすブール代数とある種の位相空間の双対性に基づいて，正規言語と有限半群の バラエティ (varieties) の関係を調べます．読むには位相空間の知識だけではなく 形式言語の知識も必要です．束論の知識，とくに，ブール代数の知識があるとなお良いです．

    5. Emanuela Merelli, Mario Rasetti : Non locality, topology, formal languages: new global tools to handle large data sets, 2013, PP. 90-99
      データの巨大な集合をそれらが織りなす geometric な特徴を使って分析しようというもののようです．

    6. ...
      あと，プログラミング言語の表示的意味論の基礎となる Scott 位相とかも，位相の計算機応用ですよね．

●論理学の基礎

  1. Hilbert の体系の例

    Wikipedia 英語版の "Hilbert system"(2018年1月17日時点) から Hilbert 流の一階述語論理の体系のエッセンスを A4 一枚程度にまとめておく．一目で眺められるようにまとめておくことには意味があるのではないかと思う．

    一応，図を説明しておく．

    まず，変数や関数記号(定数は arity=0 の関数記号とする)から Term を作り， それと述語記号あるいは等号（=）からアトミックな論理式(Atomic Formulas)を 作る．そして，それらのアトミックな論理式をもとに，論理記号 →, ￢, ∀ で つなげて，一般の論理式を作る．

    公理は真ん中の四角に書いたものである．命題論理の公理スキームがP1 ～ P4 の４つ． 全称記号を扱うための公理スキームが Q5 ～ Q7 の３つ．等号を扱うための公理スキームが I8, I9 の２つ．ここで公理と言わずに公理スキームといっているのは，それぞれが１つの論理式ではなく，例えば，P1 では，αに任意の論理式を入れたときの論理式α→αが公理であると 言っている訳で，無数の公理を書いているからである．公理としては，これらの公理スキームのほかに，さらに，これらから作られた公理に対して，全称記号を かぶせたものも公理とする．これは，次の推論規則（inference rule）を モーダスポーネンス１つだけにするためのようだ．

    そして，上で書いたように推論規則はモーダスポーネンス１個だけ．数理論理学の 本には，述語論理は，もうひとつ，一般化（Generalization rule）が設けてあることが 多いと思う．ここでは，それを公理の方に持って行って，推論規則を１つだけに したみたいだ．

    簡単な一階述語論理の体系を１ページにまとめておきたくて，この絵を作ったが， 若干，上に書いた全称記号をかぶせたものの公理の扱いが自信がない．もし，誤解が あったら申し訳ない．というくらいの確度のものとして，この絵をみていていただきたい．

    補足：日本語版 Wikipedia の「一階述語論理」の項 （2018年 1 月 19 日時点) には，推論規則として

    1. モーダス・ポーネンス (MP)
      α とα→βからβを導出

    2. 全称化 (GEN)
      αから∀x α を導出
    の２つの推論規則を設けた体系が記載されていた．私は，こちらの体系のように，この２番目の推論規則を 明示的に上げてもらった方が何となく安心する．

  2. レーベンハイム・スコーレムの定理 (Löwenheim-Skolem Theorem)

    とある勉強会で，連続体仮説の否定の無矛盾性の解説をするために レーベンハイム・スコーレムの定理を分かった気にさせる解説を執筆完（2018.09.29）．

    レーベンハイム・スコーレムの定理 (初出 1915年 ) は，一階述語論理のモデルの大きさに関する命題である．大雑把に言えば， その一階述語論理に用意された記号の集合が可算無限個のとき，その論理体系の中の 公理系がモデルを持てば，そのモデルの要素数（基数）を可算無限個まで絞ることも， 非可算無限個まで水増しすることもできるという内容である．

    これは，全体が可算個の集合からなる集合論のモデルを保証したり，自然数の集合のサイズが 非可算個でも矛盾がないことを意味し，一見，それまで築かれた数学的常識と 反するので，発見当初は，レーベンハイム・スコーレムのパラドクスとして 扱われた．その後，この定理の解釈が整理されるとともに，今は，特にパラドクスでは ないという認識になっていると思う．

    私は，今，勉強会のためにこの解説を作りながら，この定理は 無限集合に関する我々自身の思考に関わるもので，とても 含蓄のある定理だと感じている．

    某勉強会での連続体仮説の解説についての顛末

    上で書いた連続体仮説の解説を発表した勉強会は 2018 年 10 月 17 日に終わり， そこのホームページに PDF で発表資料を置いてもらった．タイトル

    「連続体仮説の解説 AGAIN」
    と 「PDF」というキーワードでぐぐれば出てくると思う．
    2020年3月27日追記：結局，その資料はこのサイトにも置くことにした．
    「連続体仮説の解説 AGAIN」の資料
    その勉強会で配布したときの表紙も載せておく．

    名前のところだけはローマ字にした．この後，ほとんど同じ内容を別の 勉強会で発表した．そのときは表紙は若干変えて

    になった．この2枚目の表紙の方が連続体仮説の否定の無矛盾性の内容を より正確に表している．最初の表紙は，最初の表紙では，最初の否可算無限の 基数ω1 を ωと |2ω| の間に入れるといっているだけだが， 二番目の表紙では，それをどうやってやるのかを表現している．つまり，集合 2ω の中にωn を押し込む（ωn から 2ω の中への 1:1 対応を作る）ことにより，

    ω=ω0 < ω1 < ... < ωn ≤ 2ω
    の状態を作るのである．

    発表の後見つかったいくつかの間違いを修正したが，まだいろいろある可能性もあるので あくまで参考に，全体的な流れをつかむために使い，詳細は自分で勉強して欲しい．

    2019.04.25(Thu.) 追記

  3. ゲーデルの不完全性定理について

    「メモのような日記のような」のコーナーに，ごくごく簡単な ゲーデルの不完全性定理の説明 を書きました．下の図のような説明です．「AI とは何か？」という議論においての簡単な説明なのですが， およその証明の概要は分かるのではないかと思います．ゲーデル数とか，どうやってゲーデル文を 定義するかの細かなところは書いていません．それらはしかるべき書籍にあたっていただくことにして， とりあえず全貌が分かるのが取り付く第一歩かと思います． あちらは，日記ですから， 日々考えたことや起こったことなどの余計なことがたくさん書いてありますので， その一部分だけへのリンクです．

    尚，上のリンクをピックして，ちょうどゲーデルの不完全性定理のところに 行かないときは，もう一度リンクをピックしてみてください．ページの 途中にリンクするときは，そのページが大きいと読み込みが終わるまで きちんとそのリンクの個所に位置付けられないことがあるようです．

    また，一階述語論理の形式的体系やモデル，完全性定理に関しては， 上のレーベンハイム・スコーレムの定理のページの見ると，関連事項が 書いてあります．ご参考までに．

    2019.12.28 (土）

  4. 数理論理学の基礎を勉強するための参考になりそうな文献

    1. Peter Smith : Gödel Without (Too Many) Tears, second edition : revised draft, 2014, pp. 1-104
      数理論理学でゲーデルの不完全性定理に焦点を当てた解説書です．この著者は このテキストの前に，
      Peter Smith : An Introduction to Gödel's Theorems (Cambridge Introductions to Philosophy) 2007, 2nd Edition 2013, 402 pages
      を出しているのだが，そちらは量が多くなりすぎたので，もう少しコンパクトなものを書いたとの こと．こちらの Gödel Without (Too Many) Tears は彼のホームページから PDF でダウンロード可能です．このテキストは述語論理などの定義は省略されて，最初から不完全性の議論に入っていますので，ほかで基礎知識は学んでおく必要があります．

    2. Lou van den Dries : Mathematical Logic(Math 570) Lecture Notes, 2016, pp. 1-114
      数理論理学のレクチャーノートです．本来はその大学の学生さん用でしょうけど，2018年 1 月 14日時点で PDF として一般に見えてます．明確に Creative Common とかの公開用の著作権がふってある訳ではありませんが，情報提供として書いておきます．内容は，述語論理，完全性定理， モデル理論，計算理論，決定可能性と不完全性定理です．

      ほかにもレクチャーノートを公開されている先生方は沢山いらっしゃると思います． 私はこのような教材を見つけて勉強させていただいている訳で，これらの方々に感謝します． 私にはこれらのレクチャーノートの中でどれが良いのか判断はつきません．学習の目的にもよるでしょうし．皆さんも探して見ると，自分の用途にあったレクチャーノートが見つかると思います．

    3. Siegfried Gottwald : Many-Valued Logics, 2005, pp. 1-56
      多値論理についての解説．

    4. Samson Abramsky : Logic and Categories As Tools For Building Theories, 2012, pp. 1-17
      圏論を知っている人向けかと思います．

      一応，前半部分が圏論の入門で後半は，圏論をロジックに使うと どんな良いことがあるかが書いてあるみたい．圏論が何の役に立つのかについて悩んでいる人のヒントになるかも．私も悩んでいるので，そのうち読もうと思う（これは圏論の説明のページに 書くべきだったかも）．
Back to Top Page