유도형

유형 이론에서, 시스템은 상수와 그 유형의 항을 생성하는 함수로부터 새로운 유형을 생성하는 기능을 가지고 있는 경우 귀납 유형을 가집니다.이 기능은 프로그래밍 언어의 데이터 구조와 유사한 역할을 하며 유형 이론이 숫자, 관계 및 트리와 같은 개념을 추가할 수 있도록 합니다.이름에서 알 수 있듯이, 유도 유형은 자기 참조형일 수 있지만, 일반적으로 구조 재귀를 허용하는 방식으로만 가능합니다.

표준적인 예는 Peano의 부호화를 사용하여 자연수를 부호화하는 것입니다.

 귀납적 내트 : 유형 :=      0 : 내트      S : 내트 -> 내트.

여기서 정수 "0"에서 또는 함수 "S"를 다른 자연수에 적용하여 자연수를 생성한다."S"는 숫자에 1을 더하는 것을 나타내는 후속 함수이다.따라서 "0"은 0, "S 0"은 1, "S (S 0)"는 2, "S (S 0)"는 3이 됩니다.

도입 이후, 유도 유형은 여전히 기술적이고 구조 재귀를 지원하면서도 점점 더 많은 구조를 인코딩하도록 확장되었습니다.

소거

유도형에는 일반적으로 그에 대한 특성을 증명하는 기능이 포함되어 있습니다.따라서 "nat"에는 다음이 포함될 수 있습니다.

 nat_elim : (전면적으로 P : 내트 -> 소품, (P 0) -> (전면적으로 n, P n -> P (S n)) -> (전면적으로 n, P n)).

이것은 "nat" 유형의 구조 재귀에 필요한 함수입니다.

실장

W형 및 M형

W형은 직관적 유형 이론(ITT)^[1]에서 충분히 근거가 있는 유형이다.이들은 자연수, 목록, 이진수 트리 및 기타 "트리 모양" 데이터 유형을 일반화합니다.허락하다U활자의 세계다.지정된 유형A:U및 부양가족 B:A→U ${\mathsf {W}}_{a:A}B(a)$ ${\mathsf {W}}_{a:A}B(a)$ : ${\mathsf {W}}_{a:A}B(a)$ ( ${\mathsf {W}}_{a:A}B(a)$ $){$ $displaystyle$ { $mathsf { W$ }} $_{a:$ $A}B(a$ 종류A정의되는 유도 유형의 생성자(무한히 많은)에 대해 "예측"으로 간주될 수 있지만, 반면,B는 각 컨스트럭터의 (극히 무한) 특성을 나타냅니다.W타입(응답).M-type)은 요소별로 레이블이 지정된 노드를 가진 잘 기초가 된(잘 기초가 되지 않은) 트리로 이해할 수도 있다.a:A또, 그 노드에 의해 라벨이 붙여진 장소.a가지다B(a)-다수 ^[2]서브트리각 W형은 소위 다항식 함수의 초기 대수와 동형이다.

0, 1, 2, …은 거주자₁ 1:1₂₂, 1, 2:2 등을 갖는 유한형이라고 하자.자연수를 W형이라고 정의할 수 있다.

\mathbb {N} : = mathmathsf {W}}_{x:\mathbf {2} f(x)

와 함께f: 2 →U에 의해 정의됩니다.f(1₂) = 0(인수가 필요 없는 0에 대한 생성자를 나타냄) 및f(2₂) = 1 (하나의 인수를 사용하는 후속 함수를 나타낸다.)

유형에 따라 목록을 정의할 수 있습니다.A:U $\operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x)$ $\operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x)$ ( $\operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x)$ ) : $\operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x)$ ( $\operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x)$ : $\operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x)$ + $\operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x)$ ) $\operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x)$ ( $\operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x)$ ) { $displaystyle \operatorname { List$ } ( $A):$ $=parammathsf {W}}_$ {(x $:\mathbf {1$ } $+A)}f($ x $\operatorname {List} (A):={\mathsf {W}}_{(x:\mathbf {1} +A)}f(x)$ )} 여기서

(\displaystyle {inl} (1_{\mathbf {1} })&=\mathbf {0} \f(\operatorname {inr} (a))&=\mathbf {1} \end{aligned}}

1은₁ 1의 유일한 거주자입니다.

f(\operatorname {inl} (1_{\mathbf {1} }))

f(\operatorname {inl} (1_{\mathbf {1} }))

f(\operatorname {inl} (1_{\mathbf {1} }))

f(\operatorname {inl} (1_{\mathbf {1} }))

(

f(\operatorname {inl} (1_{\mathbf {1} }))

)

f(\operatorname {inl} (1_{\mathbf {1} }))

{

displaystyle

f ( \

operatorname

{

inl

} ( 1 _ { \

mathbf { }

) } } 값은

f(\operatorname {inl} (1_{\mathbf {1} }))

빈 목록의 컨스트럭터에 대응합니다

f(\operatorname {inr} (a))

(

f(\operatorname {inr} (a))

f(\operatorname {inr} (a))

f(\operatorname {inr} (a))

) \

displaystyle

f ( \

operatorname

{

inr }

(

f(\operatorname {inr} (a))

a

f(\operatorname {inr} (a))

)

）

display display display 、、、、 apporororororor app 、、、、 app appororororororororororororororororororororororororororora다른 목록의 선두까지를 표시합니다.

${\mathsf {W}}_{x:A}B(x)$ W ${\mathsf {W}}_{x:A}B(x)$ ${\mathsf {W}}_{x:A}B(x)$ x : A ${\mathsf {W}}_{x:A}B(x)$ ( ${\mathsf {W}}_{x:A}B(x)$ x ${\mathsf {W}}_{x:A}B(x)$ ) { $displaystyle {mathsf {W}}_{x:A}B(x)}$ 요소의 ${\mathsf {W}}_{x:A}B(x)$ 생성자에 유형이 있습니다.

\displaystyle\mathsf {sup}:\displaystyle_{a:A} {\B(a)\to{mathsf {W}_{x:A}B(x){\Big}}\to{mathsf {W}_{x:A}B(x)}\to.}

이 규칙을 자연감산증명 형식으로 작성할 수도 있습니다.

{\displaystyle\frac{a:A\qquad f:B(a)\to{mathsf {W}_{x:A}B(x)}{\mathsf {sup}(a,f):{\mathsf {W}}_{x:A}B(x)}}}.

W형에 대한 제거 규칙은 나무에 대한 구조적 유도와 유사하게 작동합니다.(명제 유형 해석에 따라) $C:{\mathsf {W}}_{x:A}B(x)\to U$ : $C:{\mathsf {W}}_{x:A}B(x)\to U$ : $C:{\mathsf {W}}_{x:A}B(x)\to U$ ( $C:{\mathsf {W}}_{x:A}B(x)\to U$ ) $C:{\mathsf {W}}_{x:A}B(x)\to U$ { $displaystyle$ C $:{\mathsf {W}}_{x:A}B(x)\to$ U $}$ 속성이 $C:{\mathsf {W}}_{x:A}B(x)\to U$ 특정 트리의 모든 하위 트리에 대해 유지되면 해당 트리에 대해서도 유지되고 모든 트리에 대해서도 유지됩니다.

{w:\mathsf {W}}_{a:A}B(a)\qquad a:A,\;f:B(a)\to{mathsf {W}_{x:A}B(x),\c:\prod _{b:B(a)}C(f(b)\;\vdash \h,f,c):C({\mathsf {sup}(a,f)}}},{\mathsf {elim}}(w,h):C(w)}}}

확장형 이론에서는 W형(resp).M형)은 다항식 함수에 대한 초기 대수(resp. final colgebras)로 동형사상까지 정의할 수 있다.이 경우 초기성(res. finality)의 속성은 적절한 유도 ^[3]원리에 직접 대응한다.단가 공리를 갖는 집중형 이론에서, 이 대응은 호모토피(명제적 등식)^[4]^[5]^[6]에 부합한다.

M타입은 W타입과 이중으로 ^[7]스트림과 같은 유도성(잠재적으로 무한) 데이터를 나타냅니다.M 타입은 W ^[8]타입에서 파생할 수 있습니다.

상호 귀납적 정의

이 기술을 사용하면 서로 의존하는 여러 유형의 정의를 수행할 수 있습니다.예를 들어 Coq의 두 가지 상호 유도 유형을 사용하여 자연수에 대해 두 가지 패리티 술어를 정의합니다.

귀납적 심지어. : 내트 -> 소품 :=     0_is_짝수 : 심지어. O     S_of_홀수_짝수 : (전면적으로 n:내트, 이상한 n -> 심지어. (S n)) 와 함께 이상한 : 내트 -> 소품 :=     S_of_even_is_홀수 : (전면적으로 n:내트, 심지어. n -> 이상한 (S n)).

유도 재귀

유도 재귀는 ITT의 한계에 대한 연구로 시작되었습니다.일단 발견된 한계는 새로운 귀납 유형을 정의할 수 있는 규칙으로 바뀌었습니다.이러한 유형은 함수와 함수에 따라 달라질 수 있습니다.단, 두 유형이 동시에 정의되어 있는 경우입니다.

우주 유형은 유도 재귀를 사용하여 정의할 수 있습니다.

유도 유도

유도 유도에서는 유형과 유형군을 동시에 정의할 수 있습니다. $A타입$ 과 $B:A\to Type$ $B:A\to Type$ 는 A $B:A\to Type$ e $\displaystyle$ B $:$ $A\to$ Type $B:A\to Type$ 입니다.

고유도형

이것은 호모토피 타입 이론(HoTT)의 현재 연구 분야입니다.HoTT는 ID 타입(균등성)에 의해 ITT와 다릅니다.상위 유도 유형은 해당 유형의 요소를 생성하는 상수 및 함수를 사용하여 새로운 유형을 정의할 뿐만 아니라 해당 요소를 관련짓는 ID 유형의 새 인스턴스도 정의합니다.

단순한 예로는 $원형$ 을 들 수 있습니다.원형은 2개의 생성자(기준점)로 정의됩니다.

밑면 : 원

루프가 있습니다.

loop : base = base .

아이덴티티 타입의 새로운 생성자가 존재하기 때문에 원이 더 높은 유도 타입이 $됩니다$ .

「」를 참조해 주세요.

공유도는 유형 이론에서 무한한 구조를 가능하게 한다.

레퍼런스

^ Martin-Löf, Per (1984). Intuitionistic type theory (PDF). Sambin, Giovanni. Napoli: Bibliopolis. ISBN 8870881059. OCLC 12731401.
^ Ahrens, Benedikt; Capriotti, Paolo; Spadotti, Régis (2015-04-12). Non-wellfounded trees in Homotopy Type Theory. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 38. pp. 17–30. arXiv:1504.02949. doi:10.4230/LIPIcs.TLCA.2015.17. ISBN 9783939897873. S2CID 15020752.
^ Dybjer, Peter (1997). "Representing inductively defined sets by wellorderings in Martin-Löf's type theory". Theoretical Computer Science. 176 (1–2): 329–335. doi:10.1016/s0304-3975(96)00145-4.
^ Awodey, Steve; Gambino, Nicola; Sojakova, Kristina (2012-01-18). "Inductive types in homotopy type theory". arXiv:1201.3898 [math.LO].
^ Ahrens, Benedikt; Capriotti, Paolo; Spadotti, Régis (2015-04-12). Non-wellfounded trees in Homotopy Type Theory. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 38. pp. 17–30. arXiv:1504.02949. doi:10.4230/LIPIcs.TLCA.2015.17. ISBN 9783939897873. S2CID 15020752.
^ Awodey, Steve; Gambino, Nicola; Sojakova, Kristina (2015-04-21). "Homotopy-initial algebras in type theory". arXiv:1504.05531 [math.LO].
^ van den Berg, Benno; Marchi, Federico De (2007). "Non-well-founded trees in categories". Annals of Pure and Applied Logic. 146 (1): 40–59. arXiv:math/0409158. doi:10.1016/j.apal.2006.12.001. S2CID 360990.
^ Abbott, Michael; Altenkirch, Thorsten; Ghani, Neil (2005). "Containers: Constructing strictly positive types". Theoretical Computer Science. 342 (1): 3–27. doi:10.1016/j.tcs.2005.06.002.

Univalent Foundations Program (2013). Homotopy Type Theory: Univalent Foundations of Mathematics. Institute for Advanced Study.

외부 링크

[1] Martin-Löf, Per (1984). Intuitionistic type theory (PDF). Sambin, Giovanni. Napoli: Bibliopolis. ISBN 8870881059. OCLC 12731401.

[2] Ahrens, Benedikt; Capriotti, Paolo; Spadotti, Régis (2015-04-12). Non-wellfounded trees in Homotopy Type Theory. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 38. pp. 17–30. arXiv:1504.02949. doi:10.4230/LIPIcs.TLCA.2015.17. ISBN 9783939897873. S2CID 15020752.

[3] Dybjer, Peter (1997). "Representing inductively defined sets by wellorderings in Martin-Löf's type theory". Theoretical Computer Science. 176 (1–2): 329–335. doi:10.1016/s0304-3975(96)00145-4.

[4] Awodey, Steve; Gambino, Nicola; Sojakova, Kristina (2012-01-18). "Inductive types in homotopy type theory". arXiv:1201.3898 [math.LO].

[5] Ahrens, Benedikt; Capriotti, Paolo; Spadotti, Régis (2015-04-12). Non-wellfounded trees in Homotopy Type Theory. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 38. pp. 17–30. arXiv:1504.02949. doi:10.4230/LIPIcs.TLCA.2015.17. ISBN 9783939897873. S2CID 15020752.

[6] Awodey, Steve; Gambino, Nicola; Sojakova, Kristina (2015-04-21). "Homotopy-initial algebras in type theory". arXiv:1504.05531 [math.LO].

[7] van den Berg, Benno; Marchi, Federico De (2007). "Non-well-founded trees in categories". Annals of Pure and Applied Logic. 146 (1): 40–59. arXiv:math/0409158. doi:10.1016/j.apal.2006.12.001. S2CID 360990.

[8] Abbott, Michael; Altenkirch, Thorsten; Ghani, Neil (2005). "Containers: Constructing strictly positive types". Theoretical Computer Science. 342 (1): 3–27. doi:10.1016/j.tcs.2005.06.002.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Search

유도형

네임스페이스

더

목차

소거

실장

W형 및 M형

상호 귀납적 정의

유도 재귀

유도 유도

고유도형

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

유도형

소거

실장

W형 및 M형

상호 귀납적 정의

유도 재귀

유도 유도

고유도형

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.