Abstract:

The Knaster-Tarski Fixed-Point Theorem, whereby a monotone function on a complete lattice always has a least and a greatest fixed point, is valid intuitionistically by the usual proof. This is not obviously so for functions on a chain-complete poset. The classical theorem is that if a function f is progressive (i.e. x <= f(x) for all x), then every point has a fixed-point over it. Starting with a point a, we iterate the function f through the ordinals (with sups at limit ordinals) forming a chain. The sup of the chain is the desired fixed point. This proof is blocked intuitionistically, because ordinals are NOT linearly ordered. Many people have tried and failed to find a substitute proof. Recently Todd Wilson (Cal State, Fresno, a former CMU/PAL Ph.D.) found an intuitionistic proof. The interesting proof and some applications will be presented in the talk.

Back to Talks Page