Talk:Partially ordered set

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. —Preceding unsigned comment added by 128.101.184.204 (talk) 03:44, 22 March 2009 (UTC)

The term "genealogical descendancy" is not clear, especially relating to reflexivity and anti-symmetry properties. —Preceding unsigned comment added by Mochan Shrestha (talk • contribs) 10:38, 2 July 2009 (UTC)

Asymetry follows from irreflexivity

Am I wrong or follows asymmetry of a strict partial order already from irreflexivity and transitivity? If a < b and b < a then by transitivity would a < a which is a contradiction to irreflexivity. So b < a must be false ...

Yes, as your proof shows, irreflexivity and transitivity imply asymmetry. Although your proof makes use of Reductio ad absurdum, which in turn makes use of the law of the excluded middle which some mathematicians called intuitionists eschew. Paul August ☎ 17:53, Jan 6, 2005 (UTC)

This proof is not non-constructive

Hold on, what makes that proof non-constructive? We're asked to show that

$\lnot (a<b\land b<a)$

which is equivalent, sometimes by definition, to

$(a<b\land b<a)\to \bot$

in both classical and intuitionistic logic. Now prove the conditional by assuming its antecedent and deriving its consequent:

  $a<b\land b<a$ (assumption)
  $(a<b\land b<a)\to a<a$ ($\forall$ elimination, from transitivity axiom)
  $a<a\,\!$ ($\to$ elimination)
  $a<a\to \bot$ ($\forall$ elimination, from irreflexivity axiom)
  $\bot$ ($\to$ elimination)

Which proves the conditional. It's straightforward constructive reasoning, no? --MarkSweep 18:50, 6 Jan 2005 (UTC)

The first proof given above is non-contstructive since it is a proof by contradiction. Your proof may be constructive but I'm not an expert and I'm not sure if it does not somehow make use of the assumption that (A or not A) is always true. In particular I would wonder about the equivalence for (not A) that you use above, since in intuitionist logic (not A) is defined differently than in classical logic. Paul August ☎ 21:05, Jan 6, 2005 (UTC)

No, the first proof above is essentially the same proof as mine (with perhaps another layer of implication on the outside), and it is constructive. Just because a proof uses a contradiction $\bot$ doesn't mean it's non-constructive. If you define $\lnot A$ as $A\to \bot$ as usual, then natural deduction systems for classical, intuitionistic, and minimal logic only differ in terms of which (if any) form the elimination rule for $\bot$ takes. However, in the proof above, one doesn't eliminate $\bot$ at all, so it is in fact valid in minimal logic, which does not allow $\bot$ elimination. Observe:

1  $(\forall x,y,z)x<y\land y<z\to x<z$ [transitivity axiom]
2  $(\forall x)\lnot (x<x)$ [irreflexivity axiom]
3  | $a<b\,\!$ [assumption, a and b arbitrary]
4  | | $b<a\,\!$ [assumption]
5  | | $a<b\land b<a$ [$\land$I 3,4]
6  | | $a<b\land b<a\to a<a$ [$\forall$E 1]
7  | | $a<a\,\!$ [$\to$E 5,6]
8  | | $\lnot (a<a)$ [$\forall$E 2]
9  | | $a<a\to \bot$ [definition of $\lnot$ 8]
10 | | $\bot$ [$\to$E 7,9]
11 | $b<a\to \bot$ [$\to$I 4-10]
12 | $\lnot (b<a)$ [definition of $\lnot$ 11]
13 $a<b\to \lnot (b<a)$ [$\to$I 3-12]
14 $(\forall x,y)x<y\to \lnot (y<x)$ [$\forall$I 3-13]

Nowhere does this use an elimination rule for $\bot$, so it's valid in minimal logic. --MarkSweep 00:44, 7 Jan 2005 (UTC)

Well, I might be wrong ;-) but I assumed that the first poster's proof was essentially the following: Suppose a < b (line 3). We want to show that it is not the case that b < a. Now assume that b < a (line 4), then by transitivity (line 6), a < a (line 7), but this is a contradiction (line 10) by irreflexivity (line 8), therefore since assuming b < a leads to a contradiction (line 11), b < a must be false (line 12), QED. Is this not an example of "proof by contradiction? Don't the intuitionists reject this method of proof? Paul August ☎ 01:09, Jan 9, 2005 (UTC)

I've taken the liberty of annotating your informal proof with pointers to lines of the formal proof, to make it clear that the formal proof is in fact a more explicit version of the informal proof. You wrote, "since assuming b < a leads to a contradiction, b < a must be false": this is true, but it's true by definition. This means if you want to show $\lnot P$, you have to prove $P\to \bot$, 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 $\bot$ elimination (in Natural Deduction), sometimes called "ex falso quodlibet", that allows you to derive any formula you want from a contradiction (but you cannot withdraw any assumptions, for that you need Classical logic). But in this case, the contradiction is not eliminated, and in that sense this is not a "proof by contradiction". --MarkSweep 05:53, 9 Jan 2005 (UTC)

Negated statements are "classical" (regular) so 'proofs by contradiction' are intuitionistically valid. DefLog 02:47, 9 Jan 2005 (UTC)

Intuitionistic logic lets you infer ¬Q → ¬P from P → Q, though not the other direction (the best it lets you get from ¬Q → ¬P is P → ¬¬Q). Write ¬(a<a) for irreflexivity, ¬(a<b ∧ b<a) for antisymmetry, and a<b<c → a<c for transitivity. Now instantiate c with a in transitivity, infer ¬(a<a) → ¬(a<b ∧ b<a), and use modus ponens with this and irreflexivity to get antisymmetry. You can't get much more constructive than that, or direct for that matter. --Vaughan Pratt 08:31, 15 July 2007 (UTC)

Example

I have finally gotten tired of looking at this .. as a Democrat AND a member of the Sierra Club, (and a "paramathematician") even I cannot figure out this example. All this aside, this example illustrates systemic bias by assuming all Wikipedians are U.S. citizens who understand the parties involved. As someone else pointed out, using a social science metaphor to illustrate a mathematical concept has problems of its own. So I yanked the example and put it here in case anyone wants to argue about this:

Unlike a total ordering, a partial ordering need not guarantee the mutual comparability of all objects in the set. For example, we could define an ordering ⊆ on the set of all political organizations such that a⊆b if every member of a is also a member of b. This would be only a partial ordering: if a is the Sierra Club and b is the Democratic Party, then neither a⊆b nor b⊆a holds. An example of a total ordering would be to define a≤b if the name of organization a precedes that of b in alphabetical order. Partially ordered sets are studied in order theory.

I replaced this with the three or four examples that appear in the undergraduate (discrete) textbooks. Vonkje 20:30, 11 August 2005 (UTC)

Improve Examples.

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 directed graph.

Notice that there is no "R" relationship between foo.c and bar.c, or between foo.o and bar.o. In the directed graph, the foo branch and the bar branch are separate. It doesn't matter whether you build foo.o first or bar.o first, you are free to build them in either order.

Example 2, import statements in the Python programming language. Source file X may "import" source file Y, so that the objects defined in Y are available in X's namespace, and can be used by code in X. This could be notated as "Y ≤ X" and it often means that the file Y was written before the file X.

In a large collection of files, many of the files may import others, and transitivity applies: if X imports Y and Y imports Z, then the objects defined in Z are accessible somewhere in X's namespace. But there may be two files U and V where neither imports the other, either directly or through a transitive chain.

The above (light on total vs. partial) is a reasonable criticism if applied to the section on inverses. I expanded that section a little to try to clarify the difference. --Vaughan Pratt 08:39, 15 July 2007 (UTC)

Visualizing a poset

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? 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)

The Hasse diagram includes only the relations that cannot be inferred from other ones using the transitive law. So your inclusion diagram is not a Hasse diagram. Yes, the Hasse diagram fully describes the partial order, but not directly by its arrows. Two elements are ordered when there is a directed path between them, not just a single edge. —David Eppstein (talk) 17:17, 17 August 2018 (UTC)

Thanks, I see that now, but that leads to the question, is this a good way to demonstrate a poset? You need to use the properties of the poset to infer the full dependencies, but isn't that property just the thing we're trying to show? I was unaware of the definition of Hasse diagram and should have looked that up first, so I learned something today. Dgluss (talk) 17:49, 17 August 2018 (UTC)

Recent changes of notation

I am unhappy with the recent changes in the notation that were introduced by SlamDiego. I fear that the notation used in the article as it stands now is incomprehensible to the layman. — Tobias Bergemann 07:37, 4 August 2007 (UTC)

The layperson is going to see “≤” and think immediately and only of an arthimetic relation. A layperson who mistakenly believes that he understands what is written is in far worse shape than one who might take “$\preceq$” 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 “$\land$” or “$\lor$” would be silly. —SlamDiego_←T 21:51, 4 August 2007 (UTC)

I agree with Tobias and have gone a little way towards restoring the readability of the article. Your argument about laypeople reads to me like you are deliberately trying to make the article notation-heavy and difficult to read in order to scare away the non-mathematicians. That does not seem like the right way to go, to me. —David Eppstein 23:32, 4 August 2007 (UTC)

Avoid ad hominem attacks on my motives, okay? You're perfectly out-of-line. I have no desire to scare away laypeople. The article was written in a way that would mislead laypeople, and the quality of wording wasn't great.

There are many things that could be done with the notation that would be better than what was there, and some of them would be different from what I did. As far as I can see, what you've done is

• prefix the quantifiers, rather than postfix them, which doesn't make a whole lot of difference
• unpack some of the Cartesian products — notwithstanding that the article elsewhere presumed that the reader could deal with Cartesian products

I have no great objections to either of these changes. —SlamDiego_←T 01:49, 5 August 2007 (UTC)

From my point of view, what I did was

• complete rewrite the lede to more gently introduce the topic and avoid technical jargon,
• supplement the notation-only formal definition with an English description of each property, and
• rewrite the quantified formulas, getting rid of unneeded and confusing braces and brackets, and incidentally prefixing the quantifiers

To my mind, the first two of these changes are far more important than the third. —David Eppstein 02:07, 5 August 2007 (UTC)

1. I didn't edit the lead, so that's irrelevant to the dispute here.
2. Tobias Bergemann didn't call for supplemental wording, and I stated no position on that matter, so that's irrelevant to the dispute here.
3. 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.
4. I agree that the first two classes of changes are more important; but, again, they aren't what was under dispute.

—SlamDiego_←T 02:19, 5 August 2007 (UTC)

My initial comment wasn't clear, I apologize. I did not want to object against the change from “≤” to “$\preceq$” but against the use of quantifiers and junctors where I found their use to be unnecessarily formalistic and where I thought that their use actually reduced the readability of the article. However, if other readers and editors prefer the current version I can certainly live with that. — Tobias Bergemann 08:06, 6 August 2007 (UTC)

What prevailed earlier was a mix of formal notation and quasi-English were a layreader would have to struggle even to simply discern whether what seemed to be a parenthetical note were that or the parentheses were used to indicate precedence of a junctor, and whether indeed any given “and” or “or” were Boolean operators or natural language. (There isn't a simple mapping from one to the other.) The best solution is to provide both clean formal expressions and supplementary wording. Slapping things down, as if speaking and writing quickly on a chalk-board in a class-room setting with 45 minutes before the bell, will fail far more readers than even a fairly spartan formalism. —SlamDiego_←T 20:28, 6 August 2007 (UTC)

I am not a mathematician. However, an expression like

$\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}$

strikes me as far more formalistic than anything I have seen used in the literature, especially when compared with the plain-text

For all a, b, and c in P, we have that if a ≤ b and b ≤ c then a ≤ c.

which still manages to communicate the definition with only little if any ambiguity. That's what I meant when I called your changes "unnecessarily formalistic". — Tobias Bergemann 07:19, 7 August 2007 (UTC)

Not only have I seen a lot of expressions about such things that are that formalistic, but it happens to be more informal than what some of my instructors would have wanted. A more fully fomral expression would be

$\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)$

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:

1. that the wretched use of “≤” be avoided;
2. that, formally or verbally, there be nothing again like this

   This is not to say that the complex numbers cannot be totally ordered; we could for example order them lexicographically via x+iy < u+iv if and only if x < u or (x = u and y < v), but this is not ordering by magnitude in any reasonable sense as it makes 1 greater than 100i.

3. that, whatever decision is taken on formalism, there be no misrepresentation here of what it does and does not effect or preclude.

—SlamDiego_←T 22:27, 7 August 2007 (UTC)

I strongly prefer the usual ≤ notation. It is the standard notation used for partially ordered sets, and adding in the “$\preceq$” notation does not help anything but make the text harder to understand. Oleg Alexandrov (talk) 15:02, 6 August 2007 (UTC)

And I also object to the quantifiers spread out all over the place. This article is already complex enough, being about an abstract topic. There is no need to obfuscate it further. Oleg Alexandrov (talk) 15:04, 6 August 2007 (UTC)

I don't regard the “≤” notation as usual or standard. The bald claim that readers will find it harder to understand “$\preceq$” flies in the face of the fact that most laypeople have little or no exposure to non-arthimetic math, and will generally begin by mistaking “≤” as standing for an arithmetic relation. Let's not do that to them. —SlamDiego_←T 20:28, 6 August 2007 (UTC)

On ≤ vs $\scriptstyle \preceq$ I tend to agree: ≤ may be a little more standard in this context (I've seen it both ways) but $\scriptstyle \preceq$ is better for conveying the idea that the relation may not necessarily be the familiar numeric comparison. As for the quantifiers, I think it's usually preferable to spell them out in words: it takes little more space, remains as rigorous, and isn't as intimidating to nonmathematicians. —David Eppstein 20:48, 6 August 2007 (UTC)

Yes, the disadvantage of ≤ is that it may be confused with the numerical comparison. On the other hand, this may be an advantage too, since it conveys to the reader that partially ordered sets are abstract generalizations of the usual less-than-or-equal-to relation. I would argue that on the whole having "≤" in would help, rather than hinder, the exposition of the article. Oleg Alexandrov (talk) 03:13, 7 August 2007 (UTC)

The reader can be explicitly told that arthimetic $\leq$ is a special case of $\preceq$ after being informed of the general concept. Until the general concept is absorbed, even if the reader has somewhere being told that $\preceq$ is not necessarily arithmetic, his or her mind is typically going to be derailed by the notion. A classic example of this was in the protracted failure of the world to recognize Ramsey's brilliant exposition on SEU exactly because he used “$\leq$” for $\preceq$ as well as for arithmetic $\leq$. —SlamDiego_←T 22:09, 7 August 2007 (UTC)

It is not going to be derailed by the notion of arithmetic order, the old usual order will help the reader get an intuition for the new abstract one. I suggest the article be moved back to the original notation. Oleg Alexandrov (talk) 03:48, 8 August 2007 (UTC)

That's perfectly wrong; and, noting the case of Ramsey, I gave a classical illustration of how wrong it is. It is a constant struggle to get people to step away from presumptions of quantification, and the “≤” notation suckers them viciously. —SlamDiego_←T 07:30, 8 August 2007 (UTC)

Going back to previous notation

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 $\preceq$ notation. Comments? Oleg Alexandrov (talk) 17:02, 11 August 2007 (UTC)

The ordinary ≤ is quite standard; the curly form looks frankly like an affectation here. Curly inequality signs have various good uses but this isn't one of the compelling ones. --Trovatore 06:53, 19 August 2007 (UTC)

$\preceq$ and quantifier notation will be largely meaningless to someone unused to the great game. Mathematics articles have sufficient potential for being inaccessible to laymen without unexplained uses of either. --Mark H Wilkinson ^{(t, c)} 07:02, 19 August 2007 (UTC)

Our mathematics Manual of Style explicitly discourages formal notation such as quantifiers when prose will suffice. Oleg is quite right to revert.

Using the curly "\preceq" symbol is something I might favor in a mathematics text, but not here. Although we have a choice of three Unicode characters ("≼", "⪯", and "⪳" — U+227C, U+2AAF, and U+2AB3), many readers will see these as "missing character" glyphs; thus we are forced to use TeX to generate an image of the character, which frequent editors know we try to avoid for inline formulae. We have no vital semantic reasons to insist on a special character; use of ordinary "≤" is common in mathematical practice, and a certain amount of explanation is inevitable with either choice of character. --KSmrq^T 10:32, 19 August 2007 (UTC)

Certainly, $\leq$ is the standard notation, with alternatives being used primarily when more than one poset structure on a given set is considered. I've especially checked Stanley, vol.1 (which should be added to the reference list), and he uses the ordinary "less than or equal to" sign. Moreover, over 100 articles in Category:Order theory have been written using this notation, so there is only one possible choice for the parent article.

On the second point, concerning quantifiers: insistence on converting meaningful word statements into logic formulae with abundance of symbols was one of the hallmarks of the New Math and related movements, which ended in a total disaster. The idea that in this day and age (post Bourbaki), mathematicians would prefer the logic formulae to worded definitions is, quite frankly, preposterous. For example, Stanley (a great expositor) does not use them at all in the chapter on partially ordered sets, and quite possibly, anywhere throughout "Enumerative combinatorics". Outside of set theory and logic, it seems that the quantifier notation is widely used only in some real analysis textbooks. Other than a strong personal opinion of one (or two?) editor(s), unsupported by evidence, I do not discern a "case" having been made for their use. Arcfrk 10:45, 19 August 2007 (UTC)

I support the use of simpler notation as advocated above by Oleg, Digby, Mark, Trovatore, KSMrq and Arcfrk, since I noticed that the editor who was doing most of the reverting appeared to be counting votes. The subtle difficulties argued by SlamDiego did not seem to me a strong enough reason to risk confusing newcomers. I'll watch this page to see if there are any more arguments posted for why the more complex notation is needed. EdJohnston 19:33, 19 August 2007 (UTC)

Aren't partial orders transitive by definitions?

If so, how comes that in the table, the ones counted in column "Transitive" are much less than "All"? --Army1987 14:23, 27 October 2007 (UTC)

The relevant column is the one labeled "partial order". The one labeled "transitive" counts all transitive relations, some of which (e.g. the complete relation) are not partial orders. —David Eppstein 18:05, 27 October 2007 (UTC)

Transitive antisymmetric binary relations seem interesting. Work or name for them?

transitive antisymmetric binary relations seem interesting.

• Partially_ordered_set#Formal_definition insists on having the reflexive property, but then in Partially_ordered_set#Strict_and_non-strict_partial_orders goes to either insist on it(called non-strict) or oddly insist it NOT be there (strict, which is irreflexive). (Aside: it also says "irreflexive and transitive, and therefore asymmetric" - Therefore? How?/) Regardless, if you you're going to insist on it then other times insist it NOT be there, wouldn't the case were we don't specify Reflexivity at all be possibly interesting? If not the most interesting?
• Indeed, for the important underlying ordering, it doesn't seem we care much if we're currently using a reflexive relation <= (as subset-eq) or it's irreflexive variant < (as proper subset) to characterize it.

So, why are we even specifying reflexivity either way? - most especially when it seems what's really interesting is just transitive & antisymmetric:

• The transitive is the most interesting (with transitive closure & the like)
• and adding antisymmetric seems to insure we don't have cycles.

So it would seem there should be a name for just "plain old" transitive antisymmetric binary relations. Is there? Any work on them?

And why when searching for this ("transitive antisymmetric) in Wikipedia and in Google, at least on quick look, I find nothing significant? I certainly wouldn't think I was the first to think of this!

Thanks! MBParker (talk) 06:32, 28 December 2007 (UTC)

You asked, "(Aside: it also says "irreflexive and transitive, and therefore asymmetric" - Therefore? How?/)". Given transitivity, the properties of irreflexivity and asymmetry are equivalent. Asymmetry always implies irreflexivity. For the converse, let R be transitive and irreflexive and assume for contradiction both a R b and b R a hold. By transitivity, a R a, which contradicts irreflexivity. Hence R is asymmetric.

If R is transitive and antisymmetric, then for any a in the domain of R, the symmetric difference R Δ {a,  a} is still transitive and antisymmetric. So one can make any particular element reflexive or irreflexive without affecting the rest of the relation. In particular, the extremal examples of strict partial orders (totally reflexive) and weak partial orders (totally irreflexive) are put into bijective correspondence by adding or removing the diagonal. So strict and weak partial orders are essentially the same, and we can use whichever way of looking at the order is more convenient for a given application. Michael Slone (talk) 07:52, 28 December 2007 (UTC)

The Order theory article

Order theory is almost the same as this one, shouldn't they be merged? Itaj Sherman (talk) 23:55, 26 January 2008 (UTC)

Order theory is a major topic of mathematics, occupying an entire number in the mathematics subject classification. There are many types of orders other than partial orders. If the articles are too similar, it is more likely because the order theory article does not devote enough space to those other topics. They should not be merged. —David Eppstein (talk) 00:29, 27 January 2008 (UTC)

OK, what I meant was: these texts thoroughtly repeat each other, and it should be changed somehow. Obviously merging is not the solution, so I suppose that the partial order description in Order theory should be reduced and say "main article Partially ordered set". Itaj Sherman (talk) 12:57, 1 March 2008 (UTC)

Partial order in topological spaces

The newest addition to this section appears completely out of place. As far as I could tell, it does not treat the partial orders, but states some facts about general "topolical" relations. Should it be moved to "Relation (mathematics)" or just deleted due to its narrow technical nature? Arcfrk (talk) 22:01, 29 May 2008 (UTC)

Wording of chain/antichain

I realise this is more caused by my relative inexperience with english mathemathical language, but I had to do a double take on the description of a chain which is described as "If any two elements of a poset are comparable, the poset is called a chain". In my first reading this seemed to suggest to me that any poset with two elements that are comparable is a chain, while obviously it is saying that in a chain all elements are mutually comparable. Perhaps this is a mistake that more people would make and I was wondering if it's not possible to change the wording to something that would make that clearer? Wppds (talk) 09:40, 18 May 2010 (UTC)

It was changed to "every two". — Carl (CBM · talk) 02:09, 16 July 2010 (UTC)

Relation to topological sort

The article contains the misleading statement that "algorithms for finding linear extensions of partial orders are called topological sorting." This is incomplete because top. sort algorithms take as input a graph that already has all the relations figured out. When talking about extending a partial order, it is more natural to start with an oracle that, given any two elements, says whether they are comparable or returns the larger element. The comparison itself might be hard. Therefore, before you use any topological sort, you need an algorithm like what's described in "Sorting and Selection in Posets" (Constantinos Daskalakis, Richard M. Karp, et al) to create a data structure that describes the ordering efficiently. 173.79.253.13 (talk) 19:59, 14 July 2010 (UTC)

I suspect you're relying on a conception of poset that feels natural for a computer scientist ("Gee, I don't know this poset unless I possess the entire n×n relation explicitly, because if there are any gaps it may be computationally expensive to figure out how to fill them in"). By contrast, the mathematical definition of poset implies such complete knowledge. You might say that the mathematical perspective is more existential, while its computer-science cousin is more constructivist.—PaulTanenbaum (talk) 01:04, 22 April 2011 (UTC)

There is very little difference between the mathematical notion of a poset and the CS notion of the transitive closure of a directed acyclic graph. But topological sorting can be applied to any DAG, regardless of whether it is transitively closed. Since many different directed acyclic graphs correspond in this way to a single partial order, the problems of transitive closure and linear extension are distinct, although they are obviously very closely related to each other. —David Eppstein (talk) 02:52, 22 April 2011 (UTC)

Yes, I'll buy that.—PaulTanenbaum (talk) 03:09, 22 April 2011 (UTC)

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. Dotdotdotatsignapostrophe (talk) 08:18, 5 August 2011 (UTC)

You make a very good point, and I (for one) would happily take you up on your offer to add a different image. But not without offering my own brilliant idea: I'd point out that it'd be very useful to the non-technical reader if the example's ground set and partial order were both familiar enough to encourage exploration of this Hasse-diagram thing. So, for instance, I'd suggest using as the ground set a collection of members of some well-known family (The Kennedys? The Mountbatten-Windsors?) under the partial order is-descended-from. Judicious inclusion and exclusion of sundry relatives would allow you to illustrate such notions as maximals, minimals, antichains, etc. Heck, it'd even give you an excuse to work the Terminator into your example!—PaulTanenbaum (talk) 00:13, 15 September 2011 (UTC)

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? --Macrakis (talk) 20:29, 16 September 2016 (UTC)

Terminology

I'm referring to the edits of 19-23 Mar 2017: CodeTalker changed "is related to" to "preceeds" in the "Formal definitions" section, to indicate the non-symmetry. Wcherowi reverted that edit, to stay consistent with general terminology. CodeTalker then explicitly mentioned the non-symmetry of "is related to".

However, the "Formal definitions" section now says "A (non-strict) partial order is a binary relation ≤ over a set P." which is far too general. Not until 3 sentences later the defining properties are mentioned, and it isn't clear that they are requirements for (rather than, say, consequences of) a partial order.

More important, the use of "is related to" is now inconsistent with that in the lead, where it means the symmetric closure of ≤ (i.e. it is symmetric in the lead). Also note that the lead uses "preceeds" to mean ≤ itself (I agree with Wcherowi that is is probably inconsistent with general terminology).

Since I couldn't come up with a good solution, I post the issue here. Unlucky versions I thought about were

• use "less than or equal to" for ≤ in the informal explication of the definition (this makes it very clumsy, consider transitivity);
• change the article to mainly explain strict partial orders, and use "less than" for < (this needs major copy-editing, and might be an unusual setting?);
• use "preceeds" with a note to distinguish it from other notions it could be confused with, e.g. the predecessor relation in natural numbers, maybe also the covering relation is called "preceeds" by some authors? (this introduces unusual terminology)

In all these cases, "is related to" could be used for comparability, as now in the lead. Suggestions are welcome. - Jochen Burghardt (talk) 20:45, 23 March 2017 (UTC)

I think "preceeds" is not typical usage and should be avoided. I made a small copedit which might(?) help with the separation of the axioms from the top of the Formal Definition section. I think "is related to" is fine, as it is normal terminology, but the note that explicitly points out the lack of symmetry may be a good idea. — Carl (CBM · talk) 21:31, 23 March 2017 (UTC)

I may be partially to blame here. CodeTalker ran his changes by me and I gave them my blessing without looking too closely as I was focusing on the "is related to" issue. I think that Carl's edit has fixed most of the problem, but I am puzzled by Jochen's claim that the symmetric closure is implied in the lead. Am I missing something? In neither of the two instances of the use of "related" is there a symmetric relation around, as far as I can tell.--Bill Cherowitzo (talk) 22:25, 23 March 2017 (UTC)

@Wcherowi: I mean the lead sentences "The word "partial" in the names "partial order" or "partially ordered set" are used as an indication that not every pair of elements need be related. Instead, some pairs may be incomparable, meaning that neither element precedes the other in the poset. Thus, partial orders generalize the more familiar total orders, in which every pair is related." (actual version after David Eppstein's recent edit) where "related" is tacitly used as synonym of "comparable", i.e. as symmetric closure of ≤.

In contrast, in the "Formal definition" section, "related" is still introduced as meaning ≤; this inconsistency should be avoided in some way. What about just taking the lead's terminology for "Formal definition", too? - Jochen Burghardt (talk) 10:01, 24 March 2017 (UTC)

That makes sense. I think we should be able to smooth it out by editing. I made a first pass - please feel free to keep editing it. — Carl (CBM · talk) 11:49, 24 March 2017 (UTC)

@Jochen Burghardt: Thanks for the explanation. You seem to be saying that comparability is a symmetric property (but it isn't) and that is what threw me off. The issue may be moot now that the appropriate term (comparability) is being used in the lead.

There is an edit I would like to make but am holding off because I don't have a source, maybe someone can help. It is my understanding that it is common to use the term "precedence" for a partial order in the generic case, but that for specific examples a more natural terminology may be used. For example, subset inclusion or integer divisibility would only rarely be replaced by "precedes". I think that a statement to this effect would be a good addition in the formal definition section after partial order has been defined, as it would clarify the terminology used in the lead. Does anyone know of a reference for this generic comment? --Bill Cherowitzo (talk) 16:16, 24 March 2017 (UTC)

I thought about replacing the initial image by a family tree image (e.g. File:Waldburg Ahnentafel.jpg which is already used in Structural induction), to start with an illustration that is immediately understandable also for non-mathematicians. The lead's genealogical descendancy example (which I like) could then refer to that image. Does anybody consider this a good idea?

@Wcherowi: Oops! I indeed thought (and still think) that comparability is a symmetric property, defined as (a≤b or b≤a) or as (a<b or a=b or b<a). Isn't that true?

I looked for "precedence" in the few books I have available (viz.: Halmos 1976 "Naive Mengenlehre" = "Naive Set Theory"; Birkhoff 1967 "Lattice Theory"; Davey+Priestley 1990 "Introduction to Lattices and Order"), but I didn't find that term there. Halmos uses "kleiner" = "less than", Birkhoff in addition mentions some more particular terms ("contained in", "part of"), Davey+Priestley in addition mention "bigger/smaller" and "better/worse". All very quickly resort to symbol notation, i.e. to "≤" and "<". - Jochen Burghardt (talk) 11:49, 29 March 2017 (UTC)

@Jochen Burghardt: I think you are using "symmetry" at a higher level than how the term is usually used with respect to relations. For a relation R to be symmetric, (a, b) ∈ R iff (b, a) ∈ R. Thus, the only symmetric partial order is the identity relation since a partial order must be antisymmetric. You seem to be using the symmetry of "or" in viewing the comparability condition (or the Law of Tricotomy) as symmetric. If I'm wrong about this, it could be a language thing ... English can be so pesky at times.--Bill Cherowitzo (talk) 18:12, 29 March 2017 (UTC)

LaTeX vs. HTML

MOS:FORMULA says:

"Large scale formatting changes to an article or group of articles are likely to be controversial. One should not change formatting boldly from LaTeX to HTML, nor from non-LaTeX to LaTeX without a clear improvement. Proposed changes should generally be discussed on the talk page of the article before implementation."

No discussion of this sort happened with this article, and it appears to me that the previous version should be restored unless a consensus for a change here is developed. — Carl (CBM · talk) 11:46, 18 December 2017 (UTC)

I agree. Too many editors are changing formulas from math to html or vice versa. It's pointless churn, it messies our edit histories and watchlists for no good reason, and until we convince the wikimedia developers to give us working math support it's a waste of effort. For now I think we'd be better off maintaining a hiatus on format changes. —David Eppstein (talk) 18:22, 18 December 2017 (UTC)