人気ブログランキング | 話題のタグを見る

冪集合と公理的集合論

前回の記事で、領域 D の冪集合 P(D) に次の定義で所属関係 ∈ を導入すると、P(D) はすべての集合演算について閉じたブール代数(束)になることを述べた。

x ∈ A ⇔ {x} ⊂ A

この冪集合だどの程度公理的集合論の公理を充足しているかに興味が出たので、


を参考に検討してみた。ZF公理系の基本的な公理には次の公理系がある。結構数が多い。

外延性の公理: A と B が全く同じ要素を持つのなら A と B は等しい。
空集合の公理: 要素を持たない集合がただ一つ存在する。これを空集合と呼ぶ。
対の公理: 任意の要素 x, y に対して、x と y のみを要素とする集合が存在する。
和集合の公理: 任意の集合 X に対して、X の要素の要素全体からなる集合が存在する。これを X の和集合と呼ぶ。
無限公理: 空集合を要素とし、任意の要素 x に対して x ∪ {x} を要素に持つ集合が存在する。
冪集合公理: 任意の集合 X に対して X の部分集合全体の集合が存在する。これを X の冪集合と呼ぶ。
置換公理 "関数クラス"による集合の像は集合である。変数への代入ができる。
正則性公理(基礎の公理) 空でない集合は必ず自分自身と交わらない要素を持つ。

これらのうち、外延性の公理、空集合の公理、和集合の公理、冪集合の公理、置換公理などは、冪集合 P(D) でも充足されているようだ。

対の公理も要素 x, y から集合 {x, y} を生成するので冪集合でも適用されるように見えるが、よく読むと、要素 x, y から新しい要素 {x, y} を生成する生成的定義だった。この定義では、x と {x, y} から新しい要素 {x, {x, y}} を生成することができるから、集合についての生成的定義がない冪集合には適用できない。無限公理なども生成的な定義だ。

公理的集合の公理は新しい集合を生成するための生成的定義が含まれているところが、代数系としての冪集合とは異なっているようだ。

冪集合について、無制限に集合演算ができ、ラッセルのパラドックスも発生しない集合がみつかったと喜んでいたが、そうは問屋がおろさないようだ。

# by tnomura9 | 2024-03-24 10:37 | 命題論理 | Comments(0)

所属関係

集合の所属関係は、2つの対象の間の2項関係だ。すなわち、

a ∈ b

は、対象 a が対象 b に属していることを意味する。つまり、対象 a が集合 b の要素であることを意味している。

この2項関係は順序関係ではない。なぜなら、反射率も、反対称律も、推移律も満たさないからだ。少なくとも、推移律は満たさない。

また、a ∈ a のような自己言及が可能であるかどうかが問題になるが、これを認めると、自分自身だけを要素とする集合 a = {a} を考えると、

a = {a} = {{a}} = {{{a}}} ....

のように a と等価な対象が無限に生成される。単に所属関係があるかどうかの2項関係であるが、再帰的に適用されることによって、対象のジェネレータになってしまう。

また、a ∈ b, b ∈ a のようなループになる定義でも、

b = {a} = {{b}} = {{{a}}} = {{{{b}}}} = ....

のように、所属関係の定義から無限の対象が生成される。所属関係の取り扱い方は、注意しないと、無数の対象を生成するジェネレータになりかねないのだ。

さらに、a ∈ b の場合は

a ∈ b, b ∈ c, c ∈ d, .... , j ∈ k, k ∈ a のような所属関係の複数の連鎖の中でループが発生する場合も想定され、それを見極めるのは難しい。

ところで、ラッセルの集合 R は次のように定義される。

x ∈ R ⇔ x /∈ x

この時 x に R を代入すると、

R ∈ R ⇔ R /∈ R

とパラドックスになってしまう。ラッセルのパラドックスが発生するのは、集合をものの集まりと定義した素朴集合論の定義が原因ではなくて、所属関係 ∈ という2項関係を無制限に使ったのが原因だ。

このように暴れん坊の ∈ であるが、どのようにしてトラブルを起こさないように制御できるのかは明らかではない。

ただし、全く望みがないわけでもない。それは冪集合に関係している。

領域 D の冪集合 P(D) の要素は D の部分集合であり、集合演算の和集合、積集合、差集合、補集合などの演算、包含関係などの関係について閉じている。これらの演算や、関係は冪集合のどのような要素に適用されても意味のある結果をもたらす。代数系のこの演算について閉じているという性質の重要性は言うまでもない。

しかし、冪集合の代数系には、要素と集合の所属関係についての演算は存在しない。冪集合の演算は変項がすべて冪集合の要素どうしの演算であるからだ。ところが、要素と集合の所属関係は、領域 D の要素と P(D) の要素との関係である。だが、このような場合でも、領域 D の要素 x と 冪集合 P(D) の要素であるシングルトン集合 {x} との全単射を考慮すると、所属関係の定義を次のようにすることができる。

x ∈ A ⇔ {x} ⊂ A

この場合 x ∈ A は冪集合の中で {x} ⊂ A として扱うことができるので、

a ∈ A かつ b ∈ A ならば {a, b} ⊂ A

のような論理式も、

{a} ⊂ A かつ {b} ⊂ A ならば (a, b} ⊂ A

のような冪集合上の論理式に同値なものとして扱うことができる。そうして、この論理式は真である。なぜなら、A は {a} と {b} の上界であるが、{a, b} はそのような上界の最小のものであるからだ。

このように、非常に制限された形だが、2項関係 ∈ を冪集合という代数系(Bool 束)の中でパラドックスを発生させずに使うことができる。

# by tnomura9 | 2024-03-23 03:17 | 命題論理 | Comments(0)

公理的集合論における普通の集合

公理的集合論の説明では、必ず順序集を集合で表現する方法が出てくるが、(Wikipedia の「ツェルメロ=フレンケル集合論」の記事)

最初のフォン・ノイマン順序数
0 = {} =∅
1 = {0} = {∅}
2 = {0, 1} = {∅, {∅}}
3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}
4 = {0, 1, 2, 3} = {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}}

なんか、きつねに抓まれたような気になる。公理的集合論ではものの集まりという直感的な集合は定義できないのではないかという気がしてくるのだ。

ところで、公理的集合論では、変数は一階述語論理の個体変項だが、意味論的には変数の全ては集合として扱うようである。したがって、任意の2つの要素 x, y からなる集合を定める対の公理は次のようになる。

x と y が集合である場合、xとyを元として含む集合が存在する。

ただし、上の公理は一階述語論理で記述されているので、x, y が集合であると指定されているわけではなく単に個体 x, y を意味していると考えたほうが良い気がする。すなわち、

任意の個体 x, y について x と y を元として含む集合が存在する。

と表現しても問題はない気がする。

この公理を使えば x = y のときは、シングルトン集合 {x} が存在することが言える。直感的な要素を表すこのようなシングルトン集合をたくさん集めると、和集合の公理でその和集合としての集合を定義することができる。

一般的な直感からは、要素 x は個体であって、要素のシングルトン集合 {x} は個体ではないということになるが、{x} そのものを個体と認めると、そのシングルトン集合は {{x}} となるので、個体とシングルトン集合の区別はちゃんとできる。

公理的集合論の公理は、全てが集合である異世界の原理のような気がしていたが、シングルトン集合をたくさん作ってやってこれを個体要素と考えれば、ちゃんと普通の集合も定義できるような気がする。

追記

厳密に言うと、対の公理で一階述語論理の個体変項である x を要素とするシングルトン集合を作り、{x}, {y}, {z}, ... をもとに、和集合の公理で {x, y, z, ... } を作るという手順になるのだろうが面倒くさい手続きであることには変わりない。

ただし、一旦集合が定義できれば、あとは普通にラッセルのパラドックスを発生しない集合として扱うことができる ... のかもしれない。

追記2

特定の理論の要素をすべてシングルトン集合でくるんでしまうと、シングルトン集合の集合演算で、「シングルトン集合すべての和集合の冪集合」の要素をすべて集合演算で生成できる。この冪集合はブール代数になる。すなわち、その理論の要素について集合演算や論理の適用が制限なく行われることが保証される。

また、a ∈ A のような要素の所属関係も、{a} ⊂ A のようなシングルトン集合と集合の包含関係に翻訳すれば、要素と集合の所属関係を含むすべての集合演算を、冪集合の上で行うことができる。ラッセルの述語では、このようなシングルトン集合 {R} を」定義できないから、この述語を含む理論体系には集合演算と論理演算が適用できないことが分かる。

論理と集合は同じ構造でブール代数(束)なのだ。これらを適用できる理論は、ブール代数にたいして準同型でなければならないことが分かる。

追記3

ラッセルの述語を実現するためには「自分自身を要素として含まない集合」や「自分自身を要素として含む集合」を記述できないといけない。それは、集合の定義を個体と集合の所属関係によって定義することで可能になる。

個体も集合も全て対象として抽象化し、対象間の所属関係のみを考える定義法だ。対象 a と 対象 b のあいだの所属関係 a ∈ b があるとき対象 a は対象(集合) b の要素である。集合 b の外延は、b に所属する対象全ての集まりとして自然に定義できる。

このような定義において「自分自身を要素として含まない集合とは、対象 a について a ∉ a となる場合を言う。また、自分自身を要素として含む集合とは a ∈ a となる対象 a のことを言う。

対象の集合 A = {a0, a1, a2, ... } について任意の2つの要素の所属関係を全て考えると、これは、A の要素をノードとし、所属関係をエッジとする有向グラフになる。これらの中では自分自身にエッジを張る「自分自身を要素として含む集合」であるノードと、自分自身にエッジを張らない「自分自身を要素として含まない集合」であるノードに分かれる。

ところで、ラッセルの述語は「自分自身を要素として含まない集合」すべてにエッジを張る集合(ノード)を定義する。

このノードを r とすると、r はグラフのノードのうち自分自身にエッジを張らないノード全てにエッジをはることになる。しかし、r は r 自身にエッジを張ることができるだろうか。この問題がパラドックスになるのはラッセルのパラドックスから明白だ。

すなわち「自分自身を要素として含まない集合の集合」という述語によって定義できる集合 r はグラフの内部のノードには存在できないのだ。ただし、グラフの外にあるノードからはこのようなノードは存在可能だ。

したがって、ラッセルの集合は対象の集合 A の中には存在しないため、そのシングルトン集合 {r} も存在できない。すなわち、シングルトン集合から定義できる集合の中にはラッセルの集合は存在できず、ラッセルの集合を含む理論は、Aの冪集合という集合や論理のフレームワークに乗せることができないことがわかる。

# by tnomura9 | 2024-03-17 04:27 | 命題論理 | Comments(0)

命題論理の Hasse 図

前回の記事では、冪集合の Hasse 図が機械的に作成できる可能性を示した。冪集合の Hasse 図の作り方を考えているうちに、命題論理式の Hasse 図も冪集合と同じ発想で作れる気がするので記事にしてみる。例として、原子命題が A と B だけの命題論理式の体系について考えてみる。

原子命題が A と B だけなので冪集合の台集合として {A, B} を考えそれらの join と meet からなる論理式について考えれば良いようであるが、A と B の meet は 0 ではない。それは A ∧ B という論理式になるからだ。

また、命題論理の論理式には否定演算という単項演算があり、A ∧ ~A = 0, A ∨ ~A = 1 という補元律を満たさなければならない。そこで工夫をして、基本となる論理式として A とその否定命題 ~A、B とその否定命題 ~B という4つの命題を考えることにする。

さらに A∧B, A∧~B, ~A∧B, ~A∧~B という論理式を考えてみる。このとき、

(A∧B)∧(A∧~B) = 0

なので A∧B と A∧~B の meet は 0 すなわち矛盾式だ。上の4つの論理式はすべて2つの論理式の meet が 0 になるので、論理式の冪集合は台集合、

{A∧B, A∧~B, ~A∧B, ~A∧~B}

について考えることにする。

議論の見通しをよくするために p = A∧B, q = A∧~B, r = ~A∧B, s = ~A∧~B とおくと、この台集合の冪集合について、前回の記事のように要素のレベルを考えると、次のようになる。

第0レベル:0(矛盾式)
第1レベル:p, q , r, s
第2レベル:p∨q, p∨r, p∨s, q∨r, q∨s, r∨s
第3レベル:p∨q∨r, p∨q∨s, p∨r∨s, q∨r∨s
第4レベル:p∨q∨r∨s = 1(恒真式)

ここで

p∨q = A
p∨r = B
p∨s = (A∧B)∨(~A∧~B)
q∨r = (A∧~B)∨(~A∧B)
q∨s = ~B
r∨s = ~A
p∨q∨r = (A∧B)∨(A∧~B)∨(~A∧B) = A∨(B∧~B)∨(~A∧B) = A∨(~A∧B) = (A∨~A)∧(A∨B) = A∨B
p∨q∨s = (A∧B)∨(A∧~B)∨(~A∧~B) = A∨~B
p∨r∨s = (A∧B)∨(~A∧B)∨(~A∧~B) = ~A∨B
q∨r∨s = (A∧~B)∨(~A∧B)∨(~A∧~B) = ~A∨~B

なので、整理された Hasse 図の要素は次のようになる。

第0レベル:0(矛盾式)
第1レベル:A∧B, A∧~B, ~A∧B, ~A∧~B
第2レベル:A, B, (A∧B)∨(~A∧~B), (A∧~B)∨(~A∧B), ~B, ~A
第3レベル:A∨B, A∨~B, ~A∨B, ~A∨~B
第4レベル:1(恒真式)

これで Hasse 図の各レベルでの要素が分かったのであとは0レベルから始まって、順序関係の線分でノードをつないでいくだけだ。パソコンで絵を描いてみようと思ったが意外に面倒で挫折した。

作図ソフトに慣れていないせいで、絵は描けなかったが、命題論理のHasse図の特徴を見てみよう。

先ず目につくのが、Hasse図のノードとして現れる論理式の数が16しかないということだ。命題論理の論理式の式はどれだけでも長いものを作ることができるが、論理演算の交換律、結合律、分配律、補元律から縮約できるものは同値な論理式なので、結局のところ原子命題が2個の場合は、同値類の数が(2*2)^2 = 16 個になってしまうからだ。2*2 になるのは命題論理の演算子の補元律を満たすためには、原子命題とその否定命題が必要だからだ。

次に Hasse 図を作成するときの基本の要素が、原子命題ではなくて要素命題の論理積の形になっているのは、その論理式の真理表が、1行だけが真になる真理表になるからだ。それを論理和で組み合わせることによって、すべての種類の真理表を作り出すことができる。ちなみに A∧B と A∧~B の真理表は次のようになる。

A B | A∧B
T T | T
T F | F
F T | F
F F | F

A B | A∧~B
T T | F
T F | T
F T | F
F F | F

つまり、有限個の原子命題からなる命題論理の論理式は、基本の論理式を組み合わせた有限個の同値類(の代表元)で記述できることがわかる。

ところで、命題論理で重要なのは、どのような論理式がトートロジーになるかということだが、それは、この Hasse 図で示すことができる。すなわち、P, Q という論理式に順序関係 P ≦ Q といいう順序関係があるとき、論理式 P -> Q はトートロジーとなる。なぜなら、このような場合 Q = P∨X の形をしているが、

P->Q = ~P∨Q = ~P ∨ P ∨ X = 1

となるからだ。Q = P∨X の形にならない場合は P->Q がトートロジーにはならない。有限個の原子命題からなる命題論理の論理式については、トートロジーであるかどうかは Hasse 図で証明できることが分かる。

トートロジーについては上記の P ≦ Q 以外にも P ∨ ~P の形の論理式もあるが、これは P -> P または ~P -> ~P という論理式と同値だ。P ≦ P の線分は Hasse 図では省略されるがこれも P -> Q 型のトートロジーである。

冪集合の Hasse 図では補元は明記していないが、補集合がその役割を果たしており、冪集合の任意の要素の補集合は、冪集合の要素の中に存在する。

このように、冪集合と論理式の集合のブール束(可補分配則)は異なる点もあるが、同様にブール束として記述することができることが分かる。冪集合のブール束が一番わかりやすいので、束論を学習するときは冪集合をモデルとして理解するのが便利だ。

論理のフレームワークで論じられる体系は、このようにブール束である必要があることが分かる。ブール束ではない理論は、部分的にしか論理を適用できない。論理は適用する相手を選ぶのだ。

# by tnomura9 | 2024-03-10 05:44 | 命題論理 | Comments(0)

Hasse 図を作る

集合 {x, y, z} の冪集合の要素は次のように8個ある。

{x, y, z}, {x, y}, {x, z}, {y, z}, {x}, {y}, {z}, {}

この冪集合は束であることが分かっているが、その Hasse 図をどうして作ることができるのだろうか。これは、束の任意の2つの要素の meet と join は必ず存在するという性質を考えると機械的に作れることが分かる。

あとの説明に便利なように p ⊂ q のとき p は q より小さい、または、q は p より大きいと表現することにする

まず、これらの要素の内で最も小さいものを見つける。それは空集合 {} である。すなわち {} より小さい要素は {} 以外にはないからだ。そこで 空集合 {} を第0レベルの要素と呼ぶことにする。

次に、それより小さい集合は空集合しかない要素を見つけ、それらを第1レベルの要素と呼ぶことにする。第1レベルの要素に含まれるのは、

{x}, {y}, {z}

の3つだ。これらの要素の間には包含関係⊂はないので、順序関係はない。また、これらの meet を考えるとそれらはすべて空集合 {} である。すなわち、

{x}∧{y} = {}, {x}∧{z} = {}, {y}∧{z} = {}

だ。

さらに、これらのうちの2要素についての join を考える。

たとえば、{x} ⊂ {x, y} かつ {y} ⊂ {x, y} であるから {x}∨{y} = {x, y} だ。同様に、{x}∨{z} = {x, z}、{y}∨{z} = {y, z} だ。これらの3つの要素を第2レベルの要素と呼ぶことにする。すなわち、つぎの3つの要素は第2レベルの要素だ。

{x, y}, {x, z}, {y, z}

これらも第 1 レベルの要素と同じようのお互いの間の順序関係はない。第2レベルの任意の2つの要素の meet は第1レベルの要素の一つになる。また、join は {x, y} ⊂ {x, y, z} かつ {x, z} ⊂ {x, y, z} から {x, y}∨{x, z} = {x,y,z} だ。他の組み合わせについてもすべてその join は

{x, y, z}

になる。これを第3レベルの要素と呼ぶことにする。

各レベルの要素を下から、第0レベル、第1レベル、第2レベル、第3レベルと並べていくと、隣のレベル間の要素は Hasse 図に線分としてあらわされる直接の順序関係があり、同じレベルの要素間には順序関係がない。したがって、0レベルから始まって隣のレベルの要素の間に考えられる順序関係をすべて線分として記入していくと、前回の記事の Hasse 図が出来上がる。

冪集合の束はそれだけではなく、join と meet の交換則が成り立っている。すなわち同レベルの2つの要素 a, b をとると、

a∧b = b∧a, a∨b = b∨a

である。さらに meet と join は結合律も満たす。たとえば、

({x}∨{y})∨{z} = {x,y}∨{z} = {x,y}∨{x, z} = {x, y, z}

となることが、Hasse 図の線分をたどっていくことで分かる。

これは,

{x}∨({y}∨{x}) = {x, y}∨{x,z} = {x, y, z}

でもあるので、結局、

({x}∨{y})∨{z} = {x}∨({y}∨{z})

となり、join についての結合律が存在することが分かる。同じように meet についての結合律の存在も分かる。

さらには、Hasse 図の線分をたどると、

(a∧b)∨c = (a∨b)∧(a∨c) または (a∨b)∧c = (a∧c)∨(b∧c)

のような分配則が成り立つことも分かる。

このように冪集合は分配法則の成り立つ分配束である。また、冪集合が束である性質を利用して、Hasse 図を機械的に作成できる。

# by tnomura9 | 2024-03-09 20:15 | 命題論理 | Comments(0)