Talk:Weak ordering

Function for R^n

However, not for every strict weak order there is a corresponding real function. For example, there is no such function for the lexicographic order on Rⁿ.

But is seems easy to derive that there is such a function for Qⁿ × R. We can add that if there is a source.--Patrick 11:31, 21 May 2007 (UTC)[reply]

Why is strict the default?

…and weak order gets redirected here? How is this different from making strict partial order a main article that contains a definition of partial order as a variant of the primary topic? I propose turning things around (for weakness, not for partiality).—PaulTanenbaum (talk) 03:21, 18 March 2008 (UTC)[reply]

Picture isn't illustrative

Currently there's a pretty picture on the page (like a snowflake or poinsettia) that does not illustrate what a strict weak order is. (It illustrates something else, which is not entirely irrelevant; I'm not saying the picture is misleading, just that it's not the one most important picture we need to have on this page.)

It would be awesome if we could just show the graph of a strict weak order on some smallish set. Strict weak orders are really very easy to understand; I think this is a topic where a good picture would be worth all the rest of the words on the page. —Jorend (talk) 04:31, 13 December 2009 (UTC)[reply]

Permutohedron or Cayley graph?

I've made two illustrations, that are inspired by drawings in this PDF (pages 23 and 26):

The assignment of the permutations to the vertices is not the one from the permutohedron (compare), but the one from the Cayley graph that looks like the permutohedron (compare). The article says only permutohedron, not Cayley graph. Does anyone know an assignment of the weak orderings / ordered set partitions to the (hyper-)faces of this graph, where the assignment of the 24 permutations to the vertices is like in the permutohedron?

I know, that the flat representation of the permutohedron of order 4 is not actually a permutohedron, but I think that a drawing of the solid with 75 labels will be quite unusable - just like the drawing in the PDF, which does not even include all labels. mate2code 23:40, 26 May 2013 (UTC)[reply]

Incomprehensible

The article is quite incomprehensible, especially as it doesn't succeed in defining what a weak ordering is.Madyno (talk) 21:47, 28 May 2017 (UTC)[reply]

The sentence "A strict weak ordering is a binary relation < on a set S that is a strict partial order (a transitive relation that is irreflexive, or equivalently,[6] that is asymmetric) in which the relation "neither a < b nor b < a" is transitive." is one of the many possible ways of defining a weak ordering. Somewhat more focused criticisms might be helpful in improving the article. --JBL (talk) 23:14, 28 May 2017 (UTC)[reply]

Well, the first defining sentence is about a strict weak ordering. Then something is said about "one of the many possible ways of defining a weak ordering." But the definition seems to be again about a strict weak ordering. To me clear as mudd. Madyno (talk) 13:04, 29 May 2017 (UTC)[reply]

Already the introduction indicates that "strict weak order" means the same as "weak order" (both terms are bold, easy to find). Indeed, the second paragraph of the intro is devoted to a discussion of the complications involved in choosing a definition (because there are many equivalent-but-not-obviously-so choices). I do not want to say that this article is very good, but it certainly has the information you are asking about. --JBL (talk) 13:23, 29 May 2017 (UTC)[reply]

This article used to be at Strict weak ordering (it was moved to Weak ordering by David Eppstein four years ago, see diff), and it used to be somewhat more centered on that notion, see the version from March 2013. Actually, I think it would help to move the article back to Strict weak ordering as that is the notion that is usually discussed in the literature. Then again, see the remark by PaulTanenbaum at #Why is strict the default? above. Tea2min (talk) 08:26, 30 May 2017 (UTC) I have changed my mind: After reading the article again, I now think it should stay at Weak ordering. Sorry for the noise. Tea2min (talk) 08:58, 30 May 2017 (UTC)[reply]

For what it's worth, Glossary of order theory#W has the following entry (added by PaulTanenbaum in 2007):

Weak order. A partial order ≤ on a set X is a weak order provided that the poset (X, ≤) is isomorphic to a countable collection of sets ordered by comparison of cardinality.

So I don't think the meaning of the term "weak order(ing)" is really clear. Tea2min (talk) 09:53, 30 May 2017 (UTC)[reply]

What does it mean to say "a transitive relation that is irreflexive, or equivalently,[6] that is asymmetric" ? Certainly, a binary relation being transitive and irreflective is not "equivalent" to the relation being asymmetric, in any mathematical sense. Please note also that the link at [6] is dead. Furthermore, the article goes on to state that "irreflexivity and transitivity together imply asymmetry," which contradicts the previous statement, since equivalence is logically different than implication. But irreflexivity and transitivity together do not imply asymmetry, as the counterexample of any complete digraph shows. ThomasMcLeod (talk) 02:54, 6 April 2018 (UTC)[reply]

In the class of transitive relations, irreflexivity and asymmetry are equivalent. —David Eppstein (talk) 04:32, 6 April 2018 (UTC)[reply]

Fixed link [6]. - Jochen Burghardt (talk) 11:42, 6 April 2018 (UTC)[reply]

I withdraw my statement above. However, this result uses the transitive relation {aRb, bRa, aRa}, which is not what comes to mind when one thinks of transitive relations. This is a simple but non-obvious result. Furthermore, the referenced paper is as unhelpful as the article; it simply says that the proof is obvious. ThomasMcLeod (talk) 15:42, 8 April 2018 (UTC)[reply]

I kind of agree with ThomasMcLeod that the reference here is not great. Surely some undergraduate textbook somewhere has written this down and actually spelled it out? --JBL (talk) 16:44, 8 April 2018 (UTC)[reply]

Posets are a generalization?

I removed the claim from the intro that posets are generalizations of weak orders, pointing out that not every weak order is a poset. The edit was reverted with the comment "nevertheless, the information contained in a weak order is a special case of the information contained in a partial order".

I do not agree with this statement. Partial orders can express the fact that certain elements are incomparable, while weak orders can express the fact that certain elements are tied in rank. Neither can express the other type of information, and neither type of information is a special case of the other.

For example, the set of physical quantities is partially ordered by size: 1 meter is less than 1 mile and 1 pound is less than 2 pounds, but 2 pounds and 1 meter are incomparable (and not tied in rank!). The set of colors is weak ordered by my preferences: I prefer red over green but I like green and blue equally (though they are comparable!).

I would mention in the intro that weak orders, just like partial orders, generalize total orders and are generalized by preorders. Total orders are precisely those relations that are both partial orders and weak orders. AxelBoldt (talk) 03:09, 29 October 2020 (UTC)[reply]

If < is the relation of a strict weak order then defining ≤ by (x ≤ y iff x<y or x=y) gives a partial order. If ≤ is a partial order with the extra property that incomparability is transitive then defining < by (x < y iff x ≤ y and x ≠ y) gives a strict weak order. Both of these transformations are bijective and are just the standard way to convert < to ≤ or vice versa for partial orders. In this sense the weak orders are exactly equivalent to a subclass of partial orders, the ones in which incomparability is transitive. More precisely, the strict weak orders are exactly a subclass of the strict partial orders, without even any equivalencing required. For your color example I would say that the set of colors is also partially ordered by your preferences: you prefer red over green but green and blue are incomparable. It does not describe any different relation among these colors, it is just using different words. This point of view is very important in understanding semiorders, which are between weak orders and partial orders in how constrained vs expressive they are; if you don't think of weak and partial orders as being comparable, it would not make sense to say that something else is between them. It is true that the weak orders are also equivalent in a different way to the total preorders, but so what? That doesn't affect their equivalence to a special case of partial orders. —David Eppstein (talk) 05:39, 29 October 2020 (UTC)[reply]

I'm using "weak order" as synonymous with "total preorder", as does our article. It is true that every weak order W gives rise to a partial order PW, and that W can be recovered from PW. But it seems a stretch to say that therefore weak orders are generalized by partial orders. Every group G gives rise to a ring ZG and a topological space TG such that G can be recovered from ZG and also from TG. Would you say that therefore rings and topological spaces generalize groups? AxelBoldt (talk) 17:19, 29 October 2020 (UTC)[reply]

Our article uses both strict preorders and total preorders because there is no significant difference in information content between these two concepts. Saying that it is only about total preorders and not strict weak orders is incorrect. —David Eppstein (talk) 17:23, 29 October 2020 (UTC)[reply]

Would you say that therefore rings and topological spaces generalize groups? Realizing a weak order as a poset involves no extra structure, so these are not very good analogies; a better analogy would be that monoids generalize groups. But, even so, the answer to your question is "yes". In fact, this perspective is very fruitful, at least with respect to rings: it motivates the representation theory of algebras from the representation theory of groups via the group algebra. --JBL (talk) 17:53, 29 October 2020 (UTC)[reply]

Removing potentially unnecessary hypothesis in alternative statement of transitivity of incomparability

I changed this

If $x$ is incomparable with $y$ then for all $z\neq x$ satisfying $z\neq y,$ either ( $x<z{\text{ and }}y<z$ ) or ( $z<x{\text{ and }}z<y$ ) or ( $z$ is incomparable with $x$ and $z$ is incomparable with $y$ ).

To this

If $x$ is incomparable with $y$ then for all $z$ , either ( $x<z{\text{ and }}y<z$ ) or ( $z<x{\text{ and }}z<y$ ) or ( $z$ is incomparable with $x$ and $z$ is incomparable with $y$ ).

And David Eppstein reverted this with justification "None of the three consequences is true for z=x"

I believe that If z=x then z is incomparable with x by irreflexivity and incomparable with y by substitution and the assumption that x is incomparable with y, so the third consequence is true. Anomalistic (talk) 19:26, 23 January 2023 (UTC)[reply]