−Table of Contents
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: x≤x
transitive: x≤y, y≤z⟹x≤y
antisymmetric: x≤y, y≤x⟹x=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<z⟹x<y
Remark: The above definitions are related via: x≤y⟺x<yorx=y and x<y⟺x≤y, x≠y.
For a partially ordered set P, define the dual P∂=⟨P,≥⟩ by x≥y⟺y≤x. 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:P→Q that is order-preserving:
x≤y⟹f(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
Classtype | Universal Horn class |
---|---|
Universal theory | Decidable |
First-order theory | Undecidable |
Amalgamation property | |
Strong amalgamation property | |
Epimorphisms are surjective |
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