"self type and coinductive type" での依存型に対応した余帰納法の誤りについて

[Hexirp]

"self type and coinductive type" の依存型に対応した余帰納法を導いている所のことである。

ここが怪しいと思っていた。なので、 Stack Overflow で質問してみた。すると、やっぱり間違っていたみたいである。

[Hexirp]

Π P : Stream A -> Type.
Π destruct_head : Π x : Stream A. P x -> Σ y : A. Path A (head x) y.
Π destruct_tail : Π x : Stream A. P x -> P (tail x).
(Σ y : Stream A. P y)

これは P x が反変から共変になっているから怪しいと思ったんだよね。やっぱり間違っていた。

[Hexirp]

余依存型が必要らしい。そのために最初は依存型を形式化してみる。

Dependent_Type A = A -> Type

これは問題ない。

Codependent_Type A = A * Type

すると余依存型はこうなるのではないだろうか？

[Hexirp]

Dependent_Type : Type -> Type

with : pi (A : Type) -> Dependent_Type A -> A -> Type

Dependent_Type = lambda A : Type => A -> Type

with = lambda (A : Type) (x : _) (y : _) => x y

Codependent_Type : Type -> Type

with : pi (A : Type) -> Codependent_Type A -> A -> Type

Codependent_Type = lambda A : Type => Product A Type

with = lambda (A : Type) (x : _) (y : _) => Path (Product.first x) y

Dependent_Type_Volume : Type -> Type

display : (A : Type) -> Dependent_Type_Volume A -> A

embed : (A : Type) -> Dependent_Type A -> Dependent_Type_Volume A

A : Type
display A : Dependent_Type_Volume A -> A
f : Unit -> A

pullback : Pullback (Dependent_Type_Volume A) Unit (display A) f
_ : Path (type pullback) (Dependent_Type A)
_ : Path (first pullback) (embed A)

Codependent_Type_Volume : Type -> Type

codisplay : (A : Type) -> A -> Codependent_Type_Volume A

coembed : (A : Type) -> Codependent_Type_Volume A  -> Codependent_Type A

A : Type
codisplay A : Codependent_Type_Volume A -> A

pushout : Pushout (Codependent_Type_Volume A) Unit (codisplay A) (constant unit)
_ : Path (type pushout) (Codependent_Type A)
_ : Path (left pushout) (coembed A)

Dependent_Type_Volume = lambda A : Type => sigma x : A **

[Hexirp]

まず、 A : Type と、それに関する依存型 P : A -> Type を考える。

圏論において、 A -> Type という型は、いきなり実装するのが難しい。そこで、 P? : Type という型を考えて、その性質を記述することにする。

まず、 p : P? -> A という射がある。これは表示射 (display map) という。この p はファイバー (fiber) である。より具体的に書くと、任意の point : Unit -> A に対して、それと引き戻し (pull back) を成す。これが P? が A の依存型であるための条件である。

[Hexirp]

ファイバーの性質として、 p は任意の射 f : X -> A に対して引き戻しを成す。

[Hexirp]

具体的に P? は Dependent_Sum A P で p は Dependent_Sum.first A P で与えられる。

[Hexirp]

同じように A に対する余依存型は Q! と書く。この Q! は、余表示射 q : A -> Q! を持ち、この q は余ファイバーである。つまり、 q は Unit.const : A -> Unit と押し出しを成す。

[Hexirp]

p と point の引き戻しは、まさに P (point Unit.value) のことである。

[Hexirp]

この Q! の元々の Q が、どんな型なのかが問題である。

[Hexirp]

自然数のストリームは Stream -> F Stream である。ここで F A = Nat × A である。これは terminal coalgebra of an endofunctor である。

これにより head : Stream -> Nat と tail : Stream -> Stream が存在することになる。

Stream で coinduction を行いたい。このためには、 A を Stream であるとする。 q : Stream -> Q! である。

head と q による押し出しを作ることが出来なければならない。

[Hexirp]

q : Q? -> A と任意の f : X -> A が引き戻しを成すのは、おそらく、 Unit.const : X -> Unit が一意であり、 point : Unit -> A に Function.const (f x) を代入することにより f : X -> A をエミュレートできるからである。

cofiber でも同じことは出来るのだろうか？

[Hexirp]

1. ファイバー
2. ファイバー

1 から 2 は構成される。それは "inductive type" に書かれているように substitution による。

具体的には f*P : Dependent_Sum X (lambda x => P (f x)) と Dependent_Sum.first : f*P -> X と _ : f*P -> P? による。

% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZARgBpiBdUkANwEMAbAVxiRAEEQBfU9TXfIRRkADFVqMWbAAoB+brxAZseAkRHlx9Zq0QgAKgr4rB60mOrape-QAIAOvbwBbeLYD6t9rbndxMKABzeCJQADMAJwhnJAAmahwIJA0QBjoAIxgGaX5VIVSYMJwQS0ldEEdnOhwACwjnYDQcLiMQSOikMhBE5NKdNjRW9pjEAGYEpMRiHnCokfHuydiuCi4gA
\begin{tikzcd}
T \times _ A P? \arrow[r] \arrow[d] & P? \arrow[d, "p"] \\
T \arrow[r, "\mathrm{pt}"]          & A                
\end{tikzcd}

% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZARgBpiBdUkANwEMAbAVxiRAEEQBfU9TXfIRRkADFVqMWbAAoB+brxAZseAkRHlx9Zq0QgAGgr4rB60mOrape-QAIAOvbwBbeLYD6t9rbndxMKABzeCJQADMAJwhnJAAmahwIJA0QBjoAIxgGaX5VIVSYMJwQS0ldEDCjCqiYxDIQROTSnTY0KsjopABmBKS6nnCa7t64rgouIA
\begin{tikzcd}
X \times _ A P? \arrow[r] \arrow[d] & P? \arrow[d, "p"] \\
X \arrow[r, "f"]                    & A                
\end{tikzcd}

[Hexirp]

A に依存する型とは、 P? という型であり、特別な射 p : P? -> A を持ち、それは任意の対象 X と射 f : X -> A と引き戻しを成す。

[Hexirp]

A に余依存する型とは、 Q! という型であり、特別な射 q : A -> Q! を持ち、それは任意の対象 X と射 f : A -> X と押し出しを成す。

[Hexirp]

A を添字とした余積とは、 A を添字とした対象の族 P から、 Σ (x : A) P_x と生成されるものであり、 x : A に対して i_x : P_x -> Σ (x : A) P_x という射を持ち、それは任意の対象 X と射 f_x : P_x -> X が存在した時に Σ (x : A) P_x -> X が存在するという普遍性を持つ。

[Hexirp]

A を添字とした積とは、 A を添字とした対象の族 P から、 Π (x : A) P_x と生成されるものであり、 x : A に対して i_x : Π (x : A) P_x -> P_x という射を持ち、それは任意の対象 X と射 f_x : X -> P_x が存在した時に X -> Π (x : A) P_x が存在するという普遍性を持つ。

[Hexirp]

おそらく、余依存型の形式化には higher inductive type が必要なんだよな。

[Hexirp]

おそらく、余依存型の形式化には higher inductive type が必要なんだよな。

それは、 higher coinductive type が未知なことからも分かる。

[Hexirp]

A を添字とした余積は、 f : B -> A を使って、 B を添字とした余積に変基することが出来る。

[Hexirp]

A を添字とした積は、 f : A -> B を使っても、 B を添字とした積に変基することは出来ない。

[Hexirp]

A を添字とした積は、 f : B -> A を使って、 B を添字とした積に変基することが出来る。

[Hexirp]

A に依存する型は、 f : B -> A を使って、 B に依存する型に変基することが出来る。

[Hexirp]

A に余依存する型は、 f : A -> B を使って、 B に余依存する型に変基することが出来なければならない。

[Hexirp]

とすると、やはり A に余依存する型は A × Type となるべきなのであろうか？

[Hexirp]

あるいは、もしかしたら Quotient (A × Type) (λ x y. x.1 = x.1) なのかもしれない……

[Hexirp]

A → Type は fibration を作らなければならない。同様に A × Type も cofibration を作らなければならないだろう。

[Hexirp]

English Wikipedia によると、 A → X が、任意の S に対して A → S から X → S への拡張を作ることが出来る時に cofibration というらしい。

[Hexirp]

A に余依存する型とは、 Q! という型であり、特別な射 q : A -> Q! を持ち、それは任意の対象 X と射 f : A -> X と押し出しを成す。

つまり、上記の文脈で言えば Q! -> X が存在するだけで充分だということだろうか？

[Hexirp]

English Wikipedia によると、 A → X が、任意の S に対して A → S から X → S への拡張を作ることが出来る時に cofibration というらしい。

ここの A に A を X に Q! を S に X を当てはめれば Q! -> X が存在するだけで十分ということになる。

[Hexirp]

English Wikipedia によると、区間型 Interval を使って可換図式の形で条件を書くことが出来るらしい。区間型は cubical type theory に出てくるものだ。

A がある。それに余依存する型 Q! がある。 q : A → Q! がある。

このとき、任意の X に対して f : A → X から f' : Q! → X を作ることが出来る。ここで、 f x = f' (q x) が満たされる。

さらに、 H : A → Interval → X で H x 0 = f x を満たすものから H' : Q! → Interval → X で H' x 0 = f' x を満たすものを得ることが出来る。ここで、 H x 0 = H' (q x) 0 = f' (q x) が満たされる。可換図式を参照せよ。

% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZABgBpiBdUkANwEMAbAVxiRAEEQBfU9TXfIRRkAjFVqMWbAIoB+brxAZseAkRHlx9Zq0QgAkgAIAOsZwRDAZQV8Vg9aTHVtUvda7iYUAObwioADMAJwgAWyQyEHMkACZnSV0QAAkbEGCwiOpoxA0JHTYARxBqBjoAIxgGAAV+VSEQIKxvAAscVPTwnKyIJABmEvLKmrs1PUaWtvj8vQCAcnaQzrionsR+vNcQAFoACmIASgWMrpXYkqwwRKg6OGavYo3EpPmPLiA
\begin{tikzcd}
A \arrow[r, "H"] \arrow[d, "q"']             & I \to S \arrow[d, "-(0)"] \\
Q? \arrow[r, "f'"'] \arrow[ru, "H'", dashed] & S                        
\end{tikzcd}

[Hexirp]

English Wikipedia によると cofibration の実例として mapping cylinder というものがあるらしい。

これは任意の射 f : X → Y から cofibration なる射 X → M f を作ることが出来るらしい。

[Hexirp]

これを余依存型に当てはめると f : X → Y から X に余依存する型を生成することが出来ることになる。

[Hexirp]

mapping cylinder とは f : X → Y に対する Quotient (Sum (Product Interval X) Y) (R X Y f) である。

ただし、 R とは R X Y f (Sum.left (Product.pair Interval.0 x)) (Sum.right (f x)) を満たす最小の等価関係である。

[Hexirp]

M A B f は A に余依存している型を包んだものである。

[Hexirp]

あと一歩で解けそうなので、ここでもう一度まとめなおすことにしよう。

[Hexirp]

数学的帰納法を型理論に持ち込むと (P : Nat → Type) → P 0 → ((n : Nat) → P n → P (n + 1)) → (x : Nat) → P x という形になる。ここで P という依存型が現れている。

[Hexirp]

このように帰納型は依存型に関して帰納法の原理を行うことが出来る。

[Hexirp]

また、これが自分型での表現を可能にすることにも繋がっている。

[Hexirp]

一方で、余帰納型は、 (P : Type) → (P → A) → (P → P) → P → Stream A という風に、依存型を使った「余帰納法の原理」が出来ない。

[Hexirp]

こうなると、自分型での表現が出来なかったりする。

[Hexirp]

あと、 Masaki Hara さんによると終余代数であることが証明できないらしい。

そういや前も書いたけどCoqの帰納型はちゃんと始代数になってるのに余帰納型は終余代数になってない。0-cellが多すぎる(i.e. 1-cellが少なすぎる) それはまあそういう公理を各型ごとに追加すればいいんだけど関数外延性と似たモヤモヤ感がある 要するに余帰納型を作った時に0-cellの余再帰だけではなく1-cellの余再帰ができるようにすればいい気がするんだよね。それで見た目は高階帰納型の分解や関数外延性に近くなりそう(なので操作的意味論を与えようとするとホットな感じになるかもしれない) — Masaki Hara, Twitter

[Hexirp]

というわけで、過去の私は、余帰納型において、余帰納法の原理を記述するためには、余依存型が必要であるというところまで考えたのである。

CoInductive Type には Codependent type が必要 — Hexirp, Twitter

[Hexirp]

だが、余依存型とは何なのかというところで、ずっと行き詰っていた。

[Hexirp]

そこで、余依存型に求められる要件を列挙することにしたのである。

• P は A に余依存する型であるとする。このとき、 P を x : A に「適用」できなければならない。
• P は A に余依存する型であるとする。このとき、 f : A → B を使って、 B に余依存する型を得ることが出来なければならない。
• A が余帰納型であるとする。 P は A に余依存する型であるとする。このとき、 P → A を余依存化できなければならない。
• Q が A に余依存するということは、 Q! という型があり、特別な射 q : A -> Q! を持ち、それは任意の対象 X と射 f : A -> X と押し出しを成すことである。

[Hexirp]

ここで、 Q が A に余依存するとき、 Q! は cofibration であることが分かる。そして、この cofibration の型理論の内部での実例として mapping cylinder というものがある。これは、 interval type または higher inductive type を使って実装することが出来る。 HoTT/HoTT での実装のように。

[Hexirp]

問題は次の通りである。

• Q の型は何なのか？
• _! は何なのか？
• q : A → Q! は何なのか？

[Hexirp]

まず、 _! は mapping cylinder からの連想で push-out により実装されるのではないかと考えられる。

[Hexirp]

Q の型は A × Type なのではないかと考えられる。 P の型が A → Type であり、これを随伴の関係を使って裏返す。

[Hexirp]

もしかして、 _! は _.1 と _.2 による push-out とか……？

[Hexirp]

まず、上記の定義だと、 Q は変基性を満たす。そして、 Q! も、また普遍性により変基性を満たす。 x : A に「適用」するのは (t.1 = x) × t.2 で行けるか？ q は分からない。