Partially Ordered Sets


Definition

A partially ordered set (poset) is a relational structure     <P,   >   where        is a binary relation that is reflexive, antisymmetric and transitive, i.e. satisfies   x  x,   x  y  and  y  x    x = y, and   x  y  and  y  z    x  z.  
A strict partially ordered set (strict poset) is a relational structure     <P, < >   where   <   is a binary relation that is irreflexive, and transitive, i.e. satisfies   ¬x < x   and   x < y  and  y < z    x < z.  

Basic Results

Examples

Decision problems

Universal Horn Theory: Decidable
First order theory: Undecidable

Spectra and growth

Finite spectrum:

Subclasses

semilattices
trees
linearly ordered sets

Expansions

partially ordered algebraic structures