请输入您要查询的字词:

 

单词 Poset
释义

poset

\\xyoption

all

A poset, or partially ordered setMathworldPlanetmath, consists of a set Pand a binary relationMathworldPlanetmath on P which satisfies the followingproperties:

  • is reflexiveMathworldPlanetmathPlanetmath (http://planetmath.org/Reflexive), so aa alwaysholds;

  • is antisymmetric, so if ab and ba hold, thena=b; and

  • is transitiveMathworldPlanetmathPlanetmathPlanetmathPlanetmath (http://planetmath.org/Transitive3), so if aband bc hold, then ac also holds.

The relationMathworldPlanetmath is called a partial orderMathworldPlanetmath on P. Inpractice, (P,) is usually conflated with P; if a distinction isneeded, P is called the ground set or underlying set of (P,).The binary relation < defined by removing the diagonal from (i.e.  a<b iff ab and ab) satisfies the following properties:

  • < is irreflexiveMathworldPlanetmath, so if a<b holds, then b<a does nothold; and

  • < is transitive.

Since is reflexive, it can be uniquely recovered from < by addingthe diagonal. For this reason, an irreflexive and transitive binaryrelation < (called a strict partial order) also defines a poset, by meansof the associated relation described above (which is called weak partial order).

Since every partial order is reflexive and transitive, every poset isa preorderMathworldPlanetmath. The notion of partial order is stricter than that ofpreorder, Let Q be the structureMathworldPlanetmath with ground set Q={a,b} andbinary relation ={(a,a),(a,b),(b,a),(b,b)}. A diagramof this structure, omitting loops, is displayed below.

\\xymatrixb\\ar@//[d]a\\ar@//[u]

Observe that the binary relation on Q is reflexive and transitive,so Q is a preorder. On the other hand, ab and ba, while ab. So the binary relation on Q is notantisymmetric, implying that Q is not a poset.

Since every total orderMathworldPlanetmath is reflexive, antisymmetric, and transitive,every total order is a poset. The notion of partial order is weakerthan that of total order. A total order must obey the trichotomy law,which states that for any a and b in the order, either ab orba. Let P be the structure with ground set {a,b,c} andbinary relation ={(a,a),(a,b),(a,c),(b,b),(c,c)}. Adiagram of this structure, omitting loops, is displayed below.

\\xymatrixb&&c&a\\ar[ul]\\ar[ur]&

Observe that the binary relation on P is reflexive, antisymmetric,and transitive, so P is a poset. On the other hand, neither bc nor cb holds in P. Thus P fails to satisfy thetrichotomy law and is not a total order.

The failure of the trichotomy law for posets motivates the followingterminology. Let P be a poset. If ab or ba holds inP, we say that a and b are comparable; otherwise, we saythey are incomparable. We use the notation abto indicate that a and b are incomparable.

If (P,P) and (Q,Q) are posets, then a functionMathworldPlanetmathφ:PQ is said to be order-preserving, ormonotone, provided that it preserves inequalities. That is,φ is order-preserving if whenever aPb holds, it followsthat φ(a)Qφ(b) also holds. The identity functionMathworldPlanetmath onthe ground set of a poset is order-preserving. If (P,P),(Q,Q), and (R,R) are posets and φ:PQ andψ:QR are order-preserving functions, then thecompositionMathworldPlanetmath ψφ:PR is also order-preserving.

Posets together with order-preserving functions form a category, whichwe denoted by 𝐏𝐨𝐬𝐞𝐭. Thus an order-preserving functionbetween the ground sets of two posets is sometimes also called amorphism of posets. The category of posets hasarbitrary productsPlanetmathPlanetmath (http://planetmath.org/ProductofPosets). Moreover, everyposet can itself be viewed as a category, and it turns out that amorphism of posets is the same as a functor between the two posets.

Examples of posets

The two extreme posets are the chain, in which any two elements arecomparable, and the antichainMathworldPlanetmath, in which no two elements arecomparable. A poset with a singleton underlying set is necessarilyboth a chain and an antichain, but a poset with a larger underlyingset cannot be both.

Example 1.

Let be the set of natural numbers. Inductively define abinary relation on by the following rules:

  • for any n, the relation 0n holds; and

  • whenever mn, the relation m+1n+1 also holds.

Then (,) is a chain, hence a poset. This structure canbe naturally embedded in the larger chains of the integers, therational numbers, and the real numbers.

The next example shows that nontrivial antichains exist.

Example 2.

Let P be a set with cardinality greater than 1. Let be thediagonal of P. Thus represents equality, which is trivially apartial order relation (which is also the intersectionDlmfMathworldPlanetmath of all partialorderings on P). By construction, ab in P if and onlya=b. Thus no two elements of P are comparable.

So far the only posets we have seen are chains and antichains. Mostposets are neither. The following construction gives many suchexamples.

Example 3.

If X is any set, the powerset P=P(X) of X is partially orderedby inclusion, that is, by the relation AB if and only ifAB.

There are important structure theorems for posets concerning chainsand antichains. One of the foundational results is Dilworth’stheorem. This theorem was massively generalized by Greene andKleitman.

A final example shows that one can manufacture a poset from an existing one.

Example 4.

Let P be a poset ordered by . The dual poset of P is defined asfollows: it has the same underlying set as P, whose order is defined by abiff ba. It is easy to see that is a partial order. The dual of Pis usually denoted by P.

Graph-theoretical view of posets

Let P be a poset with strict partial order <. Then P can beviewed as a directed graphMathworldPlanetmath with vertex set the ground set of P andedge set <. For example, the following diagram displays the BooleanalgebraMathworldPlanetmath B2 as a directed graph.

\\xymatrix&{0,1}&{0}\\ar[ur]&&{1}\\ar[ul]&\\ar[ul]\\ar[uu]\\ar[ur]&

If P is a sufficiently complicated poset, then drawing all of theedges of P can obscure rather than reveal the structure of P. Forthis reason it is convenient to restrict attention to a subrelation of< from which < can be uniquely recovered.

We describe a method of constructing a canonical subgraphMathworldPlanetmath of P fromwhich the partial order can be recovered as long as every interval ofP has finite height. If a and b are elements of P, then wesay that b covers a if a<b and there are no elements ofP strictly larger than a but strictly smaller than b, that is, if[a,b]={a,b}. Two elements are said to be consecutive ifone covers another. Define a binary relation <: on P by

a<:b if and only if b covers a.

By construction, the binary relation <: is a subset of <. Since< is transitive, the transitiveclosureMathworldPlanetmath (http://planetmath.org/ClosureOfASetViaRelations) of <: is also contained in <.

Proposition.

Suppose every interval of P has finite height. Then < is thetransitive closure of <:.

Proof.

We prove this by inductionMathworldPlanetmath on height. By definition of <:, if a<band the height of [a,b] is 1, then a<:b.

Assume for induction that whenever a<b and the height of [a,b] isat most n, then (a,b) is in the transitive closure of <:.Suppose that a<b and that the height of [a,b] is n+1. Sinceevery chain in [a,b] is finite, it contains an element c which isstrictly larger than a and minimalPlanetmathPlanetmath (http://planetmath.org/MaximalElement) withrespect to this property. Therefore [a,c]={a,c}, from which weconclude that a<:c. Since the interval [c,b] is a propersubinterval of [a,b], it has height at most n, so by the inductionassumptionPlanetmathPlanetmath we conclude that (c,b) is in the transitive closure of<:. Since (a,c) and (c,b) are in the transitive closure of<:, so is (a,b). Hence whenever a<b and the height of [a,b]is at most n+1, then (a,b) is in the transitive closure of <:.

This completesPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the proof.∎

In the same way we associated a graph to < we can associate a graphto <:. The graph is usually called the Hasse diagramMathworldPlanetmath of the poset.Below we display the graph associated to the cover relation <: ofB2.

\\xymatrix&{0,1}&{0}\\ar[ur]&&{1}\\ar[ul]&\\ar[ul]\\ar[ur]&

For simplicity, the Hasse diagram of a poset is usually drawn as anundirected graph. Elements which are higher in the partial orderrelation are drawn physically higher. Since a strict partial order isacyclic, this can be done uniquely and the partial order can berecovered from the drawing.

References

  • 1 Grätzer, G., General lattice theory, 2nd ed., Birkhäuser, 1998.
  • 2 Stanley, R., Enumerative Combinatorics, vol. 1, 2nd ed., CambridgeUniversity Press, Cambridge, 1996.
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 15:09:56