ハイティング代数意味論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/25 04:07 UTC 版)
「直観主義論理」の記事における「ハイティング代数意味論」の解説
古典論理において、我々はしばしば論理式の取る真理値について議論する。この値は普通はブール代数の元から選ぶ。ブール代数の交わりと結びは論理結合子の ∧ {\displaystyle \wedge } と ∨ {\displaystyle \vee } に同一視される。そして A ∧ B {\displaystyle A\wedge B} の真理値は A {\displaystyle A} と B {\displaystyle B} の真理値のブール代数における交わりとする。このとき論理式が古典論理において妥当であることと、任意のブール代数とその上で値を取る真理値割り当てに対して論理式の真理値が ⊤ {\displaystyle \top } であることとが同値となる。 直観主義論理においても同様の完全性定理が成立するが、論理式の真理値はブール代数の代わりにハイティング代数の元を用いる。ブール代数はハイティング代数の特別な場合である。このとき論理式が直観主義論理で妥当であることと、任意のハイティング代数とその上で値を取る真理値割り当てに対して論理式の真理値が ⊤ {\displaystyle \top } であることは同値である。 論理式が妥当であることを確かめる為には、ひとつのハイティング代数の上で調べれば十分であることが証明できる。そのハイティング代数は数直線 R {\displaystyle \mathbb {R} } の開部分集合からなるハイティング代数である。 この代数系において、 ∧ {\displaystyle \wedge } と ∨ {\displaystyle \vee } は集合の交わりと結びである。また A → B {\displaystyle A\to B} は i n t ( A c ∪ B ) {\displaystyle \mathrm {int} (A^{c}\cup B)} すなわち A {\displaystyle A} の補集合と B {\displaystyle B} との和集合の内部である。（これは古典論理における含意の演算の結果を開集合になるように調整したものである。様相論理の観点から見るとこれは必然性を外側に付けているのと同じことになる。） ⊥ {\displaystyle \bot } は空集合 ∅ {\displaystyle \varnothing } であり、 ⊤ {\displaystyle \top } は全体集合 R {\displaystyle \mathbb {R} } である。否定 ¬ A {\displaystyle \neg A} は A → ⊥ {\displaystyle A\to \bot } と定義されるが、これは A {\displaystyle A} の補集合の開核すなわち外部と一致する。この対応付けによって直観主義的に妥当な論理式はちょうど空間全体が割り当てられるものと一致する。 例えば矛盾律 ¬ ( A ∧ ¬ A ) {\displaystyle \neg (A\wedge \neg A)} は妥当である。なぜなら開集合 X {\displaystyle X} を A {\displaystyle A} の付値としてどのように選んでも ¬ ( A ∧ ¬ A ) {\displaystyle \neg (A\wedge \neg A)} の値は次のように直線全体となるからである： v a l ( ¬ ( A ∧ ¬ A ) ) = i n t ( ( X ∧ i n t ( X c ) ) c ) {\displaystyle \mathrm {val} (\neg (A\wedge \neg A))=\mathrm {int} ((X\wedge \mathrm {int} (X^{c}))^{c})} 位相空間論によれば i n t ( X c ) {\displaystyle \mathrm {int} (X^{c})} は X c {\displaystyle X^{c}} の部分集合であり、 X {\displaystyle X} との共通部分は空であるから、 i n t ( ∅ c ) = i n t ( R ) = R {\displaystyle \mathrm {int} (\varnothing ^{c})=\mathrm {int} (\mathbb {R} )=\mathbb {R} } したがってこの論理式の付値は真であり、妥当であることが従う。 しかし排中律 A ∨ ¬ A {\displaystyle A\vee \neg A} は非妥当である。それには A {\displaystyle A} に ( 0 , ∞ ) {\displaystyle (0,\infty )} を割り当てるとよい。すると ¬ A {\displaystyle \neg A} の付値は ( − ∞ , 0 ] {\displaystyle (-\infty ,0]} の内部、すなわち ( − ∞ , 0 ) {\displaystyle (-\infty ,0)} であり、目的の論理式の付値は ( 0 , ∞ ) {\displaystyle (0,\infty )} および ( − ∞ , 0 ) {\displaystyle (-\infty ,0)} の和集合、すなわち R ∖ { 0 } {\displaystyle \mathbb {R} \setminus \{0\}} となる。これは空間全体に一致しない。 数直線からハイティング代数を作る上のやり方は任意の位相空間に対しても適用できる。位相空間論では閉包の開核がもとと一致する集合を正則開集合という。これはこのハイティング代数における二重否定で不変な集合と同じものである。正則開集合の全体は（完備）ブール代数を成す。これは古典論理が二重否定によって直観主義論理に埋め込めるというグリベンコの定理に対応している。
※この「ハイティング代数意味論」の解説は、「直観主義論理」の解説の一部です。
「ハイティング代数意味論」を含む「直観主義論理」の記事については、「直観主義論理」の概要を参照ください。
- ハイティング代数意味論のページへのリンク
