Tuesday, April 8, 2014

Slice categories

For the definition, see, for example, nlab or Wikipedia.
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 $\bf 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 $\bf{Set}$, and two functions $f : X \to Z$ and $g : Y \to Z$ into $Z$ whose fibers are finite sets, the following are logically equivalent:
  1. $f : X \to Z$ and $g : Y \to Z$ determine the same image multiset $|f^{-1}| = |g^{-1}| : Z \to \bf N$ on $Z$.
  2. $\forall z\in Z \quad |f^{-1}(z)| = |g^{-1}(z)|$.
  3. $\forall z\in Z \quad$ there exists a bijection $f^{-1}(z) \overset{h_z}{\longleftrightarrow} g^{-1}(z)$.
  4. there exists a bijection $X \overset{h}{\longleftrightarrow} Y$ which makes the following diagram commute \[\begin{array}{cccc} X & \overset{h}{\longleftrightarrow} & Y\\ f\downarrow && \downarrow g\\ Z & = & Z\\ \end{array}\]
  5. $f$ and $g$ are isomorphic as objects of ${\bf Set}\downarrow Z$.
The logical equivalence of a. and e. implies:
The operation of taking the image multiset $$({\bf Set}\downarrow Z)_0 \xrightarrow[]{|()^{-1}|} {\bf Set}(Z,\bf N)$$ is a complete invariant for the relation of isomorphism on $({\bf Set}\downarrow Z)_0$.
(Where, as usual, $()_0$ denotes taking the underlying set of objects of a category.)

Proof (outline):
a$\iff$b: By definition.
b$\iff$c: Follows from the general fact that two sets are equinumerous iff there is a bijection between them.
c$\iff$d: Consider the following diagram: \[\begin{array}{ccccc} f^{-1}(z) && \overset{\exists h_z}{\longleftrightarrow} && g^{-1}(z)\\ \Vert &&&& \Vert\\ f^{-1}(z) & \longrightarrow & 1 & \longleftarrow & g^{-1}(z)\\ \downarrow && \forall \downarrow z && \downarrow\\ X & \xrightarrow[f]{} & Z & \xleftarrow[g]{} & Y\\ \Vert &&&& \Vert \\ X && \underset{\exists h}{\longleftrightarrow} && Y\\ \end{array}\] 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$\iff$e: 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