Talk:Partially ordered set
![]() | This ![]() It is of interest to the following WikiProjects: | ||||||||||
|
Introduction
[edit]I think the introduction could be made at the same time easier to understand and more concise. (I don't like 1st paragraph introductions that contain more than the strict necessary, because to modify it, you have to modify the whole page which may give problems if it grows large.)
I suggest to give the example of set theoretical inclusion and a counter example like {1} and {2} (for non-comparability). The example of political organizations is unnecessarily complicated and in some sense even wrong. (Who knows if strict inclusion does not hold, if not today then maybe somewhen in the future? Especially in politics, nothing is impossible...)
I suggest that the real life example be changed. "Is a descendant of" is not a partial ordering of people, since I am not a descendant of myself. —Preceding unsigned comment added by 128.101.184.204 (talk) 03:44, 22 March 2009 (UTC)
The term "genealogical descendancy" is not clear, especially relating to reflexivity and anti-symmetry properties. —Preceding unsigned comment added by Mochan Shrestha (talk • contribs) 10:38, 2 July 2009 (UTC)
Asymetry follows from irreflexivity
[edit]Am I wrong or follows asymmetry of a strict partial order already from irreflexivity and transitivity? If a < b and b < a then by transitivity would a < a which is a contradiction to irreflexivity. So b < a must be false ...
- Yes, as your proof shows, irreflexivity and transitivity imply asymmetry. Although your proof makes use of Reductio ad absurdum, which in turn makes use of the law of the excluded middle which some mathematicians called intuitionists eschew. Paul August ☎ 17:53, Jan 6, 2005 (UTC)
This proof is not non-constructive
[edit]- Hold on, what makes that proof non-constructive? We're asked to show that
- which is equivalent, sometimes by definition, to
- in both classical and intuitionistic logic. Now prove the conditional by assuming its antecedent and deriving its consequent:
(assumption) ( elimination, from transitivity axiom) ( elimination) ( elimination, from irreflexivity axiom) ( elimination)
- Which proves the conditional. It's straightforward constructive reasoning, no? --MarkSweep 18:50, 6 Jan 2005 (UTC)
- The first proof given above is non-contstructive since it is a proof by contradiction. Your proof may be constructive but I'm not an expert and I'm not sure if it does not somehow make use of the assumption that (A or not A) is always true. In particular I would wonder about the equivalence for (not A) that you use above, since in intuitionist logic (not A) is defined differently than in classical logic. Paul August ☎ 21:05, Jan 6, 2005 (UTC)
- No, the first proof above is essentially the same proof as mine (with perhaps another layer of implication on the outside), and it is constructive. Just because a proof uses a contradiction doesn't mean it's non-constructive. If you define as as usual, then natural deduction systems for classical, intuitionistic, and minimal logic only differ in terms of which (if any) form the elimination rule for takes. However, in the proof above, one doesn't eliminate at all, so it is in fact valid in minimal logic, which does not allow elimination. Observe:
- The first proof given above is non-contstructive since it is a proof by contradiction. Your proof may be constructive but I'm not an expert and I'm not sure if it does not somehow make use of the assumption that (A or not A) is always true. In particular I would wonder about the equivalence for (not A) that you use above, since in intuitionist logic (not A) is defined differently than in classical logic. Paul August ☎ 21:05, Jan 6, 2005 (UTC)
1 [transitivity axiom] 2 [irreflexivity axiom] 3 | [assumption, a and b arbitrary] 4 | | [assumption] 5 | | [I 3,4] 6 | | [E 1] 7 | | [E 5,6] 8 | | [E 2] 9 | | [definition of 8] 10 | | [E 7,9] 11 | [I 4-10] 12 | [definition of 11] 13 [I 3-12] 14 [I 3-13]
- Nowhere does this use an elimination rule for , so it's valid in minimal logic. --MarkSweep 00:44, 7 Jan 2005 (UTC)
Well, I might be wrong ;-) but I assumed that the first poster's proof was essentially the following: Suppose a < b (line 3). We want to show that it is not the case that b < a. Now assume that b < a (line 4), then by transitivity (line 6), a < a (line 7), but this is a contradiction (line 10) by irreflexivity (line 8), therefore since assuming b < a leads to a contradiction (line 11), b < a must be false (line 12), QED. Is this not an example of "proof by contradiction? Don't the intuitionists reject this method of proof? Paul August ☎ 01:09, Jan 9, 2005 (UTC)
- I've taken the liberty of annotating your informal proof with pointers to lines of the formal proof, to make it clear that the formal proof is in fact a more explicit version of the informal proof. You wrote, "since assuming b < a leads to a contradiction, b < a must be false": this is true, but it's true by definition. This means if you want to show , you have to prove , which will necessarily involve a contradiction, but it is not a proof by contradiction in my book. It's just a plain old conditional proof, where the formula you conditionally derive just happens to be a contradiction. "Proof by contradiction" means that you derive something from a contradiction, in other words, you eliminate the contradiction. Note that this is possible in intuitionistic logic, which has rule for elimination (in Natural Deduction), sometimes called "ex falso quodlibet", that allows you to derive any formula you want from a contradiction (but you cannot withdraw any assumptions, for that you need Classical logic). But in this case, the contradiction is not eliminated, and in that sense this is not a "proof by contradiction". --MarkSweep 05:53, 9 Jan 2005 (UTC)
Negated statements are "classical" (regular) so 'proofs by contradiction' are intuitionistically valid. DefLog 02:47, 9 Jan 2005 (UTC)
Intuitionistic logic lets you infer ¬Q → ¬P from P → Q, though not the other direction (the best it lets you get from ¬Q → ¬P is P → ¬¬Q). Write ¬(a<a) for irreflexivity, ¬(a<b ∧ b<a) for antisymmetry, and a<b<c → a<c for transitivity. Now instantiate c with a in transitivity, infer ¬(a<a) → ¬(a<b ∧ b<a), and use modus ponens with this and irreflexivity to get antisymmetry. You can't get much more constructive than that, or direct for that matter. --Vaughan Pratt 08:31, 15 July 2007 (UTC)
Example
[edit]I have finally gotten tired of looking at this .. as a Democrat AND a member of the Sierra Club, (and a "paramathematician") even I cannot figure out this example. All this aside, this example illustrates systemic bias by assuming all Wikipedians are U.S. citizens who understand the parties involved. As someone else pointed out, using a social science metaphor to illustrate a mathematical concept has problems of its own. So I yanked the example and put it here in case anyone wants to argue about this:
- Unlike a total ordering, a partial ordering need not guarantee the mutual comparability of all objects in the set. For example, we could define an ordering ⊆ on the set of all political organizations such that a⊆b if every member of a is also a member of b. This would be only a partial ordering: if a is the Sierra Club and b is the Democratic Party, then neither a⊆b nor b⊆a holds. An example of a total ordering would be to define a≤b if the name of organization a precedes that of b in alphabetical order. Partially ordered sets are studied in order theory.
I replaced this with the three or four examples that appear in the undergraduate (discrete) textbooks. Vonkje 20:30, 11 August 2005 (UTC)
Improve Examples.
[edit]It would be better for clarity to not only describe a selection of sets, but actually write them out too so people can see the set rather than just consider it.
Clarification
[edit]The article is a bit light on the difference between partially and totally ordered sets. If we think of "R" as the numerical comparison "≤" and the set is the integers, then the three rules clearly apply:
- For all integers a, a ≤ a.
- For all integers a and b, if a ≤ b and b ≤ a then a = b.
- For all integers a, b, and c, if a ≤ b and b ≤ c then a≤c.
What makes the integers a totally ordered set is that there is no pair of integers for which the "≤" relationship is unspecified. For all integers a and b, at least one of these statements is true:
- a ≤ b
- b ≤ a
In a partially ordered set that is not totally ordered, there is at least one pair of members a and b for which neither aRb nor bRa is true.
Example 1, dependencies in Make. A makefile specifies the dependencies between objects (usually files) that must be observed in building a piece of software as a multiple-step process. For instance an executable foobar might be built by linking object files foo.o and bar.o. In turn, foo.o is built by compiling foo.c, and bar.o is built by compiling bar.c. Both foo.c and bar.c include a header file plugh.h. Then we could write:
- plugh.h R foo.o
- foo.c R foo.o
- plugh.h R bar.o
- bar.c R bar.o
- foo.o R foobar
- bar.o R foobar
where "R" here means "is required in order to build". A makefile contains this same information, in a slightly different syntax. This could also be drawn as a directed graph.
Notice that there is no "R" relationship between foo.c and bar.c, or between foo.o and bar.o. In the directed graph, the foo branch and the bar branch are separate. It doesn't matter whether you build foo.o first or bar.o first, you are free to build them in either order.
Example 2, import statements in the Python programming language. Source file X may "import" source file Y, so that the objects defined in Y are available in X's namespace, and can be used by code in X. This could be notated as "Y ≤ X" and it often means that the file Y was written before the file X.
In a large collection of files, many of the files may import others, and transitivity applies: if X imports Y and Y imports Z, then the objects defined in Z are accessible somewhere in X's namespace. But there may be two files U and V where neither imports the other, either directly or through a transitive chain.
- The above (light on total vs. partial) is a reasonable criticism if applied to the section on inverses. I expanded that section a little to try to clarify the difference. --Vaughan Pratt 08:39, 15 July 2007 (UTC)
Visualizing a poset
[edit]I've found the Hasse diagram, which provides one way to visualize a poset. Are there other ways to do this? One thought that comes to mind is something akin to a hierarchical category listing with cross-references:
- grandparent 1
- parent 1
- child 1
- child 2
- grandchild
- parent 2
- child 2 (see parent 1)
- child 3
- parent 1
- grandparent 2
- parent 2 (see grandparent 1)
- parent 3
Is there an article on this general topic? modify 14:08, 27 April 2007 (UTC)
Does the given Hasse diagram actually fully describe set inclusion? I would think it should look like this:
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/7/7e/Set_inclusion.jpg/220px-Set_inclusion.jpg)
— Preceding unsigned comment added by Dgluss (talk • contribs) 17:12, 17 August 2018 (UTC)
- The Hasse diagram includes only the relations that cannot be inferred from other ones using the transitive law. So your inclusion diagram is not a Hasse diagram. Yes, the Hasse diagram fully describes the partial order, but not directly by its arrows. Two elements are ordered when there is a directed path between them, not just a single edge. —David Eppstein (talk) 17:17, 17 August 2018 (UTC)
Thanks, I see that now, but that leads to the question, is this a good way to demonstrate a poset? You need to use the properties of the poset to infer the full dependencies, but isn't that property just the thing we're trying to show? I was unaware of the definition of Hasse diagram and should have looked that up first, so I learned something today. Dgluss (talk) 17:49, 17 August 2018 (UTC)
Recent changes of notation
[edit]I am unhappy with the recent changes in the notation that were introduced by SlamDiego. I fear that the notation used in the article as it stands now is incomprehensible to the layman. — Tobias Bergemann 07:37, 4 August 2007 (UTC)
- The layperson is going to see “≤” and think immediately and only of an arthimetic relation. A layperson who mistakenly believes that he understands what is written is in far worse shape than one who might take “” to be incomprehensible. The rest of the changes mostly amounted to turning awkward (and often ungrammatic) constructions into cleaner mathematical expressions. The article, for example, already had “¬” in it; a presumption that a reader who could recognize that couldn't handle “” or “” would be silly. —SlamDiego←T 21:51, 4 August 2007 (UTC)
I agree with Tobias and have gone a little way towards restoring the readability of the article. Your argument about laypeople reads to me like you are deliberately trying to make the article notation-heavy and difficult to read in order to scare away the non-mathematicians. That does not seem like the right way to go, to me. —David Eppstein 23:32, 4 August 2007 (UTC)
- Avoid ad hominem attacks on my motives, okay? You're perfectly out-of-line. I have no desire to scare away laypeople. The article was written in a way that would mislead laypeople, and the quality of wording wasn't great.
- There are many things that could be done with the notation that would be better than what was there, and some of them would be different from what I did. As far as I can see, what you've done is
- prefix the quantifiers, rather than postfix them, which doesn't make a whole lot of difference
- unpack some of the Cartesian products — notwithstanding that the article elsewhere presumed that the reader could deal with Cartesian products
- I have no great objections to either of these changes. —SlamDiego←T 01:49, 5 August 2007 (UTC)
- From my point of view, what I did was
- complete rewrite the lede to more gently introduce the topic and avoid technical jargon,
- supplement the notation-only formal definition with an English description of each property, and
- rewrite the quantified formulas, getting rid of unneeded and confusing braces and brackets, and incidentally prefixing the quantifiers
- To my mind, the first two of these changes are far more important than the third. —David Eppstein 02:07, 5 August 2007 (UTC)
- From my point of view, what I did was
- I didn't edit the lead, so that's irrelevant to the dispute here.
- Tobias Bergemann didn't call for supplemental wording, and I stated no position on that matter, so that's irrelevant to the dispute here.
- The removal of the braces and brackets makes expressions look simpler, but it also makes them more ambiguous. If you think that the reader will already understand the subject well enough to, in effect, mentally insert the removed brackets and braces, that's fine; but, implicitly, that is what he or she must now do.
- I agree that the first two classes of changes are more important; but, again, they aren't what was under dispute.
- —SlamDiego←T 02:19, 5 August 2007 (UTC)
- My initial comment wasn't clear, I apologize. I did not want to object against the change from “≤” to “” but against the use of quantifiers and junctors where I found their use to be unnecessarily formalistic and where I thought that their use actually reduced the readability of the article. However, if other readers and editors prefer the current version I can certainly live with that. — Tobias Bergemann 08:06, 6 August 2007 (UTC)
- What prevailed earlier was a mix of formal notation and quasi-English were a layreader would have to struggle even to simply discern whether what seemed to be a parenthetical note were that or the parentheses were used to indicate precedence of a junctor, and whether indeed any given “and” or “or” were Boolean operators or natural language. (There isn't a simple mapping from one to the other.) The best solution is to provide both clean formal expressions and supplementary wording. Slapping things down, as if speaking and writing quickly on a chalk-board in a class-room setting with 45 minutes before the bell, will fail far more readers than even a fairly spartan formalism. —SlamDiego←T 20:28, 6 August 2007 (UTC)
- I am not a mathematician. However, an expression like
- strikes me as far more formalistic than anything I have seen used in the literature, especially when compared with the plain-text
- For all a, b, and c in P, we have that if a ≤ b and b ≤ c then a ≤ c.
- which still manages to communicate the definition with only little if any ambiguity. That's what I meant when I called your changes "unnecessarily formalistic". — Tobias Bergemann 07:19, 7 August 2007 (UTC)
- I am not a mathematician. However, an expression like
- Not only have I seen a lot of expressions about such things that are that formalistic, but it happens to be more informal than what some of my instructors would have wanted. A more fully fomral expression would be
- But that's rather beside the point. The choice between verbal expression and formal expression is non-rival; the article can have both. I'd like it to have formal expressions because they can be clean and unambiguous; I think that verbal expressions before or after would also be a Good Thing.
- However, my main concerns are:
- that the wretched use of “≤” be avoided;
- that, formally or verbally, there be nothing again like this
- This is not to say that the complex numbers cannot be totally ordered; we could for example order them lexicographically via x+iy < u+iv if and only if x < u or (x = u and y < v), but this is not ordering by magnitude in any reasonable sense as it makes 1 greater than 100i.
- that, whatever decision is taken on formalism, there be no misrepresentation here of what it does and does not effect or preclude.
- —SlamDiego←T 22:27, 7 August 2007 (UTC)
- Not only have I seen a lot of expressions about such things that are that formalistic, but it happens to be more informal than what some of my instructors would have wanted. A more fully fomral expression would be
I strongly prefer the usual ≤ notation. It is the standard notation used for partially ordered sets, and adding in the “” notation does not help anything but make the text harder to understand. Oleg Alexandrov (talk) 15:02, 6 August 2007 (UTC)
- And I also object to the quantifiers spread out all over the place. This article is already complex enough, being about an abstract topic. There is no need to obfuscate it further. Oleg Alexandrov (talk) 15:04, 6 August 2007 (UTC)
- I don't regard the “≤” notation as usual or standard. The bald claim that readers will find it harder to understand “” flies in the face of the fact that most laypeople have little or no exposure to non-arthimetic math, and will generally begin by mistaking “≤” as standing for an arithmetic relation. Let's not do that to them. —SlamDiego←T 20:28, 6 August 2007 (UTC)
- On ≤ vs I tend to agree: ≤ may be a little more standard in this context (I've seen it both ways) but is better for conveying the idea that the relation may not necessarily be the familiar numeric comparison. As for the quantifiers, I think it's usually preferable to spell them out in words: it takes little more space, remains as rigorous, and isn't as intimidating to nonmathematicians. —David Eppstein 20:48, 6 August 2007 (UTC)
- Yes, the disadvantage of ≤ is that it may be confused with the numerical comparison. On the other hand, this may be an advantage too, since it conveys to the reader that partially ordered sets are abstract generalizations of the usual less-than-or-equal-to relation. I would argue that on the whole having "≤" in would help, rather than hinder, the exposition of the article. Oleg Alexandrov (talk) 03:13, 7 August 2007 (UTC)
- The reader can be explicitly told that arthimetic is a special case of after being informed of the general concept. Until the general concept is absorbed, even if the reader has somewhere being told that is not necessarily arithmetic, his or her mind is typically going to be derailed by the notion. A classic example of this was in the protracted failure of the world to recognize Ramsey's brilliant exposition on SEU exactly because he used “” for as well as for arithmetic . —SlamDiego←T 22:09, 7 August 2007 (UTC)
- It is not going to be derailed by the notion of arithmetic order, the old usual order will help the reader get an intuition for the new abstract one. I suggest the article be moved back to the original notation. Oleg Alexandrov (talk) 03:48, 8 August 2007 (UTC)
- That's perfectly wrong; and, noting the case of Ramsey, I gave a classical illustration of how wrong it is. It is a constant struggle to get people to step away from presumptions of quantification, and the “≤” notation suckers them viciously. —SlamDiego←T 07:30, 8 August 2007 (UTC)
Going back to previous notation
[edit]After a week during which all parties had the chance to make their case, I reverted the text before the edits by SlamDiego primarily to remove the quantifiers, but also to put back the ≤ notation.
It appears to me that there was good agreement about revering the quantifiers, and there was not enough discussion on the merits of ≤ versus the notation. Comments? Oleg Alexandrov (talk) 17:02, 11 August 2007 (UTC)
- The ordinary ≤ is quite standard; the curly form looks frankly like an affectation here. Curly inequality signs have various good uses but this isn't one of the compelling ones. --Trovatore 06:53, 19 August 2007 (UTC)
- and quantifier notation will be largely meaningless to someone unused to the great game. Mathematics articles have sufficient potential for being inaccessible to laymen without unexplained uses of either. --Mark H Wilkinson (t, c) 07:02, 19 August 2007 (UTC)
- Our mathematics Manual of Style explicitly discourages formal notation such as quantifiers when prose will suffice. Oleg is quite right to revert.
- Using the curly "\preceq" symbol is something I might favor in a mathematics text, but not here. Although we have a choice of three Unicode characters ("≼", "⪯", and "⪳" — U+227C, U+2AAF, and U+2AB3), many readers will see these as "missing character" glyphs; thus we are forced to use TeX to generate an image of the character, which frequent editors know we try to avoid for inline formulae. We have no vital semantic reasons to insist on a special character; use of ordinary "≤" is common in mathematical practice, and a certain amount of explanation is inevitable with either choice of character. --KSmrqT 10:32, 19 August 2007 (UTC)
Certainly, is the standard notation, with alternatives being used primarily when more than one poset structure on a given set is considered. I've especially checked Stanley, vol.1 (which should be added to the reference list), and he uses the ordinary "less than or equal to" sign. Moreover, over 100 articles in Category:Order theory have been written using this notation, so there is only one possible choice for the parent article.
On the second point, concerning quantifiers: insistence on converting meaningful word statements into logic formulae with abundance of symbols was one of the hallmarks of the New Math and related movements, which ended in a total disaster. The idea that in this day and age (post Bourbaki), mathematicians would prefer the logic formulae to worded definitions is, quite frankly, preposterous. For example, Stanley (a great expositor) does not use them at all in the chapter on partially ordered sets, and quite possibly, anywhere throughout "Enumerative combinatorics". Outside of set theory and logic, it seems that the quantifier notation is widely used only in some real analysis textbooks. Other than a strong personal opinion of one (or two?) editor(s), unsupported by evidence, I do not discern a "case" having been made for their use. Arcfrk 10:45, 19 August 2007 (UTC)
- I support the use of simpler notation as advocated above by Oleg, Digby, Mark, Trovatore, KSMrq and Arcfrk, since I noticed that the editor who was doing most of the reverting appeared to be counting votes. The subtle difficulties argued by SlamDiego did not seem to me a strong enough reason to risk confusing newcomers. I'll watch this page to see if there are any more arguments posted for why the more complex notation is needed. EdJohnston 19:33, 19 August 2007 (UTC)
Aren't partial orders transitive by definitions?
[edit]If so, how comes that in the table, the ones counted in column "Transitive" are much less than "All"? --Army1987 14:23, 27 October 2007 (UTC)
- The relevant column is the one labeled "partial order". The one labeled "transitive" counts all transitive relations, some of which (e.g. the complete relation) are not partial orders. —David Eppstein 18:05, 27 October 2007 (UTC)
Transitive antisymmetric binary relations seem interesting. Work or name for them?
[edit]transitive antisymmetric binary relations seem interesting.
- Partially_ordered_set#Formal_definition insists on having the reflexive property, but then in Partially_ordered_set#Strict_and_non-strict_partial_orders goes to either insist on it(called non-strict) or oddly insist it NOT be there (strict, which is irreflexive). (Aside: it also says "irreflexive and transitive, and therefore asymmetric" - Therefore? How?/) Regardless, if you you're going to insist on it then other times insist it NOT be there, wouldn't the case were we don't specify Reflexivity at all be possibly interesting? If not the most interesting?
- Indeed, for the important underlying ordering, it doesn't seem we care much if we're currently using a reflexive relation <= (as subset-eq) or it's irreflexive variant < (as proper subset) to characterize it.
So, why are we even specifying reflexivity either way? - most especially when it seems what's really interesting is just transitive & antisymmetric:
- The transitive is the most interesting (with transitive closure & the like)
- and adding antisymmetric seems to insure we don't have cycles.
So it would seem there should be a name for just "plain old" transitive antisymmetric binary relations. Is there? Any work on them?
And why when searching for this ("transitive antisymmetric) in Wikipedia and in Google, at least on quick look, I find nothing significant? I certainly wouldn't think I was the first to think of this!
Thanks! MBParker (talk) 06:32, 28 December 2007 (UTC)
- You asked, "(Aside: it also says "irreflexive and transitive, and therefore asymmetric" - Therefore? How?/)". Given transitivity, the properties of irreflexivity and asymmetry are equivalent. Asymmetry always implies irreflexivity. For the converse, let R be transitive and irreflexive and assume for contradiction both a R b and b R a hold. By transitivity, a R a, which contradicts irreflexivity. Hence R is asymmetric.
- If R is transitive and antisymmetric, then for any a in the domain of R, the symmetric difference R Δ {a, a} is still transitive and antisymmetric. So one can make any particular element reflexive or irreflexive without affecting the rest of the relation. In particular, the extremal examples of strict partial orders (totally reflexive) and weak partial orders (totally irreflexive) are put into bijective correspondence by adding or removing the diagonal. So strict and weak partial orders are essentially the same, and we can use whichever way of looking at the order is more convenient for a given application. Michael Slone (talk) 07:52, 28 December 2007 (UTC)
The Order theory article
[edit]Order theory is almost the same as this one, shouldn't they be merged? Itaj Sherman (talk) 23:55, 26 January 2008 (UTC)
- Order theory is a major topic of mathematics, occupying an entire number in the mathematics subject classification. There are many types of orders other than partial orders. If the articles are too similar, it is more likely because the order theory article does not devote enough space to those other topics. They should not be merged. —David Eppstein (talk) 00:29, 27 January 2008 (UTC)
OK, what I meant was: these texts thoroughtly repeat each other, and it should be changed somehow. Obviously merging is not the solution, so I suppose that the partial order description in Order theory should be reduced and say "main article Partially ordered set". Itaj Sherman (talk) 12:57, 1 March 2008 (UTC)
Partial order in topological spaces
[edit]The newest addition to this section appears completely out of place. As far as I could tell, it does not treat the partial orders, but states some facts about general "topolical" relations. Should it be moved to "Relation (mathematics)" or just deleted due to its narrow technical nature? Arcfrk (talk) 22:01, 29 May 2008 (UTC)
Wording of chain/antichain
[edit]I realise this is more caused by my relative inexperience with english mathemathical language, but I had to do a double take on the description of a chain which is described as "If any two elements of a poset are comparable, the poset is called a chain". In my first reading this seemed to suggest to me that any poset with two elements that are comparable is a chain, while obviously it is saying that in a chain all elements are mutually comparable. Perhaps this is a mistake that more people would make and I was wondering if it's not possible to change the wording to something that would make that clearer? Wppds (talk) 09:40, 18 May 2010 (UTC)
- It was changed to "every two". — Carl (CBM · talk) 02:09, 16 July 2010 (UTC)
Relation to topological sort
[edit]The article contains the misleading statement that "algorithms for finding linear extensions of partial orders are called topological sorting." This is incomplete because top. sort algorithms take as input a graph that already has all the relations figured out. When talking about extending a partial order, it is more natural to start with an oracle that, given any two elements, says whether they are comparable or returns the larger element. The comparison itself might be hard. Therefore, before you use any topological sort, you need an algorithm like what's described in "Sorting and Selection in Posets" (Constantinos Daskalakis, Richard M. Karp, et al) to create a data structure that describes the ordering efficiently. 173.79.253.13 (talk) 19:59, 14 July 2010 (UTC)
- I suspect you're relying on a conception of poset that feels natural for a computer scientist ("Gee, I don't know this poset unless I possess the entire n×n relation explicitly, because if there are any gaps it may be computationally expensive to figure out how to fill them in"). By contrast, the mathematical definition of poset implies such complete knowledge. You might say that the mathematical perspective is more existential, while its computer-science cousin is more constructivist.—PaulTanenbaum (talk) 01:04, 22 April 2011 (UTC)
- There is very little difference between the mathematical notion of a poset and the CS notion of the transitive closure of a directed acyclic graph. But topological sorting can be applied to any DAG, regardless of whether it is transitively closed. Since many different directed acyclic graphs correspond in this way to a single partial order, the problems of transitive closure and linear extension are distinct, although they are obviously very closely related to each other. —David Eppstein (talk) 02:52, 22 April 2011 (UTC)
- Yes, I'll buy that.—PaulTanenbaum (talk) 03:09, 22 April 2011 (UTC)
- There is very little difference between the mathematical notion of a poset and the CS notion of the transitive closure of a directed acyclic graph. But topological sorting can be applied to any DAG, regardless of whether it is transitively closed. Since many different directed acyclic graphs correspond in this way to a single partial order, the problems of transitive closure and linear extension are distinct, although they are obviously very closely related to each other. —David Eppstein (talk) 02:52, 22 April 2011 (UTC)
New example?
[edit]If there's one flaw that I can see in this otherwise wonderful article, it's that both Hasse diagrams given are those of Boolean lattices (the first for B_3, the second for B_6). Boolean lattices are so well-behaved, it may lead the lay-reader to incorrectly assume things about posets in general. For instance, he or she might think all posets are pure (meaning every maximal chain has the same length) or that all elements at a particular height cover the same number of elements. All in all, I think the Boolean lattices are too nice to demonstrate how complicated and asymmetric posets can be. I'm fine with one Boolean lattice, but both images are Boolean. Do you think we could include a figure of a non-pure poset's Hasse diagram? I'd be more than happy to make one. Dotdotdotatsignapostrophe (talk) 08:18, 5 August 2011 (UTC)
- You make a very good point, and I (for one) would happily take you up on your offer to add a different image. But not without offering my own brilliant idea: I'd point out that it'd be very useful to the non-technical reader if the example's ground set and partial order were both familiar enough to encourage exploration of this Hasse-diagram thing. So, for instance, I'd suggest using as the ground set a collection of members of some well-known family (The Kennedys? The Mountbatten-Windsors?) under the partial order is-descended-from. Judicious inclusion and exclusion of sundry relatives would allow you to illustrate such notions as maximals, minimals, antichains, etc. Heck, it'd even give you an excuse to work the Terminator into your example!—PaulTanenbaum (talk) 00:13, 15 September 2011 (UTC)
- The alternative is a maze of spaghetti, so my feeling is that fewer edges but a greater need for inference is a better choice. —David Eppstein (talk) 17:54, 17 August 2018 (UTC)
Strictness in lead
[edit]Lead reads:
- A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the set, one of the elements precedes the other.
This is the definition of a strict poset. But the article goes on to define an (unqualified) partial order as a non-strict partial order. I'm not sure how to edit the lead's definition so that it is both correct and simple. Ideas? --Macrakis (talk) 20:29, 16 September 2016 (UTC)
Terminology
[edit]I'm referring to the edits of 19-23 Mar 2017: CodeTalker changed "is related to" to "preceeds" in the "Formal definitions" section, to indicate the non-symmetry. Wcherowi reverted that edit, to stay consistent with general terminology. CodeTalker then explicitly mentioned the non-symmetry of "is related to".
However, the "Formal definitions" section now says "A (non-strict) partial order is a binary relation ≤ over a set P." which is far too general. Not until 3 sentences later the defining properties are mentioned, and it isn't clear that they are requirements for (rather than, say, consequences of) a partial order.
More important, the use of "is related to" is now inconsistent with that in the lead, where it means the symmetric closure of ≤ (i.e. it is symmetric in the lead). Also note that the lead uses "preceeds" to mean ≤ itself (I agree with Wcherowi that is is probably inconsistent with general terminology).
Since I couldn't come up with a good solution, I post the issue here. Unlucky versions I thought about were
- use "less than or equal to" for ≤ in the informal explication of the definition (this makes it very clumsy, consider transitivity);
- change the article to mainly explain strict partial orders, and use "less than" for < (this needs major copy-editing, and might be an unusual setting?);
- use "preceeds" with a note to distinguish it from other notions it could be confused with, e.g. the predecessor relation in natural numbers, maybe also the covering relation is called "preceeds" by some authors? (this introduces unusual terminology)
In all these cases, "is related to" could be used for comparability, as now in the lead. Suggestions are welcome. - Jochen Burghardt (talk) 20:45, 23 March 2017 (UTC)
- I think "preceeds" is not typical usage and should be avoided. I made a small copedit which might(?) help with the separation of the axioms from the top of the Formal Definition section. I think "is related to" is fine, as it is normal terminology, but the note that explicitly points out the lack of symmetry may be a good idea. — Carl (CBM · talk) 21:31, 23 March 2017 (UTC)
- I may be partially to blame here. CodeTalker ran his changes by me and I gave them my blessing without looking too closely as I was focusing on the "is related to" issue. I think that Carl's edit has fixed most of the problem, but I am puzzled by Jochen's claim that the symmetric closure is implied in the lead. Am I missing something? In neither of the two instances of the use of "related" is there a symmetric relation around, as far as I can tell.--Bill Cherowitzo (talk) 22:25, 23 March 2017 (UTC)
- @Wcherowi: I mean the lead sentences "The word "partial" in the names "partial order" or "partially ordered set" are used as an indication that not every pair of elements need be related. Instead, some pairs may be incomparable, meaning that neither element precedes the other in the poset. Thus, partial orders generalize the more familiar total orders, in which every pair is related." (actual version after David Eppstein's recent edit) where "related" is tacitly used as synonym of "comparable", i.e. as symmetric closure of ≤.
- In contrast, in the "Formal definition" section, "related" is still introduced as meaning ≤; this inconsistency should be avoided in some way. What about just taking the lead's terminology for "Formal definition", too? - Jochen Burghardt (talk) 10:01, 24 March 2017 (UTC)
- That makes sense. I think we should be able to smooth it out by editing. I made a first pass - please feel free to keep editing it. — Carl (CBM · talk) 11:49, 24 March 2017 (UTC)
- @Jochen Burghardt: Thanks for the explanation. You seem to be saying that comparability is a symmetric property (but it isn't) and that is what threw me off. The issue may be moot now that the appropriate term (comparability) is being used in the lead.
- There is an edit I would like to make but am holding off because I don't have a source, maybe someone can help. It is my understanding that it is common to use the term "precedence" for a partial order in the generic case, but that for specific examples a more natural terminology may be used. For example, subset inclusion or integer divisibility would only rarely be replaced by "precedes". I think that a statement to this effect would be a good addition in the formal definition section after partial order has been defined, as it would clarify the terminology used in the lead. Does anyone know of a reference for this generic comment? --Bill Cherowitzo (talk) 16:16, 24 March 2017 (UTC)
- I thought about replacing the initial image by a family tree image (e.g. File:Waldburg Ahnentafel.jpg which is already used in Structural induction), to start with an illustration that is immediately understandable also for non-mathematicians. The lead's genealogical descendancy example (which I like) could then refer to that image. Does anybody consider this a good idea?
- @Wcherowi: Oops! I indeed thought (and still think) that comparability is a symmetric property, defined as (a≤b or b≤a) or as (a<b or a=b or b<a). Isn't that true?
- I looked for "precedence" in the few books I have available (viz.: Halmos 1976 "Naive Mengenlehre" = "Naive Set Theory"; Birkhoff 1967 "Lattice Theory"; Davey+Priestley 1990 "Introduction to Lattices and Order"), but I didn't find that term there. Halmos uses "kleiner" = "less than", Birkhoff in addition mentions some more particular terms ("contained in", "part of"), Davey+Priestley in addition mention "bigger/smaller" and "better/worse". All very quickly resort to symbol notation, i.e. to "≤" and "<". - Jochen Burghardt (talk) 11:49, 29 March 2017 (UTC)
- @Jochen Burghardt: I think you are using "symmetry" at a higher level than how the term is usually used with respect to relations. For a relation R to be symmetric, (a, b) ∈ R iff (b, a) ∈ R. Thus, the only symmetric partial order is the identity relation since a partial order must be antisymmetric. You seem to be using the symmetry of "or" in viewing the comparability condition (or the Law of Tricotomy) as symmetric. If I'm wrong about this, it could be a language thing ... English can be so pesky at times.--Bill Cherowitzo (talk) 18:12, 29 March 2017 (UTC)
LaTeX vs. HTML
[edit]MOS:FORMULA says:
- "Large scale formatting changes to an article or group of articles are likely to be controversial. One should not change formatting boldly from LaTeX to HTML, nor from non-LaTeX to LaTeX without a clear improvement. Proposed changes should generally be discussed on the talk page of the article before implementation."
No discussion of this sort happened with this article, and it appears to me that the previous version should be restored unless a consensus for a change here is developed. — Carl (CBM · talk) 11:46, 18 December 2017 (UTC)
- I agree. Too many editors are changing formulas from math to html or vice versa. It's pointless churn, it messies our edit histories and watchlists for no good reason, and until we convince the wikimedia developers to give us working math support it's a waste of effort. For now I think we'd be better off maintaining a hiatus on format changes. —David Eppstein (talk) 18:22, 18 December 2017 (UTC)
Lack of definition
[edit]The article says very little about the ordering of ordinal numbers, and when it does, it is in too explanative/introductory phrases that makes it hard to descipher if they represent a tehnical part of the concept.
The only appearance of some sort of "ordinal1 < ordinal2" before the "Von Neumann definition" section is:
- "they start with the natural numbers, 0, 1, 2, 3, 4, 5, … After all natural numbers comes the first infinite ordinal, ω, and after that come ω+1, ω+2, ω+3, and so on".
It is hard to tell if this is a part of the definition, a consequence of the ordinal generation definition, or just an intuition point.
Particularly, when explaining the the ordinal as the equivalence class of sets with same order type, I can't tell how the order of these equivalence classes appear.
Things are better in the "Von Neumann definition" section, since there "element of" is explicitly the order relation -- even though I consider working with "subset of" would be shorter and simpler.
PS: I bet for most readers the punchline is how ω appears and the introductions seems just to be ad-hoc explanations of equivalence classes and orders. Usually the first phrase in Wikipedia articles uniquely targets the concept more accurately than just saying "generalization of natural numbers"188.27.126.226 (talk) 20:04, 20 October 2018 (UTC)
- I guess, your critics is meant for Ordinal number, not Partially ordered set? If yes, you better re-post it at the talk page there. - Jochen Burghardt (talk) 13:13, 21 October 2018 (UTC)
p-ART-ially ordered - A-ntisymmetric, R-eflexive, and T-ransitive
[edit]I have trouble remembering which conditions are on which kind of order. In the name 'pARTial order' the three letters ART remind me that the relation must be antisymmetric, reflexive, and transitive. Acorrector (talk) 10:08, 19 September 2019 (UTC)
- I like this memory aid, and I think it could be helpful for people reading the article; memorising/remembering axioms can be difficult, especially in this case where there are axioms for strict partial orders and non-strict partial orders with similar names (e.g. "antisymmetric" and "asymmetric" - although these both begin with "a" so perhaps this isn't the best example). I would support this memory aid being added to the article if other people agree. Joel Brennan (talk) 21:19, 11 December 2020 (UTC)
Relation of <, ≤, >, ≥
[edit]@JayBeeEll: The reasons why I deleted the text under Partially_ordered_set#Notation are, in more detail:
- It assumes a particular naming. If an ordering relation is called e.g. "R" (which sometimes does happen), the text isn't applicable.
- There are many ways in which one relation may determine another uniquely. People having a background mainly in real analysis may be mislead to think that "≤" is obtained as the complement of ">"; the text gives them no hint.
- The original text also claimed "these definitions are all equivalent", where I couldn't imagine which kind of equivalence is meant. - Thank you for not restoring this sentence.
Now that you intend to use the text as a summary, I additionally see the problem that it introduces the notions "strict" and "non-strict" before they are defined.
For these reasons, I suggest to postpone the text to the end of Partially_ordered_set#Formal_definition, and to mix it with Mathnerd314159's recent addition about orderings defined (redundantly) by 3- or 5-tuples. Also, I would like to edit the text, where necessary, in such a way that e.g. "<" can always be replaced by "R". In particular, I'd like to mention that strict relations are most commonly denoted by "<" or ">", and non-strict ones by "≤" and "≥", and if both "<" and "≤" are used, the former is mostly tacitly understood to be the irreflexive kernel of the latter, etc. And to add a footnote that "≤" needn't be the complement of ">" (or better: a necessary and sufficient condition for being the complement - I guess, connexity). The section heading Partially_ordered_set#Dual_orders should be kept, since this notion is important by its own, but Partially_ordered_set#Equivalence_of_strict_and_non-strict_partial_orders (the heading containing again the misleading "equivalence", and the text being rather verbose) could be dissolved into the postponed summary. I'm not sure about the section heading for the summary, maybe "Redundant definitions"?
What do you think about that? - Jochen Burghardt (talk) 17:58, 25 July 2021 (UTC)
- Regarding calling a relation R - according to googled sources, this refers specifically to a "partial order relation". Describing a poset as a tuple (P,R) does happen (google "javatpoint partial order relation" which is blocked from Wikipedia), but I don't think it's the norm w.r.t. notation. For example [1] switches midway from R to ≤. I think the reason is that the R notation does not express a non-strict / strict distinction, where with ≤ or < it is clear. So replacing ≤,< with R,S, requires a rather long set of definitions. Anyways, following the idea of distinguishing between partial order relations and partially ordered sets, I think the flow should be something like:
- Informal definition
- Partial order relations
- Non-strict, strict
- Notation (defining notation used for the rest of the article, defining strict and non-strict in terms of each other, referring to dual orders via a link in passing)
- Examples
- Then the discussion of the redundancy is limited to the notation section. Is it better? --Mathnerd314159 (talk) 17:16, 26 July 2021 (UTC)
- The source you point to uses R to talk about completely general relations and gives many examples, most of which are not partial orders. It doesn't "switch" from R to ≤; ≤ is just an example of one specific kind of relation. --Macrakis (talk) 17:57, 26 July 2021 (UTC)
- Before page 14 a relation is denoted R, after page 14 a relation is denoted ≤ (or rather the curvy version of ≤). Seems like a switch (in notation) to me. The question is whether it's a good convention that the article should adopt. --Mathnerd314159 (talk) 02:07, 27 July 2021 (UTC)
- The source you point to uses R to talk about completely general relations and gives many examples, most of which are not partial orders. It doesn't "switch" from R to ≤; ≤ is just an example of one specific kind of relation. --Macrakis (talk) 17:57, 26 July 2021 (UTC)
Error in "Correspondence of strict and non-strict partial order relations"?
[edit]Below, isn't the highlighted "" a typo? Shouldn't it be ""?
A non-strict partial order may be converted to a strict partial order by removing all relationships of the form ; that is, the strict partial order is the set , where is the identity relation on and denotes set subtraction.
BrianH123 (talk) 20:09, 2 September 2021 (UTC)
- No, it's ok as is. We are modifying the ≤ relation, not the = relation, so it is the a≤a pairs of the ≤ relation that should be removed. —David Eppstein (talk) 20:32, 2 September 2021 (UTC)
- Well, technically is short for "". So is isn't a relationship at all, it's a formula. It's somewhat of an abuse of notation. is the relationship (tuple element). I've corrected this. --Mathnerd314159 (talk) 19:02, 1 January 2022 (UTC)
Who is ordering? Give an example.
[edit]Who is ordering? Give an example. 2409:4043:2E8E:C8FC:0:0:8089:220D (talk) 17:19, 9 February 2022 (UTC)
- "Ordering" is used as a noun throughout the article, so your question doesn't make sense. - Jochen Burghardt (talk) 09:38, 10 February 2022 (UTC)
The jargonification of the lead section
[edit]This edit by Erel Segal made the first sentence a wall of jargon impenetrable to the vast majority of potential readers. Part of this (the very strange linking to Levi-Cevita symbol) has been improved in subsequent edits, but still I am inclined to do a much more significant revert in order to begin with a potentially comprehensible high-level description. Before I do that, I am checking whether anyone else would like to weigh in on the question. --JBL (talk) 18:53, 1 March 2023 (UTC)
- I did think about reverting it but I think Erel's version satisfies a property that the version before did not, namely that the first sentence actually defines "partial order". I guess what is really needed is a definition like the lead sentence in group (mathematics) (featured article), that starts out informal and then gives the formal properties. Maybe something like this:
- In mathematics, especially order theory, a partially ordered set (poset for short) is a set with a homogeneous binary relation (a partial order) that states whether an elements precedes another element, in such a way that the relation is reflexive, transitive and antisymmetric.
- The other issue is I'm not sure this definition is actually accepted. Last I checked there were still several old textbooks that defined "partial order" to be irreflexive partial orders, so the article was carefully worded to avoid picking a side. I asked ChatGPT and it was like "oh of course partial order means the reflexive version" so maybe the nomenclature has stabilized, but I think just BOLDly changing it without a discussion is probably too bold. Mathnerd314159 (talk) 19:37, 1 March 2023 (UTC)
- Erel Segal merely (1) started with "partial order" rather than with "partially ordered set" (I agree with Mathnerd314159 that this was a good idea, it made the definition simpler and shorter), and (2) rearranged the lead such that the formal definition comes first (I agree with JayBeeEll that this was not a good idea). When we try to remedy (2), we shouldn't use the (old and current) informal phrase "intuitive concept of an ordering, sequencing, or arrangement", since "ordering" is what we are going to explain (and it shouldn't be used in it own explanation), while "sequencing" is adequate for total, but not for partial orders. So I'd suggest something like:
In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders, in which every pair is comparable. Formally, a partial order is a homogeneous binary relation that is reflexive, transitive and antisymmetric. A partially ordered set (poset for short) is a set on which a partial order is defined.
- This is just a rearrangement of old and current lead text, so it might need some further local improvements. - Jochen Burghardt (talk) 11:09, 2 March 2023 (UTC)
- The suggestion in green looks great IMHO. --Erel Segal (talk) 15:07, 2 March 2023 (UTC)
- I agree, I think that's better than any of the recent versions. --JBL (talk) 18:53, 2 March 2023 (UTC)
Done I changed the lead as suggested. Feel free to apply local improvements. - Jochen Burghardt (talk) 19:05, 2 March 2023 (UTC)
- I agree, I think that's better than any of the recent versions. --JBL (talk) 18:53, 2 March 2023 (UTC)
- The suggestion in green looks great IMHO. --Erel Segal (talk) 15:07, 2 March 2023 (UTC)
Converse relation symbol
[edit]@Mathnerd314159: In section Partially ordered set#Informal definition, you reverted my edit "x>y" --> "y<x".
My point is that the section tacitly assumes that the relation is called "<", and that ">" denotes its converse. However, there are also different names for partial orders, like "|" for "is a divisor of", or just "R"; in these cases there are no "natural" symbols for the converse. The authors of the Sage reference manual (citation [1]) apparently didn't think about this issue; however, in the implementation of P.compare_elements(x,y)
they most likely had to consider it, since the name P
has no "natural converse symbol". (I guess, the implementation will look like if (x==y) return 0; else if (P.is_member([x,y])) return -1 else if (P.is_member([y,x])) return 1; else return None;
, using C-like rather than proper Sage syntax).
Another point is that the paragraph tacitly assumes strict partial orders, which are not yet introduced at that point. - Jochen Burghardt (talk) 11:49, 2 March 2023 (UTC)
- In the informal definition section, I am trying to push an alternative definition of partial orders, namely defining them as a comparison operator A -> A -> {GT,LT,EQ,INCOMPARABLE}. The 4-valued comparison operator and the various p.o. relations are two different ways of defining the same thing, and either can be taken as the base notion. I think the 4-valued function definition is clearer as a mental model than the typical p.o. relation presentation (which leads to 4 interconnected relations <, leq, > , geq and confusion as to which relation actually defines the poset). It is possible to define a poset completely in terms of the 4-valued function satisfying some properties (e.g. the anti-symmetry property "compare x y = GT <-> compare y x = LT"), although I haven't found a good source presenting that so it's not in the article. But, taking that definition as the base definition, there is nothing that assumes that ">" denotes a converse, or that strict partial orders exist - those can all be defined in terms of the 4-valued function, e.g. we say x > y holds if compare x y = GT, and similarly x leq y if compare x y is either LT or EQ. Mathnerd314159 (talk) 18:00, 2 March 2023 (UTC)
- Ok, I understood your intention now; and I agree that "GT" is just an operator result, and there is no converse-relation issue. In the article section, it didn't become clear to me that it is supposed to be an alternative definition. Maybe it is a good idea to insert into the article section your above first sentence ("... alternative definition of partial orders, namely defining them as a comparison operator A -> A -> {GT,LT,EQ,INCOMPARABLE}"). Your approach works only for strict partial orders, doesn't it? This should also be mentioned, which, in turn, would require to move the section below Partially_ordered_set#Strict_partial_order. - Jochen Burghardt (talk) 18:18, 2 March 2023 (UTC)
- I tried moving the section, it seems a little better. I'm not really sure what you want the article to say about strict partial orders. Mathnerd314159 (talk) 00:34, 3 March 2023 (UTC)
- I like your new version. I made some minor additions in the Hasse-diagram paragraph, and a suggestion about the cmp function - fell free to revert it. - Jochen Burghardt (talk) 11:42, 3 March 2023 (UTC)
- I tried moving the section, it seems a little better. I'm not really sure what you want the article to say about strict partial orders. Mathnerd314159 (talk) 00:34, 3 March 2023 (UTC)
- Ok, I understood your intention now; and I agree that "GT" is just an operator result, and there is no converse-relation issue. In the article section, it didn't become clear to me that it is supposed to be an alternative definition. Maybe it is a good idea to insert into the article section your above first sentence ("... alternative definition of partial orders, namely defining them as a comparison operator A -> A -> {GT,LT,EQ,INCOMPARABLE}"). Your approach works only for strict partial orders, doesn't it? This should also be mentioned, which, in turn, would require to move the section below Partially_ordered_set#Strict_partial_order. - Jochen Burghardt (talk) 18:18, 2 March 2023 (UTC)
Most general definition
[edit]@Mathnerd314159: The definition by Wallis.2013 (requiring transitivity and antisymmetry only) is quite interesting. I wonder if there are proerties mentioned in the article that are not satisfied by all Wallis-orders. Trying to check, I read through subsection "Extrema", and found that it tacitly assumes that and are weak partial orders, and and are strict ones. I guess this assumption is made thoughout the whole article, and therefore should be mentioned explicitly, preferably in section "Correspondence of strict and non-strict partial order relations", i.e. immediately after weak and strict orders were introduced. If we were to elaborate more on Wallis-orders, we should use an own symbol for them, e.g. , or , or , or something similar. In that case, I'd suggest to insert a subsection for them right after "Strict partial orders". - Jochen Burghardt (talk) 14:33, 4 March 2023 (UTC)
- Well if you think of the partial relation as the matrix then what we're talking about is the diagonal. Irreflexive is all 0's, reflexive is all 1's, and Wallis's general definition allows any mixture of 0's and 1's. There's not really any extra structure allowed by the generality, it's just a partial order with some extra information, similar to how a partial equivalence relation is just an equivalence relation plus a larger domain. Maybe I should just move Wallis to the "alternative definitions" section so that it's clear it's an unusual definition. Mathnerd314159 (talk) 20:31, 4 March 2023 (UTC)
- I did the move. I guess it would be nice if there was a better name for them than Wallis-orders or transitive antisymmetric relations, but searching for it just shows reflexive partial orders and filtering out reflexive gives noise. Mathnerd314159 (talk) 22:04, 4 March 2023 (UTC)
Antisymmetry is counter-intuitive to every order relation in real life
[edit]The article states in requirement 2 that a (partial) order has to be antisymmetric:
- If and then , i.e. no two distinct elements precede each other.
This is 100% counter-intuitive against every real-life order. Take the order of "wealth": If is not wealthier than and not wealthier than there is no need whatsoever that . Or take the order of "body size": If and there may well be that and are different people. Or take as order relation the "largeness of cities": If cities and both have 1.000 inhabitants, then we have and , but there is no need that there is only 1 city with exactly 1.000 inhabitants.
So the question arises: Why do the mathematicians insist on antisymmetry? Against almost every real-life order relation?
It would be easy to allow and handle order relations in which two different elements compare equal; this would be kind of equivalence and could be termed equivalent or equal-valued. With an order relation, if 2 elements are comparable there would be 3 possible outcomes: "greater than", "less than", or "equivalent" (‒ and not only "greater than", "less than", and "identical"). And it would also be easy to allow and define their so-called "non-strict" or "weak" analogues.
(And in the pure mathematical example of the divisibility relation, the surprise that it is an order relation within the natural numbers, but not within the integers would disappear.) ‒Nomen4Omen (talk) 13:31, 1 April 2023 (UTC)
- Your title is badly phrased - antisymmetry is an important property of an order, or rather the strict version (asymmetry): you cannot have both a < b and b < a. All the orders you list satisfy the asymmetry property, except maybe the integers, but even there you can require that the norms are different.
- As far as your actual complaint, I think it is addressed by defining partial orders on a setoid rather than a set. Then = is an equivalence relation rather than an innate notion on sets, and would mean "equivalent" in the sense you desire, avoiding any implication that they are "the same" in a real-life sense. For example, when comparing wealth, it would mean the amounts of wealth are equal, rather than that the people who own the wealth are the same. This is one of the advantages of the definition via a 4-valued comparison operator, in that it does not have a separate = relation so is already generalized this way. I guess I'll add a "partial order on a setoid" definition to the alternative definitions. Mathnerd314159 (talk) 17:44, 1 April 2023 (UTC)
- @Nomen4Omen: I guess what you are looking for is a preorder: it does not require anti-symmetry, and should cover all your given examples. - Jochen Burghardt (talk) 18:35, 1 April 2023 (UTC)
- @Jochen Burghardt:Thank you very much! I did not yet read the whole article, but it may be that preorder is what I am looking for.
- Because we are talking about definitions, we all know that the mathematicians can define almost everything what they want to define.
- Another question: Can you give an example of a weak partial order (= one that allows equality) for which antisymmetry is an important property? ‒Nomen4Omen (talk) 09:20, 2 April 2023 (UTC)
- Weak partial orders are in natural one-to-one correspondence with strict partial orders; among named partial orders, one doesn’t distinguish the two structures by name. If you believe in the virtue of any particular strict partial order (the Boolean lattice, perhaps) then you also automatically believe in its sister weak partial order. —JBL (talk) 22:49, 2 April 2023 (UTC)
- @Nomen4Omen: The first example that comes to my mind is on sets. Many proofs of propositions of the form (with appropriate sets) shows , and then (and then tacitly use anti-symmetry). - Jochen Burghardt (talk) 08:20, 3 April 2023 (UTC)
- See e.g.the proof footnotes in Regular_language#Equivalent_formalisms (where, however, the logic notation and is used rather than the set-theoretic notation and ). - Jochen Burghardt (talk) 08:25, 3 April 2023 (UTC)
- The partial orders you contemplate in your first post here are all of the following form: there is a set P and a function f from P to a total order (probably, R or N) and we declare a < b in the poset if and only if f(a) < f(b). This is an extremely limited class of order relations with very limited structure (just ordinal sums of antichains). There is no need to think about the axiomatic definition of posets if all you want to talk about are such simple order relations. --JBL (talk) 17:38, 3 April 2023 (UTC)
- You are right: they are of this form which is extremely frequent in normal life. The f is kind of a measurement function which supports the ordering of the elements. –Nomen4Omen (talk) 19:17, 3 April 2023 (UTC)