FS.yaml

id: FS
name: category of finite sets and surjections
notation: $\FS$
objects: finite sets
morphisms: surjective maps
description: This category is badly-behaved in itself, but it appears in representation theory. It has two connected components, consisting of the empty set and the non-empty finite sets.
nlab_link: null

tags:
  - combinatorics
  - set theory

related:
  - B
  - FI
  - FinSet

satisfied_properties:
  - property: locally small
    proof: There is a forgetful functor $\FS \to \Set$ and $\Set$ is locally small.

  - property: locally finite
    proof: There is a faithful functor $\FS \to \FinSet$ and <a href="/category/FinSet">$\FinSet$</a> is locally finite.

  - property: essentially countable
    proof: Every finite set is isomorphic to some $\{1,\dotsc,n\}$ for some $n \in \IN$.

  - property: right cancellative
    proof: This is trivial.

  - property: cogenerator
    proof: 'We prove that $\{0,1\}$ is a cogenerator: The surjective maps $X \to \{0,1\}$ correspond to the non-empty proper subsets of $X$. If $a,b \in X$ are elements that have the same image under each surjective map $X \to \{0,1\}$, it therefore means that they lie in the same non-empty proper subsets of $X$. This implies $a=b$: If $X = \{a\}$, this is trivial. Otherwise, use the subset $\{a\}$.'

  - property: coequalizers
    proof: We construct coequalizers as in <a href="/category/FinSet">$\FinSet$</a> (or $\Set$) and observe that the universal property still holds when we restrict to surjective maps.

  - property: wide pushouts
    proof: 'We construct wide pushouts as in <a href="/category/Set">$\Set$</a> and observe that the universal property still holds when we restrict to surjective maps. If $f_i : S \to X_i$ are surjective maps and $P$ is their wide pushout, then each $X_i \to P$ is surjective, so that in particular $P$ is finite.'

  - property: epi-regular
    proof: 'If $f : X \to Y$ is a surjective map of finite sets, it is the coequalizer of the two projections $p_1, p_2 : X \times_Y X \rightrightarrows X$ in <a href="/category/FinSet">$\FinSet$</a>, but also in $\FS$. Notice that $p_1,p_2$ are surjective. Even though $X \times_Y X$ is not a pullback in $\FS$, we can use this finite set here.'

  - property: multi-complete
    proof: >-
      Let $D : \I \to \FS$ be a small diagram. Let $L \subseteq \prod_{i \in \I} D(i)$ be the limit object of the corresponding diagram in $\Set$. Consider the set of all finite subsets $R \subseteq L$ with the property that $p_i(R) = D(i)$ for every $i \in \I$. For each of these, $(R \xrightarrow{p_i|_R} D(i))_{i \in \I}$ is a cone in $\FS$. We claim that the set of these cones is universal:
      Let $(f_i : T \to D(i))_{i \in \I}$ be any cone in $\FS$. Let $R \subseteq L$ be the image of the induced map of sets $f : T \to \prod_{i \in \I} D(i)$ defined by $p_i f = f_i$. Then $R$ is finite, since $T$ is finite, and we have $p_i(R) = p_i(f(T)) = f_i(T) = D(i)$. Moreover, the map $f$ corestricts to a map $f' : T \to R$ with $p_i|_R  \, f' = f_i$. Therefore, $f'$ is a morphism of cones.
      Conversely, let $h : T \to R$ be a morphism of cones, i.e. $p_i|_R \, h = f_i$, where $R$ is not known yet. Then $h$ equals the corestriction of the map into the product induced by the $f_i$, and $h$ is surjective as a morphism in $\FS$. This shows that both $R$ and the morphism of cones are unique.

  - property: generalized variety
    proof: 'Let $D : \I \to \FS$ be a sifted diagram. Consider the set
      $$\{\card(D(i)) : i \in \I\} \subseteq \IN.$$
      Since $\IN$ is well-ordered and $\I$ is non-empty, it has a minimal element, say $\card(D(i_0))$. For every morphism $i_0 \to i$ then the map of finite sets $D(i_0) \to D(i)$ is an isomorphism since it is surjective and $\card(D(i_0)) \leq \card(D(i))$. Therefore, every sifted diagram is eventually constant. From Corollary 3 <a href="/content/sifted-colimits-in-groupoids">here</a> we deduce that $\FS$ is a generalized variety.'

  - property: finitely accessible
    proof: 'In the previous proof we have seen that every sifted diagram is eventually constant. From Corollary 4 <a href="/content/sifted-colimits-in-groupoids">here</a> we deduce $\FS$ is finitely accessible.'

  - property: ℵ₁-cofiltered limits
    proof: >-
      Let $D : \I \to \FS$ be an $\aleph_1$-cofiltered diagram. We claim that the set
      $$\bigl\{\card(D(i)) : i \in \I\bigr\} \subseteq \IN$$
      is bounded. If not, for every $n \in \IN$ there is some $i_n \in \I$ with $\card(D(i_n)) \geq n$. Choose a cone $(j \to i_n)_{j \in \I}$. For every $n \in \IN$ the set $F(j)$ surjects onto $F(i_n)$, so that $\card(F(j)) \geq n$. This contradicts the fact that $F(j)$ is finite. Hence, the maximum
      $$M \coloneqq \max \bigl\{\card(D(i)) : i \in \I \bigr\} \in \IN$$
      is well-defined. Let $\J \subseteq \I$ be the full subcategory of those $i \in \I$ with $\card(D(i)) = M$. Then $\J$ is non-empty, and when there is a morphism $i \to j$ with $j \in \J$ we also have $i \in \J$. Since $\I$ is cofiltered, it follows that $\J \subseteq \I$ is initial. Therefore, the limit of $D$ coincides with the limit of $D|_{\J}$.
      But this diagram is constant: for every $j \to j'$ in $\J$ the map $D(j) \to D(j')$ is a surjective map between finite sets of the same cardinality $M$, hence bijective. This implies that the limit of $D|_{\J}$ exists and is given by any $D(j)$ with $j \in \J$.

unsatisfied_properties:
  - property: small
    proof: Even the collection of all singletons is not small.

  - property: skeletal
    proof: This is trivial.

  - property: countable
    proof: This is trivial.

  - property: core-thin
    proof: Its core is <a href="/category/B">$\IB$</a>, which we know is not thin.

  - property: generator
    proof: Let $G$ be a finite set. There are at least two morphisms $G + 2 \rightrightarrows 2$, but there is no morphism $G \to G + 2$ at all. Hence, $G$ is not a generator.

  - property: connected
    proof: 'If $f : \varnothing \to X$ is surjective, then $X = \varnothing$, and if $f : X \to \varnothing$ is any map, then also $X = \varnothing$. This shows that $\{ \varnothing \}$ is a connected component in this category. (The other connected component consists of all non-empty finite sets.)'

  - property: sequential limits
    proof: 'Let $X_n \coloneqq \{1,\dotsc,n\}$. We define the truncation $p_n : X_{n+1} \to X_n$ by extending the identity of $X_n$ with $p_n(n+1) \coloneqq n$. Assume the sequence of truncations $\cdots \to X_2 \to X_1$ has a limit $(f_n : X \to X_n)$ in this category. But $f_n$ is surjective, so that $\card(X) \geq n$ for all $n$. Since $X$ is finite, this is a contradiction.'

  - property: pullbacks
    proof: The connected component of non-empty sets has a terminal object, $1$, and it suffices to prove that it has no products. Let $X$ be a finite set with more than $1$ element. Assume that the product $P$ of $X$ with itself exists. The diagonal $X \to P$ is a split monomorphism, hence injective, but also surjective, i.e. an isomorphism. In other words, the two projections $P \rightrightarrows X$ are equal. The universal property of $P$ now implies that every two morphisms $Y \rightrightarrows X$ are equal, which is absurd.

  - property: binary copowers
    proof: Assume that the copower $X \coloneqq 2+2$ exists. Since we have a surjective map $2 \to X$, the set $X$ has at most $2$ elements. The codiagonal $X \to 2$ shows that $X$ has at least $2$ elements. Thus, $X \cong 2$. For all finite sets $Y$ we get a bijection $\Hom(2,Y) \cong \Hom(2,Y)^2$, in particular the cardinalities are the same. For $Y=2$ this gives the contradiction $2 = 4$.

  - property: locally cocartesian coclosed
    proof: >-
      If $X$ is a finite set, the coslice category $X / \FS$ is thin and in fact equivalent to the lattice of equivalence relations on $X$. If $X$ has $\geq 3$ elements, it is not codistributive* and <a href="/category-implication/dual_distributive_criterion">hence</a> not cocartesian coclosed: For simplicity assume $X = \{a,b,c\}$. The bottom element $\bot$ corresponds to the partition $\{\{a\},\{b\},\{c\}\}$, the top element $\top$ to the partition $\{\{a,b,c\}\}$. Now consider the three equivalence relations $E_1,E_2,E_3$ corresponding to the three partitions
      $$\{\{a,b\},\{c\}\}, \, \{\{a,c\},\{b\}\}, \, \{\{b,c\},\{a\}\}.$$
      Then
      $$E_1 \vee (E_2 \wedge E_3) = E_1 \vee \bot = E_1,$$
      but
      $$(E_1 \vee E_2) \wedge (E_1 \vee E_3) = \top \wedge \top = \top.$$
      *For thin categories, the properties codistributive and distributive <a href="/category-implication/distributive_duality">are equivalent</a>.

  - property: multi-initial object
    proof: If a multi-initial object exists, then the connected component consisting of non-empty finite sets has an initial object $X$. Then, any non-empty finite set cannot have a cardinality strictly greater than $X$,  which is a contradiction.

special_objects: {}

special_morphisms:
  isomorphisms:
    description: bijective maps
    proof: This follows exactly as for sets.
  monomorphisms:
    description: bijective maps
    proof: 'Assume that $f : X \to Y$ is a monomorphism in this category. If $a,b \in X$ are such that $a \neq b$ but $f(a) = f(b)$, let $h : X \to X$ be the transposition that swaps $a$, $b$. Then $f \circ \id_X = f = f \circ h$, so by assumption $\id_X = h$, a contradiction. This shows that $f$ is bijective.'
  epimorphisms:
    description: every morphism
    proof: This is trivial.
  regular monomorphisms:
    description: same as monomorphisms
    proof: This is because the category is mono-regular.
  regular epimorphisms:
    description: same as epimorphisms
    proof: This is because the category is epi-regular.