Shouldn't this concept be defined by saying every nonempty subset of a well-partially-ordered set has minimal elements? Michael Hardy 00:09, 23 Feb 2004 (UTC)
No. WPO also includes no infinite antichains; an infinite antichain has (infinitely many) minimal elements. Also, that graph minors are a WPO is equivalent to Robertson-Seymour: in one direction, the set of graphs not in the downward-closed set is upward-closed, the minimal elements are an antichain, and so the set of minimal forbidden graphs is finite (all of this up to isomorphism). In the other direction, it's trivial to show that there is no infinite descending chain, and if there is an infinite antichain (the other way the WPO definition can fail), then the graphs that do not lie above this antichain are a downward-closed set with an infinite set of forbidden minors, contradicting R-S. I'm reverting the comment about R-S. Populus 19:35, 2 Jun 2004 (UTC)
A question about nomenclature: is the name Well Partial Order standard? In set theory, they define a well founded partial order, as a partially ordered set, such that every non-empty subset has a minimal element (see for instance [K. Kunen, Set theory]); therefore, there is space for confusion. Moreover, I have seen the term "Noetherian Order" used instead of WPO (in the PhD thesis of M. Schmeling). --Manta 17:12, 30 Mar 2005 (UTC)
Merge with Well-quasi-ordering?
editI suggested the merge. The main concept behing wqo and wpo are the same even though the technicalities may differ slightly. We need a single article in an encyclopedia and the job of helping you find out where is the article is better left to indexes, links, redirects, disambiguation pages, etc. Wikipedia is not a dictionary.
The resulting article can list other variants like better-quasi-orderings etc. Btw, comparing the variants is more natural inside a single article.
PhS 10:39, 5 September 2005 (UTC)
I think we need to merge and call the result well-quasi-ordering. It's the standard name given to a well-developed section of combinatorics. I cite the following as references:
1. Kruskal, J. The Theory of well-quasi-ordering: a frequently discovered concept. J. Combinatoriral Theory 13 (1972), 297-305
2. Nash-Williams, C. St J.A. On well quasi-ordering infinite trees. Proc. Cambridge Philos. Soc. 61 (1965), 697-720
3. Laver, L. Well-quasi-orderings and sets of finite sequences. Proc.
Cambridge Philos. Soc. 79 (1976), 1-10
4. Robertson, N; Seymour, P.D. Graph Minors. XIX. Well-quasi-ordering on a surface. J. Combinatorial Theory, Series B 90 (2004) 325-385
I merged the two articles today. PhS 13:29, 25 February 2006 (UTC)
more jargon
editIn Bourbaki-speak, a "partial well-order" is a what Wiki calls a well partial order, and a "Noetherian order" is the opposite of a partial well-order. (In a Noetherian ring, the inclusion relation between ideals is a Noetherian order, whence the jargon.) There are 8 or 9 different known characterizations of these types of orders; e.g. they support an (ordinal-valued) Grundy function, or, they admit a strictly increasing mapping onto a well-ordered set. I can knock up an article with the whole story, if there is any interest. LDH (talk) 09:09, 24 November 2008 (UTC)
- The terminology I am familiar with makes Noetherian the opposite of well-founded order, not wpo. (The rationale is the same: note that the inclusion relation between ideals of a Noetherian ring may have infinite antichains, consider for example.) Likewise, a strictly increasing mapping to a well-ordered set exists for every well-founded relation. Are you sure you are not confusing well partial orders with well-founded orders?—Emil J. 14:27, 18 December 2012 (UTC)
