Proposition 16.4.23. Let \(P\) be a poset. Then \(P\) is finite as a poset if and only if it is a finite category.
Proof
The statement βifβ follows directly from Corollary 16.4.22, so it remains to show βonly ifβ. Since the assertion that \(P\) is a finite category is a proposition, we may fix an isomorphism \(\{1,\dots, n\}\cong P^\simeq\) to do so.
We first observe, by induction on \(n\), that every nonempty poset with decidable order and \(n\) objects has a maximal object. Indeed, remove one object \(p\). If no object remains, then \(p\) is maximal. Otherwise, choose by induction a maximal object \(m\) of the remaining poset and decide whether \(m\leq p\). If \(m\leq p\), then \(p\) is maximal; if not, then \(m\) remains maximal after adjoining \(p\). For the first assertion, an object of the remaining poset above \(p\) would also be above \(m\), and hence would equal \(m\); antisymmetry would then identify it with \(p\). The second assertion follows because the only new possible object above \(m\) is \(p\).
We now prove the proposition by strong induction on \(n\). The case \(n=0\) is clear. Suppose that \(P\) has \(n+1\) objects and choose a maximal object \(m\). Let \(Q\) be the full subposet on the objects distinct from \(m\), let \(P_{\leq m}\) be the full subposet on the objects \(x\leq m\), and put \(P_{<m}=Q\cap P_{\leq m}\). The poset \(Q\) has \(n\) objects. Since the predicate \(x\leq m\) is decidable, filtering a cardinal presentation of \(Q\) gives a cardinal presentation of \(P_{<m}\) with at most \(n\) objects. Both \(Q\) and \(P_{<m}\) are therefore finite categories by the induction hypothesis. Moreover, \[ P_{\leq m}=P_{<m}\star[0]\, , \] so \(P_{\leq m}\) is finite by Corollary 16.4.11.
It remains to verify that the square
is a pushout in \(\Cat\). Every chain \([k]\to P\) lies in \(Q\) or in
\(P_{\leq m}\): if it contains \(m\), maximality forces all its vertices to
lie below \(m\). A chain lies in both subposets precisely when it lies in
\(P_{<m}\). Since equality with \(m\) is decidable, this exhibits each nerve
level as a union of two subsets with the stated intersection. Applying
the Rezk nerve therefore gives a levelwise pushout square.
Mapping this levelwise pushout into the nerve of an arbitrary category, and using the full
faithfulness of the nerve from Corollary 15.1.13, gives the pushout universal
property in \(\Cat\). Since finite categories are closed under pushouts by
Lemma 16.4.6, \(P\) is finite, as required.