Shows that the category of finite sets is finitely complete and cocomplete.
The main difficulty is constructing coequalisers. We take a conceptually simple but inefficient approach: we start by constructing quotients of decidable equivalence relations, show that coequalisers can be built as quotients of a closure, and that the closure of a decidable relation on a finite set is decidable (essentially by a pathfinding algorithm built by induction on the size of the finite set).
Checklist
Before submitting a merge request, please check the items below:
[X] The imports of new modules have been sorted with support/sort-imports.hs (or nix run --experimental-features nix-command -f . sort-imports).
[X] All new code blocks have "agda" as their language.
If your change affects many files without adding substantial content, and
you don't want your name to appear on those pages (for example, treewide
refactorings or reformattings), start the commit message and PR title with chore:.
Lavenza
commented
4 months ago
Description
Shows that the category of finite sets is finitely complete and cocomplete.
The main difficulty is constructing coequalisers. We take a conceptually simple but inefficient approach: we start by constructing quotients of decidable equivalence relations, show that coequalisers can be built as quotients of a closure, and that the closure of a decidable relation on a finite set is decidable (essentially by a pathfinding algorithm built by induction on the size of the finite set).
Checklist
Before submitting a merge request, please check the items below:
support/sort-imports.hs(ornix run --experimental-features nix-command -f . sort-imports).If your change affects many files without adding substantial content, and you don't want your name to appear on those pages (for example, treewide refactorings or reformattings), start the commit message and PR title with
chore:.