曇りなき眼で見定めブログ

学生です。勉強したことを書いていく所存です。リンクもコメントも自由です! お手柔らかに。。。アマゾンアソシエイトやってまっせ。更新のお知らせはTwitter@cut_eliminationで

「直観主義型理論(ITT, Intuitionistic Type Theory)」勉強会ノート其ノ拾伍「直和の応用(途中から)」(予習編)

 シリーズの他の回はこちらから。

&規則

 はてなブログでは"&"をTeX記法でうまく表示できないという問題に直面しているがそれはさておき。

 \Pi\supset のときと同様、Bx に依存しないときに以下のようになる。

 A&B \equiv A \times B \equiv (\Sigma x \in A)B

&の規則は以下の下段である。

f:id:cut_elimination:20210617145844p:plain

 この前と同様 \Sigma\exists と&の規則を並べることで対応関係をわかりやすくしている。

&形成則

 この前は"generalization"という言葉がよくわからない意味で使われていると思っていたが、勘違いだった。A&B が命題だというには普通は AB が命題だとわかっている必要があるが、ここでは B が命題だというのは A \; true という仮定のもとでわかっていればよい、仮定なしが普通の形成則である、という意味で一般化になっている。

&導入則

 隠した証明を復元すると、A&B の(カノニカルな)証明は A の証明 aB の証明 b のペア (a, b) である。

&除去則

 規則の C はもちろん AB にできるので、よく見る除去則にすることもできる。逆にそこから今回の除去則を出すこともできる。

f:id:cut_elimination:20210617151510j:plain

例:left projection

 p(c) \equiv E(c, (x, y)x)

と定義し、これを cleft projection(左射影)と呼ぶ。

f:id:cut_elimination:20210617151936j:plain

のように、(\Sigma x \in A)B(x) の要素 c を実行すると (a, b) \; (a \in A, b \in B(a)) が得られ、Eの代入をやると a (\in A)(メソッド a を実行すると A のカノニカルな要素が得られる)が得られるので、\Sigma除去則と等号則のインスタンスとして以下の左射影則が得られる(pcc に依存しているので前提の c は隠せない)。

f:id:cut_elimination:20210617153701j:plain

論理的な解釈をすると、(\exists x)B(x)が真なとき B を満たす A の要素が得られるということを意味する(テキストの \Sigma は誤植かと)。この項は唯一のものを \iota 演算子で表したり((\iota x)B(x))なんらかのあるものを \epsilon 演算子で表したりする((\epsilon x)B(x))が、このような演算子直観主義的には必要ない。何故なら (\Sigma x \in A)B(x) が真であるのはそれが証明ができるときなので(項を指定する必要はない)。項(\epsilon x)B(x) については困難な点がある。これは性質 B(x) に項を対応させる関数として構成されるのであって (\exists x)B(x) の証明の関数ではないということである。なのでヒルベルトは上にかいたような \epsilon 規則を導入した。ITTではこれは余計になる。もうひとつは後ほど。※このあたりは数学の哲学の深い話っぽい。

例:right projection

 q(c) \equiv E(c, (x, y)y)

と定義し、これを c right projection(右射影)と呼ぶ。テキストにいろいろと説明があるのだが、要するに x \in A から p(\(x, y)\) \in A が得られ、\Sigma除去則と等号則のインスタンスとして以下の右射影則が得られるのである。

f:id:cut_elimination:20210617153730j:plain

ヒルベルトのもうひとつの \epsilon 規則(テキストは誤植だと思う)は右射影のふたつめの規則があれば必要ない。また、ひとつめの規則から我々のよく知るより強い&除去則が得られる。Bx に依存しないとき、証明(construction)を隠せばよい。Bx に依存している場合は左射影と同様で結論部が c に依存しているので前提部の c は隠せない。

連言の公理とその他の応用

 私の担当ではないのでよろしく。

 やっぱり導出をかくと命題論理の自然演繹みたいになるということであろう。