Characterizing Posets by Functions Into Natural Numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T02:46:02Z http://mathoverflow.net/feeds/question/102621 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102621/characterizing-posets-by-functions-into-natural-numbers Characterizing Posets by Functions Into Natural Numbers Mikhail Gudim 2012-07-19T07:03:07Z 2012-07-26T00:17:07Z <p>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)$?</p> <p>I should mention here that the only example I am interested in is the poset of prime ideals in a commutative Noetherian ring.</p> <p>It would be great if you could include references.</p> <p>Thanks!</p> http://mathoverflow.net/questions/102621/characterizing-posets-by-functions-into-natural-numbers/102623#102623 Answer by Christian Stump for Characterizing Posets by Functions Into Natural Numbers Christian Stump 2012-07-19T07:43:08Z 2012-07-19T13:31:35Z <p>If you have given all <strong>linear extensions</strong> 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 &lt; w$ in P iff $v &lt;_\sigma w$ for all permutations $\sigma \in \mathcal{L}(P)$.</p> <p>Proof:</p> <p>One direction is obvious: if $v &lt; w$ in P, then, by definition, $v &lt;_\sigma w$ for all permutations $\sigma \in \mathcal{L}(P)$.</p> <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 <a href="http://en.wikipedia.org/wiki/Partially_ordered_set#Strict_and_non-strict_partial_orders" rel="nofollow">http://en.wikipedia.org/wiki/Partially_ordered_set#Strict_and_non-strict_partial_orders</a>.</p> <p>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 &lt; w}$ and $P_{w &lt; v}$ with $v &lt; w$ and $w &lt; v$ respectively. Since $$\emptyset \neq \mathcal{L}(P_{v &lt; w}), \mathcal{L}(P_{w &lt; v}) \subseteq \mathcal{L}(P),$$ we finally found two permutations $\sigma,\tau \in \mathcal{L}(P)$ with $v &lt; _ \sigma w$ and $w &lt; _ \tau v$. $\qquad\square$</p> <p>For references see the wiki page on linear extensions:</p> <p><a href="http://en.wikipedia.org/wiki/Linear_extension" rel="nofollow">http://en.wikipedia.org/wiki/Linear_extension</a></p> <p>Or am I misunderstanding something in your question?</p> <p>Best, Christian</p> http://mathoverflow.net/questions/102621/characterizing-posets-by-functions-into-natural-numbers/102695#102695 Answer by Nik Weaver for Characterizing Posets by Functions Into Natural Numbers Nik Weaver 2012-07-19T19:22:01Z 2012-07-19T19:22:01Z <p>Sitting inside <code>$Hom(P,{\bf N})$</code> is the set <code>$P^*$</code> of monotone functions from <code>$P$</code> into <code>$\{0,1\}$</code>. This set carries the structure of a "Stone lattice", and the normal lattice homomorphisms from any Stone lattice into <code>$\{0,1\}$</code> will be a poset, in the case of <code>$P^*$</code> it recovers <code>$P$</code>. 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.</p>