Movatterモバイル変換


[0]ホーム

URL:


Jump to content
WikipediaThe Free Encyclopedia
Search

Semantics of type theory

From Wikipedia, the free encyclopedia
(Redirected fromCategory with families)

Thesemantics oftype theory involves several closely related types of models, which are constructed and studied in order to justify axioms and new type theories, and to use type theory as aninternal language forcategories,higher categories and other mathematical structures.

Types of models

[edit]

Categories with families

[edit]

LetFam{\displaystyle \operatorname {Fam} } denote thecategory of families of sets: an object is a family(Ai)iI{\displaystyle (A_{i})_{i\in I}} where eachAi{\displaystyle A_{i}} is a set, and a morphismf:(Ai)iI(Bj)jJ{\displaystyle f:(A_{i})_{i\in I}\to (B_{j})_{j\in J}} is a functionr:IJ{\displaystyle r:I\to J} together with, for eachiI{\displaystyle i\in I}, a functionti:AiBr(i){\displaystyle t_{i}:A_{i}\to B_{r(i)}}. (This category isequivalent to thearrow categorySet{\displaystyle \operatorname {Set} ^{\to }} ofSet{\displaystyle \operatorname {Set} } through the functor that sends a functionf:AI{\displaystyle f:A\to I} to the family(f1(i))iI{\displaystyle (f^{-1}(i))_{i\in I}}, with the natural action on morphisms.)

Acategory with families (CwF) consists of the following data:[1][2][3]

Fully unfolding the requirements results in the following presentation of CwFs as ageneralized algebraic theory.[5] (The notation(x:A)B(x){\displaystyle (x:A)\to B(x)} stands for the dependent productx:AB(x){\displaystyle \prod _{x:A}B(x)}, and curly braces denote arguments which are left implicit for readability.)

Con:Set(contexts)Sub:ConConSet(substitutions):{ΓΔΣ:Con}SubΔΓSubΣΔSubΣΓ(composition of substitutions)id:{Γ:Con}SubΓΓ(identity substitution):(ΓΔΣΘ:Con)(γ:SubΘΣ)(δ:SubΣΔ)(σ:SubΔΓ)(σδ)γ=σ(δγ)(associativity of composition):(ΓΔ:Con)(σ:SubΔΓ)σid=σ(right identity law):(ΓΔ:Con)(σ:SubΔΓ)idσ=σ(left identity law)Ty:ConSet(types)Tm:(Γ:Con)TyΓSet(terms)[]:{ΓΔ:Con}TyΓSubΔΓTyΔ(substitution in types)[]:{ΓΔ:Con}{A:TyΓ}TmA(σ:SubΔΓ)TmA[σ](substitution in terms):(ΓΔΣ:Con)(δ:SubΣΔ)(σ:SubΔΓ)(A:TyΓ)A[σδ]=A[σ][δ](functoriality of substitution in types):(Γ:Con)(A:TyΓ)A[id]=A(idem):(ΓΔΣ:Con)(δ:SubΣΔ)(σ:SubΔΓ)(A:TyΓ)(t:TmA)t[σδ]=t[σ][δ](functoriality of substitution in terms):(Γ:Con)(A:TyΓ)(t:TmA)t[id]=t(idem):Con(empty context)ε:(Γ:Con)SubΓ(substitution to the empty context):(Γ:Con)(σ:SubΓ)σ=εΓ(uniqueness of substitution to the empty context)(,):(Γ:Con)TyΓCon(context extension)wk:{Γ:Con}{A:TyΓ}Sub(Γ,A)Γ(weakening)(,):{ΓΔ:Con){A:TyΓ}(σ:SubΔΓ)TmA[σ]SubΔ(Γ,A)(substitution extension):(ΓΔΣCon)(σ:SubΔΓ)(δ:SubΣΔ)(A:TyΓ)(t:TmA[σ])(σ,t)δ=(σδ,t[δ])(naturality of substitution extension)hd:{ΓΔ:Con){A:TyΓ}(σ:SubΔ(Γ,A))TmA[wkσ](head term of a substitution):(ΓΔΣ:Con)(A:TyΓ)(σ:SubΔΓ)(δ:SubΣΔ)hd(σδ)=(hdσ)[δ](naturality of head):(ΓΔ:Con)(A:TyΓ)(σ:SubΔ(Γ,A))σ=(wkσ,hdσ)(head is inverse to substitution extension):(ΓΔ:Con)(A:TyΓ)(σ:SubΔΓ)(t:TmA[σ])hd(σ,t)=t(idem){\displaystyle {\begin{aligned}\\{\mathsf {Con}}&:{\mathsf {Set}}&&{\text{(contexts)}}\\{\mathsf {Sub}}&:{\mathsf {Con}}\to {\mathsf {Con}}\to {\mathsf {Set}}&&{\text{(substitutions)}}\\-\circ -&:\{\Gamma \,\Delta \,\Sigma :{\mathsf {Con}}\}\to {\mathsf {Sub}}\,\Delta \,\Gamma \to {\mathsf {Sub}}\,\Sigma \,\Delta \to {\mathsf {Sub}}\,\Sigma \,\Gamma &&{\text{(composition of substitutions)}}\\{\mathsf {id}}&:\{\Gamma :{\mathsf {Con}}\}\to {\mathsf {Sub}}\,\Gamma \,\Gamma &&{\text{(identity substitution)}}\\&:(\Gamma \,\Delta \,\Sigma \,\Theta :{\mathsf {Con}})(\gamma :{\mathsf {Sub}}\,\Theta \,\Sigma )\,(\delta :{\mathsf {Sub}}\,\Sigma \,\Delta )(\sigma :{\mathsf {Sub}}\,\Delta \,\Gamma )\\&\quad \to (\sigma \circ \delta )\circ \gamma =\sigma \circ (\delta \circ \gamma )&&{\text{(associativity of composition)}}\\&:(\Gamma \,\Delta :{\mathsf {Con}})\to (\sigma :{\mathsf {Sub}}\,\Delta \,\Gamma )\to \sigma \circ {\mathsf {id}}=\sigma &&{\text{(right identity law)}}\\&:(\Gamma \,\Delta :{\mathsf {Con}})\to (\sigma :{\mathsf {Sub}}\,\Delta \,\Gamma )\to {\mathsf {id}}\circ \sigma =\sigma &&{\text{(left identity law)}}\\{\mathsf {Ty}}&:{\mathsf {Con}}\to {\mathsf {Set}}&&{\text{(types)}}\\{\mathsf {Tm}}&:(\Gamma :{\mathsf {Con}})\to {\mathsf {Ty}}\,\Gamma \to {\mathsf {Set}}&&{\text{(terms)}}\\-[-]&:\{\Gamma \,\Delta :{\mathsf {Con}}\}\to {\mathsf {Ty}}\,\Gamma \to {\mathsf {Sub}}\,\Delta \,\Gamma \to {\mathsf {Ty}}\,\Delta &&{\text{(substitution in types)}}\\-[-]&:\{\Gamma \,\Delta :{\mathsf {Con}}\}\{A:{\mathsf {Ty}}\,\Gamma \}\to {\mathsf {Tm}}\,A\to (\sigma :{\mathsf {Sub}}\,\Delta \,\Gamma )\to {\mathsf {Tm}}\,A[\sigma ]&&{\text{(substitution in terms)}}\\&:(\Gamma \,\Delta \,\Sigma :{\mathsf {Con}})(\delta :{\mathsf {Sub}}\,\Sigma \,\Delta )(\sigma :{\mathsf {Sub}}\,\Delta \,\Gamma )(A:{\mathsf {Ty}}\,\Gamma )\\&\quad \to A[\sigma \circ \delta ]=A[\sigma ][\delta ]&&{\text{(functoriality of substitution in types)}}\\&:(\Gamma :{\mathsf {Con}})(A:{\mathsf {Ty}}\,\Gamma )\to A[{\mathsf {id}}]=A&&{\text{(idem)}}\\&:(\Gamma \,\Delta \,\Sigma :{\mathsf {Con}})(\delta :{\mathsf {Sub}}\,\Sigma \,\Delta )(\sigma :{\mathsf {Sub}}\,\Delta \,\Gamma )(A:{\mathsf {Ty}}\,\Gamma )(t:{\mathsf {Tm}}\,A)\\&\quad \to t[\sigma \circ \delta ]=t[\sigma ][\delta ]&&{\text{(functoriality of substitution in terms)}}\\&:(\Gamma :{\mathsf {Con}})(A:{\mathsf {Ty}}\,\Gamma )(t:{\mathsf {Tm}}\,A)\to t[{\mathsf {id}}]=t&&{\text{(idem)}}\\\diamond &:{\mathsf {Con}}&&{\text{(empty context)}}\\\varepsilon &:(\Gamma :{\mathsf {Con}})\to {\mathsf {Sub}}\,\Gamma \,\diamond &&{\text{(substitution to the empty context)}}\\&:(\Gamma :{\mathsf {Con}})(\sigma :{\mathsf {Sub}}\,\Gamma \,\diamond )\to \sigma =\varepsilon \,\Gamma &&{\text{(uniqueness of substitution to the empty context)}}\\(-,-)&:(\Gamma :{\mathsf {Con}})\to {\mathsf {Ty}}\,\Gamma \to {\mathsf {Con}}&&{\text{(context extension)}}\\{\mathsf {wk}}&:\{\Gamma :{\mathsf {Con}}\}\{A:{\mathsf {Ty}}\,\Gamma \}\to {\mathsf {Sub}}\,(\Gamma ,A)\,\Gamma &&{\text{(weakening)}}\\(-,-)&:\{\Gamma \,\Delta :{\mathsf {Con}})\{A:{\mathsf {Ty}}\,\Gamma \}\\&\quad \to (\sigma :{\mathsf {Sub}}\,\Delta \,\Gamma )\to {\mathsf {Tm}}\,A[\sigma ]\to {\mathsf {Sub}}\,\Delta \,(\Gamma ,A)&&{\text{(substitution extension)}}\\&:(\Gamma \,\Delta \,\Sigma \,{\mathsf {Con}})(\sigma :{\mathsf {Sub}}\,\Delta \,\Gamma )(\delta :{\mathsf {Sub}}\,\Sigma \,\Delta )(A:{\mathsf {Ty}}\,\Gamma )(t:{\mathsf {Tm}}\,A[\sigma ])\\&\quad \to (\sigma ,t)\circ \delta =(\sigma \circ \delta ,t[\delta ])&&{\text{(naturality of substitution extension)}}\\{\mathsf {hd}}&:\{\Gamma \,\Delta :{\mathsf {Con}})\{A:{\mathsf {Ty}}\,\Gamma \}\to (\sigma :{\mathsf {Sub}}\,\Delta \,(\Gamma ,A))\to {\mathsf {Tm}}\,A[{\mathsf {wk}}\circ \sigma ]&&{\text{(head term of a substitution)}}\\&:(\Gamma \,\Delta \,\Sigma :{\mathsf {Con}})(A:{\mathsf {Ty}}\,\Gamma )(\sigma :{\mathsf {Sub}}\,\Delta \,\Gamma )(\delta :{\mathsf {Sub}}\,\Sigma \,\Delta )\\&\quad \to {\mathsf {hd}}(\sigma \circ \delta )=({\mathsf {hd}}\,\sigma )[\delta ]&&{\text{(naturality of head)}}\\&:(\Gamma \,\Delta :{\mathsf {Con}})(A:{\mathsf {Ty}}\,\Gamma )(\sigma :{\mathsf {Sub}}\,\Delta \,(\Gamma ,A))\to \sigma =({\mathsf {wk}}\circ \sigma ,{\mathsf {hd}}\,\sigma )&&{\text{(head is inverse to substitution extension)}}\\&:(\Gamma \,\Delta :{\mathsf {Con}})(A:{\mathsf {Ty}}\,\Gamma )(\sigma :{\mathsf {Sub}}\,\Delta \,\Gamma )(t:{\mathsf {Tm}}\,A[\sigma ])\to {\mathsf {hd}}\,(\sigma ,t)=t&&{\text{(idem)}}\end{aligned}}}

Other

[edit]
[icon]
This sectionneeds expansion. You can help byadding to it.(November 2025)

Other notions of models include comprehension categories, categories with attributes and contextual categories.[4]

Interpretation of type formers

[edit]
[icon]
This section is empty. You can help byadding to it.(November 2025)

Main models

[edit]
[icon]
This sectionneeds expansion. You can help byadding to it.(November 2025)

Models of type theory include the standard model (or set model),[1][3], the term model (or syntactic model, or initial model),[1][3], the setoid model,[citation needed] the groupoid model,[6] thesimplicial set model,[7] and several models incubical sets starting with the BCH (Bezem–Coquand–Huber) model.[8]

References

[edit]
  1. ^abcHofmann, Martin (1997). "Syntax and semantics of dependent types".Extensional constructs in intensional type theory. London: Springer. pp. 13–54.doi:10.1007/978-1-4471-0963-1_2.ISBN 978-1-4471-0963-1.
  2. ^Gratzer, Daniel; Angiuli, Carlo.Principles of dependent type theory(PDF). Retrieved2025-11-21.
  3. ^abcGratzer, Daniel."Denotational semantics of type theory"(PDF).
  4. ^abCategorical semantics of dependent type theory at thenLab
  5. ^Generalized algebraic theory at thenLab
  6. ^Hofmann, Martin;Streicher, Thomas (1994). "The groupoid model refutes uniqueness of identity proofs".Proceedings of the Ninth Annual IEEE Symposium on Logic in Computer Science (LICS 1994).LICS 1994. IEEE Computer Society Press. pp. 208–212.
  7. ^Kapulkin, Chris; LeFanu Lumsdaine, Peter (2012)."The simplicial model of univalent foundations (after Voevodsky)".Journal of the European Mathematical Society.arXiv:1211.2851.doi:10.4171/JEMS/1050.
  8. ^Bezem, Marc;Coquand, Thierry; Huber, Simon (2014)."A model of type theory in cubical sets". In Matthes, Ralph; Schubert, Aleksy (eds.).19th International Conference on Types for Proofs and Programs (TYPES 2013). TYPES 2013. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 26. Schloss Daghstuhl — Leibniz Zentrum für Informatik. pp. 107–128.ISBN 978-3-939897-72-9.ISSN 1868-8969.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Semantics_of_type_theory&oldid=1325342181"
Categories:
Hidden categories:

[8]ページ先頭

©2009-2025 Movatter.jp