Namespaces
Variants
Actions

Difference between revisions of "Partially ordered set"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (tex encoded by computer)
Line 1: Line 1:
 +
<!--
 +
p0717201.png
 +
$#A+1 = 210 n = 0
 +
$#C+1 = 210 : ~/encyclopedia/old_files/data/P071/P.0701720 Partially ordered set
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A non-empty set on which some [[Order (on a set)|order relation]] is given.   
 
A non-empty set on which some [[Order (on a set)|order relation]] is given.   
  
Examples of partially-ordered sets. 1) The set of natural numbers with the usual order relation. 2) The set of natural numbers, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717201.png" /> means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717202.png" /> divides <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717203.png" />. 3) The set of all subsets of some set, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717204.png" /> means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717205.png" />. 4) The set of all real-valued functions on the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717206.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717207.png" /> means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717208.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p0717209.png" />. 5) The set of all finite increasing sequences of natural numbers, where
+
Examples of partially-ordered sets. 1) The set of natural numbers with the usual order relation. 2) The set of natural numbers, where $  a \leq  b $
 +
means that $  a $
 +
divides $  b $.  
 +
3) The set of all subsets of some set, where $  a \leq  b $
 +
means that $  a \subseteq b $.  
 +
4) The set of all real-valued functions on the interval $  [ 0 , 1 ] $,
 +
where $  f \leq  g $
 +
means that $  f ( t) \leq  g ( t) $
 +
for all $  t \in [ 0 , 1 ] $.  
 +
5) The set of all finite increasing sequences of natural numbers, where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172010.png" /></td> </tr></table>
+
$$
 +
( a _ {1} \dots a _ {k} )  \leq  ( b _ {1} \dots b _ {l} )
 +
$$
  
means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172012.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172013.png" /> (cf. [[Tree|Tree]]). 6) An arbitrary non-empty set, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172014.png" /> means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172015.png" /> (such a set is called a trivial or discrete partially ordered set).
+
means that $  k \leq  l $
 +
and $  a _ {i} = b _ {i} $
 +
for $  1 \leq  i \leq  k $(
 +
cf. [[Tree|Tree]]). 6) An arbitrary non-empty set, where $  a \leq  b $
 +
means that $  a = b $(
 +
such a set is called a trivial or discrete partially ordered set).
  
Every partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172016.png" /> can be considered as a [[Small category|small category]], whose objects are the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172017.png" /> and in which the set of morphisms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172018.png" /> consists of one element if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172019.png" /> and is empty otherwise. Conversely, every small category in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172020.png" /> contains at most one element for each pair of objects <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172021.png" /> is equivalent to the category of a partially-ordered set.
+
Every partially ordered set $  P $
 +
can be considered as a [[Small category|small category]], whose objects are the elements of $  P $
 +
and in which the set of morphisms $  H ( a , b ) $
 +
consists of one element if $  a \leq  b $
 +
and is empty otherwise. Conversely, every small category in which $  H ( a , b ) \cup H( b, a) $
 +
contains at most one element for each pair of objects $  ( a, b) $
 +
is equivalent to the category of a partially-ordered set.
  
If one defines the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172022.png" /> on a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172023.png" /> by putting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172024.png" /> whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172025.png" />, then this relation also turns out to be an order relation. The resulting set is said to be the opposite or dual partially ordered set to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172026.png" />.
+
If one defines the relation $  \geq  $
 +
on a partially ordered set $  P $
 +
by putting $  a \geq  b $
 +
whenever $  b \leq  a $,  
 +
then this relation also turns out to be an order relation. The resulting set is said to be the opposite or dual partially ordered set to $  P $.
  
 
{{Anchor|isomorphism}}
 
{{Anchor|isomorphism}}
A mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172027.png" /> from a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172028.png" /> into a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172029.png" /> is called isotone (antitone), or an (anti-) homomorphism, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172030.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172031.png" /> implies
+
A mapping $  \phi $
 +
from a partially ordered set $  P $
 +
into a partially ordered set $  P  ^  \prime  $
 +
is called isotone (antitone), or an (anti-) homomorphism, if $  a \leq  b $
 +
in $  P $
 +
implies
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172032.png" /></td> </tr></table>
+
$$
 +
\phi ( a)  \leq  \phi ( b) \ \
 +
( \phi ( b)  \leq  \phi ( a))
 +
$$
  
in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172033.png" />. A bijective (anti-) homomorphism is called an (anti-) isomorphism. The identity mapping of a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172034.png" /> onto itself is an anti-isomorphism between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172035.png" /> and its dual. An isomorphism is a special case of a [[Residual mapping|residual mapping]]. The composite of two anti-homomorphisms is a homomorphism. The collection of all partially ordered sets forms a [[Category|category]] if the isotone mappings are taken as morphisms. Every non-empty subset of a partially ordered set is a partially ordered set with respect to the induced order relation.
+
in $  P  ^  \prime  $.  
 +
A bijective (anti-) homomorphism is called an (anti-) isomorphism. The identity mapping of a partially ordered set $  P $
 +
onto itself is an anti-isomorphism between $  P $
 +
and its dual. An isomorphism is a special case of a [[Residual mapping|residual mapping]]. The composite of two anti-homomorphisms is a homomorphism. The collection of all partially ordered sets forms a [[Category|category]] if the isotone mappings are taken as morphisms. Every non-empty subset of a partially ordered set is a partially ordered set with respect to the induced order relation.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172036.png" /> is a non-empty subset of a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172037.png" />, then the lower cone <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172038.png" /> (the upper cone <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172039.png" />) is defined to be the set of all elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172040.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172041.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172042.png" />) for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172043.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172044.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172045.png" />, the subset
+
If $  A $
 +
is a non-empty subset of a partially ordered set $  P $,  
 +
then the lower cone $  A  ^  \nabla  $(
 +
the upper cone $  A  ^  \Delta  $)  
 +
is defined to be the set of all elements $  x \in P $
 +
such that $  x \leq  a $(
 +
$  a \leq  x $)  
 +
for all $  a \in A $.  
 +
If $  a , b \in P $
 +
and $  a \leq  b $,  
 +
the subset
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172046.png" /></td> </tr></table>
+
$$
 +
[ a , b ]  = a  ^  \Delta  \cap b  ^  \nabla  = \
 +
\{ {x } : {a \leq  x \leq  b } \}
 +
$$
  
is called an interval or segment. The cones <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172047.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172049.png" />, are often called intervals also. An element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172050.png" /> of a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172051.png" /> is called greatest (least) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172052.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172053.png" />) for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172054.png" />. In this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172055.png" /> is the unique element in the intersection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172056.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172057.png" />). A greatest (least) element of a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172058.png" /> (if it exists) is called a unit (a zero) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172059.png" />, and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172060.png" /> . An element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172061.png" /> of a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172062.png" /> is called maximal (minimal) if, for any element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172063.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172064.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172065.png" />) only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172066.png" />. In other words
+
is called an interval or segment. The cones $  a  ^  \Delta  $
 +
and $  a  ^  \nabla  $,  
 +
$  a \in P $,  
 +
are often called intervals also. An element $  u $
 +
of a subset $  A $
 +
is called greatest (least) if $  a \leq  u $(
 +
$  u \leq  a $)  
 +
for all $  a \in A $.  
 +
In this case $  u $
 +
is the unique element in the intersection $  A \cup A  ^  \Delta  $(
 +
$  A \cap A  ^  \nabla  $).  
 +
A greatest (least) element of a partially ordered set $  P $(
 +
if it exists) is called a unit (a zero) of $  P $,  
 +
and is denoted by $  1 $.  
 +
An element $  m $
 +
of a subset $  A $
 +
is called maximal (minimal) if, for any element $  x \in A $,  
 +
$  m \leq  x $(
 +
$  x \leq  m $)  
 +
only if $  m = x $.  
 +
In other words
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172067.png" /></td> </tr></table>
+
$$
 +
m  ^  \Delta  \cap A  = m \ \
 +
( m  ^  \nabla  \cap A  = m ) .
 +
$$
  
A greatest (least) element is maximal (minimal). The converse does not always hold. A least (greatest) element of the upper (lower) cone <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172068.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172069.png" />) is called a least upper (greatest lower) bound of the subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172070.png" />, and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172071.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172072.png" />). Rewriting this definition, one can say that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172073.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172074.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172075.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172076.png" /> whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172077.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172078.png" />. There is an analogous way of rewriting the definition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172079.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172080.png" /> is a chain, then the last condition may be expressed thus;  "… and if u'&lt;a0 for some a0 A whenever u'&lt; u" , as is usual in mathematical analysis. Elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172081.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172082.png" />) are often called upper (lower) bounds for the subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172083.png" />. It is clear that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172084.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172085.png" />. It is a common convention that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172086.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172087.png" />. The following properties hold:
+
A greatest (least) element is maximal (minimal). The converse does not always hold. A least (greatest) element of the upper (lower) cone $  A  ^  \Delta  $(
 +
$  A  ^  \nabla  $)  
 +
is called a least upper (greatest lower) bound of the subset $  A $,  
 +
and is denoted by $  \sup  A $(
 +
$  \inf  A $).  
 +
Rewriting this definition, one can say that $  u = \sup  A $
 +
if $  u \geq  a $
 +
for all $  a \in A $
 +
and if $  u  ^  \prime  \geq  u $
 +
whenever $  u  ^  \prime  \geq  a $
 +
for all $  a \in A $.  
 +
There is an analogous way of rewriting the definition of $  \inf  A $.  
 +
If $  P $
 +
is a chain, then the last condition may be expressed thus;  "… and if u'&lt;a0 for some a0 A whenever u'&lt; u" , as is usual in mathematical analysis. Elements of $  A  ^  \Delta  $(
 +
$  A  ^  \nabla  $)  
 +
are often called upper (lower) bounds for the subset $  A $.  
 +
It is clear that $  1 = \sup  P $
 +
and 0 = \inf  P $.  
 +
It is a common convention that $  \sup  \emptyset = 0 $
 +
and $  \inf  \emptyset = 1 $.  
 +
The following properties hold:
  
a) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172088.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172089.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172090.png" />;
+
a) if $  A \subseteq B $,  
 +
then $  B  ^  \Delta  \subseteq A  ^  \Delta  $
 +
and $  B  ^  \nabla  \subseteq A  ^  \nabla  $;
  
b) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172091.png" />;
+
b) $  A \subseteq A ^ {\Delta \nabla } \cap A ^ {\nabla \Delta } $;
  
c) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172092.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172093.png" />;
+
c) $  A  ^  \Delta  = A ^ {\Delta \nabla \Delta } $
 +
and $  A  ^  \nabla  = A ^ {\nabla \Delta \nabla } $;
  
d) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172094.png" />;
+
d) $  ( A \cup B )  ^  \Delta  = A  ^  \Delta  \cap B  ^  \Delta  $;
  
e) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172095.png" />;
+
e) $  ( A \cup B )  ^  \nabla  = A  ^  \nabla  \cap B  ^  \nabla  $;
  
f) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172096.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172097.png" /> exists, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172098.png" />;
+
f) if $  \sup  A $
 +
or $  \inf  A  ^  \Delta  $
 +
exists, then $  \sup  A = \inf  A  ^  \Delta  $;
  
g) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p07172099.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720100.png" /> exists, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720101.png" />;
+
g) if $  \inf  A $
 +
or $  \sup  A  ^  \nabla  $
 +
exists, then $  \inf  A = \sup  A  ^  \nabla  $;
  
h) (generalized associativity) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720102.png" /> is a set of subsets of a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720103.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720104.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720105.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720106.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720107.png" />) exist for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720108.png" />, then
+
h) (generalized associativity) if $  \{ {A _  \alpha  } : {\alpha \in I } \} $
 +
is a set of subsets of a partially ordered set $  P $
 +
and if $  \sup ( \cup _  \alpha  A _  \alpha  ) $
 +
and $  \sup  A _  \alpha  $(
 +
$  \inf ( \cup _  \alpha  A _  \alpha  ) $
 +
and $  \inf  A _  \alpha  $)  
 +
exist for all $  \alpha \in I $,  
 +
then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720109.png" /></td> </tr></table>
+
$$
 +
\sup ( \cup _  \alpha  A _  \alpha  )  = \sup \{
 +
\sup A _  \alpha  \} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720110.png" /></td> </tr></table>
+
$$
 +
( \inf ( \cup _  \alpha  A _  \alpha  )  = \
 +
\inf \{ \inf A _  \alpha  \} ) ;
 +
$$
  
i) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720111.png" /> is an isotone mapping from a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720112.png" /> into a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720113.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720114.png" /> and if both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720115.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720116.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720117.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720118.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720119.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720120.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720121.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720122.png" />) exist, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720123.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720124.png" />).
+
i) if $  \phi $
 +
is an isotone mapping from a partially ordered set $  P $
 +
into a partially ordered set $  P  ^  \prime  $,  
 +
if $  A \subseteq P $
 +
and if both $  \sup  A $
 +
in $  P $
 +
and $  \sup  \phi ( A) $
 +
in $  P  ^  \prime  $(
 +
$  \inf  A $
 +
in $  P $
 +
and $  \inf  \phi ( A) $
 +
in $  P  ^  \prime  $)  
 +
exist, then $  \sup  \phi ( A) \leq  \phi ( \sup  A ) $(
 +
$  \phi ( \inf  A ) \leq  \inf  \phi ( A) $).
  
Some of the definitions and results introduced above may be obtained from one another by changing the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720125.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720126.png" />. This applies, for example, to the definitions of upper and lower cones, and those of greatest and least elements. Such concepts are said to be dual. In particular, the statements d) and e) are dual, as are f) and g). This is all expressed in the general duality principle (cf. [[Duality principle|Duality principle]] in partially ordered sets).
+
Some of the definitions and results introduced above may be obtained from one another by changing the symbol $  \leq  $
 +
to $  \geq  $.  
 +
This applies, for example, to the definitions of upper and lower cones, and those of greatest and least elements. Such concepts are said to be dual. In particular, the statements d) and e) are dual, as are f) and g). This is all expressed in the general duality principle (cf. [[Duality principle|Duality principle]] in partially ordered sets).
  
 
Special forms of partially ordered sets are totally ordered sets (or chains), well-ordered sets, directed sets, lattices, semi-lattices, and Boolean algebras (cf. [[Boolean algebra|Boolean algebra]]; [[Directed set|Directed set]]; [[Lattice|Lattice]]; [[Semi-lattice|Semi-lattice]]; [[Totally ordered set|Totally ordered set]]; [[Well-ordered set|Well-ordered set]]). A special role is played by algebraic structures that are also partially ordered sets (cf. [[Ordered semi-group|Ordered semi-group]]; [[Partially ordered group|Partially ordered group]]; [[Ordered ring|Ordered ring]]). The concept of a partially ordered set is one of the most fundamentals notions in general mathematics, and is used extensively, both in mathematics itself and in its applications.
 
Special forms of partially ordered sets are totally ordered sets (or chains), well-ordered sets, directed sets, lattices, semi-lattices, and Boolean algebras (cf. [[Boolean algebra|Boolean algebra]]; [[Directed set|Directed set]]; [[Lattice|Lattice]]; [[Semi-lattice|Semi-lattice]]; [[Totally ordered set|Totally ordered set]]; [[Well-ordered set|Well-ordered set]]). A special role is played by algebraic structures that are also partially ordered sets (cf. [[Ordered semi-group|Ordered semi-group]]; [[Partially ordered group|Partially ordered group]]; [[Ordered ring|Ordered ring]]). The concept of a partially ordered set is one of the most fundamentals notions in general mathematics, and is used extensively, both in mathematics itself and in its applications.
Line 60: Line 200:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  G. Birkhoff,  "Lattice theory" , ''Colloq. Publ.'' , '''25''' , Amer. Math. Soc.  (1973)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N. Bourbaki,  "Elements of mathematics. Theory of sets" , Addison-Wesley  (1968)  (Translated from French)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.G. Kurosh,  "Lectures on general algebra" , Chelsea  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  V.V. Rozen,  "Partial operations on ordered sets" , Saratov  (1973)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  L.A. Skornyakov,  "Elements of lattice theory" , A. Hilger  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  S.O. Shatunovskii,  ''Zap. Novoross. Obshch. Estestvoispytatelei'' , '''26'''  (1904)  pp. 21–25</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  S.O. Shatunovskii,  , ''Proc. 1-st All-Russian Congress of Mathematics Teachers'' , '''1'''  (1913)  pp. 276–281  (In Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  S.O. Shatunovskii,  "Introduction to analysis" , Odessa  (1923)  (In Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  G. Cantor,  "Ueber unendliche Punktmannigfaltigkeiten, V"  ''Math. Ann.'' , '''21'''  (1883)  pp. 545–591</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  G. Cantor,  "Beiträge zur Begründung der transfiniten Mengenlehre, I"  ''Math. Ann.'' , '''46'''  (1895)  pp. 481–512</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  F. Hausdorff,  "Grundzüge der Mengenlehre" , Leipzig  (1914)  (Reprinted (incomplete) English translation: Set theory, Chelsea (1978))</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  E.H. Moore,  H.L. Smith,  "A general theory of limits"  ''Amer. J. Math.'' , '''44'''  (1922)  pp. 102–121</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  G. Birkhoff,  "Lattice theory" , ''Colloq. Publ.'' , '''25''' , Amer. Math. Soc.  (1973)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N. Bourbaki,  "Elements of mathematics. Theory of sets" , Addison-Wesley  (1968)  (Translated from French)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.G. Kurosh,  "Lectures on general algebra" , Chelsea  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  V.V. Rozen,  "Partial operations on ordered sets" , Saratov  (1973)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  L.A. Skornyakov,  "Elements of lattice theory" , A. Hilger  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  S.O. Shatunovskii,  ''Zap. Novoross. Obshch. Estestvoispytatelei'' , '''26'''  (1904)  pp. 21–25</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  S.O. Shatunovskii,  , ''Proc. 1-st All-Russian Congress of Mathematics Teachers'' , '''1'''  (1913)  pp. 276–281  (In Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  S.O. Shatunovskii,  "Introduction to analysis" , Odessa  (1923)  (In Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  G. Cantor,  "Ueber unendliche Punktmannigfaltigkeiten, V"  ''Math. Ann.'' , '''21'''  (1883)  pp. 545–591</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  G. Cantor,  "Beiträge zur Begründung der transfiniten Mengenlehre, I"  ''Math. Ann.'' , '''46'''  (1895)  pp. 481–512</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  F. Hausdorff,  "Grundzüge der Mengenlehre" , Leipzig  (1914)  (Reprinted (incomplete) English translation: Set theory, Chelsea (1978))</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  E.H. Moore,  H.L. Smith,  "A general theory of limits"  ''Amer. J. Math.'' , '''44'''  (1922)  pp. 102–121</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
A partially ordered set, or poset, is said to satisfy the maximum condition if every chain of increasing elements stabilizes, i.e. if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720127.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720128.png" /> for all large enough <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720129.png" />. Such a set is also called a Noetherian poset. Dually one has the minimum condition and an Artinian poset.
+
A partially ordered set, or poset, is said to satisfy the maximum condition if every chain of increasing elements stabilizes, i.e. if $  a _ {1} \leq  a _ {2} \leq  \dots $,  
 +
then $  a _ {n} = a _ {m} $
 +
for all large enough $  n> m $.  
 +
Such a set is also called a Noetherian poset. Dually one has the minimum condition and an Artinian poset.
  
 
The words join and meet (or supremum and infimum) are often used in place of  "least upper bound"  and  "greatest lower bound" , respectively.
 
The words join and meet (or supremum and infimum) are often used in place of  "least upper bound"  and  "greatest lower bound" , respectively.
  
A useful pictorial representation of a finite partially ordered set is provided by its Hasse diagram, which is a [[Graph|graph]] having one vertex for each element of the underlying set, and an edge joining the vertices corresponding to elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720130.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720131.png" /> (with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720132.png" /> represented higher up the page than a) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720133.png" /> but there is no element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720134.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720135.png" />. (Here  "a&lt; b"  means, as usual,  "a≤ b but a≠ b" ). For example, the diagram below represents a certain five-element partially ordered set having a least element but no greatest element.
+
A useful pictorial representation of a finite partially ordered set is provided by its Hasse diagram, which is a [[Graph|graph]] having one vertex for each element of the underlying set, and an edge joining the vertices corresponding to elements $  a $
 +
and $  b $(
 +
with $  b $
 +
represented higher up the page than a) if $  a < b $
 +
but there is no element $  c $
 +
with  $  a < c < b $.  
 +
(Here  "a&lt; b"  means, as usual,  "a≤ b but a≠ b" ). For example, the diagram below represents a certain five-element partially ordered set having a least element but no greatest element.
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/p071720a.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/p071720a.gif" />
Line 74: Line 221:
 
Figure: p071720a
 
Figure: p071720a
  
From such a diagram the entire order relation may be read off using transitivity: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720136.png" /> if and only if there is a raising path from the vertex corresponding to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720137.png" /> to that corresponding to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720138.png" />.
+
From such a diagram the entire order relation may be read off using transitivity: $  a \leq  b $
 +
if and only if there is a raising path from the vertex corresponding to $  a $
 +
to that corresponding to $  b $.
  
 
The applied theory of partial order is of very much more mathematical interest than the pure. Partial orderings arise naturally in all branches of mathematics. Broadly, there are two principal types of partially ordered sets of mathematical objects: partial solutions of problems, ordered by consistent extension — here one wants a maximal, indeed a complete, solution; and diagrams of related objects, for which the aim is not to cross it but to analyze it.
 
The applied theory of partial order is of very much more mathematical interest than the pure. Partial orderings arise naturally in all branches of mathematics. Broadly, there are two principal types of partially ordered sets of mathematical objects: partial solutions of problems, ordered by consistent extension — here one wants a maximal, indeed a complete, solution; and diagrams of related objects, for which the aim is not to cross it but to analyze it.
  
 
==Choice and dependent choice.==
 
==Choice and dependent choice.==
Probably a majority of the applications of the [[Axiom of choice|axiom of choice]] involve one of the order-theoretic versions of the axiom. These are mainly: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720139.png" />) the maximality principle (also called the [[Zorn lemma|Zorn lemma]]): If a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720140.png" /> includes an upper bound of each of its totally ordered subsets, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720141.png" /> has a maximal element. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720142.png" />) A variant form: Each partially ordered set contains a maximal totally ordered subset. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720143.png" />) The Teichmüller–Tukey principle: If a family of conditions on partial functions from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720144.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720145.png" /> concerns only their values on finite subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720146.png" />, then there is a maximal partial function satisfying these conditions. Each of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720147.png" />)–<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720148.png" />) is equivalent to the axiom of choice.
+
Probably a majority of the applications of the [[Axiom of choice|axiom of choice]] involve one of the order-theoretic versions of the axiom. These are mainly: $  \alpha $)  
 +
the maximality principle (also called the [[Zorn lemma|Zorn lemma]]): If a partially ordered set $  X $
 +
includes an upper bound of each of its totally ordered subsets, then $  X $
 +
has a maximal element. $  \beta $)  
 +
A variant form: Each partially ordered set contains a maximal totally ordered subset. $  \gamma $)  
 +
The Teichmüller–Tukey principle: If a family of conditions on partial functions from $  A $
 +
to $  B $
 +
concerns only their values on finite subsets of $  A $,  
 +
then there is a maximal partial function satisfying these conditions. Each of $  \alpha $)–
 +
$  \gamma $)  
 +
is equivalent to the axiom of choice.
  
The principle of dependent choice (Brouwer's infinity lemma, König's selection theorem) is this. Suppose given an infinite sequence of non-empty finite sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720149.png" />, and a relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720150.png" /> true for certain pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720151.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720152.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720153.png" />. Suppose that for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720154.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720155.png" /> is true for at least one <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720156.png" />. Then there exists a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720157.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720158.png" />, such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720159.png" /> is true for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720160.png" />. A classic application of dependent choice is to colouring in four colours an infinite planar map <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720161.png" />. Enumerate the regions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720162.png" /> in any order; let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720163.png" /> be the submap composed of the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720164.png" /> regions; let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720165.png" /> be the set of admissible colourings of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720166.png" />. The relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720167.png" /> is extension; each colouring of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720168.png" /> extends a (unique) colouring of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720169.png" />. By the four-colour theorem (cf. [[Graph colouring|Graph colouring]]; [[Four-colour problem|Four-colour problem]]), each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720170.png" /> is non-empty. Accordingly there is a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720171.png" /> of colourings of the submaps <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720172.png" /> which is consistent, since each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720173.png" /> is an extension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720174.png" />. This determines a colouring of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720175.png" />.
+
The principle of dependent choice (Brouwer's infinity lemma, König's selection theorem) is this. Suppose given an infinite sequence of non-empty finite sets $  S _ {n} $,  
 +
and a relation $  R $
 +
true for certain pairs $  ( x, y) $,  
 +
where $  x \in S _ {n} $
 +
and $  y \in S _ {n+} 1 $.  
 +
Suppose that for each $  y \in S _ {n+} 1 $,
 +
$  R( x, y) $
 +
is true for at least one $  x $.  
 +
Then there exists a sequence $  ( x _ {n} ) $,  
 +
$  x _ {n} \in S _ {n} $,  
 +
such that $  R( x _ {n} , x _ {n+} 1 ) $
 +
is true for all $  n $.  
 +
A classic application of dependent choice is to colouring in four colours an infinite planar map $  M $.  
 +
Enumerate the regions of $  M $
 +
in any order; let $  M _ {n} $
 +
be the submap composed of the first $  n $
 +
regions; let $  S _ {n} $
 +
be the set of admissible colourings of $  M _ {n} $.  
 +
The relation $  R $
 +
is extension; each colouring of $  M _ {n+} 1 $
 +
extends a (unique) colouring of $  M _ {n} $.  
 +
By the four-colour theorem (cf. [[Graph colouring|Graph colouring]]; [[Four-colour problem|Four-colour problem]]), each $  S _ {n} $
 +
is non-empty. Accordingly there is a sequence $  ( x _ {n} ) $
 +
of colourings of the submaps $  M _ {n} $
 +
which is consistent, since each $  x _ {n+} 1 $
 +
is an extension of $  x _ {n} $.  
 +
This determines a colouring of $  M $.
  
 
==Combinatorics.==
 
==Combinatorics.==
In the combinatorics of ordered objects or diagrams of objects, usually the role of the partial order is inseparable, or separable only unnaturally, from the rest of the structure. There is a neat illustration in the series of nine papers  "On the foundations of combinatorial theory. I–IX" , published by G.C. Rota and collaborators in 1964–1974. Paper I [[#References|[a4]]] is subtitled  "Theory of Möbius functions" . The Möbius function of a (finite, or locally finite in a suitable sense) partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720176.png" /> is an integer-valued function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720177.png" /> of two variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720178.png" />, which is 0 unless <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720179.png" />. The characteristic property is that, like the number-theoretic [[Möbius function|Möbius function]], it inverts the process of summing a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720180.png" /> with values in an additive group, to the sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720181.png" /> defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720182.png" />; the formula is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720183.png" />. These Möbius functions recur often in the rest of the series and in many other places.
+
In the combinatorics of ordered objects or diagrams of objects, usually the role of the partial order is inseparable, or separable only unnaturally, from the rest of the structure. There is a neat illustration in the series of nine papers  "On the foundations of combinatorial theory. I–IX" , published by G.C. Rota and collaborators in 1964–1974. Paper I [[#References|[a4]]] is subtitled  "Theory of Möbius functions" . The Möbius function of a (finite, or locally finite in a suitable sense) partially ordered set $  X $
 +
is an integer-valued function $  \mu $
 +
of two variables $  x, y \in X $,  
 +
which is 0 unless $  x \leq  y $.  
 +
The characteristic property is that, like the number-theoretic [[Möbius function|Möbius function]], it inverts the process of summing a function $  f: X \rightarrow G $
 +
with values in an additive group, to the sum $  f ^ { * } : X \rightarrow G $
 +
defined by $  f ^ { * } ( y) = \sum [ f( x) : x \leq  y ] $;  
 +
the formula is $  f( y) = \sum [ f ^ { * } ( x) \mu ( x, y) : x \leq  y ] $.  
 +
These Möbius functions recur often in the rest of the series and in many other places.
  
One of the fundamental theorems of combinatorics is, exceptionally, in pure order theory. That is the [[Dilworth theorem|theorem of R. Dilworth]]: A partially ordered set is the union of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720184.png" /> totally ordered subsets if and only if it contains no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720185.png" /> pairwise incomparable elements. In [[Combinatorial analysis|combinatorial analysis]] this theorem is mentioned, but it is bracketed with P. Hall's theorem on systems of distinct representatives. Note the radical difference: Dilworth's theorem is true for arbitrary partially ordered sets, the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720186.png" /> being finite [[#References|[a2]]]. Hall's theorem applies only to systems of distinct representatives of families of finite sets. For the relationships of Dilworth's theorem, see [[#References|[a1]]].
+
One of the fundamental theorems of combinatorics is, exceptionally, in pure order theory. That is the [[Dilworth theorem|theorem of R. Dilworth]]: A partially ordered set is the union of $  n $
 +
totally ordered subsets if and only if it contains no $  n+ 1 $
 +
pairwise incomparable elements. In [[Combinatorial analysis|combinatorial analysis]] this theorem is mentioned, but it is bracketed with P. Hall's theorem on systems of distinct representatives. Note the radical difference: Dilworth's theorem is true for arbitrary partially ordered sets, the number $  n $
 +
being finite [[#References|[a2]]]. Hall's theorem applies only to systems of distinct representatives of families of finite sets. For the relationships of Dilworth's theorem, see [[#References|[a1]]].
  
Sometimes the nature of a naturally occurring partial order is the central problem. For instance, much study has been devoted to extensions of Kuratowski's theorem that the set of topological types of non-planar finite graphs, ordered by imbeddability, has just two minimal elements. (See [[Graph, planar|Graph, planar]]; [[Graph theory|Graph theory]].) Here, as in many cases, the naturally given order relation is only a quasi-ordering (cf. [[Pre-order|Pre-order]]), i.e. a reflexive, transitive relation. Every quasi-ordering of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720187.png" /> determines a partial ordering on the equivalence classes of the equivalence relation  "x≤ y and y≤ x" . Accordingly one is interested in well-quasi-ordered sets: sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720188.png" /> with a quasi-ordering under which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720189.png" /> contains no infinite pairwise incomparable set and no infinite strictly-decreasing sequence. Then in the associated partially ordered set of equivalence classes, the set of minimal elements of each non-empty subset is non-empty and finite. N. Robertson and P. Seymour have announced the theorem — extending a number of previous results — that finite graphs are well-quasi-ordered by the relation of containment as a minor. (Here a [[Minor of a graph|minor of a graph]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720190.png" /> is a graph that can be obtained from a subgraph of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720191.png" /> by contracting edges.) The proof is emerging in a long series of papers; the subtitles of the first nine are given in the announcement [[#References|[a3]]], and six of them have so far (1989) been published.
+
Sometimes the nature of a naturally occurring partial order is the central problem. For instance, much study has been devoted to extensions of Kuratowski's theorem that the set of topological types of non-planar finite graphs, ordered by imbeddability, has just two minimal elements. (See [[Graph, planar|Graph, planar]]; [[Graph theory|Graph theory]].) Here, as in many cases, the naturally given order relation is only a quasi-ordering (cf. [[Pre-order|Pre-order]]), i.e. a reflexive, transitive relation. Every quasi-ordering of a set $  X $
 +
determines a partial ordering on the equivalence classes of the equivalence relation  "x≤ y and y≤ x" . Accordingly one is interested in well-quasi-ordered sets: sets $  X $
 +
with a quasi-ordering under which $  X $
 +
contains no infinite pairwise incomparable set and no infinite strictly-decreasing sequence. Then in the associated partially ordered set of equivalence classes, the set of minimal elements of each non-empty subset is non-empty and finite. N. Robertson and P. Seymour have announced the theorem — extending a number of previous results — that finite graphs are well-quasi-ordered by the relation of containment as a minor. (Here a [[Minor of a graph|minor of a graph]] $  G $
 +
is a graph that can be obtained from a subgraph of $  G $
 +
by contracting edges.) The proof is emerging in a long series of papers; the subtitles of the first nine are given in the announcement [[#References|[a3]]], and six of them have so far (1989) been published.
  
Well-quasi-ordering is the beginning of the combinatorics of infinite partially ordered sets, a division of [[Set theory|set theory]] which has some impressive results but relatively little connection with most of mathematics. However, another aspect of infinite partially ordered sets is fundamental for topology and functional analysis: this is convergence of nets. (See [[Net (directed set)|Net (directed set)]].) The role of subsequences in ordinary convergence of sequences is taken by subnets, which are carried by convergent mappings between directed sets; that is, mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720192.png" /> such that the image of every cofinal subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720193.png" /> is cofinal in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720194.png" />. The use of cofinal subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720195.png" /> is not sufficient (as it is for sequences). However, one has the theorem of J.W. Tukey: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720196.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720197.png" /> are directed sets for which there are convergent mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720198.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720199.png" />, then there exists a directed set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720200.png" /> in which both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720201.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720202.png" /> can be imbedded as cofinal subsets (and conversely). In this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720203.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720204.png" /> are said to be cofinally similar, or of the same cofinal type.
+
Well-quasi-ordering is the beginning of the combinatorics of infinite partially ordered sets, a division of [[Set theory|set theory]] which has some impressive results but relatively little connection with most of mathematics. However, another aspect of infinite partially ordered sets is fundamental for topology and functional analysis: this is convergence of nets. (See [[Net (directed set)|Net (directed set)]].) The role of subsequences in ordinary convergence of sequences is taken by subnets, which are carried by convergent mappings between directed sets; that is, mappings $  f: D \rightarrow E $
 +
such that the image of every cofinal subset of $  D $
 +
is cofinal in $  E $.  
 +
The use of cofinal subsets $  D \subset  E $
 +
is not sufficient (as it is for sequences). However, one has the theorem of J.W. Tukey: If $  D $
 +
and $  E $
 +
are directed sets for which there are convergent mappings $  f: D \rightarrow E $
 +
and $  g: E \rightarrow D $,  
 +
then there exists a directed set $  F $
 +
in which both $  D $
 +
and $  E $
 +
can be imbedded as cofinal subsets (and conversely). In this case $  D $
 +
and $  E $
 +
are said to be cofinally similar, or of the same cofinal type.
  
The classification of cofinal types is in a primitive state. All countable directed sets without a greatest element are of one cofinal type. The main further results known are: A) it is consistent with the axioms of set theory (ZFC) that there are only three more cofinal types represented by directed sets of power <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720205.png" /> (namely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720206.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720207.png" />, and the set of finite subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720208.png" />); but B) there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720209.png" /> different cofinal types of directed sets of the power of the continuum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071720/p071720210.png" />, see [[#References|[a5]]].
+
The classification of cofinal types is in a primitive state. All countable directed sets without a greatest element are of one cofinal type. The main further results known are: A) it is consistent with the axioms of set theory (ZFC) that there are only three more cofinal types represented by directed sets of power $  \aleph _ {1} $(
 +
namely $  \omega _ {1} $,  
 +
$  \omega _ {0} \times \omega _ {1} $,  
 +
and the set of finite subsets of $  \omega _ {1} $);  
 +
but B) there are $  2 ^ {\mathfrak c } $
 +
different cofinal types of directed sets of the power of the continuum $  {\mathfrak c } $,  
 +
see [[#References|[a5]]].
  
 
====References====
 
====References====

Revision as of 08:05, 6 June 2020


A non-empty set on which some order relation is given.

Examples of partially-ordered sets. 1) The set of natural numbers with the usual order relation. 2) The set of natural numbers, where $ a \leq b $ means that $ a $ divides $ b $. 3) The set of all subsets of some set, where $ a \leq b $ means that $ a \subseteq b $. 4) The set of all real-valued functions on the interval $ [ 0 , 1 ] $, where $ f \leq g $ means that $ f ( t) \leq g ( t) $ for all $ t \in [ 0 , 1 ] $. 5) The set of all finite increasing sequences of natural numbers, where

$$ ( a _ {1} \dots a _ {k} ) \leq ( b _ {1} \dots b _ {l} ) $$

means that $ k \leq l $ and $ a _ {i} = b _ {i} $ for $ 1 \leq i \leq k $( cf. Tree). 6) An arbitrary non-empty set, where $ a \leq b $ means that $ a = b $( such a set is called a trivial or discrete partially ordered set).

Every partially ordered set $ P $ can be considered as a small category, whose objects are the elements of $ P $ and in which the set of morphisms $ H ( a , b ) $ consists of one element if $ a \leq b $ and is empty otherwise. Conversely, every small category in which $ H ( a , b ) \cup H( b, a) $ contains at most one element for each pair of objects $ ( a, b) $ is equivalent to the category of a partially-ordered set.

If one defines the relation $ \geq $ on a partially ordered set $ P $ by putting $ a \geq b $ whenever $ b \leq a $, then this relation also turns out to be an order relation. The resulting set is said to be the opposite or dual partially ordered set to $ P $.

A mapping $ \phi $ from a partially ordered set $ P $ into a partially ordered set $ P ^ \prime $ is called isotone (antitone), or an (anti-) homomorphism, if $ a \leq b $ in $ P $ implies

$$ \phi ( a) \leq \phi ( b) \ \ ( \phi ( b) \leq \phi ( a)) $$

in $ P ^ \prime $. A bijective (anti-) homomorphism is called an (anti-) isomorphism. The identity mapping of a partially ordered set $ P $ onto itself is an anti-isomorphism between $ P $ and its dual. An isomorphism is a special case of a residual mapping. The composite of two anti-homomorphisms is a homomorphism. The collection of all partially ordered sets forms a category if the isotone mappings are taken as morphisms. Every non-empty subset of a partially ordered set is a partially ordered set with respect to the induced order relation.

If $ A $ is a non-empty subset of a partially ordered set $ P $, then the lower cone $ A ^ \nabla $( the upper cone $ A ^ \Delta $) is defined to be the set of all elements $ x \in P $ such that $ x \leq a $( $ a \leq x $) for all $ a \in A $. If $ a , b \in P $ and $ a \leq b $, the subset

$$ [ a , b ] = a ^ \Delta \cap b ^ \nabla = \ \{ {x } : {a \leq x \leq b } \} $$

is called an interval or segment. The cones $ a ^ \Delta $ and $ a ^ \nabla $, $ a \in P $, are often called intervals also. An element $ u $ of a subset $ A $ is called greatest (least) if $ a \leq u $( $ u \leq a $) for all $ a \in A $. In this case $ u $ is the unique element in the intersection $ A \cup A ^ \Delta $( $ A \cap A ^ \nabla $). A greatest (least) element of a partially ordered set $ P $( if it exists) is called a unit (a zero) of $ P $, and is denoted by $ 1 $. An element $ m $ of a subset $ A $ is called maximal (minimal) if, for any element $ x \in A $, $ m \leq x $( $ x \leq m $) only if $ m = x $. In other words

$$ m ^ \Delta \cap A = m \ \ ( m ^ \nabla \cap A = m ) . $$

A greatest (least) element is maximal (minimal). The converse does not always hold. A least (greatest) element of the upper (lower) cone $ A ^ \Delta $( $ A ^ \nabla $) is called a least upper (greatest lower) bound of the subset $ A $, and is denoted by $ \sup A $( $ \inf A $). Rewriting this definition, one can say that $ u = \sup A $ if $ u \geq a $ for all $ a \in A $ and if $ u ^ \prime \geq u $ whenever $ u ^ \prime \geq a $ for all $ a \in A $. There is an analogous way of rewriting the definition of $ \inf A $. If $ P $ is a chain, then the last condition may be expressed thus; "… and if u'<a0 for some a0 A whenever u'< u" , as is usual in mathematical analysis. Elements of $ A ^ \Delta $( $ A ^ \nabla $) are often called upper (lower) bounds for the subset $ A $. It is clear that $ 1 = \sup P $ and $ 0 = \inf P $. It is a common convention that $ \sup \emptyset = 0 $ and $ \inf \emptyset = 1 $. The following properties hold:

a) if $ A \subseteq B $, then $ B ^ \Delta \subseteq A ^ \Delta $ and $ B ^ \nabla \subseteq A ^ \nabla $;

b) $ A \subseteq A ^ {\Delta \nabla } \cap A ^ {\nabla \Delta } $;

c) $ A ^ \Delta = A ^ {\Delta \nabla \Delta } $ and $ A ^ \nabla = A ^ {\nabla \Delta \nabla } $;

d) $ ( A \cup B ) ^ \Delta = A ^ \Delta \cap B ^ \Delta $;

e) $ ( A \cup B ) ^ \nabla = A ^ \nabla \cap B ^ \nabla $;

f) if $ \sup A $ or $ \inf A ^ \Delta $ exists, then $ \sup A = \inf A ^ \Delta $;

g) if $ \inf A $ or $ \sup A ^ \nabla $ exists, then $ \inf A = \sup A ^ \nabla $;

h) (generalized associativity) if $ \{ {A _ \alpha } : {\alpha \in I } \} $ is a set of subsets of a partially ordered set $ P $ and if $ \sup ( \cup _ \alpha A _ \alpha ) $ and $ \sup A _ \alpha $( $ \inf ( \cup _ \alpha A _ \alpha ) $ and $ \inf A _ \alpha $) exist for all $ \alpha \in I $, then

$$ \sup ( \cup _ \alpha A _ \alpha ) = \sup \{ \sup A _ \alpha \} , $$

$$ ( \inf ( \cup _ \alpha A _ \alpha ) = \ \inf \{ \inf A _ \alpha \} ) ; $$

i) if $ \phi $ is an isotone mapping from a partially ordered set $ P $ into a partially ordered set $ P ^ \prime $, if $ A \subseteq P $ and if both $ \sup A $ in $ P $ and $ \sup \phi ( A) $ in $ P ^ \prime $( $ \inf A $ in $ P $ and $ \inf \phi ( A) $ in $ P ^ \prime $) exist, then $ \sup \phi ( A) \leq \phi ( \sup A ) $( $ \phi ( \inf A ) \leq \inf \phi ( A) $).

Some of the definitions and results introduced above may be obtained from one another by changing the symbol $ \leq $ to $ \geq $. This applies, for example, to the definitions of upper and lower cones, and those of greatest and least elements. Such concepts are said to be dual. In particular, the statements d) and e) are dual, as are f) and g). This is all expressed in the general duality principle (cf. Duality principle in partially ordered sets).

Special forms of partially ordered sets are totally ordered sets (or chains), well-ordered sets, directed sets, lattices, semi-lattices, and Boolean algebras (cf. Boolean algebra; Directed set; Lattice; Semi-lattice; Totally ordered set; Well-ordered set). A special role is played by algebraic structures that are also partially ordered sets (cf. Ordered semi-group; Partially ordered group; Ordered ring). The concept of a partially ordered set is one of the most fundamentals notions in general mathematics, and is used extensively, both in mathematics itself and in its applications.

The definition of a partially ordered set was first clearly formulated by F. Hausdorff [11], although the axioms appearing in the definition of an order relation had been considered by G. Leibniz around 1690. An accurate definition of a totally ordered set was first given by G. Cantor [10]. In the same work he defined the order type of a totally ordered set, that is, in modern terminology, the class of all totally ordered sets isomorphic to a given one. Even earlier, Cantor had considered well-ordered sets [9], although the definition he gave does not agree with the modern one. An original approach to the axiomatic definition of totally ordered sets was presented by S.O. Shatunovskii [6], [7]. Ordered sets were used by Shatunovskii [8], and also by E.H. Moore and H.L. Smith [12], in connection with the general definition of limit in mathematical analysis.

See also the references [6][9] to Lattice.

References

[1] G. Birkhoff, "Lattice theory" , Colloq. Publ. , 25 , Amer. Math. Soc. (1973)
[2] N. Bourbaki, "Elements of mathematics. Theory of sets" , Addison-Wesley (1968) (Translated from French)
[3] A.G. Kurosh, "Lectures on general algebra" , Chelsea (1963) (Translated from Russian)
[4] V.V. Rozen, "Partial operations on ordered sets" , Saratov (1973) (In Russian)
[5] L.A. Skornyakov, "Elements of lattice theory" , A. Hilger (1977) (Translated from Russian)
[6] S.O. Shatunovskii, Zap. Novoross. Obshch. Estestvoispytatelei , 26 (1904) pp. 21–25
[7] S.O. Shatunovskii, , Proc. 1-st All-Russian Congress of Mathematics Teachers , 1 (1913) pp. 276–281 (In Russian)
[8] S.O. Shatunovskii, "Introduction to analysis" , Odessa (1923) (In Russian)
[9] G. Cantor, "Ueber unendliche Punktmannigfaltigkeiten, V" Math. Ann. , 21 (1883) pp. 545–591
[10] G. Cantor, "Beiträge zur Begründung der transfiniten Mengenlehre, I" Math. Ann. , 46 (1895) pp. 481–512
[11] F. Hausdorff, "Grundzüge der Mengenlehre" , Leipzig (1914) (Reprinted (incomplete) English translation: Set theory, Chelsea (1978))
[12] E.H. Moore, H.L. Smith, "A general theory of limits" Amer. J. Math. , 44 (1922) pp. 102–121

Comments

A partially ordered set, or poset, is said to satisfy the maximum condition if every chain of increasing elements stabilizes, i.e. if $ a _ {1} \leq a _ {2} \leq \dots $, then $ a _ {n} = a _ {m} $ for all large enough $ n> m $. Such a set is also called a Noetherian poset. Dually one has the minimum condition and an Artinian poset.

The words join and meet (or supremum and infimum) are often used in place of "least upper bound" and "greatest lower bound" , respectively.

A useful pictorial representation of a finite partially ordered set is provided by its Hasse diagram, which is a graph having one vertex for each element of the underlying set, and an edge joining the vertices corresponding to elements $ a $ and $ b $( with $ b $ represented higher up the page than a) if $ a < b $ but there is no element $ c $ with $ a < c < b $. (Here "a< b" means, as usual, "a≤ b but a≠ b" ). For example, the diagram below represents a certain five-element partially ordered set having a least element but no greatest element.

Figure: p071720a

From such a diagram the entire order relation may be read off using transitivity: $ a \leq b $ if and only if there is a raising path from the vertex corresponding to $ a $ to that corresponding to $ b $.

The applied theory of partial order is of very much more mathematical interest than the pure. Partial orderings arise naturally in all branches of mathematics. Broadly, there are two principal types of partially ordered sets of mathematical objects: partial solutions of problems, ordered by consistent extension — here one wants a maximal, indeed a complete, solution; and diagrams of related objects, for which the aim is not to cross it but to analyze it.

Choice and dependent choice.

Probably a majority of the applications of the axiom of choice involve one of the order-theoretic versions of the axiom. These are mainly: $ \alpha $) the maximality principle (also called the Zorn lemma): If a partially ordered set $ X $ includes an upper bound of each of its totally ordered subsets, then $ X $ has a maximal element. $ \beta $) A variant form: Each partially ordered set contains a maximal totally ordered subset. $ \gamma $) The Teichmüller–Tukey principle: If a family of conditions on partial functions from $ A $ to $ B $ concerns only their values on finite subsets of $ A $, then there is a maximal partial function satisfying these conditions. Each of $ \alpha $)– $ \gamma $) is equivalent to the axiom of choice.

The principle of dependent choice (Brouwer's infinity lemma, König's selection theorem) is this. Suppose given an infinite sequence of non-empty finite sets $ S _ {n} $, and a relation $ R $ true for certain pairs $ ( x, y) $, where $ x \in S _ {n} $ and $ y \in S _ {n+} 1 $. Suppose that for each $ y \in S _ {n+} 1 $, $ R( x, y) $ is true for at least one $ x $. Then there exists a sequence $ ( x _ {n} ) $, $ x _ {n} \in S _ {n} $, such that $ R( x _ {n} , x _ {n+} 1 ) $ is true for all $ n $. A classic application of dependent choice is to colouring in four colours an infinite planar map $ M $. Enumerate the regions of $ M $ in any order; let $ M _ {n} $ be the submap composed of the first $ n $ regions; let $ S _ {n} $ be the set of admissible colourings of $ M _ {n} $. The relation $ R $ is extension; each colouring of $ M _ {n+} 1 $ extends a (unique) colouring of $ M _ {n} $. By the four-colour theorem (cf. Graph colouring; Four-colour problem), each $ S _ {n} $ is non-empty. Accordingly there is a sequence $ ( x _ {n} ) $ of colourings of the submaps $ M _ {n} $ which is consistent, since each $ x _ {n+} 1 $ is an extension of $ x _ {n} $. This determines a colouring of $ M $.

Combinatorics.

In the combinatorics of ordered objects or diagrams of objects, usually the role of the partial order is inseparable, or separable only unnaturally, from the rest of the structure. There is a neat illustration in the series of nine papers "On the foundations of combinatorial theory. I–IX" , published by G.C. Rota and collaborators in 1964–1974. Paper I [a4] is subtitled "Theory of Möbius functions" . The Möbius function of a (finite, or locally finite in a suitable sense) partially ordered set $ X $ is an integer-valued function $ \mu $ of two variables $ x, y \in X $, which is 0 unless $ x \leq y $. The characteristic property is that, like the number-theoretic Möbius function, it inverts the process of summing a function $ f: X \rightarrow G $ with values in an additive group, to the sum $ f ^ { * } : X \rightarrow G $ defined by $ f ^ { * } ( y) = \sum [ f( x) : x \leq y ] $; the formula is $ f( y) = \sum [ f ^ { * } ( x) \mu ( x, y) : x \leq y ] $. These Möbius functions recur often in the rest of the series and in many other places.

One of the fundamental theorems of combinatorics is, exceptionally, in pure order theory. That is the theorem of R. Dilworth: A partially ordered set is the union of $ n $ totally ordered subsets if and only if it contains no $ n+ 1 $ pairwise incomparable elements. In combinatorial analysis this theorem is mentioned, but it is bracketed with P. Hall's theorem on systems of distinct representatives. Note the radical difference: Dilworth's theorem is true for arbitrary partially ordered sets, the number $ n $ being finite [a2]. Hall's theorem applies only to systems of distinct representatives of families of finite sets. For the relationships of Dilworth's theorem, see [a1].

Sometimes the nature of a naturally occurring partial order is the central problem. For instance, much study has been devoted to extensions of Kuratowski's theorem that the set of topological types of non-planar finite graphs, ordered by imbeddability, has just two minimal elements. (See Graph, planar; Graph theory.) Here, as in many cases, the naturally given order relation is only a quasi-ordering (cf. Pre-order), i.e. a reflexive, transitive relation. Every quasi-ordering of a set $ X $ determines a partial ordering on the equivalence classes of the equivalence relation "x≤ y and y≤ x" . Accordingly one is interested in well-quasi-ordered sets: sets $ X $ with a quasi-ordering under which $ X $ contains no infinite pairwise incomparable set and no infinite strictly-decreasing sequence. Then in the associated partially ordered set of equivalence classes, the set of minimal elements of each non-empty subset is non-empty and finite. N. Robertson and P. Seymour have announced the theorem — extending a number of previous results — that finite graphs are well-quasi-ordered by the relation of containment as a minor. (Here a minor of a graph $ G $ is a graph that can be obtained from a subgraph of $ G $ by contracting edges.) The proof is emerging in a long series of papers; the subtitles of the first nine are given in the announcement [a3], and six of them have so far (1989) been published.

Well-quasi-ordering is the beginning of the combinatorics of infinite partially ordered sets, a division of set theory which has some impressive results but relatively little connection with most of mathematics. However, another aspect of infinite partially ordered sets is fundamental for topology and functional analysis: this is convergence of nets. (See Net (directed set).) The role of subsequences in ordinary convergence of sequences is taken by subnets, which are carried by convergent mappings between directed sets; that is, mappings $ f: D \rightarrow E $ such that the image of every cofinal subset of $ D $ is cofinal in $ E $. The use of cofinal subsets $ D \subset E $ is not sufficient (as it is for sequences). However, one has the theorem of J.W. Tukey: If $ D $ and $ E $ are directed sets for which there are convergent mappings $ f: D \rightarrow E $ and $ g: E \rightarrow D $, then there exists a directed set $ F $ in which both $ D $ and $ E $ can be imbedded as cofinal subsets (and conversely). In this case $ D $ and $ E $ are said to be cofinally similar, or of the same cofinal type.

The classification of cofinal types is in a primitive state. All countable directed sets without a greatest element are of one cofinal type. The main further results known are: A) it is consistent with the axioms of set theory (ZFC) that there are only three more cofinal types represented by directed sets of power $ \aleph _ {1} $( namely $ \omega _ {1} $, $ \omega _ {0} \times \omega _ {1} $, and the set of finite subsets of $ \omega _ {1} $); but B) there are $ 2 ^ {\mathfrak c } $ different cofinal types of directed sets of the power of the continuum $ {\mathfrak c } $, see [a5].

References

[a1] M. Aigner, "Combinatorial theory" , Springer (1979) (Translated from German)
[a2] R.P. Dilworth, "A decomposition theorem for partially ordered sets" Ann. Math. (2) , 51 (1950) pp. 161–166
[a3] N. Robertson, P.D. Seymour, "Graph minors - a survey" I. Anderson (ed.) , Surveys in Combinatorics 1985 , Cambridge Univ. Press (1985) pp. 153–171
[a4] G.C. Rota, "On the foundations of combinatorial theory. I: Theory of Möbius functions" Z. Wahrsch. , 2 (1964) pp. 340–368
[a5] S. Todorčević, "Directed nets and cofinal types" Trans. Amer. Math. Soc. , 290 (1985) pp. 711–723
[a6] G. Grätzer, "General lattice theory" , Birkhäuser (1978) (Original: Lattice theory. First concepts and distributive lattices. Freeman, 1978)
How to Cite This Entry:
Partially ordered set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Partially_ordered_set&oldid=48138
This article was adapted from an original article by L.A. Skornyakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article