On Non-Well-founded Multisets:
Scott Collapse in the Multiworld

Giovanna D'Agostino

Dipartimento di Matematica e informatica
Universtita' di Udine
Via delle Scienze 206
33100 Udine

Albert Visser

Department of Philosophy
Heidelberglaan 8
3584 CS Utrecht
The Netherlands.


We define the class of non well-founded multisets and provide three different descriptions of this class: as collapsed multigraphs, as trees, or as infinitary formulae. Our major tool in this task is Scott-bisimulation, which was originally conceived to give an axiomatization of non well-founded multisets. The natural generalization of Scott-bisimulation from graphs to multigraphs allows us to have a theory of multigraph decorations and a notion of collapse in complete analogy with the theory of graph decorations and collapse given by the non well-founded axiomatization of sets ZFCA. We also show how our approach to multisets fits in the framework developed by Barwise and Moss.

Bibtex Entry