6.1 Directed sets and directed completeness

Directed sets and directed completeness are key concepts in order theory, providing a framework for understanding limits and completeness in abstract structures. These ideas generalize sequences from analysis to more complex mathematical settings, offering insights into partially ordered sets.

Directed sets have special properties that allow for the study of upper and lower bounds. Directed completeness extends this notion, requiring that every directed subset has a supremum. This concept is crucial in fixed point theorems and has applications in computer science and domain theory.

Definition of directed sets

• Fundamental concept in order theory providing structure to partially ordered sets
• Generalizes the notion of sequences in analysis to more abstract mathematical structures
• Plays crucial role in studying limits and completeness in ordered structures

Properties of directed sets

Top images from around the web for Properties of directed sets

• 

  Modular Visualization of Distributed Systems View original

  Is this image relevant?

• 

  Directed acyclic graph - Wikipedia View original

  Is this image relevant?

• 

  Grafico aciclico diretto - Directed acyclic graph - qaz.wiki View original

  Is this image relevant?

• 

  Modular Visualization of Distributed Systems View original

  Is this image relevant?

• 

  Directed acyclic graph - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Properties of directed sets

• 

  Modular Visualization of Distributed Systems View original

  Is this image relevant?

• 

  Directed acyclic graph - Wikipedia View original

  Is this image relevant?

• 

  Grafico aciclico diretto - Directed acyclic graph - qaz.wiki View original

  Is this image relevant?

• 

  Modular Visualization of Distributed Systems View original

  Is this image relevant?

• 

  Directed acyclic graph - Wikipedia View original

  Is this image relevant?

1 of 3

• Non-empty set D with a preorder relation ≤
• For any two elements x, y ∈ D, there exists z ∈ D such that x ≤ z and y ≤ z
• Reflexivity holds for all elements in D (a ≤ a for all a ∈ D)
• Transitivity applies (if a ≤ b and b ≤ c, then a ≤ c)
• Does not require antisymmetry, distinguishing it from partial orders

Examples of directed sets

• Natural numbers with usual ordering (any two elements have a common upper bound)
• Power set of a set ordered by inclusion (union of any two subsets serves as upper bound)
• Real numbers with standard ordering (maximum of two numbers is an upper bound)
• Set of all finite subsets of an infinite set ordered by inclusion
• Positive real numbers ordered by divisibility (least common multiple as upper bound)

Directed subsets

• Subsets of partially ordered sets that maintain directed properties
• Essential for studying completeness and fixed point theorems in order theory
• Provide localized structure within larger ordered sets

Upper bounds of directed subsets

• Elements greater than or equal to all elements in the directed subset
• May not exist for all directed subsets in a given partially ordered set
• When they exist, form a set of candidates for the supremum of the directed subset
• Play crucial role in defining directed completeness of ordered structures
• Can be used to construct new directed sets (set of upper bounds often forms a filter)

Lower bounds of directed subsets

• Elements less than or equal to all elements in the directed subset
• Less commonly used than upper bounds in the context of directed sets
• May not exist for all directed subsets in a given partially ordered set
• When they exist, form a set of candidates for the infimum of the directed subset
• Useful in dual constructions and certain order-theoretic arguments

Directed completeness

• Fundamental property in order theory related to the existence of suprema for directed subsets
• Generalizes concepts of completeness from real analysis to more abstract ordered structures
• Crucial in fixed point theorems and domain theory in computer science

Definition of directed completeness

• Partially ordered set P is directed complete if every directed subset has a supremum in P
• Requires existence of least upper bound for all non-empty directed subsets
• Formally, for any directed subset D ⊆ P, $\sup D \in P$ exists
• Also known as directed-complete partial order (dcpo)
• Weaker notion than complete lattice, as it only requires suprema for directed subsets

Properties of directed complete posets

• Contain all finite suprema of their elements
• Closed under directed suprema of monotone functions
• Satisfy fixed point theorems (Knaster-Tarski, Kleene)
• Form cartesian closed category, important in denotational semantics
• May not have all infima or suprema of arbitrary subsets
• Include complete lattices and ω-complete partial orders as special cases

Directed supremum

• Least upper bound of a directed subset in a partially ordered set
• Key concept in studying completeness and continuity in order theory
• Generalizes notion of limit from analysis to more abstract structures

Existence of directed supremum

• Not guaranteed in all partially ordered sets
• Defines directed completeness when it exists for all directed subsets
• Can be constructed as union of all elements in some cases (power sets)
• May require axiom of choice for existence in certain infinite structures
• Existence often proved using Zorn's lemma in more complex scenarios

Uniqueness of directed supremum

• Always unique when it exists due to antisymmetry of partial orders
• Defined as least element of the set of upper bounds of a directed subset
• Can be characterized by universal property: $\forall x \in D, x \leq \sup D$ and $\forall y, (\forall x \in D, x \leq y) \implies \sup D \leq y$
• Preserved under order isomorphisms between partially ordered sets
• Plays crucial role in defining Scott continuity of functions between ordered structures