Partially ordered set

In mathematics, a partially ordered set (or poset for short) is a set equipped with a partial order relation, formalizing the intuitive concept of a (not necessarily total order) ordering. == Example == Unlike a total order, 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. == Formal definition == A partial order is a binary relation ''R'' over a set ''P'' which is reflexive relation, antisymmetric relation, and transitive relation, i.e., for all ''a'', ''b'' and ''c'' in ''P'', we have that: *''aRa'' (reflexivity); *if ''aRb'' and ''bRa'' then ''a'' = ''b'' (antisymmetry); and *if ''aRb'' and ''bRc'' then ''aRc'' (transitivity). A set with a partial order is called a partially ordered set. The term ''ordered set'' is sometimes also used for posets, as long as it is clear from the context that no other kinds of orders are meant. In particular, totally ordered sets can also be referred to as "ordered sets", especially in areas where these structures are more common than posets. However, most articles should not cause confusion as long as all formal definitions employ exact terminology. == Strict and weak partial orders == In some contexts, the partial order defined above is called a weak (or reflexive) partial order. In these contexts a strict (or irreflexive) partial order is a binary relation which is irreflexive relation and transitive relation, and therefore asymmetric relation. In other words, for all ''a'', ''b'', and ''c'' in ''P'', we have that: *¬(''aRa'') (irreflexivity); *if ''aRb'' then ¬(''bRa'') (asymmetry); and *if ''aRb'' and ''bRc'' then ''aRc'' (transitivity). If ''R'' is a weak partial order, then ''R'' − {(''a'', ''a'') | ''a'' in ''P''} is the corresponding strict partial order. Similarly, every strict partial order has a corresponding weak partial order, and so the two definitions are essentially equivalent. Strict partial orders are also useful because they correspond more directly to directed acyclic graphs (dags): every strict partial order is a dag, and the transitive closure of a dag is both a strict partial order and also a dag itself. == See also == *order theory *preorder *total order *directed set *equivalence relation Order theory Set theory

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...) == Asymetry follows from irreflexivity == Am I wrong or follows asymmetry of a strict partial order already from irreflexivity and transitivity? If ''a'' < ''b'' and ''b'' < ''a'' then by transitivity would ''a'' < ''a'' which is a contradiction to irreflexivity. So ''b'' < ''a'' must be false ... :Yes, as your proof shows, irreflexivity and transitivity imply asymmetry. Although your proof makes use of Reductio ad absurdum, which in turn makes use of the law of the excluded middle which ''some'' mathematicians called intuitionism eschew. User:Paul August User_talk:Paul August 17:53, Jan 6, 2005 (UTC) === This proof is not non-constructive === ::Hold on, what makes that proof non-constructive? We're asked to show that :::

\lnot (a

::which is equivalent, sometimes by definition, to ::: $(a$ ::in both classical and intuitionistic logic. Now prove the conditional by assuming its antecedent and deriving its consequent: $a$ (assumption) $(a$ ( $\forall$ elimination, from transitivity axiom) $a (\to elimination) a (\forall elimination, from irreflexivity axiom) \bot (\to elimination)

::Which proves the conditional. It's straightforward constructive reasoning, no? --$ User: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. User:Paul August User_talk: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 [transitivity axiom]
2 (\forall x) \lnot (x [irreflexivity axiom]
3 | a [assumption, a and b arbitrary]
4 | | b [assumption]
5 | | a$ [ $\land$ I 3,4] 6 | | $a$ [ $\forall$ E 1] 7 | | $a [\to E 5,6]
8 | | \lnot(a [\forall E 2]
9 | | a [definition of \lnot 8]
10 | | \bot [\to E 7,9]
11 | b [\to I 4-10]
12 | \lnot(b [definition of \lnot 11]
13 a$ [ $\to$ I 3-12] 14 $(\forall x,y) x [\forall I 3-13]
::::Nowhere does this use an elimination rule for \bot, so it's valid in minimal logic. --$ User:MarkSweep 00:44, 7 Jan 2005 (UTC) Well, I might be wrong ;-) but I assumed that the first poster's proof was essentially the following: Suppose ''a'' < ''b'' (line 3). We want to show that it is not the case that ''b'' < ''a''. Now assume that ''b'' < ''a'' (line 4), then by transitivity (line 6), ''a'' < ''a'' (line 7), but this is a contradiction (line 10) by irreflexivity (line 8), therefore since assuming ''b'' < ''a'' leads to a contradiction (line 11), ''b'' < ''a'' must be false (line 12), QED. Is this not an example of "proof by contradiction? Don't the intuitionists reject this method of proof? User:Paul August User_talk:Paul August 01:09, Jan 9, 2005 (UTC) :I've taken the liberty of annotating your informal proof with pointers to lines of the formal proof, to make it clear that the formal proof is in fact a more explicit version of the informal proof. You wrote, "since assuming ''b'' < ''a'' leads to a contradiction, ''b'' < ''a'' must be false": this is true, but it's true by definition. This means if you want to show $\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". --User:MarkSweep 05:53, 9 Jan 2005 (UTC) Negated statements are "classical" (regular) so 'proofs by contradiction' are intuitionistically valid. User:DefLog 02:47, 9 Jan 2005 (UTC)

See other meanings of words starting from letter:
P
PA | PB | PC | PD | PE | PF | PG | PH | PI | PJ | PK | PL | PM | PN | PO | PR | PS | PT | PU | PW | PX | PY | PZ |

Words begining with Partially_ordered_set:

Partially_ordered_set
Partially_ordered_set
Partially_ordered_sets