Formalization of Countable Multisets

Mathias Schack Rabing 📧 and Dmitriy Traytel 🌐

June 13, 2026

Abstract

We define countable multisets as a generalization of finite multisets. Countable multisets are equivalently represented as functions from elements to extended natural numbers ($\mathbb{N} \cup \{\infty\}$) returning non-zero values for countably many elements, or as quotients of lazy lists modulo infinitary permutations. We register countable multisets as a bounded natural functor (BNF), enabling nested (co)recursion through them in (co)datatypes. We further define the subtype of countably infinite multisets and register it as a BNF, too.

License

BSD License

Note

A first complete version of the proofs was manually written by the authors. LLMs (GPT 5.4, Claude Sonnet 4.6) were used to convert messy apply-style proofs to canonical Isar. All the lemma statements remained unchanged during this refactoring.

Topics

Session Countable_Multiset

Depends on