6.6 Completion of posets

Completion of posets extends partial orders to complete lattices, preserving existing relations while adding new elements to fill gaps. This process transforms partial orders into more structured total orders, aiding in understanding ordered sets.

Various completion methods exist, each with unique properties. The Dedekind-MacNeille completion is the smallest complete lattice containing the original poset, while ideal and filter completions use directed subsets. These methods have applications in algebra, topology, and computer science.

Definition of completion

• Completion in order theory extends partial orders to complete lattices
• Preserves existing order relations while adding new elements to fill gaps
• Fundamental concept for understanding structure and properties of ordered sets

Partial order vs total order

Top images from around the web for Partial order vs total order

• 

  comparability graphs of dimension 3 posets graphs View original

  Is this image relevant?

• 

  Partially ordered set - Wikipedia View original

  Is this image relevant?

• 

  comparability graphs of posets of interval dimension d graphs View original

  Is this image relevant?

• 

  comparability graphs of dimension 3 posets graphs View original

  Is this image relevant?

• 

  Partially ordered set - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Partial order vs total order

• 

  comparability graphs of dimension 3 posets graphs View original

  Is this image relevant?

• 

  Partially ordered set - Wikipedia View original

  Is this image relevant?

• 

  comparability graphs of posets of interval dimension d graphs View original

  Is this image relevant?

• 

  comparability graphs of dimension 3 posets graphs View original

  Is this image relevant?

• 

  Partially ordered set - Wikipedia View original

  Is this image relevant?

1 of 3

• Partial orders allow incomparable elements (not every pair of elements related)
• Total orders require every pair of elements to be comparable
• Completion process often transforms partial orders into more structured total orders
• Partial order example $(A, \leq)$ where $A = \{a, b, c\}$ and $a \leq b$, but $c$ incomparable to $a$ and $b$

Complete lattice concept

• Complete lattice contains supremum (least upper bound) and infimum (greatest lower bound) for all subsets
• Every nonempty subset has a join (supremum) and a meet (infimum)
• Completion aims to construct a complete lattice from a given partial order
• Example complete lattice power set of a set $X$, ordered by inclusion, with $\cup$ as join and $\cap$ as meet

Types of completions

• Various completion methods exist to transform partial orders into complete lattices
• Each type of completion has unique properties and applications in order theory
• Understanding different completions helps in choosing appropriate methods for specific problems

Dedekind-MacNeille completion

• Smallest complete lattice containing the original poset
• Preserves all existing joins and meets of the original poset
• Constructed using cuts (pairs of subsets) of the original poset
• Applications in algebraic structure theory and topology

Ideal completion

• Uses ideals (downward-closed, directed subsets) of the original poset
• Results in an algebraic complete lattice
• Preserves directed joins of the original poset
• Useful in domain theory and theoretical computer science

Filter completion

• Dual concept to ideal completion, using filters (upward-closed, directed subsets)
• Produces a complete lattice with properties dual to ideal completion
• Preserves directed meets of the original poset
• Applications in logic and lattice theory

Properties of completions

• Completions exhibit important characteristics that make them useful in order theory
• Understanding these properties helps in analyzing and applying completions effectively
• Different types of completions may preserve or introduce specific properties

Universality

• Universal property ensures uniqueness up to isomorphism
• Any order-preserving map from the original poset to a complete lattice factors through the completion
• Allows for consistent extension of functions defined on the original poset
• Example universal property $f \colon P \to L$ factors as $f = g \circ i$, where $i$ is the embedding and $g$ preserves all joins

Embedding of original poset

• Completion contains an isomorphic copy of the original poset
• Order relations from the original poset are preserved in the completion
• Allows for studying the original poset within the context of the completion
• Embedding function $i \colon P \to C(P)$ where $C(P)$ is the completion of $P$

Preservation of existing joins

• Completions often maintain joins (least upper bounds) present in the original poset
• Dedekind-MacNeille completion preserves all existing joins and meets
• Ideal completion preserves directed joins
• Important for maintaining structural properties of the original poset

Construction methods

• Various techniques exist for constructing completions of partial orders
• Each method has its own advantages and may be more suitable for specific types of posets
• Understanding construction methods aids in implementing and analyzing completions

Cut-based completion

• Uses cuts (pairs of subsets) to define new elements in the completion
• Dedekind-MacNeille completion is a prominent example of cut-based completion
• Cuts defined as $(A, B)$ where $A$ is a lower set and $B$ is an upper set
• Order on cuts $(A_1, B_1) \leq (A_2, B_2)$ if and only if $A_1 \subseteq A_2$ (equivalently, $B_2 \subseteq B_1$)

Ideal-based completion

• Constructs completion using ideals (downward-closed, directed subsets) of the original poset
• Results in an algebraic complete lattice
• Order on ideals defined by subset inclusion
• Example ideal in $(N, \leq)$ initial segment $\{1, 2, ..., n\}$ for some $n \in N$

Galois connection approach

• Utilizes Galois connections between power sets of the original poset
• Defines closure operators to construct the completion
• Allows for a more abstract and general approach to completion
• Galois connection between $P(X)$ and $P(Y)$ given by functions $f \colon P(X) \to P(Y)$ and $g \colon P(Y) \to P(X)$

Applications of completions

• Completions play crucial roles in various areas of mathematics and computer science
• Understanding applications helps in recognizing the importance of completions in different fields
• Completions often bridge gaps between different mathematical structures

Algebraic structure theory

• Completions used to study and classify algebraic structures
• Help in understanding relationships between different types of algebras
• Applications in universal algebra and lattice theory
• Example completion of a distributive lattice to a complete Boolean algebra

Topology connections

• Completions have important applications in topology and analysis
• Used in constructing compactifications of topological spaces
• Help in studying convergence and continuity properties
• Dedekind completion of rational numbers yields real numbers, crucial in analysis

Computer science uses

• Completions applied in semantics of programming languages
• Used in domain theory for modeling recursive definitions
• Applications in formal verification and program analysis
• Example using ideal completion to model recursive data types in programming languages

Completion of specific posets

• Examining completions of well-known posets provides insights into the process
• Helps in understanding how completions work in concrete cases
• Illustrates the power of completions in extending mathematical structures

Completion of natural numbers

• Dedekind completion of natural numbers with usual order yields non-negative real numbers
• Adds limits of increasing sequences of rationals
• Introduces concepts of infinity and infinitesimals
• Completion process bridges discrete and continuous mathematics

Completion of real numbers

• Dedekind completion of rational numbers yields real numbers
• Fills "gaps" in rational numbers by adding irrational numbers
• Crucial for analysis and continuity concepts
• Example $\sqrt{2}$ as a Dedekind cut in the rationals

Completion of Boolean algebras

• Completion of a Boolean algebra yields a complete Boolean algebra
• Adds infinite joins and meets to the original structure
• Important in logic and set theory
• Example completion of finite power set algebra to infinite power set algebra

Theoretical considerations

• Deeper analysis of completions reveals important theoretical aspects
• Understanding these considerations helps in advanced applications of completions
• Provides insights into the nature of order structures and their extensions

Uniqueness of completions

• Different types of completions may yield non-isomorphic results
• Dedekind-MacNeille completion unique up to isomorphism for a given poset
• Ideal completion and filter completion may differ from Dedekind-MacNeille completion
• Uniqueness often characterized by universal properties

Cardinality issues

• Completion may increase the cardinality of the original poset
• Important considerations for infinite posets
• Affects computational complexity and theoretical properties
• Example Dedekind completion of countable dense linear order yields uncountable completion

Categorical perspective

• Completions can be viewed as functors in category theory
• Allows for more abstract and general treatment of completions
• Connects order theory with broader mathematical frameworks
• Example completion as a left adjoint to the forgetful functor from complete lattices to posets

Relationship to other concepts

• Completions interact with various other mathematical notions
• Understanding these relationships provides a broader context for completions
• Helps in applying completions in diverse mathematical settings

Completions vs extensions

• Completions add new elements to fill gaps, extensions may add elements arbitrarily
• Completions preserve certain properties, extensions may not
• Completions often minimal among extensions with certain properties
• Example completion of rationals to reals vs algebraic extension of rationals

Completions vs compactifications

• Completions in order theory analogous to compactifications in topology
• Both add "ideal" elements to make structures more well-behaved
• Completions focus on order properties, compactifications on topological properties
• Stone-Čech compactification as topological analogue of certain order completions

Completions vs closures

• Completions add new elements, closures typically do not
• Both aim to make structures more "complete" in some sense
• Closures often operate within the original set, completions expand it
• Example topological closure vs Dedekind completion of a subset of real numbers

Advanced topics

• Exploration of completions in more specialized areas of mathematics
• Demonstrates the broad applicability of completion concepts
• Connects order theory with advanced mathematical theories

Completion in continuous lattices

• Continuous lattices generalize notion of completeness
• Completion process adapted for continuous structures
• Applications in domain theory and theoretical computer science
• Example ideal completion of a continuous poset yields a continuous lattice

Completion in domain theory

• Domain theory uses specialized completions for modeling computation
• Ideal completion plays a crucial role in constructing domains
• Connections to semantics of programming languages and recursion theory
• Scott domains as completions of certain partial orders

Completion in topos theory

• Topos theory provides a categorical framework for completions
• Generalizes set-theoretic notions to more abstract settings
• Allows for studying completions in intuitionistic logic and constructive mathematics
• Example Dedekind-MacNeille completion in a topos generalizing classical construction