![]() | This ![]() It is of interest to the following WikiProjects: | ||||||||||
|
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)
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 ...
(assumption) ( elimination, from transitivity axiom) ( elimination) ( elimination, from irreflexivity axiom) ( elimination)
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]
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)
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)
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:
I replaced this with the three or four examples that appear in the undergraduate (discrete) textbooks. Vonkje 20:30, 11 August 2005 (UTC)
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.
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:
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:
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:
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.
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:
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:
— Preceding unsigned comment added by Dgluss ( talk • contribs) 17:12, 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)
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)
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)
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)
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)
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)
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)
transitive antisymmetric binary relations seem interesting.
So, why are we even specifying reflexivity either way? - most especially when it seems what's really interesting is just transitive & antisymmetric:
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)
Order theory is almost the same as this one, shouldn't they be merged? Itaj Sherman ( talk) 23:55, 26 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)
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)
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)
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)
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)
Lead reads:
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)
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
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)
MOS:FORMULA says:
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)
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:
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 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)
@ JayBeeEll: The reasons why I deleted the text under Partially_ordered_set#Notation are, in more detail:
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)
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)
Who is ordering? Give an example. 2409:4043:2E8E:C8FC:0:0:8089:220D ( talk) 17:19, 9 February 2022 (UTC)
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)
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.
@ 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)
@ 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)
The article states in requirement 2 that a (partial) order has to be antisymmetric:
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)
![]() | This ![]() It is of interest to the following WikiProjects: | ||||||||||
|
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)
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 ...
(assumption) ( elimination, from transitivity axiom) ( elimination) ( elimination, from irreflexivity axiom) ( elimination)
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]
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)
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)
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:
I replaced this with the three or four examples that appear in the undergraduate (discrete) textbooks. Vonkje 20:30, 11 August 2005 (UTC)
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.
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:
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:
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:
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.
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:
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:
— Preceding unsigned comment added by Dgluss ( talk • contribs) 17:12, 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)
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)
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)
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)
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)
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)
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)
transitive antisymmetric binary relations seem interesting.
So, why are we even specifying reflexivity either way? - most especially when it seems what's really interesting is just transitive & antisymmetric:
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)
Order theory is almost the same as this one, shouldn't they be merged? Itaj Sherman ( talk) 23:55, 26 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)
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)
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)
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)
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)
Lead reads:
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)
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
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)
MOS:FORMULA says:
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)
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:
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 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)
@ JayBeeEll: The reasons why I deleted the text under Partially_ordered_set#Notation are, in more detail:
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)
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)
Who is ordering? Give an example. 2409:4043:2E8E:C8FC:0:0:8089:220D ( talk) 17:19, 9 February 2022 (UTC)
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)
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.
@ 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)
@ 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)
The article states in requirement 2 that a (partial) order has to be antisymmetric:
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)