集合と論理

対象の集合を領域 D とする。領域 D のべき集合を 2^D とする。2^D の要素は D の可能な部分集合の全てを含んでいる。

述語 P(x) は 領域 D から2値集合 V = {True, False} への写像である。領域 D の任意の要素を a とすると、P(a) は必ず True, または False の値をとる。すなわち、命題 P(a) は必ず真または偽の値をとる。P(x) が真となるような D の要素を集めるとそれは D の部分集合になる。これを P(x) の真理集合と言う。一方 P(x) が偽の値をとるような D の要素 x も集合になる。これは P(x) の真理集合の補集合になる。述語 P(x) に対し領域 D の部分集合は、真理集合とその補集合に二分できる。つまり、真理集合と述語の真偽の間には同値関係が存在し、述語によって無制限の内包的定義で集合を定義できる。

命題 P(x) と領域 D のべき集合 2^D の関係を考えると、P(x)が真であるという条件は 2^D の要素と対応するが、P(x) の真理集合と Q(x) の真理集合が一致する場合、述語 P(x) と Q(x) は同等である。つまり、述語としての表現が変わっていても、真理集合が同じ場合、領域 D については P(x) と Q(x) は論理的に同値である。

べき集合 2^D の要素間の集合演算はべき集合 2 ^ D について閉じている。集合演算と論理演算の同値性を考えると、領域 D における述語 P(x) の全ての論理演算については演算可能である。集合の内包的定義に制限はなく、論理演算は全て真理集合と対応している。

このモデルでは、集合は全て内包的定義で定義され、領域 D におけるすべての論理演算は、べき集合 2^D の集合演算と置き換えることができる。これが本来の論理と集合の関係だったのではないだろうか。論理的推論はこのような領域 D の集合について用いられるときは矛盾を生じないのだ。

領域 D とラッセルのパラドックス

さて、それでは矛盾がないはずの内包公理が、どうしてラッセルのパラドックスを発生してしまうのかを考えてみる。そこで、まず、上に述べた領域 D に帰属関係を定める。領域 D の全ての要素について、2項関係 ∈ を定める。a が b に属しているとき a ∈ b は真値をとりそうでないとき偽値をとる。属しているという言葉は無定義用語だ、とくに要素と集合の帰属関係でなくてもいい。ただし、b を固定し x ∈ b が真となる要素 x を集めたときそれは一つの D の部分集合になる。これはまた 2^D の要素でもある。また、この集合は P(x) = x ∈ b という述語に対する真理集合でもある。

この2項関係は a ∈ a のような自己言及も禁止していないとする。そうすると領域 D の全ての要素について x ∈ x であるか x /∈ x であるかの二つのグループに分けることができる。これらは Q(x) = x ∈ x という述語の真理集合と、その真理集合の補集合だ。これらは確かに領域 D の部分集合である。すなわち、2^D の要素でもある。

ところで要素 b を固定したときに x ∈ b を満たす要素を集めるとそれは領域 D の部分集合だ。したがって、要素 b はその真理集合を代表しているという見方もできる。すなわち b は内包的定義が {x | x ∈ b} である集合と同一視してもいい。領域 D については全ての内包的定義による集合が 2^D の要素であるから。b の表す集合は存在する。

それでは内包的定義が {x | x /∈ x} であるような集合は存在するだろうか。それは上の議論から明らかに領域 D の部分集合として存在する。なぜなら領域 D の全ての二つの要素の間には二項関係が定義可能だからだ。領域 D の要素は確かに自分自身の間に帰属関係があるものと、自分自身の間には帰属関係がないものが存在する。これらはまた、べき集合 2^D の要素でもある。このことは R(x) = x /∈ x という述語が領域 D の部分集合を定めることを意味する。領域 D において「自分自身を要素として含まない要素の集合」はあきらかに存在する。

ところが内包的定義が {x | x/∈ x} となるような集合と同一視できる領域 D の要素は存在しない。なぜなら、そのような領域 D の要素を仮定するとラッセルのパラドックスが発生してしまうからだ。このことは内包的定義 {x | x /∈ x} を満たす領域 D の集合は存在するにも関わらず、そのような集合と同一視できる領域 D の要素は存在しないことを示している。これがラッセルのパラドックスの正体だ。

上にも述べたように領域 D において、そのすべての部分集合は述語で定めることができる。しかし、領域 D に帰属関係 ∈ を導入することによって発生する集合を代表する要素を、集合と同一視した場合はそうではない。そのような要素に対する集合を定めることができない述語も存在してしまう。そうすると、無制限な内包的定義では集合を定めることができないのではないかという議論が出てくる。しかし、そうではない。無制限な内包公理で領域 D の集合を定めることができる。無制限な内包的定義が適用できないのは、領域 D の集合を帰属関係で定義しようとした場合の集合と同一視できる領域 D の要素を考えた場合なのだ。

こういう風に考えると「集合とは物の集まりである」という素朴集合論の定義には罪がないことが分かる。それは、領域 D の要素間の帰属関係が全ての集合を定めることができると考えたことによる矛盾なのだ。つまり、領域 D の要素を集合と同一視しようとしたところに齟齬が発生したのである。

領域 D が有限集合の場合、明らかに領域 D の要素数だけで領域 D のべき集合 2^D の全要素を代表させることはできない。また、領域 D が無限集合であったとしても、領域 D の2項関係を考えたとき不動点が発生するためにラッセルのパラドックスが発生してしまう。領域 D の部分集合についての議論を、領域 D の要素の帰属関係だけで完結させようとすることが間違っているのだ。

自分自身を要素とするかしないか

こういう風に考えていくと「集合が自分自身を要素とするかしないか」というのは、集合にとって本質的な性質ではないような気がする。集合が自分自身を要素とするかしないかという問いは、領域 D に所属関係という2項関係を導入しなければ発生しない問だからだ。「自分自身を要素として含まない集合の集合は自分自身を要素として含むか」という問いは、集合の一般的な性質ではなく、領域 D に所属関係を導入して領域 D の要素と集合を同一視したことによる副次的な性質についての問いではないだろうかと思う。

[PR]
# by tnomura9 | 2018-02-05 16:22 | ラッセルのパラドックス | Comments(0)

分出公理

ツェルメロ=フレンケルの公理系 (ZF: Zermelo-Fraenkel) についてイメージを作ってきたこのシリーズの記事も、外延性の公理、空集合の公理、対の公理、和集合の公理、冪集合公理、無限公理を調べてきて、分出公理をのこすのみになった。ウィキペディアには分出公理の代わりに置換公理を上げてあるが、分出公理のほうがイメージを作りやすいのでこちらのほうを調べてみる。

公理的集合論の抽象的な公理について考えてみてきたが、意外にイメージを作りやすかった。外延性の公理、空集合の公理、対の公理、和集合の公理、冪集合公理によって、空集合を出発点にして再帰的に無限に有限集合を作ることができる。また、無限公理によって、それらの要素を無限に含む無限集合が定義できる。しかし、集合という対象はこれらの公理で作り出すことができるが、それらに論理的演算を適用する方法は定義されていない。それを行うのが分出公理だ。

ところで、公理的集合論が考え出された一番の理由はラッセルのパラドックスだ。ナイーブな内包公理を素朴集合に適用するとラッセルのパラドックスが発生してしまう。問題は、上の公理で規定された集合がラッセルのパラドックスを除外できているかどうかだ。

上の公理で規定された集合のうち、有限集合は自分自身を要素として含むことはない。また、これらの集合で作られる自然数の集合の要素もすべて有限集合なので、無限集合である自然数の集合は自分自身を要素として含むことはない。したがって、「自分自身を要素として含まない集合の集合は自分自身を要素として含むか」というラッセルのパラドックスの問いは成立しない。

また、すべての集合の集合は、空集合から生成されるのは有限集合ばかりなので、すべての集合の集合という無限集合はそれには含まれない。したがって、空集合から生成される有限集合全てに自然数の集合という無限集合を合わせてもすべての集合の集合を公理系から生成することはできない。したがって、カントールのパラドックスもこれらの集合では発生しない。

あとは、制限された内包公理がそのようなラッセルのパラドックスのような困った集合を作り出さなければいい。制限された内包公理である分出公理は次のようになる。
分出公理 任意の集合 X と A を自由変数として使用しない論理式 ψ(x) に対して、X の要素 x で ψ(x) をみたすような x 全体の集合が存在する
これはざっくりというと、何か既知の集合を全体集合と考えて固定すると、その要素の集合を内包的定義で定めることができるということだ。すべての集合の集合とか、自分自身を要素として含まない集合のようなものは、もとになる全体集合を仮定していないので集合として定義できない。

内包公理と集合との同等性があれば、論理式をそのまま集合に置き換えて論議することも、逆に集合の議論を論理式に変換することも可能になるので便利だが、そうは上手くいかなかった。しかし全体集合を考えることで、その全体集合の中では論理式と集合の同等性を保証することができるということで実用的にはいろいろな数学的な議論に集合を利用することができる。

全体集合を考えるという制限を課すことで、公理的集合論に安全に論理を導入できることになった。

全体集合の重要性は、集合の演算を考えるときのベン図のことを考えればわかる。命題は真か偽かのどちらかの値をとる。それに対応する真理集合は真理集合とその補集合が必要になるが、全体集合がなければ補集合を定めることができない。二値論理を集合に適用するためにはどうしても全体集合が必要なのだ。

公理的集合論の世界は、このような、空集合から生成される無限の有限集合と自然数の集合という無限集合と、全体集合という制限の下での内包公理からなる、無矛盾な集合の世界のようだ。

公理的集合論についての記事はこれで終わるが、この記事を書こうと思った理由は、公理的集合論の公理が大半が再帰的定義だということに気が付いたことだ。再帰関数の定義は抽象的になりやすくイメージを作りにくい。

fact 1 = 1
fact n = n * fact (n-1)

また、再帰関数の値の計算は、次に示す階乗の計算のように関数値を再帰的に還元することによって求められる。

fact 3 = (3 * (fact 2)) = (3 * (2 * (fact 1))) = (3 * (2 * (1))) = 6

ところが、これは base case から出発して生成的に計算していくと途端に見通しが良くなる。

fact 1 = 1
fact 2 = 2 * (fact 1) = 2
fact 3 = 3 * (fact 2) = 3 * 2 = 6

したがって、公理的集合論の抽象的な定義も base case から生成的にその定義で作られる集合を調べていったら分かりやすいのではないかと考えたのだ。この目論見は上手くいったのではないかと思う。一連の記事によって公理的集合論の7つの抽象的な公理から具体的なイメージを作ることに成功したような気がする。

もちろん専門家ではないので基礎知識も少なく間違ったことを言っているのかもしれないが、少なくとも、再帰的定義を生成規則として捉えることで、抽象的な公理から具体的イメージを作り出すことが比較的容易にできるのではないかという問題提起にはなったのではないかと思う


[PR]
# by tnomura9 | 2018-02-03 21:14 | ラッセルのパラドックス | Comments(0)

無限公理

素朴集合論の公理のうち、空集合を定義する空集合の公理と、外延性公理、対の公理、和集合の公理、(有限集合に限定したときの)べき集合の公理からは、無限に集合を生成することができる。ただし、このようにして作られる集合はすべて有限集合だ。

これは、自然数は無限にあるが、個々の自然数は有限であることとよく似ている。base case から初めて生成規則で新しい要素を作成する再帰的方法では、無限に操作を続けることはできるが、生成される要素は全て有限集合だ。

しかし、このままでは公理的集合論には無限集合を含めることができないことになる。自然数のような無限集合は数学では普通にあらわれるので、無限集合が扱えない集合論は価値が低い。

そこでこの集合の世界に無限集合を導入するための公理が次に述べる無限公理だ。無限公理は次のようになる。
無限公理 空集合を要素として含み、かつ、任意の要素 x に対して x ∪ {x} を要素に持つ集合が存在する
一読してもどのような集合か全くイメージできない。しかし、任意の要素 x に対して x ∪ {x} を要素に持つという部分が再帰的定義になっている。このような場合は base case から出発して再帰的定義を要素の生成規則と考えて集合を作ってみると分かりやすい。

この定義で定められる集合を X とすると、X の要素は再帰的定義「任意の要素 x に対して x ∪ {x} を要素に持つ」によって生成されることが分かる。そのための出発点である base case は明らかに空集合 {} である。すなわち、

{} ∈ X

である。X の要素 {} に再帰的定義を適用すると {} と {{}} の和集合が X の要素として含まれる。{}の要素は何もないし、{{}} の要素は {} だから、再帰的定義で作られる新しい要素は {{}} である。すなわち、

{}, {{}} ∈ X

である。さらに、この新しい要素 {{}} に再帰的定義を適用すると、新しい要素は {{}} と {{{}}} の和集合なので、{{}, {{}}} になる。従って、

{}, {{}}, {{}, {{}}} ∈ X

さらに、この要素の中で最も新しい {{}, {{}}, {{}, {{}}} に再帰的定義を適用すると、新しい要素は {{}, {{}}} と {{{}, {{}}, {{}, {{}}}} の和集合なので {{}, {{}}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}} となる。すなわち、

{}, {{}}, {{},{{}}, {{}, {{}}}, {{}, {{}}, {{},{{}}} ∈ X

したがって、x ∪ {x} という再帰的定義で次々に successor を作っていくことができる。これは、公理的集合の世界に自然数を構築する時の方法と同じだ。このように再帰的定義で作られる要素は全て同じ集合 X に属すると定義するのが無限公理の目的だ。

無限公理以外の公理では、空集合から再帰的に集合を作り出し、その中に無限公理によって自然数の集合を再帰的に定義していることになる。ただし、空集合から再帰的に作り出された集合はすべて有限集合であり、無限公理による自然数の集合はそのどれにも含まれない。

無限集合は、他の公理によって定義される集合とは交点がない。ある意味集合ならざる集合を無限公理によって集合として容認しているとも言える。有限集合とは異なり、無限集合は一種のファンタジーではないかという気さえする。


[PR]
# by tnomura9 | 2018-02-03 19:37 | ラッセルのパラドックス | Comments(0)

冪集合公理

公理集合論では冪集合公理によって、任意の集合の冪集合が存在する。
冪集合公理 任意の集合 X に対して X の部分集合全体の集合が存在する
X が有限集合の場合、冪集合の公理は明らかだ。Xの部分集合をつくるアルゴリズムが存在するからだ。たとえば、集合 X = {a, b, c} のとき、その部分集合を a を含むものと a を含まないものに分ける。

{a, ... }
{b, ...}

さらに、それぞれのグループで b を含むものと、b を含まないものに分ける。

{a, b, ...}
{a, c, ...}
{b, ...}
{c, ...}

さらに c についても同様のグループ分けをする。

{a, b, c}
{a, b}
{a, c}
{a}
{b, c}
{b}
{c}
{}

こうして X の全部の要素について検討すれば全ての X の部分集合を拾い上げることができるので、Xの冪集合は次のように定められる。

P(X) = {{a, b, c}, {a, b}, {a, c}, {b, c}, {a}, {b}, {c}, {}}

この手続は次のようにプログラム化できる。

Prelude> :{
Prelude| let
Prelude| pow [] = [[]]
Prelude| pow (x:xs) = (map (x:) (pow xs)) ++ (pow xs)
Prelude| :}
Prelude> pow [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

これまで調べた、外延性の公理、空集合の公理、対の公理、和集合の公理、冪集合公理から構築できる公理的集合論の世界は、空集合 {} を base case にして {{}}, {{{}}}, {{}, {{{}}}}, などのように有限集合を無限に作り出していく集合の生成体系で、そのなかでは和集合の演算が導入されている。また、その中にはそれらの集合の冪集合も含まれる。

ただし、ここまでの公理で生成される集合はどれをとっても有限集合だ。集合論の目論見のひとつは無限集合を扱うことだから、この集合モデルに無限集合を取り込みたい。それを可能にするのが無限公理だが、これについては別に述べる。

また、この集合には自分自身を含む集合は存在しない。したがって、自分自身を含まない集合は自分自身を含むかという議論は成立しない。

この集合の世界には和集合の演算は存在するが、それ以外の共通部分などの演算は定義されていない。これは、この集合の世界に内包的な集合の定義を導入することによって、論理演算を集合に適用することが可能になる。これについても別に述べる。

この集合の世界の集合は全て空集合から誘導されたもので、通常の集合とは随分様子が違うが、{{}, {{}}} のようなものは要素を複数含む集合なので、通常の集合と共通な構造があるとも言える。この世界には自然数のような数学的対象は存在していないが、その中に自然数と同じような構造をこの世界の集合で構築することができるので、それを利用すれば自然数の構造を、この集合の世界に映し出すことができる。

結局、公理的集合論の目論見は、論理操作が可能で、矛盾もない集合の世界を構築し、その中に一般的な数学の構造を構築することなのだろう。


[PR]
# by tnomura9 | 2018-02-02 08:02 | ラッセルのパラドックス | Comments(0)

対の公理と和集合の公理

公理的集合論の対の公理は次のようになる。
対の公理 任意の要素 x, y に対して x と y のみを要素とする集合が存在する
この公理で定義される集合の要素はつねに2個だ。

したがって、要素を1つだけ含む集合の定義は、この公理と外延性の公理を組み合わせる必要がある。つまり要素 a に対して集合 {a, a} が定義できるが、外延性の公理を適用するとこれは {a} と等しい。外延性の公理は次のようになる。
外延性の公理 A のどの要素を取っても B の要素であり、その逆も真である場合 A と B は等しい。
また、要素が a, b, c とあるとき、e = {a, b}, f = {b, c} の存在は対の公理で定義できるし、これに加えて g = {e, f} も集合である。ここで g に和集合の公理を適用すると、g = {{a, b}, {b, c}} なので h = {a, b, c} は集合である。このように対の公理と和集合の公理を組み合わせると、任意の(有限個)の要素をもつ集合が定義できる。和集合の公理は次のようになる。
和集合の公理 任意の集合 X に対して、X の要素の要素全体からなる集合が存在する
この操作は Haskell の concat 関数と nub 関数で実行できる。

Prelude> import Data.List
Prelude Data.List> nub $ concat [[1,2], [2,3]]
[1,2,3]

和集合の公理はまた、任意の集合の和集合が存在することを保証する。g = {a, b, c}, h = {c, d} という2つの集合があるときに、対の公理から i = {g, h} という集合を作ることができる。これに和集合の公理を適用すると j = {a, b, c, d} ができる。これは明らかに g と h の和集合だ。すなわち、公理的集合ではどの2つの集合についても和集合が集合として存在する。

これも次のように Haskell で確認できる。

Prelude> import Data.List
Prelude Data.List> let a = [1,2,3]
Prelude Data.List> let b = [3,4]
Prelude Data.List> let c = [a, b]
Prelude Data.List> nub $ concat c
[1,2,3,4]

和集合の公理はその名前の通り、公理的集合論の任意の2つの集合の和集合が存在することを保証する。

公理的集合論の公理は抽象的に書いてあるが、実際にはプログラムで実現できるような具体性もある。抽象的だと思って敬遠していただけだった。再帰的な定義は視点を変えて新しいデータを作るための生成規則だと考えるとイメージしやすい。

[PR]
# by tnomura9 | 2018-02-01 16:48 | ラッセルのパラドックス | Comments(0)

外延性の公理

公理的集合論の外延性の公理は次のようになる。
外延性の公理 A と B が全く同じ要素を持つのなら A と B は等しい
要素が全く同じなら集合 A と集合 B は等しいのは当然のようだが、この公理を適用すると、{a, a, a} と {a, a} と {a} は同じ集合ということになる。{a,a,a} のどの要素を取ってもそれは {a} の要素だし、{a} の要素は全て {a, a, a} の要素だからだ。
つまり集合では重複した要素は取り除かれる。これは、ものの集まりを考えるときにやや特殊な考え方になる。

Haskell の Data.List モジュールには nub (要点) という関数がある。リストから重複する要素を取り除く関数だ。

Prelude> import Data.List
Prelude Data.List> nub [1,1,2,3,3,3,4,4]
[1,2,3,4]

Python の場合は集合型というデータ型があるので重複した要素の除去は自動的に行われる。

>>> {1,1,2,3,3,3,4,4}
{1, 2, 3, 4}

プログラムを組むときは、リストが重複した要素を持つのは、むしろこちらのほうが普通なので、外延性の公理はリストに制約をかけるものである。

しかし、空集合 {} から対の公理を使って {{}, {}} が作られるがこれは外延性の公理で {{}} と等しいものとされる。空集合のみを要素とする集合 {{}} は外延性の公理がなければ、対の公理だけでは作ることができない。

外延性の公理という制約が、対の公理と組み合わせることによって空集合のみを要素とする集合を作ることができる。対の公理だけではこのような集合を作ることはできないので、制約によって却って表現の拡充が行われることになる。

公理集合論の集合は、一般的に考えるものの集まりよりはかなり制約を受けたものの集まりになるようだ。

[PR]
# by tnomura9 | 2018-01-30 11:42 | ラッセルのパラドックス | Comments(0)

公理的集合論の世界

以前の記事『なぜ素朴集合論は矛盾するのか』で素朴集合論の世界を「帰属関係の定義された対象のネットワークの全体」として捉えると、なぜラッセルのパラドックスが起きてしまうのかを述べた。

「集合とはものの集まりというもの」であるという直観的な定義は上のようなネットワークとして捉えることができるように思われる。しかし、このネットワークでは、そのすべての対象の集合を考えたとき、その部分集合の全てをそれらの対象で代表させるということはできないという表現力の不足を招く。このため、集合(対象)としては表せない、ネットワークの対象の集まりであるクラスが発生してしまうのだ。

このようなクラスを発生させない集合だけを集めるために、公理的集合論の公理群が決められ、これこそが集合であり素朴的集合論の集合は欠陥があるとされている。しかし、公理的集合論の集合が一口にどんな集合なのかは、公理を眺めていてもはっきりしない。集合論を学ぶときに、この公理的集合論の指し示す集合が目に見えないのが大きな不満になる。

そこで、公理的集合論の公理群からどのような集合の世界が見えてくるかを考えてみた。矛盾のない真の集合とはどのような形をしているのかを見てみたいと思ったのだ。

Wikipedia から抜粋した公理的集合論である ツェルメロ=フレンケルの公理系 (ZF: Zermelo-Fraenkel) の公理は次のようになる。
外延性の公理 A と B が全く同じ要素を持つのなら A と B は等しい

空集合の公理 要素を持たない集合が存在する

対の公理 任意の要素 x, y に対して、x と y のみを要素とする集合が存在する

和集合の公理 任意の集合 X に対して、X の要素の要素全体からなる集合が存在する

無限公理 空集合を要素とし、任意の要素 x に対して x ∪ {x} を要素に持つ集合が存在する

冪集合公理 任意の集合 X に対して X の部分集合全体の集合が存在する

置換公理 "関数クラス"による集合の像は集合である

正則性公理(基礎の公理) 空でない集合は必ず自分自身と交わらない要素を持つ
どれも抽象的で具体的なイメージを作り辛いが、よく眺めていると、空集合の公理からべき集合の公理まではその定義が再帰的定義であることが分かる。再帰的定義はコンピュータのプログラムではよくあらわれる関数の定義の方法だ。例えば自然数の階乗を求める関数は次のように定義できる。

Prelude> :{
Prelude| let
Prelude| fact 0 = 1
Prelude| fact n = n * fact (n-1)
Prelude| :}
Prelude> fact 5
120

fact n を計算するのにそれ自身の関数 fact を使っている。巡回しているようだが fact 5 を展開してみるとその仕組みが分かる。

fact 5 = 5 * (fact 4) = 5 * 4 * (fact 3) = 5 * 4 * 3 * (fact 2) = 5 * 4 * 3 * 2 * (fact 1) = 5 * 4 * 3 * 2 * 1 * (fact 0) = 5 * 4 * 3 * 2 * 1 * 1 = 120

このように fact n を fact n = n * fact (n-1) という定義によって次々に展開していけば、最後には fact 0 = 1 という固定された値にたどり着くため、それを計算することによって階乗が計算できる。この fact 0 = 1 という定義を base case というが、これがなければ fact n = n * fact (n-1) という recursive case のみでは展開が無限に続くだけなので fact n の値を求めることはできない。

上の空集合の公理~べき集合の公理までが、このような再帰的定義であって、集合の世界を再帰的に定義している。例えば対の公理
対の公理 任意の要素 x, y に対して、x と y のみを要素とする集合が存在する
の場合は、集合の世界に属する対象 x, y をとり、この二つの既知の対象を要素とする集合 z を作る方法を定義している。これは、集合の世界の要素を、集合の世界の要素で定義するため再帰的な定義である。これは上でのべた再帰的定義の recursive case にあたる。

さきに述べたように再帰的定義では base case がなければ無限の再帰を引き起こしてしまうので、base case が必要になる。それでは上の公理群の中で base case といえるのはどの公理だろうか。

それは空集合の公理である。

上の公理のなかで、空集合の公理以外は集合を定義するのに recursive case として再帰的に定義している。すなわち、すでに集合として認められたものから新しい集合を生成するというやり方だ。再帰的定義は生成規則でもある。

ところが、空集合の公理
空集合の公理 要素を持たない集合が存在する
は base case だ。つまり集合を定義するのにほかの集合を必要としない。要素を持たない空集合はそれ自身で集合を定義することができる。言い換えると公理的集合論でア・プリオリに存在するのは空集合のみなのである。公理的集合論の他の集合は全て、この空集合に、ほかの再帰的定義を適用して生成された集合なのである。例えば空集合 {} に対の公理を適用して

{{},{}} = {{}}

という空集合を要素とする集合を作ることができる。つまり公理的集合論で定義される集合とは、空集合を出発点として他の生成規則である再帰的定義を適用して作られる集合の全体なのだ。これは、素朴集合論の定義から直感的にイメージする集合とは少し異なっている。しかし、このようにして作られた集合の集まりの中に、矛盾のない論理や数学が構築できるのだ。

つまり、公理的集合論の世界は一種のコンピュータのデータの世界と考えたほうがいいかもしれない。コンピュータのデータの世界は1と0の記号列からできている世界だが、シミュレーションプログラムを組むことで、森羅万象をその中に表現することができる。公理的集合論の集合もそのようなビットの世界の一種と考えることができる。

不可思議な公理的集合論の集合もこのようにとらえると視覚化できて抽象感が薄らぐのではないだろうか。

[PR]
# by tnomura9 | 2018-01-28 08:22 | ラッセルのパラドックス | Comments(0)

Python でシーザー暗号

以前に Haskell でシーザー暗号を作ってみたが、Python でもできるのではないかと思ってやってみた。

>>> chars = [chr(x) for x in range(97,97+26)]
>>> chars
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', '
'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
>>> rotate = lambda n,xs: xs[n:] + xs[:n]
>>> rotate(3, chars)
['d', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', '
't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c']
>>> code = rotate(3, chars)
>>> code
['d', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', '
't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c']
>>> encoder = dict(zip(chars, code))
>>> encoder['c']
'f'
>>> decoder = dict(zip(code, chars))
>>> decoder['f']
'c'
>>> encode = lambda xs: ''.join([encoder[x] for x in xs])
>>> encode('hello')
'khoor'
>>> decode = lambda xs: ''.join([decoder[x] for x in xs])
>>> decode('khoor')
'hello'

上の例はコンソール上で関数チェックをしながらの操作だが、プログラムだけを抜き出すと次のようになる。

>>> chars = [chr(x) for x in range(97,97+26)]
>>> rotate = lambda n,xs: xs[n:] + xs[:n]
>>> code = rotate(3, chars)
>>> encoder = dict(zip(chars, code))
>>> decoder = dict(zip(code, chars))
>>> encode = lambda xs: ''.join([encoder[x] for x in xs])
>>> decode = lambda xs: ''.join([decoder[x] for x in xs])

あまり Python らしくないプログラムかもしれないが、それでもきちんと動くプログラムだ。逆に言うと、リストの内包的定義や、λ記法や、関数オブジェクトを自然に仕様の中に取り込んでいることが分かる。

[PR]
# by tnomura9 | 2018-01-22 18:12 | Python | Comments(0)

Python datetime モジュール

Pythonの datetime モジュールを使ってみた。今日の日付と曜日を調べた。

>>> from datetime import date
>>> today = date.today()
>>> today.isoformat()
'2018-01-12'
>>> today.year
2018
>>> today.month
1
>>> today.day
12
>>> today.weekday()
4
>>> weekday = 'Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday'.split(',')
>>> weekday
['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']
>>> weekday[today.weekday()]
'Friday'

ついでに安室奈美恵の生まれた日の曜日を求めた。

>>> amuro = date(1977,9,20)
>>> weekday[amuro.weekday()]
'Tuesday'

Python 言語の基本的な使い方が分かったら、あとは標準や非標準のモジュールを調べて、問題解決に使う必要がある。しかし、そのためにはプログラミングで解決すべき問題がなければならない。さしあたって解決したい問題がないというのがアマチュアプログラマの弱点だ。

自分が何をやりたいのか。それを解決するためのプログラミング言語以外の知識を持ち合わせているか。そちらのほうを明確にするのが必要なのだ。

[PR]
# by tnomura9 | 2018-01-12 12:54 | Python | Comments(0)

Python で木構造を扱う

関数型言語でよく使われるデータ構造にはリスト型以外に木構造がある。Haskell の場合には木構造は代数的データ型で定義する。例えば次のようにノードには左右の木構造を収め、リーフに文字列を収めるデータ構造 Tree を定義する。

Prelude> data Tree = Node Tree Tree | Leaf String deriving Show
Prelude> let a = Node (Leaf "hello") (Node (Leaf "world") (Leaf "."))

この木構造のリーフの値を列挙する go_around 関数は次のように再帰的に定義できる。

Prelude> :{
Prelude| let
Prelude| go_around (Leaf str) = [str]
Prelude| go_around (Node left right) = go_around(left) ++ go_around(right)
Prelude| :}
Prelude> go_around a
["hello","world","."]

Python で木構造を定義するには、ノードとリーフのデータ型をクラスで定義する。Haskell で代数的データ型で定義したところを、Python ではクラスを定義することで木構造のデータ型を作ることになる。代数的データ型のデータがクラスのインスタンスに相当するわけだ。こう考えると、クラスの定義の、新しいデータ型を定義するという一面が明らかになる。あるいは、オブジェクト指向言語のクラスの性質の一部は Haskell の代数的データ型として捉えることができることが分かる。

class Node:
    def __init__(self,left,right):
        self.left = left
        self.right = right

class Leaf:
    def __init__(self,data):
        self.data = data
    def get(self):
        return self.data
def go_around(tree):
    if isinstance(tree, Leaf):
        return [tree.get()]
    else:
        return go_around(tree.left) + go_around(tree.right)

a = Node(Leaf('hello'), Node(Leaf(','), Leaf('world')))
print(go_around(a))

実行例

================== RESTART: C:/Users/****/Desktop/tree.py ==================
['hello', ',', 'world']

このように、Haskell の代数的データ型とPythonのクラス定義の意味合いが同じ事が分かる。どんなプログラム言語であれ、プログラムをデータ構造とアルゴリズムとして捉えるとそれらのプログラム言語の本質をとらえて活用できるような気がする。データ構造とアルゴリズムへのアプローチの仕方に言語の特徴がみられるだけだからだ。
Python という言語の使い方がなんとなくわかった気がするので Python 関係の記事はこれで終わりにする。AI との関連性についてはもう少し沈黙して勉強しないといけない。


[PR]
# by tnomura9 | 2018-01-08 15:49 | Python | Comments(0)