Processing math: 100%

Partially ordered sets

Abbreviation: Pos

Definition

A \emph{partially ordered set} (also called \emph{ordered set} or \emph{poset} for short) is a structure P=P, such that P is a set and is a binary relation on P that is

reflexive: xx

transitive: xy, yzxy

antisymmetric: xy, yxx=y.

Definition

A \emph{strict partial order} is a structure P,< such that P is a set and < is a binary relation on P that is

irreflexive: ¬(x<x)

transitive: x<y, y<zx<y

Remark: The above definitions are related via: xyx<yorx=y and x<yxy, xy.

For a partially ordered set P, define the dual P=P, by xyyx. Then P is also a partially ordered set.

Morphisms

Let P and Q be posets. A morphism from P to Q is a function f:PQ that is order-preserving:

xyf(x)f(y)

Examples

Example 1: R,, the real numbers with the standard order.

Example 2: P(S),, the collection of subsets of a sets S, ordered by inclusion.

Example 3: Any poset is order-isomorphic to a poset of subsets of some set, ordered by inclusion.

Basic results

Properties

Finite members

f(1)=1f(2)=2f(3)=5f(4)=16f(5)=63f(6)=318f(7)=2045f(8)=16999f(9)=183231f(10)=2567284f(11)=46749427f(12)=1104891746f(13)=33823827452f(14)=1338193159771f(15)=68275077901156f(16)=4483130665195087

http://oeis.org/A000112

Subclasses

Superclasses

References


QR Code
QR Code partially_ordered_sets (generated for current page)