Talk:Partially ordered set

From Wikipedia, the free encyclopedia

Contents 1 Introduction 2 Asymetry follows from irreflexivity 2.1 This proof is not non-constructive 3 Example 4 Clarification

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

[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.