# Is a directed set countable, if for each element there are only finitely many smaller ones?

A directed set is a pair $(A,\leq)$ where $\leq$ is a reflexive, transitive relation such that for any $x,y\in A$ we have some $z$ such that $x,y\leq z$. (This comes up when dealing with categorical limits and topological nets).

In particular $(\mathbb{N},\leq)$ and $(\mathbb{R},\leq)$ are directed sets.

To help get comfortable with them, I imposed a "smallness" criteria: Let's say a "finite-type" directed set is a directed set where every element has finitely many predecessors (smaller elements).

My Guess: Finite-type directed sets are always countable.

As before $(\mathbb{N},\leq)$ is an example, but now $(\mathbb{R},\leq)$ is too big and is a non-example. Another example is $(\mathbb{N}^2,\leq)$ where $(a,b)\leq (c,d)$ iff $(c,d)-(a,b)\in \mathbb{N}^2$ and it's higher dimensional analogues. However, I've personally been unable to equip $\mathbb{N}^\mathbb{N}$ with an appropriate finite-type directed set structure.

Is there a clean proof or counterexample regarding my guess? Or does this somehow end up touching upon foundational things such as the axiom of choice?

• In your $(\mathbb{N}^2,\leq)$ example, is $(1,4) \le (2,3)$ or is $(2,3) \le (1,4)$? – Henry Apr 21 '16 at 10:58
• Neither. The two would be incomparable. However, (2,4) is larger than both for example. – Christian Bueno Apr 21 '16 at 11:10

Let $X$ be any set, and let $A$ be the collection of finite subsets of $X$; $A$ is directed by $\subseteq$, and each member of $A$ has only finitely many predecessors in that order. However, if $X$ is infinite, then $|A|=|X|$, so the cardinality of $A$ can be as large as you like.
• This is equivalent to a second construction. Let $A$ be any set. We make a directed set $D$ whose minimal elements will be exactly the elements of $A$. Let $D_1 = A$ and given $D_i$ let $D_{i+1}$ be the set of all pairs $\{a,b\}$ of elements of $D_i$, and let $a \leq \{a,b\}$ and $b \leq \{a,b\}$. Let $D = \bigcup_{i \in \mathbb{N}} D_i$. Then $D$ is a directed set, which can be visualized as a kind of tree whose minimal elements are from $A$. If we identify each element of $D$ with the set of atoms below if, the elements of $D$ correspond to finite subsets of $A$, with the order $\subseteq$ – Carl Mummert Apr 21 '16 at 10:36