Glivenko の定理の代数的証明

なんかいいやり方があったような気がしたけど思い出せなくて考えてたらできたメモ。いまいち証明できた気分にならないので,もしかすると正しくないのかもしれない。

Theorem: 命題論理式  \phi が claissical tautology ⇔  \neg\neg\phi が intuitionistic tautology.

右から左は簡単で,左から右が問題。classical tautology の二重否定をどんなハイティング代数でどう解釈しても 1 になることをいう。

準備

H をハイティング代数とし, H' = \{ x \in H \mid \neg\neg x = x\} とする。また  \neg\neg: H \ni x \mapsto \neg\neg x \in H' とする。

Lemma 1: H' は H の順序でブール代数になる。

ただし演算の入れ方に注意が必要。meet と complement は H のものでよいけど,H' は join で閉じていない。H での join を  \sqcup とすると,H' の join は  \neg\neg(a \sqcup b) で与えられる。

Lemma 2:  \neg\neg: H \to H'ハイティング代数準同型である。

これは 0, 1, meet, join, relative pseudocomplement が二重否定で保存されることをいえばよい。具体的には

  •  \neg\neg 0 = 0
  •  \neg\neg 1 = 1
  •  \neg\neg(x \sqcap y) = \neg\neg x \sqcap \neg\neg y
  •  \neg\neg(x \sqcup y) = \neg\neg(\neg\neg x \sqcup \neg\neg y)
  •  \neg\neg(x \Rightarrow y) = \neg\neg x \Rightarrow \neg\neg y

がいえればよい。join は H と H' で定義が異なるのでこうなる。

これ,代数的に示すのはだいぶ難しい気がするので,論理式で書いて LJ で証明するのが一番楽だと思う。それか自動証明。

Theorem の証明

論理式  \phi の付値 v での解釈を  [\phi]_v と書くことにする。

任意のハイティング代数 H とその上の付値 v をとる。 w = \neg\neg \circ v で H' 上の付値を定義する。

 \neg\neg準同型だから任意の論理式  \phi に対して  [ \phi ]_{w} = \neg\neg [ \phi ]_v である。

特に  \phi が classical tautology の場合,H' がブール代数であることから  [ \phi ]_{w} = 1 だから  [ \neg\neg\phi ]_v = \neg\neg [ \phi ]_v = 1 である。H, v は任意だったから  \neg\neg\phi は intuitionistic tautology である。