Lemma 16.4.21. Finite posets are closed under pushouts of posets.
Proof
Consider a diagram \(Q\xleftarrow{f} P\xrightarrow{g} R\) of finite posets. We aim to show that the pushout \(Q\amalg_P R\) (in posets) is finite again.
Let us temporarily fix cardinal presentations of \(P^\simeq,Q^\simeq,R^\simeq\) of size \(l,m,n : \N\), respectively. Using these presentations, we perform the following construction steps.
• Define a reflexive and transitive relation \(\leq\) (preorder) on the set \(X\coloneq P^\simeq\amalg Q^\simeq\amalg R^\simeq\) by starting with the coproduct order inherited from \(P\), \(Q\) and \(R\) and imposing \[p\leq f(p)\leq g(p) \leq p\] for each \(p : P^\simeq\).
• Define the equivalence relation on \(X\) generated by \((x\sim y) \coloneq (x\leq y) \times (y\leq x)\).
• Both the preorder \(\leq\) and the equivalence relation \(\sim\) can be decided by a bounded number of equalities and/or order relations in \(P\), \(Q\) and \(R\), each of which is decidable; hence both \(\leq\) and \(\sim\) are decidable.
• Using the chosen cardinal presentations we can construct a decidable subset \(Y\subseteq X\) which intersects each \(\sim\)-equivalence class exactly once. For example, one could use the bijection \(X\cong \{1,\dots,l\}\amalg \{1,\dots m\}\amalg\{1,\dots n\}\cong \{1,\dots l+m+n\}\) to define a decidable linear order \(o\) on \(X\) and then define \(Y\) to consist of those elements of \(X\) that are \(o\)-minimal in their \(\sim\)-equivalence class.
• Denote by \(u\colon X\to Y\) the map of sets that sends each \(x \in X\) to the unique \(y\in Y\) with \(x\sim y\). Moreover, we have a square
of sets which commutes because \(f(p)\sim p \sim g(p)\) for all \(p\in P\) and \(u\) identifies \(\sim\)-related terms by construction.
• By construction, the preorder \(\leq\) is antisymmetric when restricted to \(Y\); hence we have a partial order on \(Y\). Passing through Theorem 10.3.10, this yields a poset \(T\) with \((T^\simeq,\leq)=(Y,\leq)\).
• By construction of the order and Lemma 10.3.7, the commutative square above has a unique upgrade to a commutative square of posets
Showing that this square is a pushout of posets is a straightforward computation involving maps of underlying sets and the order relation.
• By construction, the poset \(T\) has again a finite set of objects (\(Y\) was defined as a decidable subset of \(P^\simeq \amalg Q^\simeq\amalg R^\simeq\)) and decidable order.
• Since the pushout \(Q\amalg_P R\) (in posets) is isomorphic to \(T\), it too is a finite poset.
Of course the construction of \(T\) itself heavily depends on the chosen cardinal presentations of \(P^\simeq\), \(Q^\simeq\) and \(R^\simeq\). But the final conclusion, namely that \(Q\amalg_P R\) is finite, is a proposition; hence we may discharge the propositional truncation, and conclude the proof.