To the top

Page Manager: Webmaster
Last update: 9/11/2012 3:13 PM

Tell a friend about this page
Print version

THE INDEPENDENCE OF MARKO… - University of Gothenburg, Sweden Till startsida
Sitemap
To content Read more about how we use cookies on gu.se

THE INDEPENDENCE OF MARKOV'S PRINCIPLE IN TYPE THEORY

Journal article
Authors Thierry Coquand
B. Mannaa
Published in Logical Methods in Computer Science
Volume 13
Issue 3
ISSN 1860-5974
Publication year 2017
Published at Department of Computer Science and Engineering (GU)
Language en
Links dx.doi.org/10.23638/lmcs-13(3:10)20...
Keywords Forcing, Dependent type theory, Markovs Principle, Computer Science, Science & Technology
Subject categories Computer and Information Science

Abstract

In this paper, we show that Markov's principle is not derivable in dependent type theory with natural numbers and one universe. One way to prove this would be to remark that Markov's principle does not hold in a sheaf model of type theory over Cantor space, since Markov's principle does not hold for the generic point of this model [CMR17]. Instead we design an extension of type theory, which intuitively extends type theory by the addition of a generic point of Cantor space. We then show the consistency of this extension by a normalization argument. Markov's principle does not hold in this extension, and it follows that it cannot be proved in type theory.

Page Manager: Webmaster|Last update: 9/11/2012
Share:

The University of Gothenburg uses cookies to provide you with the best possible user experience. By continuing on this website, you approve of our use of cookies.  What are cookies?