ABAndrej Bauer

Andrej Bauer

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Andrej Bauer has a total of 19 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Spreen spaces and the synthetic Kreisel-Lacombe-Shoenfield-Tseitin theorem

    by Andrej Bauer

    I take a constructive look at Dieter Spreen's treatment of effective topological spaces and the Kreisel-Lacombe-Shoenfield-Tseitin (KLST) continuity theorem. Transferring Spreen's ideas from classical computability theory and numbered sets to a constructive setting leads to a theory of topological spaces, in fact two of them: a locale-theoretic one embodied by the notion of $σ$-frames, and a pointwise one that follows more closely traditional topology. Spreen's notion of effective limit passing turns out to be closely related to sobriety, while his witnesses for non-inclusion give rise to a novel separation property - any point separated from an overt subset by a semidecidable subset is already separated from it by an open one. I name spaces with this property Spreen spaces, and show that they give rise to a purely constructive continuity theorem: every map from an overt Spreen space to a pointwise regular space is pointwise continuous. The theorem is easily proved, but finding non-trivial examples of Spreen spaces is harder. I show that they are plentiful in synthetic computability theory.

    • 6 June 2020
      • Vol. 12097, 253-259

    Equality Checking for General Type Theories in Andromeda 2

    by Andrej Bauer, Philipp G. Haselwarter, Anja Petković

    We designed a user-extensible judgemental equality checking algorithm for general type theories that supports computation rules and extensionality rules. The user needs only provide the equality rules they wish to use, after which the algorithm devises an appropriate notion of normal form. The algorithm is a generalization of type-directed equality checking for Martin-Löf type theory, and we implemented it in the Andromeda 2 prover.

  • Open Access

    Every metric space is separable in function realizability

    by Andrej Bauer, Andrew Swan

    We first show that in the function realizability topos every metric space is separable, and every object with decidable equality is countable. More generally, working with synthetic topology, every $T_0$-space is separable and every discrete space is countable. It follows that intuitionistic logic does not show the existence of a non-separable metric space, or an uncountable set with decidable equality, even if we assume principles that are validated by function realizability, such as Dependent and Function choice, Markov's principle, and Brouwer's continuity and fan principles.

  • Open Access

    What is algebraic about algebraic effects and handlers?

    by Andrej Bauer

    This note recapitulates and expands the contents of a tutorial on the mathematical theory of algebraic effects and handlers which I gave at the Dagstuhl seminar 18172 "Algebraic effect handlers go mainstream". It is targeted roughly at the level of a doctoral student with some amount of mathematical training, or at anyone already familiar with algebraic effects and handlers as programming concepts who would like to know what they have to do with algebra. We draw an uninterrupted line of thought between algebra and computational effects. We begin on the mathematical side of things, by reviewing the classic notions of universal algebra: signatures, algebraic theories, and their models. We then generalize and adapt the theory so that it applies to computational effects. In the last step we replace traditional mathematical notation with one that is closer to programming languages.


  • Open Access

    Design and Implementation of the Andromeda Proof Assistant

    by Andrej Bauer, Gaëtan Gilbert, Philipp G. Haselwarter, Matija Pretnar, Christopher A. Stone

    Andromeda is an LCF-style proof assistant where the user builds derivable judgments by writing code in a meta-level programming language AML. The only trusted component of Andromeda is a minimalist nucleus (an implementation of the inference rules of an object-level type theory), which controls construction and decomposition of type-theoretic judgments. Since the nucleus does not perform complex tasks like equality checking beyond syntactic equality, this responsibility is delegated to the user, who implements one or more equality checking procedures in the meta-language. The AML interpreter requests witnesses of equality from user code using the mechanism of algebraic operations and handlers. Dynamic checks in the nucleus guarantee that no invalid object-level derivations can be constructed. %even if the AML code (or interpreter) is untrusted. To demonstrate the flexibility of this system structure, we implemented a nucleus consisting of dependent type theory with equality reflection. Equality reflection provides a very high level of expressiveness, as it allows the user to add new judgmental equalities, but it also destroys desirable meta-theoretic properties of type theory (such as decidability and strong normalization). The power of effects and handlers in AML is demonstrated by a standard library that provides default algorithms for equality checking, computation of normal forms, and implicit argument filling. Users can extend these new algorithms by providing local "hints" or by completely replacing these algorithms for particular developments. We demonstrate the resulting system by showing how to axiomatize and compute with natural numbers, by axiomatizing the untyped $\lambda$-calculus, and by implementing a simple automated system for managing a universe of types.

  • Open Access

    On fixed-point theorems in synthetic computability

    by Andrej Bauer

    Lawvere’s fixed point theorem captures the essence of diagonalization arguments. Cantor’s theorem, Gödel’s incompleteness theorem, and Tarski’s undefinability of truth are all instances of the contrapositive form of the theorem. It is harder to apply the theorem directly because non-trivial examples are not easily found, in fact, none exist if excluded middle holds. We study Lawvere’s fixed-point theorem in synthetic computability, which is higher-order intuitionistic logic augmented with the Axiom of Countable Choice, Markov’s principle, and the Enumeration axiom, which states that there are countably many countable subsets of ℕ. These extra-logical principles are valid in the effective topos, as well as in any realizability topos built over Turing machines with an oracle, and suffice for an abstract axiomatic development of a computability theory. We show that every countably generated ω-chain complete pointed partial order (ωcppo) is countable, and that countably generated ωcppos are closed under countable products. Therefore, Lawvere’s fixed-point theorem applies and we obtain fixed points of all endomaps on countably generated ωcppos. Similarly, the Knaster-Tarski theorem guarantees existence of least fixed points of continuous endomaps. To get the best of both theorems, namely that all endomaps on domains (ωcppos generated by a countable set of compact elements) have least fixed points, we prove a synthetic version of the Myhill-Shepherdson theorem: every map from an ωcpo to a domain is continuous. The proof relies on a new fixed-point theorem, the synthetic Recursion Theorem, so called because it subsumes the classic Kleene-Rogers Recursion Theorem. The Recursion Theorem takes the form of Lawvere’s fixed point theorem for multi-valued endomaps.


  • Open Access

    Continuity, computability, constructivity: from logic to algorithms 2014 (Preface to the special issue: Continuity, Computability, Constructivity: From Logic to Algorithms 2014)

    by Andrej Bauer, Ulrich Berger, Willem Fouché, Dieter Spreen, Hideki Tsuiki, Martin Ziegler

    Continuity, computability, constructivity: from logic to algorithms 2014 (Preface to the special issue: Continuity, Computability, Constructivity: From Logic to Algorithms 2014)

  • Five stages of accepting constructive mathematics

    by Andrej Bauer

    On the odd day, a mathematician might wonder what constructive mathematics is all about. They may have heard arguments in favor of constructivism but are not at all convinced by them, and in any case they may care little about philosophy. A typical introductory text about constructivism spends a great deal of time explaining the principles and contains only trivial mathematics, while advanced constructive texts are impenetrable, like all unfamiliar mathematics. How then can a mathematician find out what constructive mathematics feels like? What new and relevant ideas does constructive mathematics have to offer, if any? I shall attempt to answer these questions.


  • Open Access

    An Effect System for Algebraic Effects and Handlers

    by Andrej Bauer, Matija Pretnar

    We present an effect system for core Eff, a simplified variant of Eff, which is an ML-style programming language with first-class algebraic effects and handlers. We define an expressive effect system and prove safety of operational semantics with respect to it. Then we give a domain-theoretic denotational semantics of core Eff, using Pitts's theory of minimal invariant relations, and prove it adequate. We use this fact to develop tools for finding useful contextual equivalences, including an induction principle. To demonstrate their usefulness, we use these tools to derive the usual equations for mutable state, including a general commutativity law for computations using non-interfering references. We have formalized the effect system, the operational semantics, and the safety theorem in Twelf.


  • An injection from the Baire space to natural numbers

    by Andrej Bauer

    We provide a realizability model based on infinite time Turing machines in which there is an injection from the internal Baire space, the object of infinite sequences of numbers, to the object of natural numbers.