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?

  • $\begingroup$ In your $(\mathbb{N}^2,\leq)$ example, is $(1,4) \le (2,3)$ or is $(2,3) \le (1,4)$? $\endgroup$ – Henry Apr 21 '16 at 10:58
  • $\begingroup$ Neither. The two would be incomparable. However, (2,4) is larger than both for example. $\endgroup$ – 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.

  • 4
    $\begingroup$ 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$ $\endgroup$ – Carl Mummert Apr 21 '16 at 10:36
  • $\begingroup$ Indeed, one clear issue is with sets that are not "totally directed", so you could simply have any number of elements on level 1, all of which point to level 0 (and have other elements further up as necessary). The example given is a great concrete example of this abstraction. $\endgroup$ – Nate 8 Apr 22 '16 at 5:13
  • 1
    $\begingroup$ Thought I'd share an observation that clarified things for me: After some thought, it occurred to me that a directed set is countable if and only if every element has countably many predecessors and there exists at least one element with countably many successors. From here, it's clear that every counter-example to my original question involves a directed set with all elements having uncountably many successors (of which the above is a great example). $\endgroup$ – Christian Bueno Apr 25 '16 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.