Title: Circularity, Non-wellfounded Sets, and Coalgebra

Larry Moss

Indiana University, visiting UMIACS & JHU Cog Sci

**
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.