I forgo a detailed discussion so that I can move on to state and outline the proof of an important theorem concerning a special case (a slice of the category Set of sets) of the general concept.
Theorem. (Multisets classify finite-fiber oversets up to isomorphism.)
Given a set Z in the category of sets Set, and two functions f:X→Z and g:Y→Z into Z whose fibers are finite sets, the following are logically equivalent:
- f:X→Z and g:Y→Z determine the same image multiset |f−1|=|g−1|:Z→N on Z.
- ∀z∈Z|f−1(z)|=|g−1(z)|.
- ∀z∈Z there exists a bijection f−1(z)hz⟷g−1(z).
- there exists a bijection Xh⟷Y which makes the following diagram commute Xh⟷Yf↓↓gZ=Z
- f and g are isomorphic as objects of Set↓Z.
The operation of taking the image multiset
(Set↓Z)0|()−1|→Set(Z,N)
is a complete invariant for the relation of isomorphism on (Set↓Z)0.
(Where, as usual, ()0 denotes taking the underlying set of objects of a category.)Proof (outline):
a⟺b: By definition.
b⟺c: Follows from the general fact that two sets are equinumerous iff there is a bijection between them.
c⟺d: Consider the following diagram: f−1(z)∃hz⟷g−1(z)‖ The middle third of the diagram is just the definition of f^{-1}(z) and g^{-1}(z) as pullbacks.
The top line of the diagram is condition c., giving the pointwise bijection.
The bottom third of the diagram is condition d, giving the global bijection.
If the top line exists for all z\in Z, then the fact that X \cong \sum_{z\in Z} f^{-1}(z) and likewise for Y and g means that the h_z sum to give h.
Conversely, if the bottom line exists, then the pullback properties of the two squares in the middle third of the diagram gives the existence of the h_z.
d\iffe: By definition.
QED
In particular, taking Y=X, we have:a parallel pair f,g : X \rightrightarrows Z have the same associated multiset iff
they are isomorphic as sets over Z.
No comments:
Post a Comment