<   2017年 08月 ( 13 )   > この月の画像一覧

isSubsetOf

前回の記事では領域 D のべき集合について、包含関係にある要素のペアを抜き出すプログラムを紹介した。領域 D の二つの部分集合が包含関係にあるかどうかを判別するために Set.isSubsetOf 関数を使ったが、これは Data.Set の集合型にしか使えないため、リストで表現した集合を集合型に変換していた。

この isSubsetOf 関数がリスト型のデータに使えれば便利だと思っていたら、簡単にかけてしまった。isSubsetOf 関数が定義できれば、リストのままでプログラムが実行できる。実行例は次のようになる。プログラムの意味は前回の記事と同じなので省略する。

Prelude> let isSubsetOf a b = and $ map (\x -> elem x b) a
Prelude> isSubsetOf [2,3] [1,2,3]
True
Prelude> :{
Prelude| let
Prelude| power [] = [[]]
Prelude| power (x:xs) = (power xs) ++ (map (x:) (power xs))
Prelude| :}
Prelude> power [1,2,3]
[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
Prelude> let domain = [1,2,3]
Prelude> let subs = power domain
Prelude> let cartesian = [(x, y) | x <- subs, y <- subs]
Prelude> filter (\x -> isSubsetOf (fst x) (snd x)) cartesian
[([],[]),([],[3]),([],[2]),([],[2,3]),([],[1]),([],[1,3]),([],[1,2]),([],[1,2,3]),([3],[3]),([3],[2,3]),([3],[1,3]),([3],[1,2,3]),([2],[2]),([2],[2,3]),([2],[1,2]),([2],[1,2,3]),([2,3],[2,3]),([2,3],[1,2,3]),([1],[1]),([1],[1,3]),([1],[1,2]),([1],[1,2,3]),([1,3],[1,3]),([1,3],[1,2,3]),([1,2],[1,2]),([1,2],[1,2,3]),([1,2,3],[1,2,3])]

この手の問題の解決には Haskell は非常に強力だ。

[PR]
by tnomura9 | 2017-08-31 18:05 | ラッセルのパラドックス | Comments(0)

方程式としての全称命題

この記事では全称命題は命題というよりは一種の方程式ではないのかという議論をする。

最初に一階述語論理のモデルとしての領域 D を定義する。領域 D = {1, 2, 3} のとき述語 A(x) について A(a) が真となるような対象の集合は述語 A(x) の真理集合 A* だ。これは明らかに D の部分集合である。また、a ∈ D について、a ∈ A* は A(a) の真理値と一致する。したがって a ∈ A* は命題と同一視できる。すなわち領域 D = {1, 2, 3} と D の冪集合 {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} は一階述語論理のモデルである。

この領域 D モデルでは、対象 a と真理集合 A* の対は a ∈ A* という命題をつくる。また量化子を用いた全称命題 ∀x. P(x) も真偽値を持ち命題として扱われる。

しかし、ソクラテスが人間なら、ソクラテスは死ぬという推論は、全称命題∀x. (P(x) -> Q(x)) の命題としての性質よりも、量化子がつけられる 命題 P(x) -> Q(x) の性質を利用している。すなわち、∀x. (P(x) -> Q(x)) が真であれば、P(x) と Q(x) の真理集合 P* と Q* の間に P* ⊂ Q* という関係がある。

しかし、この関係式ですら P* と Q* を特定しているわけではない。この関係を充足するすべての領域 D の真理集合を表している。したがって、全称命題 ∀x. (P(x) -> Q(x)) は特定の命題と言うよりは、この関係式を充足する真理集合の集合をしめしている。この意味で全称命題は方程式と言える。

そこで領域 D において Ax. (P(x) -> Q(x)) が真となるような述語 P(x) と Q(x) の対、あるいは真理集合 P* と Q* の対にはどのような物があるかを Haskell で計算してみた。

領域 D は domain = [1,2,3] とリストにした。定義した power 関数で domain の冪集合 subs を計算する。:{ ... :} は複数行で定義する時のコマンドだ。subs_set はリスト形式の部分集合を集合に変換する。cartesian は subs_set の直積集合。最後の結果は Set.isSubsetOf 関数で包含関係のある部分集合のペアを選びだしたもの。

Prelude> import qualified Data.Set as Set
Prelude Set> let domain = [1,2,3]
Prelude Set> :{
Prelude Set| let
Prelude Set| power [] = [[]]
Prelude Set| power (x:xs) = (power xs) ++ (map (x:) (power xs))
Prelude Set| :}
Prelude Set> let subs = power domain
Prelude Set> subs
[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
Prelude Set> let subs_set = map Set.fromList subs
Prelude Set> subs_set
Prelude Set> let cartesian = sequence [subs_set, subs_set]
Prelude Set> filter (\x -> Set.isSubsetOf (x!!0) (x!!1)) cartesian
[[fromList [],fromList []],[fromList [],fromList [3]],[fromList [],fromList [2]],[fromList [],fromList [2,3]],[fromList [],fromList [1]],[fromList [],fromList [1,3]],[fromList [],fromList [1,2]],[fromList [],fromList [1,2,3]],[fromList [3],fromList [3]],[fromList [3],fromList [2,3]],[fromList [3],fromList [1,3]],[fromList [3],fromList [1,2,3]],[fromList [2],fromList [2]],[fromList [2],fromList [2,3]],[fromList [2],fromList [1,2]],[fromList [2],fromList [1,2,3]],[fromList [2,3],fromList [2,3]],[fromList [2,3],fromList [1,2,3]],[fromList [1],fromList [1]],[fromList [1],fromList [1,3]],[fromList [1],fromList [1,2]],[fromList [1],fromList [1,2,3]],[fromList [1,3],fromList [1,3]],[fromList [1,3],fromList [1,2,3]],[fromList [1,2],fromList [1,2]],[fromList [1,2],fromList [1,2,3]],[fromList [1,2,3],fromList [1,2,3]]]

全称命題 ∀x. (P(x) -> Q(x)) が真であることは、上に示したような述語の真理集合 P* と Q* の組があることを示している。

追記

最後の結果が読みづらかったので、集合をリストに変換して表示してみた。

Prelude Set> let inclusion = filter (\x -> Set.isSubsetOf (x!!0) (x!!1)) cartesian
Prelude Set> map (\x -> map Set.toList x) inclusion
[[[],[]],[[],[3]],[[],[2]],[[],[2,3]],[[],[1]],[[],[1,3]],[[],[1,2]],[[],[1,2,3]],[[3],[3]],[[3],[2,3]],[[3],[1,3]],[[3],[1,2,3]],[[2],[2]],[[2],[2,3]],[[2],[1,2]],[[2],[1,2,3]],[[2,3],[2,3]],[[2,3],[1,2,3]],[[1],[1]],[[1],[1,3]],[[1],[1,2]],[[1],[1,2,3]],[[1,3],[1,3]],[[1,3],[1,2,3]],[[1,2],[1,2]],[[1,2],[1,2,3]],[[1,2,3],[1,2,3]]]

繰り返しの操作をループを使わずに記述できるのは嬉しい。Haskell で何か作りたくなってきた。

[PR]
by tnomura9 | 2017-08-30 08:27 | ラッセルのパラドックス | Comments(0)

含意の全称命題の意味

「全ての対象についてそれが人間であるならば、それは死すべきものである。」という全称命題が真であるということはどういうことを意味しているのだろうか。

これを記号化すると ∀x. (P(x) -> Q(x)) となる。そこで、領域 D の対象 a を取り上げて P(a) -> Q(a) という命題を作ってみる。これは含意の複合命題だから、その真理表を作ることができ、それは次のようになる。

P(a) | Q(a) | P(a) -> Q(a)
T | T | T
T | F | F
F | F | T
F | F | T

この真理表には P(a) -> Q(a) が偽の場合もある。つまり、P(a) が真で Q(a) が偽の場合は P(a) -> Q(a) は偽になる。このことは、含意の真理表は常に真になるとは限らないことを示している。

しかし、∀x. (P(x) -> Q(x)) は全ての x に対して P(x) -> Q(x) が真になることを主張している。これは真理表の結果とは異なるが、P(x) と Q(x) の間に特別な関連性があれば矛盾しない。すなわち ∀x. (P(x) -> Q(x)) の P(x) と Q(x) の間には特別な関係があり、P(a) が真であって、Q(a) が偽であるということはないと考えれば良い。

そのような特別な P(x) と Q(x) の関係では、P(a) -> Q(a) は常に真になる。この場合 P(a) -> Q(a) の真理表は次のように常に真になる。

P(a) | Q(a) | P(a) -> Q(a)
T | T | T
F | T | T
F | F | T

このとき P(a) が真であれば、Q(a) のとり得る値は真でしかない。命題 P(x) の真理集合を P* とすると P(a) が真であるということは、a ∈ P* である。このとき、Q(a) は必ず真であるので a ∈ Q* である。全称命題 ∀x. (P(x) -> Q(x)) はこの関係が領域 D のどのような対象についても成立することを示している。すなわち、任意の a について a ∈ P* ならば必ず a ∈ Q* である。

このことは領域 D の全ての対象 x について P(x) が真であるということを示しているわけではない。対象 a について P(a) は真の場合も偽の場合もある。しかし、P(a) が真の場合は必ず Q(a) も真なのだ。

ところで、a ∈ P* ならば a ∈ Q* ということは、真理集合 P* と Q* の間に包含関係 P* ⊂ Q* があることを示している。また、P* ⊂ Q* から ∀x. (P(x) -> Q(x)) も証明できる。したがって、全称命題 ∀x. (P(x) -> Q(x)) が真であるということと、P* ⊂ Q* とは同値である。

このように、一階述語論理のモデルである領域 D という対象の集合を考えれば、述語論理の推論が推論規則だけでなく、領域 D の対象と、述語の真理集合の関係としてとらえる事ができるので、述語論理の性質をより具体的に捉えることができる。

たとえば領域 D = {1,2,3,4,5} において、命題 P の真理集合が P* = {2,3} で命題 Q の真理集合が Q* = {2,3,4} であったとする。この場合明らかに P* ⊂ Q* であるが、この時の P(x) -> Q(x) の真理値を領域 D について全て調べてみると、

x = 1 のとき、P(1) = F, Q(1) = F, P(1) -> Q(1) = T
x = 2 のとき、P(2) = T, Q(2) = T, P(2) -> Q(2) = T
x = 3 のとき、P(3) = T, Q(3) = T, P(3) -> Q(3) = T
x = 4 のとき、P(4) = F, Q(4) = T, P(4) -> Q(4) = T
x = 5 のとき、P(5) = F, Q(5) = F, P(5) -> Q(5) = T

となって ∀x. (P(x) -> Q(x)) が真であるということが分かる。

一般に、一階述語論理の公理系があって、それを充足するモデルを見つけるという順番で考察が行われるが、逆に一階述語論理のはこのような領域 D の性質であって、公理系はそれを無限集合やそのたの数学的構造に適用できるように拡張したものだと考えたほうが、思考の順序としては分かりやすいのではないかと思う。

つまり、一階述語論理は有限集合の領域 D の法則であるが、その他の領域 D については一階述語論理が適用できるかどうかを改めて考えるのだ。この観点からは、ラッセルのパラドックスに別の解釈を与える事ができる。

すなわち、属性関係の与えられた集合という対象の集合である領域 D を考えたとき、この D の構造には一階述語論理が適用できないという考え方だ。ラッセルのパラドックスを集合論の危機ととらえず、このような構造を持った領域 D には一階述語論理が適用できない場合があると考えるのだ。いいかえると、ものの集まりという集合と、属性関係の与えられた対象の外延としての集合とは意味が異なっているということだ。

素朴集合論の集合とはものの集まりであるという定義には矛盾はないような気がする。しかし、集合の集合というようなものを表現するために、属性関係の与えられた集合という対象の全体として集合の世界を捉えたとき、このような領域 D では構造的に一階述語論理が適用できない場合が出てくるのだ。

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

全称命題の真理値

一階述語論理を適用する対象の領域を D = {1,2,3,4,5} とし、命題 A, B, C の真理集合を A* = {2,3}, B* = {3,4}, C* = {2,3,4} とする。すると、命題 A, B, C の命題関数は A(x) = x ∈ A*, B(x) = x ∈ B*, C(x) = x ∈ C* で定義できる。このとき命題 E = A -> B の命題関数は (A -> B) = ¬A ∨ B なので、E(x) = (x /∈ A*) or (x ∈ B*) と定義される。これらは皆 Hsskell の関数で次のように記述できる。

Prelude> import qualified Data.Set as Set
Prelude Set> let d = Set.fromList [1,2,3,4,5]
Prelude Set> let a = Set.fromList [2,3]
Prelude Set> let b = Set.fromList [3,4]
Prelude Set> let c = Set.fromList [2,3,4]
Prelude Set> let imply x = (Set.notMember x a) || (Set.member x b)

そこで、imply(x) = A(x) -> B(x) の真理集合を求めてみる。これは領域 D の要素を一つづつ imply(x) に代入して真理値が真のものだけを抜き出せばいいから、Set.filter 関数を使うことで実現できる。

Prelude Set> Set.filter imply d
fromList [1,3,4,5]

この真理集合には要素 2 が抜けているので全称命題 ∀x.(A(x)->B(x)) の真理値は偽となるはずだ。これは Prelude の and 関数で計算できるはずだが、and :: [Bool] -> Bool なので and 関数には Bool 値のリストを与えなければならない。従ってあらかじめ集合 d を Set.toList のようにリストに変換しておく必要がある。

Prelude Set> and (map imply (Set.toList d))
False

一方、領域 D の要素の少なくとも1つは imply(x) を真にするから存在命題 ∃x.(A(x) -> B(x)) の真理値は真である。存在命題の真理値の計算は Prelude の or 関数を使う。

Prelude Set> or (map imply (Set.toList d))
True

このように、量化子を使った全称命題や存在命題の真理値の計算は、領域 D の全ての要素についてそれを命題関数 imp(x) に代入した時の真理値をもとめ、それを集計することで得られる事がわかる。

全ての x について x が人間ならば x は死すべきものであるという全称命題 ∀x. (P(x) -> Q(x)) が真ならば、ソクラテスは死すべきものであるという推論では、この全称命題が真であることが仮定されているが、上の imply(x) の全称命題は残念ながら偽だ。含意 A(x) -> B(x) はどのようなときにその全称命題が真になるのだろうか。

そこで、今度は含意を含む命題 imply2 を A(x) -> C(x) で定義してみる。

Prelude Set> let imply2 x = (Set.notMember x a) || (Set.member x c)

すると imply2 の真理集合は領域 D に一致し、その全称命題は真になる。

Prelude Set> Set.filter imply2 d
fromList [1,2,3,4,5]
Prelude Set> and (map imply2 (Set.toList d))
True

どうして A(x) -> B(x) の全称命題は偽で A(x) -> C(x) の全称命題は真なのだろうか。それは A(x) の真理集合と C(x) の真理集合の間に包含関係があるからだ。

Prelude Set> Set.isSubsetOf a c
True

実際 A(x) の真理集合の要素の全ては、C(x) の真理集合の要素でもある。

Prelude Set> a
fromList [2,3]
Prelude Set> c
fromList [2,3,4]

すべての x についてそれが人間ならばそれは死すべきものであるという全称命題は、暗に x が人間の要素であれば、同時に x は死すべきものの要素でもあるということを意味していたのだ。したがって、ソクラテスは人間であるという命題が真であれば、ソクラテスは死すべきものであるという命題も真になる。

これらの推論は別にプログラムを作らなくても理解できるが、プログラムを使ってアルゴリズム化することによって、その意味するものが明確になるという利点がある。


[PR]
by tnomura9 | 2017-08-27 17:28 | ラッセルのパラドックス | Comments(0)

含意の真理集合

対象全体の集合を領域 D = [1,2,3,4,5] とする。また、述語 A(x) の真理集合を A* =[2,3]、述語 B(x) の真理集合を B* = [3,4] とする。この時命題 A(2) の真理値は真で、A(1) の真理値は偽である。これはまた 2 ∈ A* と 1 ∈ A* の真理値と一致する。従って命題 A(2) の真理値を 2 ∈ A* で表すことができる。このモデルで含意の述語 A(x) -> B(x) の真理集合を計算してみる。

ところで、命題論理の定理で A -> B = ¬A ∨ B であることがわかっている。また、命題 A(x) の真理値は x ∈ A* の値と一致するから A(x) -> B(x) の真理値は (x /∈ A*) ∨ (x ∈ B*) と一致することが分かる。

これらの条件を元に A(x) -> B(x) の真理集合を Haskell で計算すると次のようになる。

Prelude> import qualified Data.Set as Set
Prelude Set> let d = Set.fromList [1,2,3,4,5]
Prelude Set> let a = Set.fromList [2,3]
Prelude Set> let b = Set.fromList [3,4]
Prelude Set> let imply x = (Set.notMember x a) || (Set.member x b)
Prelude Set> Set.filter imply d
fromList [1,3,4,5]

計算された真理集合には要素 2 が含まれていないが、2 は a には含まれるが、b には含まれていない。つまり、A(a) は真であるが B(2) は偽である。したがって A(2) -> B(2) は偽である。従って 2 が A(x) -> B(x) の真理集合には含まれない。

A(x) -> B(x) の真理集合は集合演算で次のように直接計算することもできる。

Prelude Set> Set.union (Set.difference d a) b
fromList [1,3,4,5]

この場合は命題 A の否定の真理集合が、A の真理集合の補集合であるところが注意点だ。

上に上げた例では、A(x) -> B(x) の真理集合が領域 D と一致しないので、∀x.(A(x) -> B(x)) は偽である。A(2) -> B(2) が偽になるからだ。

このように領域 D を考えると、述語は D の部分集合、命題の真理値は x ∈ A の 値で定式化でき、命題結合子を使った複合命題の真理集合が自動的に計算できることが分かる。すなわち、一階述語論理の本質が真理集合の集合演算であることが分かる。

[PR]
by tnomura9 | 2017-08-27 00:42 | ラッセルのパラドックス | Comments(0)

Haskellと一階述語論理の集合モデル

一階述語論理の集合モデルを作って、Haskell で操作してみた。一階述語論理の有限集合モデルを次のように構成する。

まず、有限の対象の集合である領域(domain) D を考える。次に領域 D の冪集合 2^D を考えると、その要素は、一階述語論理の1変数命題関数(述語)の真理集合になる。述語 A があると、対象 a と述語 A との対 A(a) は真偽値をもつ命題をあらわし、A(a) が真になるような対象の集合は述語 A(x) の真理集合になるからだ。これを A* とすると、A* は必ず領域 D の部分集合である。

対象 a と真理集合 A* があるとき、 a ∈ A* は真偽値をもつ。すなわち A(a) と a ∈ A* は同値である。したがって、a ∈ A* を命題と考えることができる。また、真理集合 A* を述語 A(x) と同一視することができる。このとき、論理結合子による複合命題 (a ∈ A*) ∧ a ∈ B* の真理集合は A* ∩ B* と一致する。また、論理結合子の演算は 2^D について閉じている。

量化記号を使った命題 ∀x.A(x) の真偽は A(x) の真理集合が領域 D と一致するときに真となり、一致しない時に偽となる。∃x.A(x) の真偽は A(x) の真理集合が空集合 {} のとき偽となり、そうでないとき真となる。∀x. A(x) が真であることだけがわかっているとき、A(x) の真理集合は領域 D である。一方、∀x.A(x) が偽であることがわかっているときは、A(x) の真理集合は領域 D ではないことはわかるが、それ以外のどれであるかは特定できない。

2変数以上の命題関数については、領域 D の自身との直積集合で考える。命題 A(x,y) の真理集合は D x D の部分集合である。

こういうふうに抽象的に定義するとイメージがつかみにくいので Haskell で実際に集合を作ってみると言うのが目論見だ。

Haskell で集合を扱うためには Data.Set モジュールをインポートする。Data.Set モジュールの関数の名前は Prelude のものと衝突するものがあるので、qualified インポートしてモジュール名を Set にしておく。こうすれば Data.Set の関数名を Set.map のように Prelude の map と衝突させないで使うことができる。

Prelude> import qualified Data.Set as Set

Data.Set で集合を作るにはリストを fromList 関数で集合に変換する。

Prelude Set> let d = Set.fromList [1..5]
Prelude Set> d
fromList [1,2,3,4,5]
Prelude Set> let a = Set.fromList [2,3]
Prelude Set> a
fromList [2,3]
Prelude Set> let b = Set.fromList [3,4]
Prelude Set> b
fromList [3,4]

要素が集合に属しているかどうかの判別は member 関数で行う。

Prelude Set> Set.member 2 a
True

和集合を作る関数は union 関数だ。

Prelude Set> Set.union a b
fromList [2,3,4]

共通部分は intersection 関数で求めることができる。

Prelude Set> Set.intersection a b
fromList [3]

述語 A(x) の否定 ¬A(x) の真理集合は、領域 D を全体集合とした時の A* の補集合だ。これは領域 D - A* という差集合になる。差集合を求める関数は difference 関数だ。

Prelude Set> Set.difference d a
fromList [1,4,5]

member 関数は要素と集合の帰属関係を判定するが、map 関数を使うと領域 D の全ての対象に対して集合 A* への帰属関係を調べる事ができる。ただし、この場合少し工夫が必要だ。集合に対して map が使えないので、集合を toList 関数で一旦リストにする必要があるのだ。

Prelude Set> map (\x -> Set.member x a) (Set.toList d)
[False,True,True,False,False]

このように Data.Set モジュールを利用すると集合演算が簡単に行える。次回からはこの機能を利用して、一階述語論理のモデルの性質を抽象的にではなく具体的に調べることにする。


[PR]
by tnomura9 | 2017-08-26 07:56 | ラッセルのパラドックス | Comments(0)

∀xP(x) の真理集合

まず、簡単に述語論理のモデルの構成をさらってみる。

領域 D という対象の集合があり、その対象の性質を言明する A(x) という述語がある。また、対象 a と述語 A(x) の組は A(a) という命題であり、これは排中律によって必ず真か偽の値をとる。

このため、ある述語 A(x) について、領域 D の対象全てとの対をテストすることで、A(x) が真となるような領域 D の部分集合 A* を定めることができる。この A* は命題 A(x) の真理集合である。また、真理集合は必ず領域 D の部分集合であるから、真理集合は領域 D の冪集合の要素である。

原子述語 A(x) を論理結合子で結合して、A(x) ∧ B(x) のような複合述語を作ると、その真理集合は A* ∩ B* のように真理集合の集合演算の値となる。さらに、A* ∩ B* もまた、領域 D の冪集合の要素である。すなわち、領域 D は論理結合子と対応する集合演算について閉じている。したがって、領域 D に対する論理的な操作はすべて真理集合の集合演算に変換することができる。

こういうふうに考えると、論理の本質は、排中律の成立する領域 D の集合についての集合演算として捉えることができる。

しかし、述語論理には量化子という厄介なものがある。∀xP(x) というのは真か偽の値を持つ命題だが、これは対象と述語のペアではない。しかし、このような例外的な命題があると、上のようなスッキリした図式をつくることができなくなるので不便だ。そこで、形式的に ∀xP(x) の述語 Q(x) を考えてみることにした。そうすると、∀xP(x) = Q(a) のように命題を領域 D の対象と述語 Q(x) とのペアで考えることができ、Q(x) の真理集合を考えることができる。

しかし実際には ∀xP(x) の真偽値が対象との組み合わせで変ることはないので Q(x) はどのような対象との組み合わせでも常に真かまたは偽である。しかし、このことは同時に、Q(x)の真理集合が領域 D と一致するかまたは空集合であることを示している。また、∃xP(x) のような存在量化子を使った命題も、事情は同様である。

このように、存在量化子を使った命題についても形式的に述語 Q(x) を考えることで、全ての命題は対象と述語のペアで真理値が定まると考えることができる。このことで述語論理における命題とは何かということが定式化できるので、A -> (B -> A) のような命題論理の定理から、

∀x(A(x) -> (B(x) -> A(x))
∀x∀y(A(x) -> (B(y) -> A(x))
∀x(∀yA(y)(x) -> (B(x) -> ∀yA(y)(x))

などの定理を演繹できる。述語論理は述語の排中律を満たす領域 D の集合演算なのだと考えると、論理の応用範囲の広さの意味と、論理が適用できない対象 D はどんなものかというイメージが明確にできる。

何度も言うが、ラッセルのパラドックスは集合の世界 D を「所属関係を定義された対象の集合」という対象のネットワークで捉えようとしたために、領域 D が排中律を満たすことができないことを示しているだけだ。

[PR]
by tnomura9 | 2017-08-15 04:28 | ラッセルのパラドックス | Comments(0)

勇者ヨシヒコ


テレビ東京公式 Youtube チャンネル

低予算冒険活劇




[PR]
by tnomura9 | 2017-08-13 21:47 | 話のネタ | Comments(0)

ソクラテスは死ぬ

全ての人間は死ぬ。ソクラテスは人間である。ゆえにソクラテスは死ぬ。という推論を述語論理学の演繹規則から推論してもよいが、直感的なイメージが湧かない。

ここで領域 D の対象 x が人間であるという述語を A(x) とする。また、x が死すべきもの (mortal) であるという述語を B(x) とする。そうするとすべての人間は死ぬという命題は次のようにあらわされる。

∀x(A(x) -> B(x))

ここで、述語 A(x) -> B(x) の真理集合を求めてみる。命題論理では命題 A(a) -> B(a) は、¬A(a) ∨ B(a) に等しい。したがって、述語 ¬A(x) ∨ B(x) の真理集合は A(x) の真理集合 A* の補集合と B(x) の真理集合 B* の和集合になる。これは、簡単な図によって視覚化できる。領域 D を長方形の内部で表し、A* と B* を一部が重なる円の内部で表せばよい。図に書くとすぐにわかるように領域 D 内の ¬A(x) ∨ B(x) の真理集合は領域 D を埋め尽くすことはなく A* - B* の部分が空白になる。

∀xP(x) が真になる必要十分条件はこの命題の真理集合が領域 D と等しいことだから、上の場合のように穴があっては困る。したがって、∀x(A(x) -> B(x)) の真理集合が領域 D と一致するためには A* と B* の間に何らかの関係がある必要がある。

述語 A(x) -> B(x) の真理集合に穴があったのは、その部分を B* がカバーできなかったからだ。B* が A* - B* をカバーできていれば、述語 A(x) -> B(x) の真理集合は領域 D と完全に一致することになる。そういうことは起こりえる。つまり、A* が B* の部分集合であればよいのだ。A* が B* の部分集合であれば A* - B* は空集合だ。この場合は A(x) -> B(x) の真理集合は領域 D の中で穴を持たず、領域 D と一致する。

したがって、∀x(A(x) -> B(x)) の仮定の下では、A* ⊂ B* である。この時は対象 a がソクラテスであるとすると a ∈ A* なら a ∈ B* は自明である。すなわち B(a) は真であるのでソクラテスは死ぬことがわかる。

一階述語論理の1変数(アリティが 1 )の命題関数については、このように、論理的推論を含めてすべての論理学的な考察が真理集合の集合演算で理解することができる。ただし、このためには条件がある。領域 D という対象の集合がはっきりしていることと命題関数の排中律が保証されていることだ。

一階述語論理を真理集合の論理演算としてとらえると、述語論理の視覚的イメージが作りやすくなる。ただし、領域 D の存在と排中律の成立が必須の条件になる。

[PR]
by tnomura9 | 2017-08-11 18:47 | ラッセルのパラドックス | Comments(0)

一階述語論理とは何か

一般的には一階述語論理の上に集合論が構築されているが、その立場を逆転させると述語論理の意味が分かりやすいのではないだろうかと思いついた。述語論理が数学の基礎であると考えるのではなく、述語論理とは集合の性質の一つと考えたほうが矛盾がでないのではないかと思ったのだ。そこで次のような単純なモデルの例を考えてみた。

領域 D は対象 a, b, c, ... の集合であるとする。Dの要素に対し述語 A, B, C, ... が与えられ、Dの要素の一つ a と述語 A との対から命題 A(a) が作られる。A(a) は必ず真か偽の値を取り、排中律が成立するとする。A(a) が排中律を充足するかどうかは領域 D の構造によっているので、必ずしもいつも成立するわけではないが、一階述語論理は領域 D が排中律を満たす場合にのみ領域 D に適用される。つまり、一階述語論理は領域 D が排中律を満たす場合の法則で、万物の基礎とは考えない。

任意の対象を表す対象変数 x を導入すると、述語 A は命題関数 A(x) で表現することができる。命題関数 A(x) は領域 D を定義域とし、真偽値を値域とする1変数関数である。以下の議論では述語 A を命題関数 A(x) と同一視する。

領域 D の述語が排中律を充足するとき、A(a) が真であるような命題 A を充足する対象 a, b, c の集合を考えることができる。これを真理集合 A* とすると、A* は明らかに領域 D の部分集合である。また、命題関数を使うと A* = {x| A(x)}という内包的定義ができる。排中律が仮定されているので内包的定義には特に制限はない。つまり、命題関数による内包的定義は必ず真理集合を定義できる。

複数の原子述語 A(x), B(x) があるとき、原子述語は論理結合子によって C(x) = A(x) ∧ B(x) のような複合述語を作ることができる。C(x) もまた排中律を満たし、領域 D の述語である。原子述語 A(x), B(x) および論理結合子の性質から C(x) によっても真理集合 C* を定めることができる。この場合明らかに C* は領域 D の部分集合である。したがって、原子述語 A(x), B(x), ... と論理結合子によって無数の複合述語を作ることができるが、それらの複合述語の真理集合は全て領域 D の冪集合の要素である。つまり、論理結合子による複合述語の真理集合は、原子述語の真理集合の集合演算の値と一致する。

ところで、無限の原子述語や複合述語を考えることはできるが、その真理集合は必ず領域 D の部分集合である。したがって、命題の真理集合の集合の濃度は領域 D の冪集合の要素の濃度を超えることはない。そこで、述語 A(x) の真理集合が A* で、述語 B(x) の真理集合が B* であり、A* = B* のとき、述語 A(x) は 述語 B(x) と同等であるということにする。述語 A(x) と 述語 B(x) の同等関係は反射率、対象率、推移律を満たすので同値関係である。したがって、領域 D の全ての述語の集合は同等関係で類別できる。また、述語から真理集合への写像が全射の場合、述語の同値類と真理集合は全単射になる。したがって、述語の同値類と真理集合は同一視できる。

このことから、領域 D の全ての論理的操作は、領域 D の冪集合上の集合演算として表現できることがわかる。このことは、論理的操作が結局のところ領域 D の要素の分類作業にほかならないということを示している。言葉を変えれば、対象が領域 D の集合として限定され、かつ、領域 D の命題が排中律を満たすとき、領域 D には一階述語論理が適用され。その意味は領域 D の対象の分類作業であるということができる。領域 D が集合であることと、領域 D の命題が排中律を満たすという条件を満たさない場合、領域 D には論理を適用できず、領域 D は論理的ではない(論理の法則が適用できない)。

したがって、論理があらゆる数学的対象に適用できる理由が分かる。つまり、一階述語論理の議論は領域 D の要素の分類法について述べているだけであり、領域 D の命題の性質は排中律を除いて抽象化されてしまう。このため、多くの領域 D の無数の命題に対し一階述語論理による議論ができるのだ。

素朴集合の世界の領域を「帰属関係が定義された対象の集合」と考えた場合、「自分自身を要素として含まない集合の集合」という述語は排中律をみたさない。したがって、素朴集合には一階述語論理を適用できず、素朴集合の構造は論理的ではないことが分かる。一方、整数の場合は領域 D は集合であり、整数の演算についての議論は排中律を満たしているので論理が適用できるのだ。

ラッセルのパラドックスが発生するのはこのような素朴集合論の領域 D を「帰属関係が定義された対象の集合」という定義で対象のネットワークとして捉えた場合の特異な性質によるものであり、集合論の本質的な瑕疵とは言えないのではないだろうか(これについては、このブログの「集合 論理 クラス」という記事で議論した)。論理学を学ぶ上で一階述語論理を上のような観点で捉えれば、ラッセルのパラドックスについて最初に触れなくても論理学をきちんと組み立てる事ができるような気がする。論理は万能ではなく、領域 D に適用できるかどうかは領域 D の構造に依存しているのだ。


[PR]
by tnomura9 | 2017-08-09 06:40 | ラッセルのパラドックス | Comments(0)