Talk:Preorder

Reflexive vs Irreflexive

I put a flag on this article because evidently there are two ways to define quasi order, reflexive or irreflexive. Can someone clarify?

[[1]]  —Preceding unsigned comment added by 130.70.11.93 (talk) 14:16, 18 October 2009 (UTC) 

The current definition of a "preorder" arises more naturally as a generalization of the concept of partial orders but, like any such situation, the most important thing is consistency. Jwuthe2 (talk) 10:51, 3 December 2009 (UTC)

Types of preorders

Is there a commonly-used name for a complete preorder (sequence A000670 in the OEIS) within set theory? (Not a total order, mind you -- it need not be antisymmetric.) I've heard the term "weak order", but that's from the same field that uses "linear order" for total orders, so I wanted some clarification if anyone knows of something else. CRGreathouse (t | c) 20:02, 30 August 2006 (UTC)

Total preorders, of course. Thanks, Hurkyl! CRGreathouse (t | c) 04:55, 31 August 2006 (UTC)

Table

The table which shows the number of preorders needs some explanation. What precisely does the value n (given for n=1,2,3,4) denote? —Preceding unsigned comment added by 66.108.155.231 (talk) 02:19, August 28, 2007 (UTC)

That's the number of elements to be preordered. If there's just one element there's only one preorder (a <~ a). If there are two elements there are four preorders: (a <~ a, b <~ b, a <~ b), (a <~ a, b <~ b, b <~ a), (a <~ a, b <~ b, a <~ b, b <~ a), (a <~ a, b <~ b). CRGreathouse (t | c) 16:11, 4 October 2007 (UTC)

Formal definition

I was confused by the next-to-final statement in the formal definition "A preorder which is preserved in all contexts is called a precongruence." Upon reading it I was like "huh ?!" All what contexts ? There didn't seem to be any context (pun) for the notion of "contexts". Netrapt (talk) 16:43, 23 November 2008 (UTC)

I agree with Netrapt. I too find that statement confusing, because in fact the definition is not formal. I did a Google search of precongruence but could not decipher from what I read the intended meaning of the sentences about precongruences. Could someone who knows what a precongruence is correct this section? Undsoweiter (talk) 02:21, 20 February 2010 (UTC)

Digging some more, it turns out that Repton added the bit about precongruence, and later an anonymous(?) user with IP 141.76.75.213 added the bit about symmetry implying congruence. Clearly these folks knew the context for their statements, but I wish they'd left us with explicit details. The relevant edit dates are May 26, 2006 and July 28, 2006, respectively. Undsoweiter (talk) 02:31, 20 February 2010 (UTC)

Suggestions for clarifications

1. It would be helpful to understand why the "pre" in "preorder". Does it come before in some sense? Is there a "postorder"? For that matter, why the "quasi"? Might that be because the ordering described here allows items to be equal, hence not ordered? Yet that seems to be covered by "partial order". (Apparently there's also the possibility of elements simply not being related by the relation in question, not sure how that fits here.)

2. What do ~ and $\lesssim$ mean? The section Constructions appears to be trying to explain that, but seems to have contradictions, at one point describing ~ as equivalence, and elsewhere as complement. Similar odd comparisons of < and $\lesssim$.

Possible sources of vagueness: am I correct in assuming that a and b are individual members of the set S? Does ~ have a fixed meaning, or can one define it in alternative ways?

3. How does one verbally speak ~ and $\lesssim$?

Gwideman (talk) 14:15, 15 December 2009 (UTC)

It's called "preorder" because it's nearly/'just before' an order. $\lesssim$ is a generic symbol for some [pre]order; its particular meaning can vary (and often, like here, no particular meaning is intended). $\lesssim$ can be pronounced "precedes" if there's a need to say it. CRGreathouse (t | c) 00:37, 21 February 2010 (UTC)

Well, I think he meant that we should modify the article itself to clarify this, rather than discussing on the talk page. These are good points; if one never had to deal with relations before, this could all seem very confusing. I'll try to updated article to do this. linas (talk) 04:38, 20 April 2012 (UTC)

Done. I gave a big expanded intro; I think it should be much easier now, and more intuitive. linas (talk) 05:41, 20 April 2012 (UTC)

Table, again

Currently the table is titled: "Number of n-element binary relations of different types". However, shouldn't it be something more like: "Number of preorders for different binary relations and different set sizes"? (I'm assuming n is set size) Gwideman (talk) 14:22, 15 December 2009 (UTC)

No, preorders are only one column in that chart. CRGreathouse (t | c) 19:17, 15 December 2009 (UTC)

Oops, yes of course. But I'm still stumped by the title. What is an "n-element binary relation". Doesn't it really mean "Number of binary relations (of different types) for sets having n elements". Ie: "n-elements" pertains to the sets not the relations, right? Gwideman (talk) 20:27, 15 December 2009 (UTC)

I think that those phrases mean the same thing. I find "n-element binary relation" clearer. CRGreathouse (t | c) 17:16, 16 December 2009 (UTC)

theorems and lemmas?

I added the diamond lemma to the "see also" list, as an important lemma that holds for many pre-orders. Are there other lemmas/theorems that should be stated? The article hints that there are theorems from topology that require pre-orders, but its unclear if any of these can be stated as holding for pre-orders in general, (i.e. if they still say anything useful after throwing away the topology bits). linas (talk) 04:31, 20 April 2012 (UTC)

To clarify: the article currently states: Many order theoretical definitions for partially ordered sets can be generalized to preorders, but the extra effort of generalization is rarely needed.(citation needed) but for readers coming for the category theory or the comp-sci perspective, without a background in order theory, it would be interesting to know what these are. linas (talk) 17:07, 3 July 2012 (UTC)

Preorders vs directed graphs

I think this paragraph is misleading, so I have removed it:

To every preorder there corresponds a directed graph, with elements of the set corresponding to vertices, and the order relation between pairs of elements corresponding to the directed edges between vertices. Note that, in general, the corresponding graphs may be cyclic graphs: preorders may have cycles in them. Imposing the condition of anti-symmetry on the preorder (to force it into becoming a partial order) is the same as imposing the no-cycles condition on a directed graph (forcing it to become a directed acyclic graph). Imposing the condition of symmetry (to force a pre-order into being an equivalence relation) is the same as removing the direction on the edges (to create an undirected graph). In general, a preorder may have many disconnected components. The diamond lemma is an important result for certain kinds of preorders.

In particular, most directed graphs are not transitive, and therefore do not correspond to preorders in this way. And if one uses reachability to define a preorder from an arbitrary directed graph, then many digraphs will give rise to the same preorders. —David Eppstein (talk) 05:54, 20 April 2012 (UTC)

OK. I also cringed when I wrote "forced" but I couldn't think of a better way of saying it. So much for late-night editing. The main point I wanted to get across was that preorders can contain cycles, as this is not something that would ever occur to a reader who'd never heard of a pre-order before. I think the general notion that there's a graph that corresponds to orders can also bring a lot of intuition to new readers. (If most people are like me, it takes a while to realize that algebra, in general, need not be confined to neatly-ordered rows of symbols, but has a spatial, topological, graphical "shape", as it were. Things like feynmann diagrams, or category theory diagrams, shouldn't be just for the initiates; the general ideas could/should be more widely appreciated). I tried to be careful and say that the edges are defined by the relation, and not by other concepts, such as reachability. I'll try re-writing later today or tomorrow, and say explicitly "only transitive graphs" and "not reachability" or maybe something like "most digraphs aren't transitive but when they are.." I dunno. Goal is to wordsmith a poetic introduction for the young reader. linas (talk) 15:25, 20 April 2012 (UTC)

Ah hell, why wait, lets try now:

To every preorder, there corresponds a directed graph, with elements of the set corresponding to vertices, and the order relation between pairs of elements corresponding to the directed edges between vertices. The converse is not true: most directed graphs are neither reflexive nor transitive. Note that, in general, the corresponding graphs may be cyclic graphs: preorders may have cycles in them. A preorder that is antisymmetric no longer has cycles; it is a partial order, and corresponds to a directed acyclic graph. A preorder that is symmetric is an equivalence relation; it can be thought of as having lost the direction markers on the edges of the graph. In general, a preorder may have many disconnected components. The diamond lemma is an important result for certain kinds of preorders.

Would this work? linas (talk) 15:46, 20 April 2012 (UTC)

I have taken the liberty of editing this paragraph again, since some of its statements are inaccurate and therefore misleading. In particular, care needs to be taken when defining the corresponding directed graph, because reflexivity and transitivity is normally not included in the corresponding graph. By omitting them the cycles can be seen more easily and most partial orders are drawn graphically in this way. That being said, I may have described these things in a more awkward way for the newly apprised reader. As always, this may be improved by others. Zteve (talk) 15:43, 30 November 2016 (UTC)

My edit has been reverted. I can see why, though the flaws in the original paragraph are not now addressed. Here are my reasons: I chose to describe a certain vertex-covering graph rather than the direct one because the paragraph here (and one further down) talks about cycles, forgetting that there is precisely one cycle on every node of the graph as described—because a preorder is reflexive. Also, most of the diagrams that might be used to describe this have the fewest edges that are sufficient to recover the original by reachability extension (transitive closure). It is more natural to draw them this way, and cycles are much clearer. So I attempted to describe this graph in this informal paragraph so as to simplify the picture in the mind of the reader when it came to talk about the presence (or absence) of cycles. I wonder if you can suggest a way out of this confusion, David? Finally, I'm not sure if the formal correspondence below really includes reflexivity when it talks about reachability, since no mention is made of an empty path (with no edges) from a node to itself. Zteve (talk) 14:15, 13 December 2016 (UTC)

PS: The reference to cyclic graphs is basically incorrect, and confusing, when the described graph is drawn, since every one of them contains a cycle, that is a non-empty path from a node to itself. Zteve (talk) 14:20, 13 December 2016 (UTC)

The issue for me is that the transitive-closure representation of a preorder as a directed graph (the one that has an edge for every reachable pair of distinct vertices) is uniquely determined by the preorder. The transitive-reduction representation (one that has a minimal subset of those edges preserving the same reachability relation) is not. For instance, the trivial preorder in which everything is equal to everything else can be represented by any one of $(n-1)!$ directed cycles, or also in other ways by directing the edges of a tree of cycles. So, if you're looking for a 1-1 correspondence between preorders and graphs, the transitive closure is really the only way to go. —David Eppstein (talk) 18:22, 13 December 2016 (UTC)

quasi-order versus quasiorder

which spelling is correct? Both are used in the text. --Tillmo (talk) 10:10, 9 October 2012 (UTC)

Both are correct. It would be preferable not to mix them, though. In the spirit of WP:RETAIN, what we should probably do is figure out which one was used first, and change all instances to that form. --Trovatore (talk) 23:09, 9 October 2012 (UTC)

Actually, I take it back. The article is entitled preorder, whereas it could have used pre-order. Therefore we should use quasiorder for consistency, regardless of which was first. --Trovatore (talk) 23:14, 9 October 2012 (UTC)

The trouble is that preorder is nearly always written without a hyphen, whereas quasi-order gets a hyphen more often than not (IME).—Emil J. 14:42, 11 June 2013 (UTC)

Precongruences

I am deleting the following sentences, since it makes little sense.

A preorder which is preserved in all contexts (i.e. respected by all functions on P) is called a precongruence. A precongruence which is also symmetric (i.e. is an equivalence relation) is a congruence relation.

Indeed, if some relation is respected by all functions on P, then it is necessarily symmetric (just consider a function that exchanges a and b). Hence the sentence has a meaning only when context is intended in some different sense. Anyway, the word "precongruence" occurs only 38 times in the MathSciNet database, and apparently with different meanings. So the sentence can be reintroduced only after more (and clearer) explanations. Paolo Lipparini (talk) 14:18, 15 August 2015 (UTC)

The original sentence meant "all functions under consideration". The situation is similar when one says that an equivalence relation compatible with "all functions" is called a congruence: one doesnt talk of all possible functions, only the ones in the algebra, or setting, or first-order structure, or data-type, or ..., or context of interest. Actually the notion of precongruence is quite useful. PhS (talk)

asymptotic form of the OEIS sequences?

I'd be curious to see what the asymptotic form (large N) is for the OEIS sequences. 67.198.37.16 (talk) 22:04, 14 February 2016 (UTC)

Reduction and arrow direction

Early on in the article, ≤ is equated to ← and a ≤ b with “b reduces to a”. I'm sure this is usage in existence, but perhaps a source would be useful? The thing is, phrase “reduces to” here gives the opposite direction to what one would get when ordering problems by hardness using reductions, for example (which yields a preorder), and the direction of the arrow is opposite of that commonly used when defining a preorder as a thin category – i.e., a ≤ b indicates the existence of a unique morphism from a to b, not the other way around, and this is written as a forward arrow. So at least there seems to be reasonable usage out there that is the opposite of what is stated, though I'm sure the usage used in the article is frome some source more directly related to order relations? Maybe in addition to a source, a brief discussion of this issue might be merited? Mlhetland (talk) 19:52, 11 November 2017 (UTC)

Hasse-diagram

The pictured relation in the Hasse-diagram doesn't show the relation x <~ y if x/4 <= y/4, and is no preorder. The relation <~ should be pictured as: 0 -> 1 and 1 -> 0, 1 -> 2 and 2 -> 1 etc. From the picture it follows: 0 <~ 2, 2 <~ 3, but 3 <~ 0. Madyno (talk) 17:40, 23 April 2022 (UTC)

Hasse diagrams for partial orders show only a transitive reduction of the relation. In the article's image, I applied this principle to a preorder. For example, 1R0 follows from the depicted relations 1R2, 2R3, and 3R0.

I guess by "<~", you just mean R? Also, it seems to me you meant "but not 3 <~ 0" in your last sentence, right? - Jochen Burghardt (talk) 18:52, 23 April 2022 (UTC)

No, the picture shows 3 <~ 0, and not 0 <~ 3, allthough if one has to consider the relation to be transitive, this follows indirectly. In that case, the arrows could as well be reversed. It is confusing, anyway. Madyno (talk) 23:22, 23 April 2022 (UTC)

In the same sense, each Hasse diagram is confusing: to see if two vertices are related, you always have to search for an arbitrarily long path (rather than just one single edge) from one to the other. This was Hasse's idea to reduce the number of vertices to be drawn. Jochen Burghardt (talk) 14:19, 24 April 2022 (UTC)

I came here because I am confused as well. Not because of the transitive reduction - this is clear. But first, I think we should not mention the word "cycle" (" If all numbers in a cycle are considered equivalent" ---> but aren't they equivalent indeed?). And since the relation looks symmetrical, why drawing directed arcs anyway? 2A01:CB08:416:8500:89B6:7A16:6521:FE83 (talk) 07:47, 26 October 2023 (UTC)

I used "considered equivalent" since the construction of $\sim$ from $\lesssim$ is not explained before section Preorder#Preorders and partial orders on partitions which is far away from the image; indeed the numbers of a cycle are all related by $\sim$, but this notion isn't yet available in the caption. The whole relation is not symmetrical, e.g. 2R4 but not 4R2, and neither $4\lesssim 2$. We might use undirected arcs within a cycle, but this would require further lengthy explanations why there are two types of arcs. - Jochen Burghardt (talk) 09:50, 26 October 2023 (UTC)

The diagram is simply misleading as a first example of a preorder. Either accept an edit that has bidirectional arrows in the loops or pick another example, maybe a finite one? — Preceding unsigned comment added by 82.137.5.100 (talk) 01:58, 27 December 2023 (UTC)

@Jochen Burghardt: Hi Jochen, I agree with the above comments about the diagram. I find it more confusing than helpful. Drawing an equivalence relation (at each of the equivalence classes) as a cycle is uncommon, and it contradicts the definition of Hasse diagram at the target page (x < y and there does not exist z such that x < z < y) which would imply no edges between elements of each equivalence class. Also, unlike the usual edges in a Hasse diagram for posets, these edges are chosen arbitrarily and thus the representation is not unique. I think it would be more helpful to draw a smaller finite partial order with all arrows drawn (none inferred). I would also not be opposed to something like the current example if it is more clearly explained, and if the edges within each class would be drawn with bidirectional arrows as a K4 graph to avoid ambiguity. Let me know what you think. Thanks! Caleb Stanford (talk) 16:54, 19 March 2024 (UTC)

It is clear from the above discussion that the figure is confusing. Moreover it seems also original research, since nobody provided a reliable source for the use of Hasse diagrams for preorders. So, the figure seems to be not convenient. If one want to have an useful figure, one must uses a mixture of Hasse diagrams and Venn diagrams. That is, one must represent the equivalence classes under the relation $(x\leq y)\land (y\leq x)$ inside closed curves, and draw a Hasse diagram between these curves. I know that this representation may be original research, but it is so simple that it is unbelievable that it does not appear in some reliable sources.

By the way, I am surprised that the following alternative definition of preorders is not clearly provided in the article: A preorder on a set $X$ is a poset on the equivalence classes of an equivalence relation defined on $X.$ It certainly the ignorance of this basic result that led the author of the diagram to draw this confusing figure. D.Lazard (talk) 19:13, 19 March 2024 (UTC)

It does seem like a good visual representation to me, at least for finite preorders. It seems likely that some sources already use both this visualization and your alternative definition; whether they are easy to find is a different question. —David Eppstein (talk) 19:55, 19 March 2024 (UTC)

I checked the page of results on Google Scholar for "hasse diagram" "preorders". All of them that I found use @D.Lazard:'s suggested representation, with minor variations. E.g.:

• page 420 of Approximating SP-orders through total preorders
• page 309 of Generalized morphisms, a new tool for comparative evaluation of performance of fuzzy implications

One uses a slightly different representation where elements are still grouped by equivalence class, but all edges are drawn across equivalence classes rather than just a single representative:

• page 4 of Distributions of countable models of disjoint unions of Ehrenfeucht theories

Caleb Stanford (talk) 20:35, 20 March 2024 (UTC)

I have replaced the image with File:Preorder.png per the discussion above. Caleb Stanford (talk) 03:20, 14 April 2024 (UTC)