Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Exact completion and type-theoretic structures
Stockholm University, Faculty of Science, Department of Mathematics. (Logic)
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis consists of four papers and is a contribution to the study of representations of extensional properties in intensional type theories using, mainly, the language and tools from category theory. Our main focus is on exact completions of categories with weak finite limits as a category-theoretic description of the setoid construction in Martin-Löf's intensional type theory.

Paper I, which is joint work with Erik Palmgren, provides sufficient conditions for such an exact completion to produce a model of the system CETCS (Constructive Elementary Theory of the Category of Sets), a finite axiomatisation of the theory of well-pointed locally cartesian closed pretoposes with a natural numbers object and enough projectives. In particular, we use a condition inspired by Aczel's set-theoretic Fullness Axiom to obtain the local cartesian closure of an exact completion. As an application, we obtain a simple  uniform proof that the category of setoids is a model of CETCS.

Paper II was prompted by the discovery of an overlooked issue in the characterisationof local cartesian closure for exact completions due to Carboni and Rosolini. In this paper we clarify the problem, show that their characterisation is still valid when the base category has finite limits, and provide a complete solution in the general case of a category with weak finite limits.

In paper III we generalise the approach used in paper I to obtain the local cartesian closure of an exact completion to arbitrary categories with finite limits. We then show how this condition inspired by the Fullness Axiom naturally arises in several homotopy categories and apply this result to obtain the local cartesian closure of the exact completion of the homotopy category of spaces, thus answering a question left open by Marino Gran and Enrico Vitale.

Finally, in paper IV we abandon the pure category-theoretic approach and instead present a type-theoretic construction, formalised in Coq, of W-types in the category of setoids from dependent W-types in the underlying intensional theory. In particular, contrary to previous approaches, this construction does not require the assumption of Uniqueness of Identity Proofs nor recursion into a type universe.

Place, publisher, year, edition, pages
Stockholm: Department of Mathematics, Stockholm University , 2019. , p. 23
Keywords [en]
exact completion, type theory, setoid, weak limits, cartesian closure, inductive types
National Category
Algebra and Logic
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:su:diva-162275ISBN: 978-91-7797-526-7 (print)ISBN: 978-91-7797-527-4 (electronic)OAI: oai:DiVA.org:su-162275DiVA, id: diva2:1264924
Public defence
2019-01-18, sal 14, hus 5, Kräftriket, Roslagsvägen 101, Stockholm, 13:00 (English)
Opponent
Supervisors
Note

At the time of the doctoral defense, the following papers were unpublished and had a status as follows: Paper 1: Manuscript. Paper 2: Manuscript. Paper 3: Manuscript. Paper 4: Manuscript.

Available from: 2018-12-19 Created: 2018-11-21 Last updated: 2018-12-07Bibliographically approved
List of papers
1. Exact completion and constructive theories of sets
Open this publication in new window or tab >>Exact completion and constructive theories of sets
(English)Manuscript (preprint) (Other academic)
Abstract [en]

In the present paper we use the theory of exact completions to study categorical properties of small setoids in Martin-Loef type theory and, more generally, of models of the Constructive Elementary Theory of the Category of Sets, in terms of properties of their subcategories of choice objects (i.e. objects satisfying the axiom of choice). Because of these intended applications, we deal with categories that lack equalisers and just have weak ones, but whose objects can be regarded as collections of global elements. In this context, we study the internal logic of the categories involved, and employ this analysis to give a sufficient condition for the local cartesian closure of an exact completion. Finally, we apply this result to show when an exact completion produces a model of CETCS.

Keywords
setoids, exact completion, local cartesian closure, constructive set theory, categorical logic
National Category
Algebra and Logic
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-151876 (URN)
Available from: 2018-01-19 Created: 2018-01-19 Last updated: 2018-11-21Bibliographically approved
2. On the local cartesian closure of exact completions
Open this publication in new window or tab >>On the local cartesian closure of exact completions
(English)Manuscript (preprint) (Other academic)
Abstract [en]

A characterisation of cartesian closure of exact completions as a property of the projective objects was given by Carboni and Rosolini. We show that the argument used to prove that characterisation is equivalent to the projectives being closed under binary products (equivalently, being internally projective). The property in question is the existence of weak simple products (a slight strengthening of weak exponentials) and the argument used relies on two claims: that weak simple products endow the internal logic with universal quantification, and that an exponential is the quotient of a weak exponential. We show that either these claims hold if and only if the projectives are internally projectives, which entails that Carboni and Rosolini's characterisation only applies to ex/lex completions. We then argue that this limitation depends on the universal property of weak simple products, and derive from this observation an alternative notion, which we call generalised weak simple product. We conclude by showing that existence of generalised weak simple products in the subcategory of projectives is equivalent to the cartesian closure of the exact category, thus obtaining a complete characterisation of (local) cartesian closure for exact completions of categories with weak finite limits.

Keywords
Exact completion, local cartesian closure, weak limits, internal projective objects
National Category
Algebra and Logic
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-159377 (URN)
Available from: 2018-08-28 Created: 2018-08-28 Last updated: 2019-03-29
3. The Fullness Axiom and exact completions of homotopy categories
Open this publication in new window or tab >>The Fullness Axiom and exact completions of homotopy categories
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We use a category-theoretic formulation of Aczel's Fullness Axiom from Constructive Set Theory to derive the local cartesian closure of an exact completion. As an application, we prove that such a formulation is valid in the homotopy category of any model category satisfying mild requirements, thus obtaining in particular the local cartesian closure of the exact completion of topological spaces and homotopy classes of maps. Under a type-theoretic reading, these results provide a general motivation for the local cartesian closure of the category of setoids. However, results and proofs are formulated solely in the language of categories, and no knowledge of type theory or constructive set theory is required on the reader's part.

National Category
Algebra and Logic
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-162273 (URN)
Available from: 2018-11-21 Created: 2018-11-21 Last updated: 2019-01-20Bibliographically approved
4. W-types in setoids
Open this publication in new window or tab >>W-types in setoids
(English)Manuscript (preprint) (Other academic)
Abstract [en]

W-types and their categorical analogue, initial algebras for polynomial endofunctors, are an important tool in predicative systems to replace transfinite recursion on well-orderings. Current arguments to obtain W-types in quotient completions rely on assumptions, like Uniqueness of Identity Proofs, or on constructions that involve recursion into a universe, that limit their applicability to a specific setting. We present an argument, verified in Coq, that instead uses dependent W-types in the underlying type theory to construct W-types in the setoid model. The immediate advantage is to have a proof more type-theoretic in flavour, which directly uses recursion on the underlying W-type to prove initiality. Furthermore, taking place in intensional type theory and not requiring any recursion into a universe, it may be generalised to various categorical quotient completions, with the aim of finding a uniform construction of extensional W-types.

National Category
Algebra and Logic
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-162274 (URN)
Available from: 2018-11-21 Created: 2018-11-21 Last updated: 2019-01-20Bibliographically approved

Open Access in DiVA

Exact completion and type-theoretic structures(723 kB)54 downloads
File information
File name FULLTEXT01.pdfFile size 723 kBChecksum SHA-512
c2060c2a1ec2387725d6def7eb78f3dad76915473069c4a9308a8b56bb202688eb89e2c0165b93ba6ef6c800145222f24048340a6a177824eb090c81fd2a662e
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Emmenegger, Jacopo
By organisation
Department of Mathematics
Algebra and Logic

Search outside of DiVA

GoogleGoogle Scholar
Total: 54 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 742 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf