3,028 research outputs found
Modalities in homotopy type theory
No full textUnivalent homotopy type theory (HoTT) may be seen as a language for the
category of -groupoids. It is being developed as a new foundation for
mathematics and as an internal language for (elementary) higher toposes. We
develop the theory of factorization systems, reflective subuniverses, and
modalities in homotopy type theory, including their construction using a
"localization" higher inductive type. This produces in particular the
(-connected, -truncated) factorization system as well as internal
presentations of subtoposes, through lex modalities. We also develop the
semantics of these constructions
Computer Verified Exact Analysis (Tutorial)
No full textThis tutorial will illustrate how to use the Coq proof assistant to implement effective and provably correct computation for analysis. Coq provides a dependently typed functional programming language that allows users to specify both programs and formal proofs.
We will introduce dependent type theory and show how it can be used to develop both mathematics and programming. We will show how to use dependent type theory to implement constructive analysis. Specifically we will cover how to implement effective real numbers and effective integration.
This work will be done using the Coq proof assistant. The tutorial will cover how to use the Coq proof assistant. Attendees are encouraged to download and install Coq 8.2 from {\tt http://coq.inria.fr/download} and also download and make the full system of C-CoRN from {\tt http://c-corn.cs.ru.nl/download.html} beforehand
Constructive algebraic integration theory without choice
No full textContains fulltext :
32357.pdf (Author’s version preprint ) (Open Access
Finding Smart Contract Vulnerabilities with ConCert’s Property-Based Testing Framework
No full textWe provide three detailed case studies of vulnerabilities in smart contracts, and show how property based testing would have found them: 1. the Dexter1 token exchange; 2. the iToken; 3. the ICO of Brave’s BAT token. The last example is, in fact, new, and was missed in the auditing process.
We have implemented this testing in ConCert, a general executable model/specification of smart contract execution in the Coq proof assistant. ConCert contracts can be used to generate verified smart contracts in Tezos' LIGO and Concordium’s rust language. We thus show the effectiveness of combining formal verification and property-based testing of smart contracts
Internal Universes in Models of Homotopy Type Theory
No full textWe begin by recalling the essentially global character of universes in various models of homotopy type theory, which prevents a straightforward axiomatization of their properties using the internal language of the presheaf toposes from which these model are constructed. We get around this problem by extending the internal language with a modal operator for expressing properties of global elements. In this setting we show how to construct a universe that classifies the Cohen-Coquand-Huber-Mörtberg (CCHM) notion of fibration from their cubical sets model, starting from the assumption that the interval is tiny - a property that the interval in cubical sets does indeed have. This leads to an elementary axiomatization of that and related models of homotopy type theory within what we call crisp type theory
Guarded Cubical Type Theory: Path Equality for Guarded Recursion
No full textThis paper improves the treatment of equality in guarded dependent type theory (GDTT), by combining it with cubical type theory (CTT). GDTT is an extensional type theory with guarded recursive types, which are useful for building models of program logics, and for programming and reasoning with coinductive types. We wish to implement GDTT with decidable type checking, while still supporting non-trivial equality proofs that reason about the extensions of guarded recursive constructions. CTT is a variation of Martin-Löf type theory in which the identity type is replaced by abstract paths between terms. CTT provides a computational interpretation of functional extensionality, is conjectured to have decidable type checking, and has an implemented type checker. Our new type theory, called guarded cubical type theory, provides a computational interpretation of extensionality for guarded recursive types. This further expands the foundations of CTT as a basis for formalisation in mathematics and computer science. We present examples to demonstrate the expressivity of our type theory, all of which have been checked using a prototype type-checker implementation, and present semantics in a presheaf category
The principle of general tovariance
No full textWe tentatively propose two guiding principles for the construction of theories of physics, which should be satisfied by a possible future theory of quantum gravity. These principles are inspired by those that led Einstein to his theory of general relativity, viz. his principle of general covariance and his equivalence principle, as well as by the two mysterious dogmas of Bohr's interpretation of quantum mechanics, i.e. his doctrine of classical concepts and his principle of complementarity. An appropriate mathematical language for combining these ideas is topos theory, a framework earlier proposed for physics by Isham and collaborators. Our "Principle of general tovariance" states that any mathematical structure appearing in the laws of physics must be definable in an arbitrary topos (with natural numbers object) and must be preserved under so-called geometric morphisms. This principle identifies geometric logic as the mathematical language of physics and restricts the constructions and theorems to those valid in intuitionism: neither Aristotle's principle of the excluded third nor Zermelo's Axiom of Choice may be invoked. Subsequently, our "Equivalence principle" states that any algebra of observables (initially defined in the topos Sets) is empirically equivalent to a commutative one in some other topos
Gelfand spectra in Grothendieck toposes using geometric mathematics
No full textIn the (covariant) topos approach to quantum theory by Heunen, Landsman and Spitters, one associates to each unital C*-algebra A a topos T (A) of sheaves on a locale and a commutative C*-algebra A within that topos. The Gelfand spectrum of A is a locale Σ in this topos, which is equivalent to a bundle over the base locale. We further develop this external presentation of the locale Σ, by noting that the construction of the Gelfand spectrum in a general topos can be described using geometric logic. As a consequence, the spectrum, seen as a bundle, is computed fibrewise. As a by-product of the geometricity of Gelfand spectra, we find an explicit external description of the spectrum whenever the topos is a functor category. As an intermediate result we show that locally perfect maps compose, so that the externalization of a locally compact locale in a topos of sheaves over a locally compact locale is locally compact, too.
Intuitionistic quantum logic of an n-level system
No full textA decade ago, Isham and Butterfield proposed a topos theoretic approach to quantum mechanics, which meanwhile has been extended by Doering and Isham so as to provide a new mathematical foundation for all of physics. Last year, three of the present authors redeveloped and refined these ideas by combining the C*-algebraic approach to quantum theory with the so-called internal language of topos theory (see arXiv:0709.4364). The goal of the present paper is to illustrate our abstract setup through the concrete example of the C*-algebra M_n(C) of complex n x n matrices. This leads to an explicit expression for the pointfree quantum phase space and the associated logical structure and Gelfand transform of an n-level system. We also determine the pertinent non-probabilisitic state-proposition pairing (or valuation) and give a very natural topos-theoretic reformulation of the Kochen-Specker Theorem. In our approach, the nondistributive lattice P(M_n(C)) of projections in M_n(C)(which forms the basis of the traditional quantum logic of Birkhoff and von Neumann)is replaced by a specific distributive lattice of functions from the poset of all unital commutative C*-subalgebras of M_n(C) to P(M_n(C)). The latter lattice is essentially the (pointfree) topology of the quantum phase space mentioned above, and as such defines a Heyting algebra. Each element of the lattice corresponds to a ``Bohrified'' proposition, in the sense that to each classical context it associates a yes-no question pertinent to this context, rather than being a single projection as in standard quantum logic. Distributivity is recovered at the expense of the law of the excluded middle (Tertium Non Datur), whose demise is in our opinion to be welcomed, not just in intuitionistic logic in the spirit of Brouwer, but also in quantum logic in the spirit of von Neumann
Constructive Results on Operator Algebras
No full textContains fulltext :
32356.pdf (Publisher’s version ) (Open Access
- …
