公理的集合論の説明では、必ず順序集を集合で表現する方法が出てくるが、(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 は個体であって、要素のシングルトン集合 {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 図も冪集合と同じ発想で作れる気がするので記事にしてみる。例として、原子命題が 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)
集合 {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)
Hasse図は有限集合の要素の半順序関係を完全に記述できる。つまり、半順序集合の要素間の構造の視覚化が行えるとだ。半順序集合の性質はHasse図を使うことで視覚的に学習できる。 次のHasse図は、集合 {x, y, z} の冪集合の間の包含関係⊂を示している。矢印は、冪集合の要素のあいだの包含関係を表し、矢印の始点の集合は終点の集合の部分集合である。包含関係の推移律から、矢印を次々にたどっていった先と最初の矢印の始点の集合も最終的な終点の集合の部分集合である。このことから、半順序集合の推移律は視覚的にイメージできる。 上のHasse図の {x} と {y} を始点とする矢印は同じ {x, y} を終点としている。このような集合 {x, y} は {x} と {y} の上限 meet と呼ばれる。逆に {x, y} と {y, z} を終点とする矢印を逆にたどると、{y} に辿り着く。この場合 {y} は {x, y} と {y, z} の下限 join である。 これらの関係を記号 ∨ と ∧ で表すと、 {x} ∨ {y} = {x, y} {x, y} ∧ {y, z} = {y} である。これらの記号は論理記号の論理和と論理積、または、集合の和集合と積集合に似ているが、あくまでも半順序集合の性質から導き出されたものである。半順序には集合や論理式の演算の意味はないが、同じような性質がみられる。すなわち、集合と論理式はともに半順序集合の性質として記述できる。すなわち、両者には、共通の構造としての半順序集合があると考えられる。 このように半順序集合の性質は Hasse 図として視覚化されるが、これによって、半順序集合の一つである束についても視覚化できる。束の定義は次のようになる。 束(そく、英語: lattice)は、任意の二元集合が一意的な上限(最小上界、二元の結びとも呼ばれる)および下限(最大下界、二元の交わりとも呼ばれる)を持つ半順序集合である。 抽象的な定義だが、上の Hasse 図をよく観察すると、どのような2つの集合についても meet と join が存在することが分かる。束とはこのような構造の半順序集合なのだ。束の抽象的な定義も、視覚化された Hasse 図によって、その性質を理解することができる。 もちろん Hasse 図であらわされる半順序集合すべてが束になるわけではなく、束にならない構造がある。束は半順序集合ではあるが、そのうちの特別な構造であるということができる。命題論理の構造である Bool 束もやはりこのような束だ。
#
by tnomura9
| 2024-03-08 23:23
| 命題論理
|
Comments(0)
集合 P の要素に半順序関係 ≦ が定義されている集合と半順序関係の組 (P, ≦) は半順序集合 partially orderd set だ。半順序は次の3つの演算規則を満たしていなくてはならない。 反射律:x ≦ x 推移律:x ≦ y かつ y ≦ z のとき x ≦ z 反対称律:x ≦ y かつ y ≦ x ならば x = y 半順序集合の代表例は冪集合だ。集合 D の部分集合すべてからなる集合の集合は冪集合 P(D) であるが、その要素である D の部分集合の間には包含関係 ⊂ があり、これは明らかに半順序集合の演算規則を満たしている。すなわち (P(D), ⊂) は半順序集合である。 しかし、これだけでは冪集合の全体の構造は見えてこない。Hasse 図はこのような有限半順序集合の全体の構造を見えるようにしてくれるのだ。 Hasse 図の作り方は簡単だ。まず半順序集合の要素を点で表す。つぎにその要素間に半順序関係がある場合は要素を表す点と点を線分で連結する。しかし、その時に点と点が直前直後の関係にある時のみに線分で連結する。すなわち x と y の間に半順序集合があるとき x ≦ z ≦ y のような x と y の間に要素が存在しない、すなわち、x ≦ y でしかないときのみ線分で連結する。この操作を半順序集合全体に行ったときのグラフの全体が Hasse 図である。 このようにして作った Hasse 図には半順序集合の半順序関係が余すところなく表現されている。すなわち、半順序集合の任意の要素間に半順序があるかどうかは、点 x から点 y が線分で連結されるかどうかで判別することができる。すなわち、半順序集合のすべての要素間の半順序関係はすべて Hasse 図で判断できることが分かる。 Hasse 図は半順序集合の順序関係を見える化したものだ。集合 {a, b, c} の冪集合はたしかに ⊂ という集合の包含関係によって、半順序集合であるが、これだけでは全体像は見えてこない。しかし、つぎのような Hasse 図をつくると、冪集合の要素間の半順序関係を俯瞰的にとらえることができる。 このように、有限集合の半順序集合について Hasse 図はその完全な全体像を表示してくれる。 命題論理の論理式の間には含意という半順序集合がある。したがって、命題論理の論理式の集合の Hasse 図をつくれば、命題論理の論理式の間の関係の全体像を表示することができる。 命題論理の主な関心事は論理式のトートロジーだが、Hasse 図によって、トートロジーの全体像を見える化することができるのだ。
#
by tnomura9
| 2024-03-05 21:56
| 命題論理
|
Comments(0)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||