tag:blogger.com,1999:blog-66082365615176585572020-08-05T19:33:02.600+00:00Auke Booij's programming and logicAukehttp://www.blogger.com/profile/12557099016349698408noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6608236561517658557.post-1623975073600538062020-06-22T08:00:00.001+00:002020-07-22T13:21:21.598+00:00Extensional constructive real analysis via locators<div>This is an announcement of a paper in the areas of constructive mathematics, (univalent) type theory, and exact real arithmetic.<br /></div><div><br /></div><div>Abstract: Real numbers do not admit an extensional procedure for observing discrete information, such as the first digit of its decimal expansion, because every extensional, computable map from the reals to the integers is constant, as is well known. We overcome this by considering real numbers equipped with additional structure, which we call a locator. With this structure, it is possible, for instance, to construct a signed-digit representation or a Cauchy sequence, and conversely these intensional representations give rise to a locator. Although the constructions are reminiscent of computable analysis, instead of working with a notion of computability, we simply work constructively to extract observable information, and instead of working with representations, we consider a certain locatedness structure on real numbers. <br /></div><div><br /></div><div>To appear in the MSCS <a href="https://hott-uf.github.io/special-issue-17-18/">Special Issue on Homotopy Type Theory and Univalent Foundations</a> (<a href="http://export.arxiv.org/abs/1805.06781">preprint on the arXiv</a>). This work is also discussed in some more generality in my <a href="https://abooij.blogspot.com/p/phd-thesis.html">PhD thesis</a>.<br /></div>Aukehttp://www.blogger.com/profile/12557099016349698408noreply@blogger.com0tag:blogger.com,1999:blog-6608236561517658557.post-84930214577063211762017-06-20T08:00:00.003+00:002020-07-22T13:21:59.479+00:00The HoTT book reals coincide with the Escardó-Simpson reals<p>This is an announcement of a paper in the area of univalent type theory and exact real arithmetic.</p><p>Escardó and Simpson defined a notion of interval object by a universal property in any category with binary products. The Homotopy Type Theory book defines a higher-inductive notion of reals, and suggests that the interval may satisfy this universal property. We show that this is indeed the case in the category of sets of any universe. We also show that the type of HoTT book reals is the least Cauchy complete subset of the Dedekind reals containing the rationals.<br /></p><p>Preprint is on the <a href="https://arxiv.org/abs/1706.05956">arXiv</a>.</p><p>Somewhat stronger results can be found in Chapter 5 of my <a href="https://abooij.blogspot.com/p/phd-thesis.html">PhD thesis</a>. I intend to publish these results at a later stage.<br /></p>Aukehttp://www.blogger.com/profile/12557099016349698408noreply@blogger.com0tag:blogger.com,1999:blog-6608236561517658557.post-11940254781783918382016-12-01T09:00:00.001+00:002020-07-22T13:21:19.674+00:00Parametricity, automorphisms of the universe, and excluded middle<div>This is an announcement of a paper in the area of type theory and parametricity.<br /></div><div><br /></div><div>Specific violations of parametricity, or existence of non-identity automorphisms of the universe, can be used to prove classical axioms. The former was <a href="https://homotopytypetheory.org/2016/02/24/parametricity-and-excluded-middle/">previously featured</a> on the Homotopy Type Theory blog, and the latter is part of <a href="https://groups.google.com/forum/#!searchin/homotopytypetheory/automorphisms|sort:relevance/homotopytypetheory/8CV0S2DuOI8/0XibNKHou1EJ">a discussion on the HoTT mailing list</a>. In a cooperation between Martín Escardó, Peter Lumsdaine, Mike Shulman, and myself, we have strengthened these results and recorded them in a <a href="https://doi.org/10.4230/LIPIcs.TYPES.2016.7">paper that is published in the post-proceedings of TYPES 2016</a> (see also the <a href="https://arxiv.org/abs/1701.05617">preprint on arXiv</a>).</div>Aukehttp://www.blogger.com/profile/12557099016349698408noreply@blogger.com0