[Agda] A proof of omniscience in Agda
Martin Escardo
m.escardo at cs.bham.ac.uk
Fri Sep 2 23:46:25 CEST 2011
The widely quoted Limited Principle of Omniscience (LPO) is not provable
in constructive mathematics, and in particular in ML Type Theory (or in
Agda, hopefully).
However, if you enlarge the set of natural numbers with a point at
infinity, then you get a set that constructively satisfies the principle
of omniscience (in all varieties of constructive mathematics).
Here is a proof written in Agda:
http://www.cs.bham.ac.uk/~mhe/papers/omniscient/AnInfiniteOmniscientSet.html
(Given my track record of using Agda in funny ways, I emphasize that
this formal proof (1) doesn't disable the termination checker, (2)
doesn't use postulates, (3) doesn't rely on translations of classical
proofs into intuitionistic proofs, etc. It is in the purest possible
fragment of Agda, corresponding to traditional ML Type Theory.)
A proof in human notation is also available in a reference given in the
above link.
Best wishes,
Martin
More information about the Agda
mailing list