PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] ideal completion of a poset (Definition)

Let $ P$ be a poset. Consider the set $ \operatorname{Id}(P)$ of all order ideals of $ P$.

Theorem 1   $ \operatorname{Id}(P)$ is an algebraic dcpo, such that $ P$ can be embedded in.
Proof. We shall list, and when necessary, prove the following series of facts which ultimately prove the main assertion. For convenience, write $ P'=\operatorname{Id}(P)$.
  1. $ P'$ is a poset with $ \le$ defined by set theoretic inclusion.
  2. For any $ x\in P$, $ \downarrow\!\!x\in P'$.
  3. $ P$ can be embedded in $ P'$. The function $ f:P\to P'$ defined by $ f(x)=\downarrow\!\!x$ is order preserving and one-to-one. If $ x\le y$, and $ a\le x$, then $ a\le y$, hence $ \downarrow\!\!x\subseteq \downarrow\!\!y$. If $ \downarrow\!\!x=\downarrow\!\!y$, we have that $ x\le y$ and $ y\le x$, so $ x=y$, since $ \le$ is antisymmetric.
  4. $ P'$ is a dcpo. Suppose $ D$ is a directed set in $ P'$. Let $ E=\bigcup D$. For any $ x,y\in E$, $ x\in I$ and $ y\in J$ for some ideals $ I,J\in D$. As $ D$ is directed, there is $ K\in D$ such that $ I\subseteq K$ and $ J\subseteq K$. So $ x,y\in K$ and hence there is $ z\in K\subseteq E$ such that $ x\le z$ and $ y\le z$. This shows that $ E$ is directed. Next, suppose $ x\in E$ and $ y\le x$. Then $ x\in I$ for some $ I\in D$, so $ y\in I\subseteq E$ as well. This shows that $ E$ is a down set. So $ E$ is an ideal of $ P$: $ \bigvee D=E\in P'$.
  5. For every $ x\in P$, $ \downarrow\!\!x$ is a compact element of $ P'$. If $ \downarrow\!\!x\le \bigvee D$, where $ D$ is directed in $ P'$, then $ \downarrow\!\!x\subseteq \bigcup D$, or $ x\in \bigcup D$, which implies $ x\in I$ for some ideal $ I\in D$. Therefore $ \downarrow\!\!x\subseteq I$, and $ \downarrow\!\!x$ is way below itself: $ \downarrow\!\!x$ is compact.
  6. $ P'$ is an algebraic dcpo. Let $ I\in P'$. Let $ C=\lbrace \downarrow\!\!x\mid x\in I\rbrace$. For any $ x,y\in I$, there is $ z\in I$ such that $ x\le z$ and $ y\le z$. This shows that $ \downarrow\!\!x\le \downarrow\!\!z$ and $ \downarrow\!\!y\le \downarrow\!\!z$ in $ C$, so that $ C$ is directed. It is easy to see that $ I=\bigvee C$. Since $ I$ is a join of a directed set consisting of compact elements, $ P'$ is algebraic.
This completes the proof. $ \qedsymbol$

Definition. $ \operatorname{Id}(P)$ is called the ideal completion of $ P$.

Remarks.

  • In general, the ideal completion of a poset is not a complete lattice. It is complete in the sense of being directed complete. This is different from another type of completion, called the MacNeille completion of $ P$, which is a complete lattice.
  • If $ P$ is an upper semilattice, then so is $ \operatorname{Id}(P)$. In fact, the join of any non-empty family of ideals exists. Furthermore, if $ P$ has a bottom element 0, then $ \operatorname{Id}(P)$ is a complete lattice.
    Proof. Let $ S$ be a non-empty family of ideals in $ P$. Let $ A$ be the set of $ P$ consisting of all finite joins of elements of those ideals in $ S$, and $ B=\downarrow\!\!A$. Clearly, $ B$ is a lower set. For every $ a,b\in B$, we have $ c,d\in A$ such that $ a\le c$ and $ b\le d$. Since $ c$ and $ d$ are both finite joins of elements of those ideals in $ S$, so is $ c\vee d$. Since $ a\le c\vee d$ and $ b\le c\vee d$, $ B$ is directed. If $ I$ is any ideal larger than any of the ideals in $ S$, clearly $ A\subseteq I$, since $ I$ is directed. So $ B=\downarrow\!\!A\subseteq \downarrow\!\!I=I$. Therefore, $ B=\bigvee S$.

    If $ 0\in P$, then $ \langle 0\rangle$, the bottom of $ \operatorname{Id}(P)$, is the join of the empty family of ideals in $ P$. By this entry, $ \operatorname{Id}(P)$ is a complete lattice. $ \qedsymbol$

  • If $ P$ is a lower semilattice, then so is $ \operatorname{Id}(P)$.
    Proof. Let $ I,J$ be two ideals in $ P$ and $ K=I\cap J$. By definition, $ I$ and $ J$ are non-empty, so let $ a\in I$ and $ b\in J$. As $ P$ is a lower semilattice, $ c:=a\wedge b$ exists and $ c\le a$ and $ c\le b$. So $ c \in I\cap J$, and that $ K=I\cap J$ is non-empty. If $ x\le y\in K$, then $ x\le y\in I$ or $ x\in I$. Similarly $ x\in J$. Therefore $ x\in I\cap J=K$ and $ K$ is a lower set. If $ r,s\in K$, then there is $ u\in I$ and $ v\in J$ such that $ r,s\le u,v$. So $ r,s\le u\wedge v$ and $ K$ is directed. This means that $ I\cap J\in \operatorname{Id}(P)$. $ \qedsymbol$

Bibliography

1
G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. W. Mislove, D. S. Scott, Continuous Lattices and Domains, Cambridge University Press, Cambridge (2003).



"ideal completion of a poset" is owned by CWoo.
(view preamble)

View style:

See Also: lattice of ideals

Also defines:  ideal completion

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: lower semilattice, lower set, finite, bottom, upper semilattice, MacNeille completion, completion, type, directed complete, complete lattice, proof, completes, algebraic, join, easy to see, compact, way below, implies, compact element, down set, directed set, dcpo, antisymmetric, one-to-one, order, function, inclusion, series, necessary, algebraic dcpo, order ideals, poset
There is 1 reference to this entry.

This is version 5 of ideal completion of a poset, born on 2007-05-06, modified 2007-07-25.
Object id is 9340, canonical name is IdealCompletionOfAPoset.
Accessed 827 times total.

Classification:
AMS MSC: 06A06 (Order, lattices, ordered algebraic structures :: Ordered sets :: Partial order, general)
 06A12 (Order, lattices, ordered algebraic structures :: Ordered sets :: Semilattices)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)