Order Theory Unit 6 ReviewCompleteness and continuity

Key Concepts and Definitions

• Order theory studies partially ordered sets (posets) and their properties
• A poset $(P, \leq)$ consists of a set $P$ and a binary relation $\leq$ that is reflexive, antisymmetric, and transitive
• An upper bound of a subset $S$ of a poset $P$ is an element $u \in P$ such that $s \leq u$ for all $s \in S$
• A least upper bound (lub) or supremum of a subset $S$ is an upper bound $u$ such that $u \leq v$ for any other upper bound $v$ of $S$
  • Denoted as $\sup S$ or $\vee S$
• A lower bound and greatest lower bound (glb) or infimum are defined dually
  • Denoted as $\inf S$ or $\wedge S$
• A lattice is a poset in which every pair of elements has a lub and a glb
• A complete lattice is a poset in which every subset has a lub and a glb

Completeness in Ordered Sets

• Completeness is a fundamental property in order theory that ensures the existence of certain elements in a poset
• A poset is complete if every subset has a least upper bound and a greatest lower bound
• In a complete poset, every directed subset (a non-empty subset where any two elements have an upper bound in the subset) has a supremum
• Completeness allows for the construction of fixed points and the application of the Knaster-Tarski theorem
  • The Knaster-Tarski theorem states that every order-preserving function on a complete lattice has a fixed point
• Complete lattices have many desirable properties, such as the existence of a top element (greatest element) and a bottom element (least element)
• Examples of complete lattices include the real numbers with the usual order, the power set of a set ordered by inclusion, and the set of all functions from a set to a complete lattice

Types of Completeness

• Chain-completeness: A poset is chain-complete if every chain (a totally ordered subset) has a supremum
  • Every complete poset is chain-complete, but the converse is not true
• Conditional completeness: A poset is conditionally complete if every bounded subset has a supremum and an infimum
  • Bounded means there exists an upper and lower bound for the subset
• Dedekind-completeness: A linearly ordered set is Dedekind-complete if every non-empty subset that is bounded above has a supremum
  • The real numbers are Dedekind-complete, while the rational numbers are not
• $\sigma$-completeness: A poset is $\sigma$-complete if every countable subset has a supremum and an infimum
  • Every complete poset is $\sigma$-complete, but the converse is not true
• Directed-completeness: A poset is directed-complete if every directed subset has a supremum
  • Every complete poset is directed-complete, but the converse is not true

Continuity in Order Theory

• Continuity in order theory is a property of functions between posets that preserves certain order-theoretic structures
• A function $f: P \to Q$ between posets is order-preserving or monotone if $x \leq y$ in $P$ implies $f(x) \leq f(y)$ in $Q$
• An order-preserving function $f: P \to Q$ is called residuated if for every $y \in Q$, the set $\{x \in P : f(x) \leq y\}$ has a greatest element
  • The greatest element is denoted as $f^\sharp(y)$ and the function $f^\sharp: Q \to P$ is called the residual of $f$
• A function $f: P \to Q$ between complete lattices is join-continuous if $f(\vee S) = \vee f(S)$ for every subset $S$ of $P$
  • Meet-continuity is defined dually
• Scott-continuity is a stronger notion of continuity for functions between complete lattices
  • A function $f: P \to Q$ is Scott-continuous if it is order-preserving and preserves directed suprema, i.e., $f(\vee D) = \vee f(D)$ for every directed subset $D$ of $P$

Relationships Between Completeness and Continuity

• Completeness and continuity are closely related concepts in order theory
• The Knaster-Tarski theorem connects completeness and fixed points of order-preserving functions
  • Every order-preserving function on a complete lattice has a fixed point
• The Kleene fixed-point theorem relates Scott-continuity and least fixed points
  • Every Scott-continuous function on a complete lattice has a least fixed point, which is the supremum of the iterates of the function starting from the bottom element
• Continuity is preserved under composition and pointwise suprema
  • If $f: P \to Q$ and $g: Q \to R$ are continuous functions between complete lattices, then their composition $g \circ f: P \to R$ is also continuous
  • If $(f_i)_{i \in I}$ is a family of continuous functions from $P$ to $Q$, then the pointwise supremum $\vee_{i \in I} f_i$ is also continuous
• Adjunctions between complete lattices correspond to pairs of order-preserving functions that satisfy a certain continuity condition
  • If $f: P \to Q$ and $g: Q \to P$ are order-preserving functions such that $x \leq g(y) \Leftrightarrow f(x) \leq y$ for all $x \in P$ and $y \in Q$, then $f$ is join-continuous and $g$ is meet-continuous

Applications and Examples

• Completeness and continuity have numerous applications in various fields of mathematics and computer science
• In domain theory, complete lattices and continuous functions are used to model the semantics of programming languages and to study the properties of recursive definitions
  • The Scott domain is a complete lattice used to interpret lambda calculus and programming language semantics
• In topology, complete lattices and continuous functions are used to study the properties of open and closed sets, as well as to define the Scott topology on a poset
• In algebra, complete lattices and residuated functions are used to study the properties of ideals and filters in rings and modules
• In analysis, the Dedekind-completeness of the real numbers is a fundamental property that distinguishes them from the rational numbers and allows for the development of calculus and real analysis
• In optimization theory, complete lattices and continuous functions are used to study the existence and properties of optimal solutions to optimization problems
  • The Knaster-Tarski theorem can be used to prove the existence of Nash equilibria in game theory

Theorems and Proofs

• The Knaster-Tarski theorem: Every order-preserving function $f: P \to P$ on a complete lattice $P$ has a fixed point
  • Proof sketch: Consider the set $S = \{x \in P : f(x) \leq x\}$. $S$ is non-empty (since $P$ has a top element) and closed under infima (since $f$ is order-preserving). Let $x^* = \inf S$. Then $f(x^*) \leq x^*$ (since $x^* \in S$) and $x^* \leq f(x^*)$ (since $x^*$ is a lower bound of $S$). Thus, $f(x^*) = x^*$.
• The Kleene fixed-point theorem: Every Scott-continuous function $f: P \to P$ on a complete lattice $P$ has a least fixed point, which is given by $\vee_{n \in \mathbb{N}} f^n(\bot)$, where $\bot$ is the bottom element of $P$ and $f^n$ denotes the $n$-fold composition of $f$ with itself
  • Proof sketch: Let $x^* = \vee_{n \in \mathbb{N}} f^n(\bot)$. Since $f$ is Scott-continuous, $f(x^*) = f(\vee_{n \in \mathbb{N}} f^n(\bot)) = \vee_{n \in \mathbb{N}} f^{n+1}(\bot) = x^*$. Thus, $x^*$ is a fixed point of $f$. If $y$ is another fixed point of $f$, then $\bot \leq y$ and $f^n(\bot) \leq f^n(y) = y$ for all $n \in \mathbb{N}$, so $x^* \leq y$.
• The Adjunction Theorem: Let $P$ and $Q$ be complete lattices. If $f: P \to Q$ and $g: Q \to P$ are order-preserving functions such that $x \leq g(y) \Leftrightarrow f(x) \leq y$ for all $x \in P$ and $y \in Q$, then $f$ is join-continuous and $g$ is meet-continuous
  • Proof sketch: Let $S \subseteq P$. Then $f(\vee S) \leq y \Leftrightarrow \vee S \leq g(y) \Leftrightarrow \forall s \in S: s \leq g(y) \Leftrightarrow \forall s \in S: f(s) \leq y \Leftrightarrow \vee f(S) \leq y$. Thus, $f(\vee S) = \vee f(S)$. The proof for $g$ is dual.

Exercises and Problem-Solving Strategies

• When proving that a poset is complete, try to show that every subset has a supremum and an infimum
  • For suprema, show that the set of upper bounds is non-empty and closed under infima
  • For infima, show that the set of lower bounds is non-empty and closed under suprema
• When proving that a function is continuous, try to show that it preserves the relevant order-theoretic structures
  • For order-preserving functions, show that $x \leq y$ implies $f(x) \leq f(y)$
  • For join-continuous functions, show that $f(\vee S) = \vee f(S)$ for every subset $S$
  • For Scott-continuous functions, show that $f$ is order-preserving and $f(\vee D) = \vee f(D)$ for every directed subset $D$
• When solving problems involving fixed points, try to apply the relevant fixed-point theorems
  • For order-preserving functions on complete lattices, use the Knaster-Tarski theorem
  • For Scott-continuous functions on complete lattices, use the Kleene fixed-point theorem
• When solving problems involving adjunctions, try to establish the adjunction condition $x \leq g(y) \Leftrightarrow f(x) \leq y$ and use the Adjunction Theorem to deduce the continuity of $f$ and $g$
• When solving problems involving the relationship between completeness and continuity, try to use the properties of complete lattices and continuous functions to establish the desired result
  • For example, to prove that a function has a fixed point, show that its domain is a complete lattice and that the function is order-preserving or Scott-continuous