Lemma A.7. Let \(f\colon A \to B\) be a map of partially ordered sets such that for every \(b \in B\) the subset \(\{a \in A \mid b \leq f(a)\} \subseteq A\) is non-empty and filtered. Then \(f\) is cofinal. In particular:
- (1)
-
A map \(f\colon \N \to B\) into a partially ordered set is cofinal if for every \(b \in B\) there exists \(n\) with \(b \leq f(n)\).
- (2)
-
Every countable filtered partially ordered set \(Q\) admits a cofinal map \(\N \to Q\).
- (3)
-
The diagonal \(\N \to \N \times \N \) is cofinal, and so is every map \(f\colon \N \to \N \) with \(f(n) \geq n\) for all \(n\).
Proof.
The first statement was explained above. For (1), the subset \(\{n \mid b \leq f(n)\}\) is non-empty and upwards closed in \(\N \) (as \(f\) is order preserving), hence of the form \(\{n \geq n_0\}\), which is filtered. For (2), if \(Q\) is finite it has a largest element (Lemma A.5) and we may take the constant map. Otherwise enumerate \(Q = \{q_0,q_1,\dots \}\) and choose inductively \(f(0) = q_0\) and \(f(n) \geq f(n-1), q_n\); then \(f\) is order preserving and cofinal by (1). Statement (3) follows directly from (1). □