Abstract:

It has long been recognized that a large number of interesting and difficult phenomena are circular, self-referential, or self-involved in some way. The goal of this talk is to survey an approach to many circular phenomena that began with the development of non-wellfounded sets and continues in a more vigorous way with the related mathematical field of coalgebra. In particular, I hope to talk about approaches to both the Liar Paradox and the Hypergame Paradox that I worked out with Jon Barwise using non-wellfounded sets, and I want to sketch more recent work giving a coalgebraic semantics of recursive program schemes.

In theoretical computer science, circularity is often "straightened out" by appealing to domain-theoretic constructions. The very model of this move is the understanding of recursion in terms of least fixed-points. One moves to spaces of approximate objects and takes limits so as to tame the circularity. There is nothing wrong with this technically. The conceptual price is that a lot of attention is then given to these approximations, and sometimes these are not the kinds of objects one wants in the first place. The overriding metaphor seems to be one of construction from below as opposed to observation of behavior. Coalgebra gives us tools to model phenomena where "observation" is more important than "construction." The main message of the talk is to explain a systematic set of dual concepts, such as recursion/corecursion, induction/coinduction, least fixed-point/greatest fixed-point, congruence/bisimulation, initial algebra/final coalgebra, and Foundation Axiom/Anti-Foundation Axiom.