# Characterizing Posets by Functions Into Natural Numbers

Let $P$ be a poset and denote by $Hom(P, \mathbb N)$ the set of all monotone functions from $P$ to natural numbers $\mathbb N$. Under what conditions on $P$ Is it possible to recover the order on $P$ from the knowledge of $Hom(P, \mathbb N)$?

I should mention here that the only example I am interested in is the poset of prime ideals in a commutative Noetherian ring.

It would be great if you could include references.

Thanks!

-

Sitting inside $Hom(P,{\bf N})$ is the set $P^*$ of monotone functions from $P$ into $\{0,1\}$. This set carries the structure of a "Stone lattice", and the normal lattice homomorphisms from any Stone lattice into $\{0,1\}$ will be a poset, in the case of $P^*$ it recovers $P$. In fact I have just described a dual equivalence between the category of posets with order preserving maps and the category of Stone lattices with normal lattice homomorphisms. See Theorem 5.1.3 of my book Lipschitz Algebras.

-
Presumably in the case when $P$ is the poset of prime ideals of a ring, $P^∗$ is isomorphic to the lattice of semiprime ideals? –  Douglas Somerset Jul 19 '12 at 21:37
Douglas, maybe something like that is true, but it isn't literally true in general --- take the ring ${\bf Z}$, its spectrum corresponds to prime numbers (as a poset, unordered), the semiprime ideals correspond to natural numbers, and $P^*$ corresponds to the power set of the set of prime numbers. –  Nik Weaver Jul 19 '12 at 22:12
@Nik Weaver: Thanks for the answer Nik! Actually this still not the kind of answer I want, probably because I haven't stated my question very well. I've just asked another question here: mathoverflow.net/questions/102704/… –  Mikhail Gudim Jul 19 '12 at 23:41
Excellent. Incisive. An exemplar of "definitive answer" (if only the question were what the questioner truly intended, etc.) –  paul garrett Jul 19 '12 at 23:44
Thank you, Paul! –  Nik Weaver Jul 20 '12 at 4:49

If you have given all linear extensions of $\mathcal{L}(P)$ of a poset $P$. This is the set of all linear orderings (permutations) of the vertex set of $P$ preserving the order in $P$. The order in $P$ can than be recovered as $v < w$ in P iff $v <_\sigma w$ for all permutations $\sigma \in \mathcal{L}(P)$.

Proof:

One direction is obvious: if $v < w$ in P, then, by definition, $v <_\sigma w$ for all permutations $\sigma \in \mathcal{L}(P)$.

To obtain the other direction, observe that posets are in 1-1 correspondence with directed acyclic graphs, see e.g. the last paragraph of http://en.wikipedia.org/wiki/Partially_ordered_set#Strict_and_non-strict_partial_orders.

Let us consider $P$ to be identified with its directed acyclic graph. Since adding an edge either from $v$ to $w$ or from $w$ to $v$ does not create a cycle in this graph, we have posets $P_{v < w}$ and $P_{w < v}$ with $v < w$ and $w < v$ respectively. Since $$\emptyset \neq \mathcal{L}(P_{v < w}), \mathcal{L}(P_{w < v}) \subseteq \mathcal{L}(P),$$ we finally found two permutations $\sigma,\tau \in \mathcal{L}(P)$ with $v < _ \sigma w$ and $w < _ \tau v$. $\qquad\square$

For references see the wiki page on linear extensions:

http://en.wikipedia.org/wiki/Linear_extension

Or am I misunderstanding something in your question?

Best, Christian

-
Does this work for infinite posets? –  Benjamin Steinberg Jul 19 '12 at 10:42
good point! I add a proof above which doesn't distinguish between finite and infinite posets. –  Christian Stump Jul 19 '12 at 13:12
@Christian: I think what you are describing is a way to recover $P$ from the group of poset automorphisms of $P$. What I am looking at is a result similar to Yoneda's lemma in spirit. Yoneda's lemma says that knowing object $X$ in a category is equivalent to knowledge of the functor $Hom(X, - )$. I would like to know if in case of posets one can get away with only konwing $Hom(P,\mathbb N)$. –  Mikhail Gudim Jul 19 '12 at 23:06