Content deleted Content added
m stop it |
→Introduction: Reply |
||
| (135 intermediate revisions by 51 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=C|vital=yes|1=
{{WikiProject Mathematics|small=|importance=high}}
}}
== Introduction ==
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. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/128.101.184.204|128.101.184.204]] ([[User talk:128.101.184.204|talk]]) 03:44, 22 March 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
The term "genealogical descendancy" is not clear, especially relating to reflexivity and anti-symmetry properties. <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Mochan Shrestha|Mochan Shrestha]] ([[User talk:Mochan Shrestha|talk]] • [[Special:Contributions/Mochan Shrestha|contribs]]) 10:38, 2 July 2009 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
I think the wording 'Formally, a partial order..." so on should be modified to 'Formally, a partial orderING...'; I don't know, it bugs with my mind of the choice of words, leading me to think that an ordering of the elements is the appropriate choice since, ordering is the order of the elements resulting from a rule, which here is the definition of the partial ordering, right? <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/27.5.142.196|27.5.142.196]] ([[User talk:27.5.142.196#top|talk]]) 19:47, 28 May 2025 (UTC)</small>
:Google Scholar appears to have roughly three times as many hits for "a partial order" as it does for "a partial ordering". See [[WP:COMMONNAME]]. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 01:06, 30 May 2025 (UTC)
== Asymetry follows from irreflexivity ==
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 [[intuitionism|intuitionists]] eschew. [[User:Paul August|Paul August ]] [[User_talk:Paul August|☎]] 17:53, Jan 6, 2005 (UTC)
=== This proof is not non-constructive ===
::Hold on, what makes that proof non-constructive? We're asked to show that
Line 40 ⟶ 60:
::::Nowhere does this use an elimination rule for <math>\bot</math>, so it's valid in minimal logic. --[[User:MarkSweep|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? [[User:Paul August|Paul August ]] [[User_talk: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 <math>\lnot P</math>, you have to prove <math>P \to \bot</math>, 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 <math>\bot</math> 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". --[[User:MarkSweep|MarkSweep]] 05:53, 9 Jan 2005 (UTC)
'''Negated''' statements are "classical" (regular) so 'proofs by contradiction' are intuitionistically valid. [[User:DefLog|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. --[[User:Vaughan Pratt|Vaughan Pratt]] 08:31, 15 July 2007 (UTC)
== Example ==
I have finally gotten tired of looking at this .. as a Democrat <B>AND</B> a member of the Sierra Club, (and a "paramathematician") even <B>I</B> 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 order|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. [[User:Vonkje|Vonkje]] 20:30, 11 August 2005 (UTC)
== Improve Examples. ==
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 ==
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 [[Graph_%28mathematics%29|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. --[[User:Vaughan Pratt|Vaughan Pratt]] 08:39, 15 July 2007 (UTC)
== Visualizing a poset ==
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
* grandparent 2
** parent 2 (''see'' grandparent 1)
** parent 3
Is there an article on this general topic? [[User:Modify|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:
[[File:Set inclusion.jpg|thumb]] <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Dgluss|Dgluss]] ([[User talk:Dgluss#top|talk]] • [[Special:Contributions/Dgluss|contribs]]) 17:12, 17 August 2018 (UTC)</small> <!--Autosigned by SineBot-->
: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. —[[User:David Eppstein|David Eppstein]] ([[User talk: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.
[[User:Dgluss|Dgluss]] ([[User talk:Dgluss|talk]]) 17:49, 17 August 2018 (UTC)
== Recent changes of notation ==
I am unhappy with [http://en.wikipedia.org/w/index.php?title=Partially_ordered_set&diff=149061372&oldid=148341910 the recent changes in the notation] that were introduced by [[User:SlamDiego|SlamDiego]]. I fear that the notation used in the article as it stands now is incomprehensible to the layman. — [[User:Tobias Bergemann|Tobias Bergemann]] 07:37, 4 August 2007 (UTC)
:The ''lay''person 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 “<math>\preceq</math>” 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 “<math>\land</math>” or “<math>\lor</math>” would be silly. —[[User:SlamDiego|SlamDiego]]<sub><span style="font-size:x-small;">[[User_talk:SlamDiego|←T]]</span></sub> 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. —[[User:David Eppstein|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. —[[User:SlamDiego|SlamDiego]]<sub><span style="font-size:x-small;">[[User_talk:SlamDiego|←T]]</span></sub> 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. —[[User:David Eppstein|David Eppstein]] 02:07, 5 August 2007 (UTC)
:::#I didn't edit the lead, so that's irrelevant to the dispute here.
:::#[[User:Tobias Bergemann|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.
:::—[[User:SlamDiego|SlamDiego]]<sub><span style="font-size:x-small;">[[User_talk:SlamDiego|←T]]</span></sub> 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 “<math>\preceq</math>” 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. — [[User:Tobias Bergemann|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. —[[User:SlamDiego|SlamDiego]]<sub><span style="font-size:x-small;">[[User_talk:SlamDiego|←T]]</span></sub> 20:28, 6 August 2007 (UTC)
::::::I am not a mathematician. However, an expression like
:::::::<math>\left\{\left[\left(a\preceq b\right)\land\left(b\preceq c\right)\right]\Rightarrow\left(a\preceq c\right)\right\}~\forall\left(a,b,c\right)\in P^3</math>
::::::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". — [[User:Tobias Bergemann|Tobias Bergemann]] 07:19, 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 ''in''formal than what some of my instructors would have wanted. A more fully fomral expression would be
::::::::<math>\left\langle\left\{\left[\left(a\preceq b\right)\land\left(b\preceq c\right)\right]\Rightarrow\left(a\preceq c\right)\right\}\Leftarrow\left(a,b,c\right)\in P^3\right\rangle~\forall\left(a,b,c\right)</math>
:::::::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''+'''i'''''y'' < ''u''+'''i'''''v'' 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 100'''i'''.
:::::::#that, ''whatever'' decision is taken on formalism, there be no misrepresentation here of what it does and does not effect or preclude.
:::::::—[[User:SlamDiego|SlamDiego]]<sub><span style="font-size:x-small;">[[User_talk:SlamDiego|←T]]</span></sub> 22:27, 7 August 2007 (UTC)
I strongly prefer the usual ≤ notation. It is the standard notation used for partially ordered sets, and adding in the “<math>\preceq</math>” notation does not help anything but make the text harder to understand. [[User:Oleg Alexandrov|Oleg Alexandrov]] ([[User talk: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. [[User:Oleg Alexandrov|Oleg Alexandrov]] ([[User talk: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 “<math>\preceq</math>” 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. —[[User:SlamDiego|SlamDiego]]<sub><span style="font-size:x-small;">[[User_talk:SlamDiego|←T]]</span></sub> 20:28, 6 August 2007 (UTC)
::On ≤ vs <math>\scriptstyle\preceq</math> I tend to agree: ≤ may be a little more standard in this context (I've seen it both ways) but <math>\scriptstyle\preceq</math> 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. —[[User:David Eppstein|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. [[User:Oleg Alexandrov|Oleg Alexandrov]] ([[User talk:Oleg Alexandrov|talk]]) 03:13, 7 August 2007 (UTC)
::::The reader can be explicitly ''told'' that arthimetic <math>\le</math> is a special case of <math>\preceq</math> after being informed of the general concept. Until the general concept is absorbed, even if the reader has somewhere being told that <math>\preceq</math> 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 [[Frank P. Ramsey|Ramsey]]'s brilliant exposition on SEU exactly because he used “<math>\le</math>” for <math>\preceq</math> as well as for arithmetic <math>\le</math>. —[[User:SlamDiego|SlamDiego]]<sub><span style="font-size:x-small;">[[User_talk:SlamDiego|←T]]</span></sub> 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. [[User:Oleg Alexandrov|Oleg Alexandrov]] ([[User talk: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''. —[[User:SlamDiego|SlamDiego]]<sub><span style="font-size:x-small;">[[User_talk:SlamDiego|←T]]</span></sub> 07:30, 8 August 2007 (UTC)
== Going back to previous notation ==
After a week during which all parties had the chance to make their case, I [http://en.wikipedia.org/w/index.php?title=Partially_ordered_set&diff=150607043&oldid=149639093 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 <math>\preceq</math> notation. Comments? [[User:Oleg Alexandrov|Oleg Alexandrov]] ([[User talk: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. --[[User:Trovatore|Trovatore]] 06:53, 19 August 2007 (UTC)
:<math>\preceq</math> 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. --[[User:Digby Tantrum|Mark H Wilkinson]] <sup>([[User talk:Digby Tantrum|t]], [[Special:Contributions/Digby Tantrum|c]])</sup> 07:02, 19 August 2007 (UTC)
: Our [[WP:MSM|mathematics Manual of Style]] explicitly discourages formal notation such as quantifiers when prose will suffice. Oleg is quite right to revert.
: Using the curly "<tt>\preceq</tt>" symbol is something I might favor in a mathematics text, but not here. Although we have a choice of three Unicode characters ("<big style="font-size:162%">≼</big>", "<big style="font-size:162%">⪯</big>", and "<big style="font-size:162%">⪳</big>" — 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. --[[User:KSmrq|KSmrq]]<sup>[[User talk:KSmrq|T]]</sup> 10:32, 19 August 2007 (UTC)
Certainly, <math>\leq</math> 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. [[User:Arcfrk|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. [[User:EdJohnston|EdJohnston]] 19:33, 19 August 2007 (UTC)
== Aren't partial orders transitive by definitions? ==
If so, how comes that in the table, the ones counted in column "Transitive" are much less than "All"? --[[User:Army1987|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. —[[User:David Eppstein|David Eppstein]] 18:05, 27 October 2007 (UTC)
== Transitive antisymmetric binary relations seem interesting. Work or name for them? ==
[[transitive relation|transitive]] [[antisymmetric relation|antisymmetric]] [[binary relation]]s seem interesting.
* [[Partially_ordered_set#Formal_definition]] insists on having [[reflexive relation|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 relation|irreflexive]]). (Aside: it also says "[[irreflexive relation|irreflexive]] and [[transitive relation|transitive]], and therefore [[asymmetric relation|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 [[reflexive relation|reflexivity]] either way? - most especially when it seems what's really interesting is just transitive & antisymmetric''':
* The [[transitive relation|transitive]] is the most interesting (with [[transitive closure]] & the like)
* and adding [[antisymmetric relation|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) [http://en.wikipedia.org/wiki/Special:Search?search=transitive+antisymmetric&go=Go in Wikipedia] and [http://www.google.com/search?q=transitive+antisymmetric 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! [[User:MBParker|MBParker]] ([[User talk:MBParker|talk]]) 06:32, 28 December 2007 (UTC)
:You asked, "(Aside: it also says "[[irreflexive relation|irreflexive]] and [[transitive relation|transitive]], and therefore [[asymmetric relation|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. [[User:Michael Slone|Michael Slone]] ([[User talk:Michael Slone|talk]]) 07:52, 28 December 2007 (UTC)
== The [[Order theory]] article ==
[[Order theory]] is almost the same as this one, shouldn't they be merged? [[User:Itaj Sherman|Itaj Sherman]] ([[User talk: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. —[[User:David Eppstein|David Eppstein]] ([[User talk: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]]". [[User:Itaj Sherman|Itaj Sherman]] ([[User talk:Itaj Sherman|talk]]) 12:57, 1 March 2008 (UTC)
== Partial order in topological spaces ==
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? [[User:Arcfrk|Arcfrk]] ([[User talk:Arcfrk|talk]]) 22:01, 29 May 2008 (UTC)
== Wording of chain/antichain ==
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? [[User:Wppds|Wppds]] ([[User talk:Wppds|talk]]) 09:40, 18 May 2010 (UTC)
:It was changed to "every two". — Carl <small>([[User:CBM|CBM]] · [[User talk:CBM|talk]])</small> 02:09, 16 July 2010 (UTC)
== Relation to [[topological sort]] ==
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. [[Special:Contributions/173.79.253.13|173.79.253.13]] ([[User talk: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.—[[User:PaulTanenbaum|PaulTanenbaum]] ([[User talk: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. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 02:52, 22 April 2011 (UTC)
:::Yes, I'll buy that.—[[User:PaulTanenbaum|PaulTanenbaum]] ([[User talk:PaulTanenbaum|talk]]) 03:09, 22 April 2011 (UTC)
== New example? ==
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. [[User:Dotdotdotatsignapostrophe|Dotdotdotatsignapostrophe]] ([[User talk: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-Windsor]]s?) 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 [[Arnold Schwartzenegger|the Terminator]] into your example!—[[User:PaulTanenbaum|PaulTanenbaum]] ([[User talk: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. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:54, 17 August 2018 (UTC)
==Strictness in lead==
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? --[[User:Macrakis|Macrakis]] ([[User talk:Macrakis|talk]]) 20:29, 16 September 2016 (UTC)
== Terminology ==
I'm referring to the edits of 19-23 Mar 2017: {{u|CodeTalker}} changed ''"is related to"'' to ''"preceeds"'' in the "Formal definitions" section, to indicate the non-symmetry. {{u|Wcherowi}} reverted that edit, to stay consistent with general terminology. {{u|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 {{u|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. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk: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 <small>([[User:CBM|CBM]] · [[User talk:CBM|talk]])</small> 21:31, 23 March 2017 (UTC)
::I may be partially to blame here. {{u|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.--[[User:Wcherowi|Bill Cherowitzo ]] ([[User talk:Wcherowi|talk]]) 22:25, 23 March 2017 (UTC)
:::{{ping|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 {{u|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? - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk: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 <small>([[User:CBM|CBM]] · [[User talk:CBM|talk]])</small> 11:49, 24 March 2017 (UTC)
::{{ping|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? --[[User:Wcherowi|Bill Cherowitzo ]] ([[User talk:Wcherowi|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?
:::{{ping|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 "<". - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 11:49, 29 March 2017 (UTC)
::{{ping|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.--[[User:Wcherowi|Bill Cherowitzo ]] ([[User talk:Wcherowi|talk]]) 18:12, 29 March 2017 (UTC)
== LaTeX vs. HTML ==
[[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 <small>([[User:CBM|CBM]] · [[User talk:CBM|talk]])</small> 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. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:22, 18 December 2017 (UTC)
== Lack of definition ==
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"[[Special:Contributions/188.27.126.226|188.27.126.226]] ([[User talk: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. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 13:13, 21 October 2018 (UTC)
== p-ART-ially ordered - A-ntisymmetric, R-eflexive, and T-ransitive ==
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. [[User:Acorrector|Acorrector]] ([[User talk: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. [[User:Joel Brennan|Joel Brennan]] ([[User talk:Joel Brennan|talk]]) 21:19, 11 December 2020 (UTC)
== Relation of <, ≤, >, ≥ ==
{{ping|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 {{u|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? - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk: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 [https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap07.pdf] 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? --[[User:Mathnerd314159|Mathnerd314159]] ([[User talk: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. --[[User:Macrakis|Macrakis]] ([[User talk: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. --[[User:Mathnerd314159|Mathnerd314159]] ([[User talk:Mathnerd314159|talk]]) 02:07, 27 July 2021 (UTC)
== Error in "Correspondence of strict and non-strict partial order relations"? ==
Below, isn't the highlighted "<math>a \leq a</math>" a typo? Shouldn't it be "<math>a = a</math>"?
<blockquote>A non-strict partial order <math>\leq</math> may be converted to a strict partial order by removing all relationships of the form {{highlight|<math>a \leq a</math>}}; that is, the strict partial order is the set <math>< \; := \ \leq\ \setminus \ \Delta_P</math>, where <math>\Delta_P := \{ (p, p) : p \in P \}</math> is the [[identity relation]] on <math>P \times P</math> and <math>\;\setminus\;</math> denotes [[set subtraction]].</blockquote> [[User:BrianH123|BrianH123]] ([[User talk: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. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 20:32, 2 September 2021 (UTC)
:Well, technically <math>a \leq a</math> is short for "<math>(a,a)\in\leq</math>". So <math>a \leq a</math> is isn't a relationship at all, it's a [[Well-formed formula|formula]]. It's somewhat of an abuse of notation. <math>(a,a)</math> is the relationship (tuple element). I've corrected this. --[[User:Mathnerd314159|Mathnerd314159]] ([[User talk:Mathnerd314159|talk]]) 19:02, 1 January 2022 (UTC)
== Who is ordering? Give an example. ==
Who is ordering? Give an example. [[Special:Contributions/2409:4043:2E8E:C8FC:0:0:8089:220D|2409:4043:2E8E:C8FC:0:0:8089:220D]] ([[User talk: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. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 09:38, 10 February 2022 (UTC)
== The jargonification of the lead section ==
[https://en.wikipedia.org/w/index.php?title=Partially_ordered_set&diff=prev&oldid=1142087144 This edit] by {{u|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. --[[User:JayBeeEll|JBL]] ([[User_talk:JayBeeEll|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 relation|reflexive]], [[Transitive relation|transitive]] and [[Antisymmetric relation|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. [[User:Mathnerd314159|Mathnerd314159]] ([[User talk:Mathnerd314159|talk]]) 19:37, 1 March 2023 (UTC)
:{{u|Erel Segal}} merely '''(1)''' started with "partial order" rather than with "partially ordered set" (I agree with {{u|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 {{u|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:
:{{tq|In mathematics, especially order theory, a '''partial order''' on a [[Set (mathematics)|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 order]]s, in which every pair is comparable. Formally, a '''partial order''' is a [[homogeneous binary relation]] that is [[Reflexive relation|reflexive]], [[Transitive relation|transitive]] and [[Antisymmetric relation|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. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 11:09, 2 March 2023 (UTC)
::The suggestion in green looks great IMHO. --[[User:Erel Segal|Erel Segal]] ([[User talk:Erel Segal|talk]]) 15:07, 2 March 2023 (UTC)
:::I agree, I think that's better than any of the recent versions. --[[User:JayBeeEll|JBL]] ([[User_talk:JayBeeEll|talk]]) 18:53, 2 March 2023 (UTC)
::::{{done}} I changed the lead as suggested. Feel free to apply local improvements. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 19:05, 2 March 2023 (UTC)
== Converse relation symbol ==
{{ping|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 <code>P.compare_elements(x,y)</code> they most likely had to consider it, since the name <code>P</code> has no "natural converse symbol". (I guess, the implementation will look like <code>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;</code>, using [[C (programming language)|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. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk: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. [[User:Mathnerd314159|Mathnerd314159]] ([[User talk: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]]. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk: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. [[User:Mathnerd314159|Mathnerd314159]] ([[User talk: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. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 11:42, 3 March 2023 (UTC)
== Most general definition ==
{{ping|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 <math>\leq</math> and <math>\geq</math> are weak partial orders, and <math> < </math> and <math> > </math> 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. <math>\precsim</math>, or <math>\vartriangleleft</math>, or <math>\curlyeqprec</math>, or something similar. In that case, I'd suggest to insert a subsection for them right after "Strict partial orders". - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 14:33, 4 March 2023 (UTC)
:Well if you think of the partial relation as the matrix <math>P \times P</math> 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. [[User:Mathnerd314159|Mathnerd314159]] ([[User talk: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. [[User:Mathnerd314159|Mathnerd314159]] ([[User talk:Mathnerd314159|talk]]) 22:04, 4 March 2023 (UTC)
== Antisymmetry is counter-intuitive to every order relation in real life ==
The article states in requirement 2 that a (partial) order has to be [[Antisymmetric relation|antisymmetric]]:
* If <math>a \leq b</math> and <math>b \leq a</math> then <math>a = b</math>, 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 <math>A</math> is not wealthier than <math>B</math> and <math>B</math> not wealthier than <math>A</math> there is no need whatsoever that <math>A = B</math>. Or take the order of "body size": If <math>A \leq B</math> and <math>B \leq A</math> there may well be that <math>A</math> and <math>B</math> are different people. Or take as order relation the "largeness of cities": If cities <math>A</math> and <math>B</math> both have 1.000 inhabitants, then we have <math>A \leq B</math> and <math>B \leq A</math>, 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 (ring theory)|divisibility]] relation, the surprise that it is an order relation within the [[natural number]]s, but not within the [[integer]]s would disappear.) ‒[[User:Nomen4Omen|Nomen4Omen]] ([[User talk: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. [[User:Mathnerd314159|Mathnerd314159]] ([[User talk:Mathnerd314159|talk]]) 17:44, 1 April 2023 (UTC)
:{{ping|Nomen4Omen}} I guess what you are looking for is a [[preorder]]: it does not require anti-symmetry, and should cover all your given examples. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 18:35, 1 April 2023 (UTC)
::{{Ping|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? ‒[[User:Nomen4Omen|Nomen4Omen]] ([[User talk: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. —[[User:JayBeeEll|JBL]] ([[User_talk:JayBeeEll|talk]]) 22:49, 2 April 2023 (UTC)
:::{{ping|Nomen4Omen}} The first example that comes to my mind is <math>\subseteq</math> on sets. Many proofs of propositions of the form <math>A = B</math> (with <math>A, B</math> appropriate sets) shows <math>A \subseteq B</math>, and then <math>B \subseteq A</math> (and then tacitly use anti-symmetry). - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk: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 <math>\Rightarrow</math> and <math>\Leftrightarrow</math> is used rather than the set-theoretic notation <math>\subseteq</math> and <math>=</math>). - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk: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. --[[User:JayBeeEll|JBL]] ([[User_talk:JayBeeEll|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. –[[User:Nomen4Omen|Nomen4Omen]] ([[User talk:Nomen4Omen|talk]]) 19:17, 3 April 2023 (UTC)
| |||