Skip to content

Instantly share code, notes, and snippets.

Avatar

Andrej Bauer andrejbauer

View GitHub Profile
@andrejbauer
andrejbauer / UniverseInjection.agda
Last active Oct 11, 2020
Formalization of the fact that a dependent type theory with excluded middle cannot have a universe Set such that Set → Set injects into Set.
View UniverseInjection.agda
-- Counterexample by Chung Kil Hur, improved by Andrej Bauer
-- We show that it is inconsistent to have an injection I : (Set → Set) → Set and excluded middle.
-- Indeed, excluded middle and I together give a surjection J : Set → (Set → Set),
-- which by Lawvere's fixed point theorem begets a fixed point operator on Set.
-- However, negation does not have a fixed point.
module cantor where
-- generalities
@andrejbauer
andrejbauer / algebraic.v
Last active Jan 15, 2020
Unions of algebraic sets are algebraic
View algebraic.v
(* A Coq formalization of the theorem that the the union of algebraic sets are algebraic.
The file is self-contained, so we start with some general definitions
and facts from logic and sets, and basic algebraic definitions.
It should be straight-forward to translate it to any setting that has
a decent library of basic facts of logic, set theory and algebra.
*)
(* We formalize the following "paper" proof.
@andrejbauer
andrejbauer / ConstructibleNumbers.nb
Last active Sep 25, 2020
Generation of constructible numbers in Mathematica
View ConstructibleNumbers.nb
(* Content-type: application/vnd.wolfram.mathematica *)
(*** Wolfram Notebook File ***)
(* http://www.wolfram.com/nb *)
(* CreatedBy='Mathematica 11.2' *)
(*CacheID: 234*)
(* Internal cache information:
NotebookFileLineBreakTest
@andrejbauer
andrejbauer / algebraic.py
Created Aug 14, 2019
Pictures of algebraic numbers
View algebraic.py
#!/usr/local/bin/python3
# Compute algebraic numbers in the complex plane and draw a nice picture
import numpy
import sys
import argparse
import math
import cairo
import pickle
@andrejbauer
andrejbauer / localization.ml
Last active May 2, 2018
Experiments in using multicore OCaml effects to simulate dynamically created local effects.
View localization.ml
(** * General support for creation of dynamic effects *)
(** We show how to use the multicore Ocaml effects to dynamically generate local
effects. Such effects are akin to the Eff resources, and they can be used to
implement ML references.
The code is based on "Eff directly in OCaml" by Oleg Kiselyov and KC
Sivaramakrishnan (http://kcsrk.info/papers/caml-eff17.pdf). It was written by
Andrej Bauer, Oleg Kiselyov, and Stephen Dolan at the Dagstuhl seminar
"Algebraic Effect Handlers go Mainstream". *)
@andrejbauer
andrejbauer / functional2tree.eff
Created Apr 19, 2018
Use of effects and handlers to compute the tree representation of a functional.
View functional2tree.eff
(** This code is compatible with Eff 5.0, see http://www.eff-lang.org *)
(** We show that with algebraic effects and handlers a total functional
[(int -> bool) -> bool] has a tree representation. *)
(* A tree representation of a functional. *)
type tree =
| Answer of bool
| Question of int * tree * tree
@andrejbauer
andrejbauer / Graph.v
Last active Jan 28, 2019
Graph theory in Coq
View Graph.v
(** An attempt to formalize graphs. *)
Require Import Arith.
(** In order to avoid the intricacies of constructive mathematics,
we consider finite simple graphs whose sets of vertices are
natural numbers 0, 1, , ..., n-1 and the edges form a decidable
relation. *)
(** We shall work a lot with statements of the form
@andrejbauer
andrejbauer / README.markdown
Last active Feb 4, 2017
Elimination of constants and function symbols from set theory
View README.markdown

Official Zermelo-Fraenkel set theory only has the elementhood relation symbol ∈, and nothing else. Other constants, such as ∅, ⊆, ∩, ∪, f[x], etc. can be mechanically eliminated. The result of the elimination is a formula which is logically equivalent to the original, but is more complicated.

This program eliminates constants and function symbols, and generates LaTeX showing the formula before and after the elimination.

@andrejbauer
andrejbauer / algebra.v
Last active Aug 10, 2020
Uinversal algebra in Coq
View algebra.v
(* An initial attempt at universal algebra in Coq.
Author: Andrej Bauer <Andrej.Bauer@andrej.com>
If someone knows of a less painful way of doing this, please let me know.
We would like to define the notion of an algebra with given operations satisfying given
equations. For example, a group has of three operations (unit, multiplication, inverse)
and five equations (associativity, unit left, unit right, inverse left, inverse right).
*)
@andrejbauer
andrejbauer / example.m31
Last active Aug 6, 2016
Example of Andromeda ML-programming
View example.m31
(* In Andromeda everything the user writes is "meta-level programming. *)
(* ML-level natural numbers *)
mltype rec mlnat =
| zero
| succ of mlnat
end
(* We can use the meta-level numbers to define a program which computes n-fold iterations
of f. Here we give an explicit type of iterate because the ML-type inference cannot tell
You can’t perform that action at this time.