Partitions are categorically dual to both subsets and factorizations, kinda
[Prerequisite warning: basic category theory.]
In his work on Finite Factored Sets, Scott Garrabrant defined the notion of factorization. In simple terms, a factorization of a finite set consists of a set of non-trivial partitions of , , such that every element in can be "assigned" to a selection of parts, one from each partition. This gives us a bijection between and the cartesian product over : . The natural forward direction of the bijection intersects the parts, producing a singleton set with an element of : .
Scott wrote:
[...]
Intuitively, this makes sense, and I tried to put a bit more categorical flesh on this in my comment under that post. In the category Set (or rather FinSet, as we're only dealing with finite sets), the categorical product ()is the cartesian product () and the coproduct (, dual to the product, is the disjoint sum (). A factorization of a set expresses it as a cartesian product without unnecessary unit elements, i.e., without the singleton sets, as . A partition of a set expresses it as a disjoint union without unnecessary unit elements, i.e., without the empty set, as . Those unit elements — and — are the terminal and initial object, respectively, and hence also duals.
* Factorization: , where
* Partition: , where
(Point of order: perhaps, the 's can be "anything", not necessarily partitions/subsets of , but it doesn't matter categorically, because categorically, equinumerous sets are isomorphic.[1])
But there's an alternative way to view a partition, which makes things more complicated. We can think of a partition of as an epimorphism (surjection in FinSet) , where the elements of correspond to parts of , by the preimage of : . Dualizing this picture gives us a monomorphism (injection in FinSet) , representing picking some set of elements of , i.e., a subset of .
So, depending on how we represent a partition of , its dual can either be a factorizati
