\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*{free topos} \hypertarget{context}{}\subsubsection*{{Context}}\label{context} \hypertarget{foundations}{}\paragraph*{{Foundations}}\label{foundations} [[!include foundations - contents]] \hypertarget{topos_theory}{}\paragraph*{{Topos Theory}}\label{topos_theory} [[!include topos theory - contents]] \hypertarget{contents}{}\section*{{Contents}}\label{contents} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{properties}{Properties}\dotfill \pageref*{properties} \linebreak \noindent\hyperlink{foundations_2}{Foundations}\dotfill \pageref*{foundations_2} \linebreak \noindent\hyperlink{remark_two_properties_of_the_free_topos}{Remark: Two properties of the free topos}\dotfill \pageref*{remark_two_properties_of_the_free_topos} \linebreak \noindent\hyperlink{related_entries}{Related entries}\dotfill \pageref*{related_entries} \linebreak \noindent\hyperlink{links}{Links}\dotfill \pageref*{links} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak \hypertarget{idea}{}\subsection*{{Idea}}\label{idea} Given a [[higher-order logic|higher-order]] [[intuitionistic type theory]] $\mathfrak{L}$, it is possible to construct a [[topos]] $T(\mathfrak{L})$ out of the [[syntax]] of $\mathfrak{L}$. The \textbf{free topos} $T(\mathfrak{L}_0)$ is the result of this construction when $\mathfrak{L}_0$ is `pure' type theory i.e. the only types are 1 ([[unit type]]), $N$ ([[natural numbers type]]), and $\Omega$ ([[type of propositions]]) lacking relations beyond the bare necessities. As $\mathfrak{L}_0$ is an [[initial object]] in the appropriate category of type theories, the free topos $T(\mathfrak{L}_0)$ is itself initial in the corresponding category of toposes (with a natural numbers object) and suitable [[logical morphisms]] and is, therefore, also known as the \textbf{initial topos}\footnote{This is not to be confounded with the gadget of the same name in [[SGA4]] (1972, p.313) i.e. the topos $sh(\emptyset)$ of sheaves on the empty topological space aka the one point category, also called the \emph{empty topos} there. In this context the appropriate maps are [[geometric morphisms]].} . \hypertarget{properties}{}\subsection*{{Properties}}\label{properties} The [[internal language]] of the free topos is precisely pure (intuitionistic) higher order type theory. In 1978, [[Jim Lambek]] and [[Phil Scott]] exploited this connection in order to prove properties of intuitionistic type theory by [[proof theory|proof-theoretic]] means. It was observed by [[Peter Freyd]] then that the concept of a [[Freyd cover]] permits to give conceptual proofs of their findings. The following lemma and proposition is a replication of his ideas. \begin{lemma} \label{}\hypertarget{}{} For any [[category]] $C$ with a [[terminal object]] $\mathbf{1}$, the terminal object of the [[Freyd cover]] $\widehat{C}$ is [[small-projective]], i.e., the representable $\Gamma = \widehat{C}(1, -) \colon \widehat{C} \to Set$ preserves any colimits that exist. \end{lemma} \begin{proof} To check that $\Gamma^{op} \colon \widehat{C}^{op} \to Set^{op}$ preserves limits, it suffices to check that the composite \begin{displaymath} \widehat{C}^{op} \stackrel{\Gamma^{op}}{\to} Set^{op} \stackrel{2^-}{\to} Set \end{displaymath} preserves limits, because the contravariant power set functor $P = 2^-$ is monadic. But it is easily checked that this composite is the contravariant representable given by $(2, \mathbf{1}, 2 \to \Gamma(\mathbf{1}))$. \end{proof} \begin{theorem} \label{}\hypertarget{}{} The [[terminal object]] in the free topos $\mathcal{T}$ is [[connected object|connected]] and [[projective object|projective]] in the sense that $\Gamma = \hom(1, -) \colon \mathcal{T} \to Set$ preserves finite [[colimits]]. \end{theorem} \begin{proof} We divide the argument into three segments: \begin{itemize}% \item The [[hom-functor]] preserves [[finite limits]], so by general properties of [[Artin gluing]], the [[Freyd cover]] $\widehat{\mathcal{T}}$ is also a topos. Observe that $\mathcal{T}$ is equivalent to the [[slice category|slice]] $\widehat{\mathcal{T}}/M$ where $M$ is the object $(\emptyset, \mathbf{1}, \emptyset \to \Gamma(\mathbf{1}))$. Since pulling back to a slice is a logical functor, we have a logical functor \begin{displaymath} \pi \colon \widehat{\mathcal{T}} \to \mathcal{T} \end{displaymath} Since $\mathcal{T}$ is initial, $\pi$ is a retraction for the unique logical functor $i \colon \mathcal{T} \to \widehat{\mathcal{T}}$. \item We have maps $\mathcal{T}(1, -) \to \widehat{\mathcal{T}}(i 1, i-) \cong \widehat{\mathcal{T}}(1, i-)$ (the isomorphism comes from $i 1 \cong 1$, which is clear since $i$ is logical), and $\widehat{\mathcal{T}}(1, i-) \to \mathcal{T}(\pi 1, \pi i-) \cong \mathcal{T}(1, -)$ since $\pi$ is logical and retracts $i$. Their composite must be the identity on $\mathcal{T}(1, -)$, because there is only one such endomorphism, using the Yoneda lemma and terminality of $1$. \end{itemize} Finally, since $\mathcal{T}(1, -)$ is a retract of a functor $\widehat{\mathcal{T}}(1, i-)$ that preserves finite colimits (by the lemma, and the fact that the logical functor $i$ preserves finite colimits), it must also preserve finite colimits. \end{proof} This is important because it implies that the [[internal logic]] of the free topos satisfies the following properties: \begin{itemize}% \item The \emph{disjunction property}: if ``P [[or]] Q'' is provable in the empty [[context]], then either P is so provable, or Q is so provable. (Note that this clearly fails in the presence of [[excluded middle]].) \item The \emph{existence property}: if ``there exists an $x\in A$ such that $P(x)$'' is provable in the empty context, then there exists a [[global element]] $x\colon 1\to A$ such that $P(x)$ is provable in the empty context. (Again, this is clearly a [[constructive mathematics|constructivity]] property.) \item The \emph{negation property}: False is not provable in the empty context. \item All numerals in the free topos are ``standard'', i.e., the global sections functor $\Gamma = \hom(1, -): \mathcal{T} \to Set$ preserves the [[natural numbers object]] $N$ (because $N$ can be characterized in terms of finite colimits and $1$, by a theorem of Freyd). \end{itemize} \hypertarget{foundations_2}{}\subsubsection*{{Foundations}}\label{foundations_2} In the [[foundations of mathematics]], [[Jim Lambek]] proposed to use the free topos as ambient world to do mathematics in; see (\hyperlink{LambekWorld}{Lambek 2004}). Being syntactically constructed, but universally determined, with higher-order [[intuitionistic type theory]] as [[internal language]] he saw it as a reconciliation of the three classical schools of [[philosophy of mathematics]], namely [[formalism]], [[platonism]], and [[intuitionism]]. His latest views on this variant of categorical foundations can be found in (\hyperlink{LS11}{Lambek-Scott 2011}). \hypertarget{remark_two_properties_of_the_free_topos}{}\subsubsection*{{Remark: Two properties of the free topos}}\label{remark_two_properties_of_the_free_topos} Lambek and Scott mention in their 1986 monograph (\hyperlink{LambekScott86}{pp.viii, 233, 250}) two further remarkable properties of the free topos $\mathcal{T}$: \begin{itemize}% \item All maps $R\to R$ in the free topos represent continuous functions. Note that this is not the same as to say that Brouwer's theorem (``all functions $R\to R$ are continuous'') is true in the free topos, which is not the case. \item The natural numbers object $N$ is an (external) [[projective object]]. \end{itemize} The first result is attributed to [[André Joyal]], presumably unpublished, and for the second claim they refer to an unpublished manuscript by [[Michael Makkai]] and a manuscript by Friedman and Scedrov, presumably (\hyperlink{FriedmanScedrov83}{1983}). \hypertarget{related_entries}{}\subsection*{{Related entries}}\label{related_entries} \begin{itemize}% \item [[Freyd cover]] \item [[Artin gluing]] \item [[syntactic category]] \item [[adjoint modality]] \end{itemize} \hypertarget{links}{}\subsection*{{Links}}\label{links} \begin{itemize}% \item \href{http://mathoverflow.net/questions/264652/brouwers-theorem-in-the-free-topos}{MO Brouwer's theorem in the free topos?} \item \href{https://nforum.ncatlab.org/discussion/6665/free-topos/#Item_0}{nForum discussion} \end{itemize} \hypertarget{references}{}\subsection*{{References}}\label{references} The free topos was first constructed by H. Volger. A second construction appears in \begin{itemize}% \item [[Jim Lambek]], \emph{From Types to Sets} , JPAA \textbf{36} (1980) pp.113-164. \end{itemize} Freyd's proof of the above properties appears first in \begin{itemize}% \item [[Jim Lambek]], [[Phil Scott]], \emph{Intuitionist Type Theory and the Free Topos} , JPAA \textbf{19} (1980) pp. 215-257. \end{itemize} On the relation between the proof and the topos-theoretic techniques in the proof see \begin{itemize}% \item A. Scedrov, [[Phil Scott]], \emph{A note on the Friedman Slash and Freyd Covers} , pp. 443-452 in \emph{The LEJ Brouwer Centenary Symposium} , North Holland Amsterdam 1982. \item [[Jim Lambek]], [[Phil Scott]], \emph{New proofs of some intuitionistic principles} , Zeit. f\"u{}r Math. Logik \textbf{29} (1983) pp. 493-504. \end{itemize} For textbook accounts of the free topos see \begin{itemize}% \item [[Jim Lambek]], [[Phil Scott]], \emph{[[Introduction to Higher-Order Categorical Logic]]} , Cambridge UP 1986. (\href{https://synrc.com/publications/cat/Category%20Theory/Categorical%20Logic/Lambek%20J.,%20Scott%20P.J.%20Introduction%20to%20Higher%20Order%20Categorical%20Logic.pdf}{pdf}) \item [[Peter Freyd|P. Freyd]], A. Scedrov, \emph{[[Categories, Allegories]]} , North-Holland Amsterdam 1990. (1.(10)31, p.192) \item [[Elephant]] F3, to appear. \end{itemize} For dependent choice in intuitionistic type theory: \begin{itemize}% \item H. M. Friedman, A. Scedrov, \emph{Set existence property for intuitionistic theories with dependent choice} , APAL \textbf{25} no.2 (1983) pp.129-140. \end{itemize} For J. Lambek's views on the role of the free topos in [[foundations of mathematics]] see: \begin{itemize}% \item J. Couture, [[Jim Lambek]], \emph{Philosophical Reflections on the Foundations of Mathematics} , Erkenntnis \textbf{34} (1991) pp.187-209. \item [[Jim Lambek]], \emph{Are the traditional philosophies of mathematics really incompatible?} , Math. Intelligencer \textbf{16} (1994) pp.56--62. \item [[Jim Lambek]], \emph{What is the world of mathematics?} , APAL \textbf{126} (2004) pp.149-158. (\href{http://www.math.mcgill.ca/barr/lambek/pdffiles/WorldMath.pdf}{draft}) \item [[Jim Lambek]], [[Phil Scott]], \emph{Reflections on Categorical Foundations of Mathematics} , pp.171-185 in Sommaruga (ed.), \emph{Foundational Theories of Classical and Constructive Mathematics}, Springer New York 2011. (\href{https://www.site.uottawa.ca/~phil/papers/LS11.final.pdf}{draft}) \end{itemize} [[!redirects initial topos]] \end{document}