様相論理を勉強していると、S5フレームの到達可能性はユークリッド的とか言われる。これについて少し考えてみたい。
なぜ「ユークリッド」なのか?
前から疑問だったが、本当にユークリッドの『原論』に由来しているらしい*1。
- 共通概念1:同じものに等しい物同士は互いに等しい
これを形式化したものが、ユークリッド的関係と言われるらしい。関係Rがユークリッド的とは
- ∀x,y,z (xRy & xRz → yRz)
Rを「等しい」と読むと、上の共通概念1になる。
「共通概念」というのは『原論』の特殊な用語で、幾何学だけでなく算術とか、学問をする上で絶対に従うべき原理という感じ。「公理」ともいう。『原論』には5つの共通概念がある。これに対し、「幾何学の」基本的な原理は「公準」と呼ばれている。公準は5つあり、5つ目が有名な平行線公準。もっとも、現代では、共通概念と公準のどちらも公理とみなされるだろうが。なので、現代風にいえば、『原論』の公理の数は5つではなくて、10個と言わねばならない。
ユークリッド的よりも弱い関係
関係のユークリッド性に戻ろう。上の式は次の式を含意する。
- shift reflexivity:∀x,y (xRy → yRy)
これを満たすがユークリッド的でないフレームは、例えば、W = {a, b, c}, R = {<a,b>, <a,c>, <b,b>, <c,c>} などが考えられる。shift reflexivityに対応する様相論理の図式は
- □(□φ→φ)
となる。公理図式Kを使って外側のボックスを分配すると
- □□φ→□φ
が得られる。これに対応する関係は
- 稠密性:∀x,y [xRy → ∃z(xRz & zRy)]
になる。稠密性はshift reflexivityより弱い。例えば、W = {a, b, c}, R = {<a,b>, <b,b>, <b,c>} が反例のフレームか。
ユークリッド性は反射性と独立だが、shift reflexivityと稠密性densityは、ともに反射性よりも弱い。