Andrej Bauer
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Andrej Bauer has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
- Philipp G. Haselwarter
Aarhus University, Aarhus, Denmark
2 shared publications - Alex Simpson
LFCS, School of Informatics, University of Edinburgh, Scotland, UK
1 shared publication - Andrew Swan
University of Ljubljana
1 shared publication - Anja Petković
Faculty of Mathematics and Physics Faculty of Mathematics and Physics University of Ljubljana University of Ljubljana
1 shared publication - Christopher A. Stone
Harvey Mudd College
1 shared publication - Dieter Spreen
University of Siegen, Siegen, Germany
1 shared publication
Latest Publications
- Open Access
Spreen spaces and the synthetic Kreisel-Lacombe-Shoenfield-Tseitin theorem
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.
Open AccessSpreen spaces and the synthetic Kreisel-Lacombe-Shoenfield-Tseitin theorem
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
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.
- 6 June 2020
- Vol. 12097, 253-259
Equality Checking for General Type Theories in Andromeda 2
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
- 23 May 2019
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 15, Is
Every metric space is separable in function realizability
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.
- 23 May 2019
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 15, Is
Open AccessEvery metric space is separable in function realizability
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?
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 AccessWhat is algebraic about algebraic effects and handlers?
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
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 AccessDesign and Implementation of the Andromeda Proof Assistant
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
- 1 June 2017
- Published by Tbilisi Centre for Mathematical Sciences in Tbilisi Mathematical Journal
- Vol. 10 (3) , 167-181
On fixed-point theorems in synthetic computability
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.
- 1 June 2017
- Published by Tbilisi Centre for Mathematical Sciences in Tbilisi Mathematical Journal
- Vol. 10 (3) , 167-181
Open AccessOn fixed-point theorems in synthetic computability
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
- 1 January 2017
- Published by Journal of Logic and Analysis in Journal of Logic and Analysis
- Vol. 9
Continuity, computability, constructivity: from logic to algorithms 2014 (Preface to the special issue: Continuity, Computability, Constructivity: From Logic to Algorithms 2014)
Continuity, computability, constructivity: from logic to algorithms 2014 (Preface to the special issue: Continuity, Computability, Constructivity: From Logic to Algorithms 2014)
- 1 January 2017
- Published by Journal of Logic and Analysis in Journal of Logic and Analysis
- Vol. 9
Open AccessContinuity, computability, constructivity: from logic to algorithms 2014 (Preface to the special issue: Continuity, Computability, Constructivity: From Logic to Algorithms 2014)
Continuity, computability, constructivity: from logic to algorithms 2014 (Preface to the special issue: Continuity, Computability, Constructivity: From Logic to Algorithms 2014)
- 3 October 2016
- Published by American Mathematical Society (AMS) in Bulletin of the American Mathematical Society
- Vol. 54 (3) , 481-498
Five stages of accepting constructive mathematics
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.
- 3 October 2016
- Published by American Mathematical Society (AMS) in Bulletin of the American Mathematical Society
- Vol. 54 (3) , 481-498
Five stages of accepting constructive mathematics
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
- 10 December 2014
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 10, Is
An Effect System for Algebraic Effects and Handlers
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.
- 10 December 2014
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 10, Is
Open AccessAn Effect System for Algebraic Effects and Handlers
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.
- 10 November 2014
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 25 (7) , 1484-1489
An injection from the Baire space to natural numbers
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.
- 10 November 2014
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 25 (7) , 1484-1489
An injection from the Baire space to natural numbers
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.