Posts in the year 2006
Are small sentences of Peano arithmetic decidable?
- 04 November 2006
- Computation, General, Logic
Recently there has been a discussion (here, here, here, and here) on the Foundations of Mathematics mailing list about completeness of Peano arithmetic (PA) with respect to “small” sentences. Harvey Friedman made several conjectures of the following kind: “All true small sentences of PA are provable.” He proposed measures of smallness, such as counting the number of distinct variables or restricting the depth of terms. Here are some statistics concerning such statements.→ continue reading (9 comments)
International Mathematical Olympiad 2006
This year the International Mathematical Olympiad took place in Slovenia. I participated as one of the organizers (problem selection and coordination). It was probably one of the busiest and most exciting times of my life,→ continue reading
Continuity Begets Continuity (Frauenwörth slides)
- 15 August 2006
- Constructive math, Talks
With Alex Simpson.
Abstract: We present a constructive meta-theorem about sequential continuity which allows us to conclude from a constructive proof of existence of a function between complete metric spaces satisfying a given system of (functional) equations that there also exists a sequentially continuous function satisfying the system.
Presented at: Trends in Constructive mathematics, Frauenwörth am Chimsee, Germany, June 2006.
Download slides: continuity_begets_continuity_bavaria_slides.pdf→ continue reading
König's Lemma and the Kleene Tree
- 25 April 2006
- Computation, Constructive math, Publications, Tutorial
For the benefit of the topology seminar audience at the math department of University of Ljubljana, I have written a self-contained explanation of the Kleene tree, which is an interesting object in computability theory. For the benefit of the rest of the planet, I am publishing it here.→ continue reading (2 comments)
Sometimes all functions are continuous
- 27 March 2006
- Computation, Constructive math, Tutorial
You may have heard at times that there are mathematicians who think that all functions are continuous. One way of explaining this is to show that all computable functions are continuous. The point not appreciated by many (even experts) is that the truth of this claim depends on what programming language we use.→ continue reading (40 comments)
Interesting higher-order functionals
- 21 March 2006
Spaces of higher-order functions are fascinating mathematical objects that we do not know enough about. What are they and what is known about them?→ continue reading (3 comments)
Specifications via Realizability (Dagstuhl)
- 13 January 2006
With Chris Stone.
Presented at: Reliable Implementation of Real Number Algorithms: Theory and Practice, Dagstuhl Seminar 06021.
Abstract: see “Specifications via Realizability (CLASE)”.
Talk notes: rz-dagstuhl.pdf (handwritten notes of the talk with examples of how RZ works)→ continue reading