Characterizing Posets by Functions Into Natural Numbers - MathOverflow

Characterizing Posets by Functions Into Natural Numbers

2012-07-19T07:03:07Z

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!

Answer by Christian Stump for Characterizing Posets by Functions Into Natural Numbers

2012-07-19T07:43:08Z

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

Answer by Nik Weaver for Characterizing Posets by Functions Into Natural Numbers

2012-07-19T19:22:01Z

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.