Talk:Partially ordered set

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	Start Class	High Priority	Field: Foundations, logic, and set theory
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. Geometry guy 21:12, 9 July 2007 (UTC)

Contents 1 Introduction 2 Asymetry follows from irreflexivity 2.1 This proof is not non-constructive 3 Example 4 Clarification 5 Visualizing a poset 6 Recent changes of notation 7 Going back to previous notation 8 Aren't partial orders transitive by definitions? 9 Transitive antisymmetric binary relations seem interesting. Work or name for them? 10 The Order theory article 11 Partial order in topological spaces

[edit] 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...)

[edit] 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)

[edit] This proof is not non-constructive

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

which is equivalent, sometimes by definition, to

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

   (assumption)
   ( elimination, from transitivity axiom)
   ( elimination)
   ( elimination, from irreflexivity axiom)
   ( elimination)

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

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

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

1   [transitivity axiom]
2   [irreflexivity axiom]
3  |  [assumption, a and b arbitrary]
4  | |  [assumption]
5  | |  [I 3,4]
6  | |  [E 1]
7  | |  [E 5,6]
8  | |  [E 2]
9  | |  [definition of  8]
10 | |  [E 7,9]
11 |  [I 4-10]
12 |  [definition of  11]
13  [I 3-12]
14  [I 3-13]

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

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

I've taken the liberty of annotating your informal proof with pointers to lines of the formal proof, to make it clear that the formal proof is in fact a more explicit version of the informal proof. You wrote, "since assuming b < a leads to a contradiction, b < a must be false": this is true, but it's true by definition. This means if you want to show , you have to prove , which will necessarily involve a contradiction, but it is not a proof by contradiction in my book. It's just a plain old conditional proof, where the formula you conditionally derive just happens to be a contradiction. "Proof by contradiction" means that you derive something from a contradiction, in other words, you eliminate the contradiction. Note that this is possible in intuitionistic logic, which has rule for elimination (in Natural Deduction), sometimes called "ex falso quodlibet", that allows you to derive any formula you want from a contradiction (but you cannot withdraw any assumptions, for that you need Classical logic). But in this case, the contradiction is not eliminated, and in that sense this is not a "proof by contradiction". --MarkSweep 05:53, 9 Jan 2005 (UTC)

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

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

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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 “” to be incomprehensible. The rest of the changes mostly amounted to turning awkward (and often ungrammatic) constructions into cleaner mathematical expressions. The article, for example, already had “¬” in it; a presumption that a reader who could recognize that couldn't handle “” or “” would be silly. —SlamDiego_←T 21:51, 4 August 2007 (UTC)

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

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

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

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

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

From my point of view, what I did was

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

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

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 “” but against the use of quantifiers and junctors where I found their use to be unnecessarily formalistic and where I thought that their use actually reduced the readability of the article. However, if other readers and editors prefer the current version I can certainly live with that. — Tobias Bergemann 08:06, 6 August 2007 (UTC)

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

I am not a mathematician. However, an expression like

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

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

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

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

But that's rather beside the point. The choice between verbal expression and formal expression is non-rival; the article can have both. I'd like it to have formal expressions because they can be clean and unambiguous; I think that verbal expressions before or after would also be a Good Thing.

However, my main concerns are:

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 “” notation does not help anything but make the text harder to understand. Oleg Alexandrov (talk) 15:02, 6 August 2007 (UTC)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)