\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{relation between type theory and category theory}

\hypertarget{context}{}\subsubsection*{{Context}}\label{context}

\hypertarget{type_theory}{}\paragraph*{{Type theory}}\label{type_theory}

[[!include type theory - contents]]

\hypertarget{category_theory}{}\paragraph*{{Category theory}}\label{category_theory}

[[!include category theory - contents]]

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{Overview}{Overview}\dotfill \pageref*{Overview} \linebreak
\noindent\hyperlink{Theorems}{Theorems}\dotfill \pageref*{Theorems} \linebreak
\noindent\hyperlink{FirstOrderLogic}{First-order logic and hyperdoctrines}\dotfill \pageref*{FirstOrderLogic} \linebreak
\noindent\hyperlink{DependentTypeTheory}{Dependent type theory and locally cartesian closed categories}\dotfill \pageref*{DependentTypeTheory} \linebreak
\noindent\hyperlink{TypeTheories}{Type theories}\dotfill \pageref*{TypeTheories} \linebreak
\noindent\hyperlink{category_of_contexts}{Category of contexts}\dotfill \pageref*{category_of_contexts} \linebreak
\noindent\hyperlink{internal_language}{Internal language}\dotfill \pageref*{internal_language} \linebreak
\noindent\hyperlink{HomotopyTypeTheory}{Homotopy type theory and locally cartesian closed $(\infty,1)$-categories}\dotfill \pageref*{HomotopyTypeTheory} \linebreak
\noindent\hyperlink{HomotopyWithUnivalence}{Univalent homotopy type theory and elementary $(\infty,1)$-toposes}\dotfill \pageref*{HomotopyWithUnivalence} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak
\noindent\hyperlink{References}{References}\dotfill \pageref*{References} \linebreak


\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

[[type theory|Type theory]] and certain kinds of [[category theory]] are closely related. By a [[syntax-semantics duality]] one may view type theory as a formal [[syntax|syntactic]] language or \emph{calculus} for category theory, and conversely one may think of category theory as providing [[categorical semantics|semantics]] for type theory. The flavor of category theory used depends on the flavor of type theory; this also extends to [[homotopy type theory]] and certain kinds of [[(∞,1)-category theory]].

\hypertarget{Overview}{}\subsection*{{Overview}}\label{Overview}

\begin{tabular}{l|l|l|l}
flavor of type theory&$\;$equivalent to$\;$&flavor of category theory&\\
\hline 
[[intuitionistic logic&intuitionistic]] [[propositional logic]]/[[simply-typed lambda calculus]]&&[[cartesian closed category]]\\
[[multiplicative intuitionistic linear logic]]&&symmetric [[closed monoidal category]]&(\href{linear%20type%20theory#HistoryCategoricalSemantics}{various authors since {\tt \symbol{126}}68})\\
[[first-order logic]]&&[[hyperdoctrine]]&(\hyperlink{SeelyA}{Seely 1984a})\\
[[classical linear logic]]&&[[star-autonomous category ]]&(\hyperlink{Seely89}{Seely 89})\\
extensional [[dependent type theory]]&&[[locally cartesian closed category]]&(\hyperlink{Seely}{Seely 1984b})\\
[[homotopy type theory]] without [[univalence]] (intensional M-L dependent type theory)&&[[locally cartesian closed (∞,1)-category]]&(\href{locally+cartesian+closed+%28infinity%2C1%29-category#Presentations}{Cisinski 12}-(\hyperlink{Shulman12}{Shulman 12})\\
[[homotopy type theory]] with [[higher inductive types]] and [[univalence]]&&[[elementary (∞,1)-topos]]&see [[homotopytypetheory:model of type theory in an (infinity,1)-topos\\
[[dependent linear type theory]]&&[[indexed monoidal category]] (with comprehension)&(\hyperlink{Vakar14}{V\'a{}k\'a{}r 14})\\
\end{tabular}

[[!include types and logic - table]]

\hypertarget{Theorems}{}\subsection*{{Theorems}}\label{Theorems}

We discuss here formalizations and proofs of the relation/equivalence between various flavors of type theories and the corresponding flavors of categories.

\begin{itemize}%
\item \hyperlink{FirstOrderLogic}{First order logic and hyperdoctrines}


\item \hyperlink{DependentTypeTheory}{Dependent type theory and locally cartesian closed categories}


\item \hyperlink{HomotopyTypeTheory}{Homotopy type theory and locally cartesian closed (∞,1)-categories}


\item \hyperlink{HomotopyWithUnivalence}{Univalent homotopy type theory and elementary (∞,1)-toposes}



\end{itemize}
\hypertarget{FirstOrderLogic}{}\subsubsection*{{First-order logic and hyperdoctrines}}\label{FirstOrderLogic}

\begin{theorem}
\label{}\hypertarget{}{}
The [[functors]]

\begin{itemize}%
\item $Cont$, that form a [[category of contexts]] of a [[first-order logic|first-order theory]];


\item $Lang$, that forms the [[internal language]] of a [[hyperdoctrine]]



\end{itemize}
constitute an [[equivalence of categories]]

\begin{displaymath}
FirstOrderTheories
    \stackrel{\overset{Lang}{\leftarrow}}{\underset{Cont}{\to}}
  Hyperdoctrines
  \,.
\end{displaymath}
\end{theorem}
(\hyperlink{SeelyA}{Seely, 1984a})

\hypertarget{DependentTypeTheory}{}\subsubsection*{{Dependent type theory and locally cartesian closed categories}}\label{DependentTypeTheory}

We discuss here how [[dependent type theory]] is the syntax of which [[locally cartesian closed categories]] provide the [[semantics]]. For a dedicated discussion of this (and the subtle [[coherence]] issues involved) see also at \emph{[[categorical model of dependent types]]}.

\begin{theorem}
\label{SeelyEquivalence}\hypertarget{SeelyEquivalence}{}
There are [[2-functors]]

\begin{itemize}%
\item $Cont$, that forms a [[category of contexts]] of a [[Martin-Löf dependent type theory]];


\item $Lang$ that forms the [[internal language]] of a [[locally cartesian closed category]]



\end{itemize}
that constitute an [[equivalence of 2-categories]]

\begin{displaymath}
MLDependentTypeTheories
    \underoverset
     {\underset{Cont}{\longrightarrow}}
     {\overset{Lang}{\longleftarrow}}
     {\simeq}
  LocallyCartesianClosedCategories
  \,.
\end{displaymath}
\end{theorem}
This was originally claimed as an [[equivalence of categories]] (\hyperlink{Seely}{Seely, theorem 6.3}). However, that argument did not properly treat a subtlety central to the whole subject: that [[substitution]] of [[terms]] for [[variables]] composes strictly, while its [[categorical semantics]] by [[pullback]] is by the [[universal construction|very nature]] of pullbacks only defined up to [[isomorphism]]. This problem was pointed out and ways to fix it were given in (\hyperlink{Curien}{Curien}) and (\hyperlink{Hofmann}{Hofmann}); see \emph{[[categorical model of dependent types]]} for the latter. However, the full equivalence of categories was not recovered until (\hyperlink{ClairambaultDybjer}{Clairambault-Dybjer}) solved both problems by promoting the statement to an [[equivalence of 2-categories]], see also (\hyperlink{CurienGarnerHofmann}{Curien-Garner-Hofmann}). Another approach to this which also works with [[intensional identity types]] and hence with [[homotopy type theory]] is in (\hyperlink{LumsdaineWarren13}{Lumsdaine-Warren 13}).

We now indicate some of the details.

\hypertarget{TypeTheories}{}\paragraph*{{Type theories}}\label{TypeTheories}

For definiteness, self-containedness and for references below, we say what a [[dependent type theory]] is, following (\hyperlink{Seely}{Seely, def. 1.1}).

\begin{defn}
\label{}\hypertarget{}{}
A \textbf{Martin-L\"o{}f [[dependent type theory]]} $T$ is a \emph{[[theory]]} with some [[signature (in logic)|signature]] of dependent function symbols with values in types and in terms (\ldots{}) subject to the following rules

\begin{enumerate}%
\item \textbf{type formation rules}

\begin{enumerate}%
\item $1$ is a type (the [[unit type]]);


\item if $a, b$ are terms of type $A$, then $(a = b)$ is a type (the [[equality type]]);


\item if $A$ and $B[x]$ are types, $B$ depending on a [[free variable]] of type $A$, then the following symbols are types

\begin{enumerate}%
\item $\prod_{a : A} B[a]$ ([[dependent product]]), written also $(A \to B)$ if $B[x]$ in fact does not depend on $x$;


\item $\sum_{a : A} B[a]$ ([[dependent sum]]), written also $A \times B$ if $B[x]$ in fact does not depend on $x$;



\end{enumerate}


\end{enumerate}

\item \textbf{term formation rules}

\begin{enumerate}%
\item $* \in 1$ is a term of the [[unit type]];


\item (\ldots{})



\end{enumerate}

\item \textbf{equality rules}

\begin{enumerate}%
\item (\ldots{})

\end{enumerate}


\end{enumerate}
\end{defn}
\hypertarget{category_of_contexts}{}\paragraph*{{Category of contexts}}\label{category_of_contexts}

\begin{defn}
\label{}\hypertarget{}{}
Given a [[dependent type theory]] $T$, its \textbf{[[category of contexts]]} $Con(T)$ is the category whose

\begin{itemize}%
\item [[objects]] are the [[types]] of $T$;


\item [[morphisms]] $f : A \to B$ are the [[terms]] $f$ of [[function type]] $A \to B$.



\end{itemize}
Composition is given in the evident way.

\end{defn}
\begin{prop}
\label{}\hypertarget{}{}
$Con(T)$ has [[finite limits]] and is a [[cartesian closed category]].

\end{prop}
(\hyperlink{Seely}{Seely, prop. 3.1})

\begin{proof}
Constructions are straightforward. We indicated some of them.

Notice that all [[finite limits]] (as discussed there) are induced as soon as there are all [[pullbacks]] and [[equalizers]]. A [[pullback]] in $Con(T)$

\begin{displaymath}
\itexarray{
    P &\to& A
    \\
    \downarrow && \downarrow^{\mathrlap{f}}
    \\
    B &\stackrel{g}{\to}& C
  }
\end{displaymath}
is given by

\begin{displaymath}
P \simeq \sum_{a : A} \sum_{b \in B} (f(a) = g(b))
  \,.
\end{displaymath}
The [[equalizer]]

\begin{displaymath}
P \to A \stackrel{\overset{f}{\to}}{\underset{g}{\to}} B
\end{displaymath}
is given by

\begin{displaymath}
P = \sum_{a : A} (f(a) = g(a))
  \,.
\end{displaymath}
Next, the [[internal hom]]/[[exponential object]] is given by [[function type]]

\begin{displaymath}
[A,B] \simeq (A \to B)
  \,.
\end{displaymath}
\end{proof}
\begin{prop}
\label{}\hypertarget{}{}
$Con(T)$ is a [[locally cartesian closed category]].

\end{prop}
(\hyperlink{Seely}{Seely, theorem 3.2})

\begin{proof}
Define the $Con(T)$-[[indexed category|indexed]] [[hyperdoctrine]] $P(T)$ by taking for $A \in Con(T)$ the category $P(T)(A)$ to have as objects the $A$-[[dependent types]] and as morphisms $(a : A \vdash X(a) : type) \to (a : A \vdash Y(a) : type)$ the terms of dependent function type $(a : A \vdash t : (X(a) \to Y(a)))$.

This is cartesian closed by the same kind of argument as in the previous proof. It is now sufficient to exhibit a compatible [[equivalence of categories]] with the [[slice category]] $Con(T)_{/A}$.

\begin{displaymath}
Con(T)_{/A}
   \simeq
  P(T)(A)
  \,.
\end{displaymath}
In one direction, send a morphism $f : X \to A$ to the dependent type

\begin{displaymath}
a : A \vdash f^{-1}(a) \coloneqq \sum_{x : X} (a = f(x))
  \,.
\end{displaymath}
Conversely, for $a : A \vdash X(a)$ a dependent type, send it to the projection $\sum_{a : A} X(a) \to A$.

One shows that this indeed gives an equivalence of categories which is compatible with base change (\hyperlink{Seely}{Seely, prop. 3.2.4}).

\end{proof}
\begin{defn}
\label{}\hypertarget{}{}
For $T$ a dependent type theory and $C$ a locally cartesian closed category, an \textbf{[[categorical semantics|interpretation]]} of $T$ in $C$ is a morphism of locally cartesian closed categories

\begin{displaymath}
Con(T) \to C
  \,.
\end{displaymath}
An interpretation of $T$ in another dependent type theory $T'$ is a morphism of locally cartesian closed categories

\begin{displaymath}
Con(T) \to Con(T')
  \,.
\end{displaymath}
\end{defn}
\hypertarget{internal_language}{}\paragraph*{{Internal language}}\label{internal_language}

\begin{prop}
\label{}\hypertarget{}{}
Given a [[locally cartesian closed category]] $C$, define the corresponding [[dependent type theory]] $Lang(C)$ as follows

\begin{itemize}%
\item the non-dependent types of $Lang(C)$ are the [[objects]] of $C$;


\item the $A$-dependent types are the morphisms $B \to A$;


\item a context $x_1 : X_1 , x_2 : X_2, \cdots , x_n : X_n$ is a tower of morphisms

\begin{displaymath}
\itexarray{
    X_n
    \\
    \downarrow
    \\
    \cdots
    \\
    \downarrow
    \\
    X_2
    \\
    \downarrow
    \\
    X_1
  }
\end{displaymath}

\item the terms $t[x_A] : B[x_A]$ are the [[sections]] $A \to B$ in $C_{/A}$


\item the [[equality type]] $(x_A = y_A)$ is the [[diagonal]] $A \to A \times A$


\item \ldots{}



\end{itemize}
\end{prop}
\hypertarget{HomotopyTypeTheory}{}\subsubsection*{{Homotopy type theory and locally cartesian closed $(\infty,1)$-categories}}\label{HomotopyTypeTheory}

All of the above has an analog in [[(∞,1)-category theory]] and [[homotopy type theory]].

\begin{prop}
\label{}\hypertarget{}{}
Every [[presentable (∞,1)-category|presentable]] and [[locally cartesian closed (∞,1)-category]] has a presentation by a [[type-theoretic model category]]. This provides the [[categorical semantics]] for [[homotopy type theory]] (without, possibly, the [[univalence]] [[axiom]]).

This includes in particular all ([[∞-stack]]-) [[(∞,1)-toposes]] (which should in addition satisfy [[univalence]]). See also at \emph{[[internal logic of an (∞,1)-topos]]}.

\end{prop}
Some form of this statement was originally formally conjectured in (\href{Joyal11}{Joyal 11}), following (\hyperlink{Awodey10}{Awodey 10}). For more details see at \emph{\href{locally+cartesian+closed+%28infinity%2C1%29-category#InternalLogic}{locally cartesian closed (∞,1)-category}}.

\hypertarget{HomotopyWithUnivalence}{}\subsubsection*{{Univalent homotopy type theory and elementary $(\infty,1)$-toposes}}\label{HomotopyWithUnivalence}

More precise information can be found on the \href{http://ncatlab.org/homotopytypetheory/show/model+of+type+theory+in+an+%28infinity%2C1%29-topos}{homotopytypetheory wiki}.

A ([[locally presentable (∞,1)-category|locally presentable]]) [[locally Cartesian closed (∞,1)-category]] (as \hyperlink{HomotopyTypeTheory}{above}) which in addition has a system of [[object classifiers]] is an ([[(∞,1)-category of (∞,1)-sheaves|(∞,1)-sheaf]]-)[[(∞,1)-topos]].

It has been conjectured in (\hyperlink{Awodey10}{Awodey 10}) that this [[object classifier]] is the categorical semantics of a [[univalence|univalent]] [[type universe]] ([[type of types]]), hence that [[homotopy type theory]] with [[univalence]] has categorical semantics in [[(∞,1)-toposes]]. This statement was proven for the canonical $(\infty,1)$-topos [[∞Grpd]] in (\hyperlink{KapulkinLumsdaineVoevodsky12}{Kapulkin-Lumsdaine-Voevodsky 12}), and more generally for [[(∞,1)-presheaf]] $(\infty,1)$-toposes over [[elegant Reedy categories]] in (\hyperlink{Shulman13}{Shulman 13}).

In these proofs the [[type-theoretic model categories]] which interpret the homotopy type theory syntax are required to provide type universes that behave strictly under pullback. This matches the usual syntactically convenient universes in type theory (either a la Russell or a la Tarski), but more difficult to implement in the categorical semantics. More flexibly, one may consider syntactic \href{type+of+types#TarskiStyle}{type universes weakly \`a{} la Tarski} (\href{Luo12}{Luo 12}, \hyperlink{Gallozzi14}{Gallozzi 14}). These are more complicated to work with syntactically, but should have interpretations in a ([[type-theoretic model categories]] presenting) any [[(∞,1)-topos]]. Discussion of [[univalence]] in this general flexible sense is in (\hyperlink{GepnerKock12}{Gepner-Kock 12}). For the general syntactic issue see at

\begin{itemize}%
\item [[homotopytypetheory:model of type theory in an (infinity,1)-topos]]

\end{itemize}
While [[(∞,1)-sheaf]] [[(∞,1)-toposes]] are those currently understood, the basic type theory with univalent universes does not see or care about their [[locally presentable (∞,1)-category|local presentability]] as such (although it is used in other places, such as the construction of [[higher inductive types]]). It is to be expected that there is a decent concept of [[elementary (∞,1)-topos]] such that [[homotopy type theory]] with [[univalence|univalent]] [[type universes]] and some supply of [[higher inductive types]] has categorical semantics precisely in [[elementary (∞,1)-toposes]] (as conjectured in \hyperlink{Awodey10}{Awodey 10}). But the fine-tuning of this statement is currently still under investigation.

Notice that this statement, once realized, makes (or would make) Univalent HoTT+HITs a sort of [[homotopy theory|homotopy theoretic]] refinement of [[foundations of mathematics]] in [[topos theory]] as proposed by [[William Lawvere]]. It could be compared to his [[elementary theory of the category of sets]], although being a type theory rather than a theory in first-order logic, it is more analogous to the internal type theory of an elementary topos.

\hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts}

\begin{itemize}%
\item [[categorical model of dependent types]]


\item [[syntax-semantics duality]]


\item [[computational trinitarianism]]


\item [[Awodey's conjecture]]



\end{itemize}
\hypertarget{References}{}\subsection*{{References}}\label{References}

An elementary exposition of in terms of the [[Haskell]] [[programming language]] is in

\begin{itemize}%
\item WikiBooks, \emph{\href{https://en.wikibooks.org/wiki/Haskell/The_Curry%E2%80%93Howard_isomorphism}{Haskell/The Curry--Howard isomorphism}}

\end{itemize}
The [[equivalence of categories]] between [[first order logic|first order theories]] and [[hyperdoctrines]] is discussed in

\begin{itemize}%
\item [[R. A. G. Seely]], \emph{Hyperdoctrines, natural deduction, and the Beck condition}, Zeitschrift f\"u{}r Math. Logik und Grundlagen der Math. (1984) (\href{http://www.math.mcgill.ca/rags/ZML/ZML.PDF}{pdf})

\end{itemize}
The [[categorical model of dependent types]] and initiality is discussed in

\begin{itemize}%
\item Simon Castellan, \emph{Dependent type theory as the initial category with families}, 2014 (\href{http://iso.mor.phis.me/archives/2011-2012/stage-2012-goteburg/report.pdf}{pdf})

\end{itemize}
which was formalized inside type theory with set quotients of [[higher inductive types]] in:

\begin{itemize}%
\item [[Thorsten Altenkirch]], Ambrus Kaposi, \emph{Type Theory in Type Theory using Quotient Inductive Types}, (2015) (\href{http://www.cs.nott.ac.uk/~txa/publ/tt-in-tt.pdf}{pdf}), (\href{https://bitbucket.org/akaposi/tt-in-tt}{formalisation in Agda}).

\end{itemize}
Surveys inclue

\begin{itemize}%
\item [[Tom Hirschowitz]], \emph{Introduction to categorical logic} (2010) (\href{http://www.lama.univ-savoie.fr/~hirschowitz/talks/cours.pdf}{pdf})

(see the discussion building up to the theorem on \href{http://www.lama.univ-savoie.fr/~hirschowitz/talks/cours.pdf#page=96}{slide 96})


\item Roy Crole, \emph{Deriving category theory from type theory}, Theory and Formal Methods 1993 Workshops in Computing 1993, pp 15-26


\item [[Maria Maietti]], \emph{Modular correspondence between dependent type theories and categories including pretopoi and topoi}, Mathematical Structures in Computer Science archive Volume 15 Issue 6, December 2005 Pages 1089 - 1149 (\href{https://www.mittag-leffler.se/preprints/files/IML-0001-44.pdf}{pdf})



\end{itemize}
The equivalence between [[linear logic]] and [[star-autonomous categories]] is due to

\begin{itemize}%
\item [[R. A. G. Seely]], \emph{Linear logic, $\ast$-autonomous categories and cofree coalgebras}, \emph{Contemporary Mathematics} 92, 1989. ([[SeelyLinearLogic.pdf:file]], \href{http://www.math.mcgill.ca/rags/nets/llsac.ps.gz}{ps.gz})

\end{itemize}
and reviews/further developments are in

\begin{itemize}%
\item G. M. Bierman, \emph{What is a Categorical Model of Intuitionistic Linear Logic?} (\href{http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.8687}{web})


\item Andrew Graham Barber, \emph{Linear Type Theories, Semantics and Action Calculi}, 1997 (\href{http://www.lfcs.inf.ed.ac.uk/reports/97/ECS-LFCS-97-371/&#8206;}{web}, \href{http://www.lfcs.inf.ed.ac.uk/reports/97/ECS-LFCS-97-371/ECS-LFCS-97-371.pdf}{pdf})


\item [[Paul-André Melliès]] , \emph{Categorial Semantics of Linear Logic}, in \emph{Interactive models of computation and program behaviour}, Panoramas et synth\`e{}ses 27, 2009 (\href{http://www.pps.univ-paris-diderot.fr/~mellies/papers/panorama.pdf}{pdf})



\end{itemize}
For [[dependent linear type theory]] see

\begin{itemize}%
\item [[Matthijs Vákár]], \emph{Syntax and Semantics of Linear Dependent Types} (\href{http://arxiv.org/abs/1405.0033}{arXiv:1405.0033})

\end{itemize}
An [[adjunction]] between the category of [[type theory|type theories]] with [[product types]] and [[toposes]] is discussed in chapter II of

\begin{itemize}%
\item [[Joachim Lambek]], P. Scott, \emph{Introduction to higher order categorical logic}, Cambridge University Press (1986) .

\end{itemize}
The [[equivalence of categories]] between [[locally cartesian closed categories]] and [[dependent type theories]] was originally claimed in

\begin{itemize}%
\item [[R. A. G. Seely]], \emph{Locally cartesian closed categories and type theory}, Math. Proc. Camb. Phil. Soc. (1984) 95 (\href{http://www.math.mcgill.ca/rags/LCCC/LCCC.pdf}{pdf})

\end{itemize}
following a statement earlier conjectured in

\begin{itemize}%
\item [[Per Martin-Löf]], \emph{An intuitionistic theory of types: predicative part}, In Logic Colloquium (1973), ed. H. E. Rose and J. C. Shepherdson (North-Holland, 1974), 73-118. (\href{http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.131.926}{web})

\end{itemize}
The problem with strict substitution compared to weak pullback in this argument was discussed and fixed in

\begin{itemize}%
\item [[Pierre-Louis Curien]], \emph{Substitution up to isomorphism}, Fundamenta Informaticae, 19(1,2):51--86 (1993)


\item [[Martin Hofmann]], \emph{On the interpretation of type theory in locally cartesian closed categories}, Proc. CSL `94, Kazimierz, Poland. Jerzy Tiuryn and Leszek Pacholski, eds. Springer LNCS, Vol. 933 (\href{http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.4410}{CiteSeer})



\end{itemize}
but in the process the equivalence of categories was lost. This was finally all rectified in

\begin{itemize}%
\item [[Pierre Clairambault]], [[Peter Dybjer]], \emph{The Biequivalence of Locally Cartesian Closed Categories and Martin-L\"o{}f Type Theories}, in \emph{Typed lambda calculi and applications}, Lecture Notes in Comput. Sci. 6690, Springer 2011 (\href{http://arxiv.org/abs/1112.3456}{arXiv:1112.3456})

\end{itemize}
and

\begin{itemize}%
\item [[Pierre-Louis Curien]], [[Richard Garner]], [[Martin Hofmann]], \emph{Revisiting the categorical interpretation of dependent type theory} ([[CurienGarnerHofmann.pdf:file]])

\end{itemize}
Another version of this which also applies to [[intensional identity types]] and hence to [[homotopy type theory]] is in

\begin{itemize}%
\item [[Peter LeFanu Lumsdaine]], [[Michael Warren]], \emph{An overlooked coherence construction for dependent type theory}, CT2013 ([[LumsdaineWarren2013.pdf:file]])


\item [[Peter LeFanu Lumsdaine]], [[Michael Warren]], \emph{The local universes model: an overlooked coherence construction for dependent type theories} (\href{http://arxiv.org/abs/1411.1736}{arXiv:1411.1736})



\end{itemize}
The analogous statement relating [[homotopy type theory]] and [[locally cartesian closed (infinity,1)-categories]] was formally conjectured around

\begin{itemize}%
\item [[André Joyal]], \emph{Remarks on homotopical logic}, Oberwolfach (2011) (\href{http://hottheory.files.wordpress.com/2011/06/report-11_2011.pdf#page=19}{pdf})

\end{itemize}
following earlier suggestions by [[Steve Awodey]]. Explicitly, the suggestion that with the [[univalence]] axiom added this is refined to [[(∞,1)-topos theory]] appears around

\begin{itemize}%
\item [[Steve Awodey]], \emph{Type theory and homotopy} (\href{http://www.andrew.cmu.edu/user/awodey/preprints/TTH.pdf}{pdf})

\end{itemize}
Details on this higher categorical semantics of [[homotopy type theory]] are in

\begin{itemize}%
\item [[Michael Shulman]], \emph{Univalence for inverse diagrams and homotopy canonicity}, Mathematical Structures in Computer Science, Volume 25, Issue 5 ( \emph{From type theory and homotopy theory to Univalent Foundations of Mathematics} ) June 2015 (\href{https://arxiv.org/abs/1203.3253}{arXiv:1203.3253}, \href{https://doi.org/10.1017/S0960129514000565}{doi:/10.1017/S0960129514000565})

\end{itemize}
with lecture notes in

\begin{itemize}%
\item [[Mike Shulman]], \emph{Categorical models of homotopy type theory}, April 13, 2012 (\href{https://home.sandiego.edu/~shulman/hottminicourse2012/03models.pdf}{pdf})


\item [[André Joyal]], \emph{Remarks on homotopical logic}, Oberwolfach (2011) (\href{http://hottheory.files.wordpress.com/2011/06/report-11_2011.pdf#page=19}{pdf})


\item [[André Joyal]], \emph{Categorical homotopy type theory}, March 17, 2014 (\href{http://ncatlab.org/homotopytypetheory/files/Joyal.pdf}{pdf})



\end{itemize}
See also

\begin{itemize}%
\item [[Chris Kapulkin]], \emph{Type theory and locally cartesian closed quasicategories}, Oxford 2014 (\href{https://www.youtube.com/watch?v=g87bZJ2bvYk}{video})


\item [[Chris Kapulkin]], [[Peter LeFanu Lumsdaine]], \emph{The homotopy theory of type theories} (\href{https://arxiv.org/abs/1610.00037}{arXiv:1610.00037})


\item [[Chris Kapulkin]], [[Karol Szumilo]], \emph{Internal Language of Finitely Complete $(\infty,1)$-categories} (\href{https://arxiv.org/abs/1709.09519}{arXiv:1709.09519})


\item [[Valery Isaev]], \emph{Algebraic Presentations of Dependent Type Theories} (\href{https://arxiv.org/abs/1602.08504}{arXiv:1602.08504})


\item [[Valery Isaev]], \emph{Morita equivalences between algebraic dependent type theories} (\href{https://arxiv.org/abs/1804.05045}{arXiv:1804.05045})



\end{itemize}
Models specifically in ([[constructive set theory|constructive]]) [[cubical sets]] are discussed in

\begin{itemize}%
\item Marc Bezem, [[Thierry Coquand]], Simon Huber, \emph{A model of type theory in cubical sets}, 2013 (\href{http://drops.dagstuhl.de/opus/volltexte/2014/4628/}{web}, \href{http://drops.dagstuhl.de/opus/volltexte/2014/4628/pdf/7.pdf}{pdf})


\item Ambrus Kaposi, [[Thorsten Altenkirch]], \emph{A syntax for cubical type theory} (\href{http://mazzo.li/dump/aim-kaposi-pres.pdf}{pdf})


\item Simon Docherty, \emph{A model of type theory in cubical sets with connection}, 2014 (\href{http://www.illc.uva.nl/Research/Publications/Reports/MoL-2014-12.text.pdf}{pdf})



\end{itemize}
A precise definition of [[elementary (infinity,1)-topos]] inspired by giving a natural equivalence to [[homotopy type theory]] with [[univalence]] was then proposed in

\begin{itemize}%
\item [[Mike Shulman]], \emph{Inductive and higher inductive types} (2012) (\href{http://www.sandiego.edu/~shulman/hottminicourse2012/04induction.pdf}{pdf})

\end{itemize}
Categorical semantics of [[univalence|univalent]] [[type universes]] is discussed in

\begin{itemize}%
\item [[Steve Awodey]], \emph{Type theory and homotopy} (2010) (\href{http://www.andrew.cmu.edu/user/awodey/preprints/TTH.pdf}{pdf})


\item [[Chris Kapulkin]], [[Peter LeFanu Lumsdaine]], [[Vladimir Voevodsky]], \emph{The Simplicial Model of Univalent Foundations} (\href{http://arxiv.org/abs/1211.2851}{arXiv:1211.2851})


\item [[Michael Shulman]], \emph{The univalence axiom for elegant Reedy presheaves} (\href{http://arxiv.org/abs/1307.6248}{arXiv:1307.6248})


\item [[David Gepner]], [[Joachim Kock]], \emph{Univalence in locally cartesian closed ∞-categories} (\href{http://arxiv.org/abs/1208.1749}{arXiv:1208.1749})


\item [[Denis-Charles Cisinski]], \emph{Univalent universes for elegant models of homotopy types} (\href{http://arxiv.org/abs/1406.0058}{arXiv:1406.0058})



\end{itemize}
Proof that all [[∞-stack]] [[(∞,1)-topos]] have [[presentable (∞,1)-category|presentations]] by [[model categories]] which interpret (provide [[categorical semantics]]) for [[homotopy type theory]] with [[univalence|univalent]] [[type universes]]:

\begin{itemize}%
\item [[Michael Shulman]], \emph{All $(\infty,1)$-toposes have strict univalent universes} (\href{https://arxiv.org/abs/1904.07004}{arXiv:1904.07004}).

\end{itemize}
Discussion of weak Tarskian homotopy type universes is in

\begin{itemize}%
\item [[Zhaohui Luo]], \emph{Notes on Universes in Type Theory}, 2012 (\href{http://www.cs.rhul.ac.uk/home/zhaohui/universes.pdf}{pdf})


\item [[Cesare Gallozzi]], \emph{Constructive Set Theory from a Weak Tarski Universe}, MSc thesis (2014) ([[GalloziCSTTarski.pdf:file]])



\end{itemize}
A discussion of the correspondence between type theories and categories of various sorts, from lex categories to toposes is in

\begin{itemize}%
\item Maria Emilia Maietti, \emph{Modular correspondence between dependent type theories and categories including pretopoi and topoi}, Math. Struct. in Comp. Science (2005), vol. 15, pp. 1089--1149 (\href{http://www.math.unipd.it/~maietti/papers/tumscs.ps.gz}{gzipped ps}) (\href{http://dx.doi.org/10.1017/S0960129505004962}{doi})

\end{itemize}
[[!redirects relation between category theory and type theory]] [[!redirects the relation between type theory and category theory]] [[!redirects the relation between category theory and type theory]]



\end{document}