\documentclass[a4paper]{article} %\pagestyle{empty} \usepackage{amsthm} \usepackage{amsmath,amssymb} \usepackage{mathrsfs} \usepackage{graphics} \usepackage{graphicx} \graphicspath{ {./images/} } \usepackage{array,booktabs,float} \usepackage{tikz} \usetikzlibrary{positioning} \usepackage{tikz-cd} \usepackage{url} \usepackage{mathtools} \usepackage{color} %\usepackage{luatexja-fontspec} %\setmainjfont{MS Mincho} \usepackage[utf8]{inputenc} \usepackage{newunicodechar} \DeclarePairedDelimiter\floor{\lfloor}{\rfloor} \DeclarePairedDelimiter\ceil{\lceil}{\rceil} %\usepackage[dvipdfmx]{hyperref} \renewcommand{\abstractname}{} \theoremstyle{definition} \newtheorem{unsolved}{Unsolved} \newtheorem*{unsolved*}{Unsolved} \newtheorem{definition}{Definition}[section] \newtheorem*{definition*}{Definition} \newtheorem{theorem}[definition]{Theorem} \newtheorem{exercise}[definition]{Exercise} \newtheorem*{theorem*}{Theorem} \newtheorem{lemma}[definition]{Lemma} \newtheorem*{lemma*}{Lemma} \newtheorem{example}[definition]{Example} \newtheorem{example*}{Example} \newtheorem{proposition}[definition]{Proposition} \newtheorem{proposition*}{Proposition} \newtheorem{remark}[definition]{Remark} \newtheorem{remark*}{Remark} \newtheorem{claim}[definition]{Claim} \newtheorem{claim*}{Claim} \newtheorem{question}[definition]{Question} \newtheorem{question*}{Question} \newtheorem{corollary}[definition]{Corollary} \newtheorem{corollary*}{Corollary} %\renewcommand{\thethm}{\arabic{definition}} \newcommand{\transpose}[1]{{#1}^\top} \newcommand{\A}{\mathbb{A}} \newcommand{\alg}[1]{#1 \text{-alg}} \DeclareMathOperator{\Vect}{Vect} \DeclareMathOperator{\pMod}{Mod} %\newcommand{\Mod}[1]{#1\hspace{-3pt}-\hspace{-3pt}\pMod} \newcommand{\Mod}[1]{#1\text{-}\pMod} \newcommand{\Dis}[1]{\mathrm{Dis} (#1)} \newcommand{\abs}[1]{\left\lvert#1\right\rvert} \DeclareMathOperator{\true}{\text{True}} \DeclareMathOperator{\false}{\text{False}} \newcommand{\red}[1]{\textcolor{red}{#1}} \DeclareMathOperator{\Poset}{Poset} \DeclareMathOperator{\op}{op} \DeclareMathOperator{\Cat}{Cat} \DeclareMathOperator{\AG}{AG} \DeclareMathOperator{\Mor}{Mor} \DeclareMathOperator{\Ab}{Ab} \DeclareMathOperator{\Int}{Int} \DeclareMathOperator{\Group}{Group} \DeclareMathOperator*{\colim}{colim} \DeclareMathOperator{\Monoid}{Monoid} \DeclareMathOperator{\cHaus}{cHaus} \DeclareMathOperator{\Ring}{Ring} \DeclareMathOperator{\Top}{Top} \DeclareMathOperator{\Sh}{Sh} \DeclareMathOperator{\Set}{Set} \newcommand{\id}[1]{\mathrm{id}_{#1}} \newcommand{\1}{\textbf{1}} \newcommand{\2}{\textbf{2}} \newcommand{\equi}{\iff} \newcommand{\sq}{\rightsquigarrow} \newcommand{\Closed}{\mathrm{Closed}} \newcommand{\Fin}{\mathrm{Fin}} \newcommand{\LDyn}{\mathrm{LDyn}} \newcommand{\Ran}{\mathrm{Ran}} \newcommand{\Lan}{\mathrm{Lan}} \newcommand{\mpo}{\varphi_{\hspace{-1pt}\raisebox{-0.5ex}{-}}} \newcommand{\MPoly}{\mathrm{MPoly}} \newcommand{\Kleisli}{\mathrm{Kleisli}} \newcommand{\XR}{{}^{X}R} \newcommand{\yo}[1]{\mathrm{y}_{\hspace{-1pt} #1}} \newcommand{\RY}{R^{Y}} \newcommand{\Pow}[1]{\mathrm{P}(#1)} \newcommand{\Spec}[1]{\mathrm{Spec}(#1)} \newcommand{\cl}{\mathrm{cl}} \newcommand{\Mnd}{\mathrm{Monad}} \newcommand{\PtEnd}{\mathrm{PtEnd}} \newcommand{\End}{\mathrm{End}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\Rc}{\lbrack 0,\infty \rbrack} \newcommand{\Ri}{\lbrack 0,1 \rbrack} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\C}{\mathbb{C}} \newcommand{\pro}{\rotatebox{90}{\rightsquigarrow}} \newcommand{\con}[1]{See \cite[#1][]{context}} \newcommand{\ob}[1]{\mathrm{ob} (#1)} \newcommand{\ca}[1]{\mathcal{#1}} \newcommand{\ro}[1]{\mathrm{#1}} \newcommand{\com}[2]{{#1} \hspace{-3pt}\downarrow \hspace{-2pt}{#2}} \newcommand{\defeq}{\coloneqq} \newcommand{\CX}{ \C\lbrack X\rbrack} \newcommand{\quotes}[1]{``#1''} \newcommand{\textgt}[1]{\textbf{#1}} \title{An Introduction to Kan Extensions: Playing with Ordered Sets} \author{hora-algebra/ translated by ChatGPT} \date{\today} \begin{document} \maketitle \begin{abstract} Without assuming any prior knowledge of category theory, this introduction aims to convey the concept of Kan extensions within the realm of ordered set theory, using only elementary language. Various examples from different fields and levels are presented, with an emphasis on understanding through calculating toy-like examples. The intended audience for this work is quite broad, ranging from high school students who have little to no knowledge of category theory or modern mathematics, to those who are already familiar with Kan extensions and are seeking familiar or peculiar examples. \end{abstract} \section*{How to Read This Paper and Why} Readers are advised to follow one of the following approaches, depending on their level of knowledge: \begin{enumerate} \item For those unfamiliar with sets and mappings: You can get a feel for the subject by skimming Chapters 1 and 4, which primarily deal with functions from real numbers to real numbers. However, much of the other content will be inaccessible. It's recommended to start with a suitable introductory mathematics textbook. \item For those familiar with sets and mappings, but not much else about modern mathematics: You can read most of this paper, with some exceptions. Chapter 2 provides a crash course in the foundational theory of ordered sets for this paper, but consulting a suitable textbook for a more detailed explanation is also a good idea. Chapters 5 and 8 can be skipped due to their difficulty, and Chapter 7 can be skipped if motivation is a problem. \item For those studying mathematics (regardless of experience in category theory): You can read the entire paper. The crash course in ordered set theory in Chapter 2 can be skipped, merely checking notation and terminology. \item For those already familiar with Kan extensions: You are part of the intended audience. Of course, you can read the entire paper, and there are some examples specifically prepared for those already experienced with Kan extensions. \end{enumerate} Further details and explanations are provided in the subsequent sections of the paper. \section{Introduction: What is a Natural Extension?} It is often desirable to extend a partially defined function. For example, in high school mathematics, we consider extending the exponential function $2^q:\Q\to \R$ defined on rational numbers to a function $2^r:\R\to \R$ on real numbers. Diagrammatically, this corresponds to creating the following dotted line, where $\iota$ is simply an embedding map. \[ \begin{tikzcd} \Q \ar[rr,"2^q"] \ar[rd,"\iota"']& & \R \\ &\R \ar[ru, dotted]& \end{tikzcd} \] For real numbers $r$, the usual extension involves taking a sequence of rational numbers $q_1, q_2, \dots \to r$ that converge to $r$ and defining $2^r\defeq \lim_{n\to \infty} 2^{q_n}$. Note that this usual extension is not the only possible one. Indeed, \[ \begin{tikzcd} \Q \ar[rr,"2^q"] \ar[rd,"\iota"']& & \R \\ &\R \ar[ru, dotted, "f"']& \end{tikzcd} \] Any function $f$ that makes the diagram commutative (i.e., extends $2^q$) can have its values at irrational numbers arbitrarily altered and still meet the conditions, hence there are countless such $f$. The usual extension $2^r$ is just one among many. Thus, unfortunately, \textgt{a natural extension of a map does not exist}\footnote{The mathematical claim will be made after the definition of Kan extension in Example \ref{extension of maps}.}. To argue that the usual extension $2^r$ is natural, it is insufficient to consider $\Q,\R$ merely as sets. One solution is to think of $\Q,\R$ including the order structure, that is, the relation of magnitude. If we only allow $f$ that preserves the order (i.e., broadly monotonically increasing), then the usual extension $2^r$ becomes the unique extension\footnote{As suggested by the definition of $2^r$ which preserves limits, another solution is to impose continuity on $f$. However, the order structure has the advantage of appearing everywhere and thus has high generality. In fact, even the method of preserving limits will become a fundamental idea in the computational formula of Kan extension we will see later!}. Thus, in the pursuit of a natural extension, it is insufficient to consider just sets and maps. A natural extension might be obtained by considering the relationships between elements of sets. The framework for seeking natural extensions appears suitable for the theory of ordered sets and order-preserving maps. \textgt{Natural extensions might exist in the theory of orders!} %The framework for seeking natural extensions appears suitable for the theory of collections that include relationships and maps that preserve these relationships, namely the theory of categories and functors. \textgt{Natural extensions might exist for functors!} \begin{remark}[Category Theory] If one wishes to handle structures richer than order as relationships between elements of sets, one can consider categories as a generalization of ordered sets. Kan extensions are usually discussed within the framework of category theory (as far as I know as of November 2021). This will be elaborated a bit more in Chapter 9. \end{remark} \section{A Crash Course in Order Set Theory} We describe the basic definitions of order set theory. \begin{definition}[Ordered Set] An ordered set is a pair $(X,\leq)$ consisting of a set $X$ and a binary relation $\leq$, satisfying the following three conditions: \begin{itemize} \item For any $x \in X$, $x \leq x$ \item For any $x, y, z \in X$, if $x \leq y$ and $y \leq z$, then $x \leq z$ \item For any $x, y \in X$, if $x \leq y$ and $y \leq x$, then $x = y$ \end{itemize} \end{definition} These three conditions are called reflexivity, transitivity, and antisymmetry, respectively. \begin{example}[Integers, Rational Numbers, Real Numbers] The set of integers $\Z$, the set of rational numbers $\Q$, and the set of real numbers $\R$ become ordered sets with the usual order relation $\leq$. \end{example} \begin{example}[Power Set] For a set $A$, the power set $\ca{P}(A)$ (the set of all subsets of $A$) becomes an ordered set with the inclusion relation $\subset$. \end{example} \begin{example}[Trivial Order] For any set $X$, it becomes an ordered set by defining for any $x, y \in X$, $x \leq y \iff x = y$. This is called the trivial order. \end{example} \begin{exercise}[Divisibility Relation] Confirm that the set of non-negative integers $\N$ becomes an ordered set with the divisibility relation $\mid$. \end{exercise} \begin{exercise}[Human Relations!?] Here's a less formal exercise. Let $P$ be the set of humans. Define a binary relation $\leq$ on $P$ as $p \leq q$ in the following ways. Think about which ones form an order and for those that don't, identify which of reflexivity, transitivity, or antisymmetry does not hold. \begin{enumerate} \item $p$ is a descendant of $q$. \item $p$ is a descendant of $q$, or $p = q$. \item $p$ and $q$ know each other. \item $p$ thinks favorably of $q$. \item $p$ can reach $q$ by a finite number of acquaintances. \item $p$ and $q$ are of the same age. \end{enumerate} \end{exercise} The ordered set $(P,\leq)$ will henceforth be abbreviated as $P$. This is a convenient but improper practice common in mathematics. \begin{definition}[Order-Preserving Map] For ordered sets $P, Q$, a map $f: P \to Q$ is said to be order-preserving if for any $x, y \in P$ \[x \leq y \implies f(x) \leq f(y)\] \end{definition} \begin{example}[Example in Real Numbers] A map $f: \R \to \R$ is an order-preserving map if and only if it is a non-decreasing function. $f(x) = x$, $f(x) = 0$, and $f(x) = 2^x$ are order-preserving maps, but $f(x) = -x$, $f(x) = 2^{-x}$, and $f(x) = \sin(x)$ are not. \end{example} \begin{definition}[Order of Order-Preserving Maps] For ordered sets $P, Q$ and order-preserving maps $f, g: P \to Q$, define $f \leq g$ as \[\text{for any } p \in P, f(p) \leq g(p)\] \end{definition} \begin{example}[Example in Real Numbers] If $f(x) = x + 2, g(x) = x + 3$, then $f \leq g$, but if $f(x) = 2^x, g(x) = 3^x$, then neither $f \leq g$ nor $g \leq f$. \end{example} \begin{exercise}[Ordered Set of All Order-Preserving Maps] Verify that the set of all order-preserving maps from an ordered set $P$ to $Q$, denoted $Q^P$, becomes an ordered set with the order of order-preserving maps $\leq$. \end{exercise} \begin{definition}[Least Element, Greatest Element] For an element $p$ in an ordered set $P$, $p$ is called the least element of $P$ if \[\text{for any } q \in P, p \leq q\] and $p$ is the greatest element of $P$ if \[\text{for any } q \in P, q \leq p\] \end{definition} \begin{example}[Example in Real Numbers] There are no least or greatest elements in $\R$. \end{example} \begin{example}[Example in Non-Negative Integers] In $\N$, $0$ is the least element. There is no greatest element. \end{example} Least and greatest elements are opposite concepts. Such mutually opposite concepts are called dual concepts. We will provide a more adequate explanation of the term "dual" in this context. For an ordered set $(P,\leq)$, the reversed ordered set $(P,\geq)$ is also an ordered set. A concept $C$ in the reversed ordered set is said to be the dual concept of $C$ in $P$. With the knowledge presented so far in Chapter 2, it is possible to read Chapters 5 and 9, with a few specific exceptions, without Chapters 6, 7, and 8. The following knowledge is necessary to read those chapters. \begin{definition}[Upper Bound, Lower Bound] For an ordered set $P$ and its subset $S \subset P$, an element $p \in P$ is called an upper bound of $S$ if \[\text{for any } s \in S, s \leq p\] and $p \in P$ is a lower bound of $S$ if \[\text{for any } s \in S, p \leq s\] \end{definition} Upper and lower bounds are dual concepts. Note that any element is both an upper and lower bound of the empty set. \begin{definition}[$\sup,\inf$] For an ordered set $P$ and its subset $S \subset P$, the $\sup$ (supremum) of $S$ is the least of its upper bounds, and the $\inf$ (infimum) of $S$ is the greatest of its lower bounds. \end{definition} $\sup$ and $\inf$ are also dual concepts. The ideas of the least of upper bounds and the greatest of lower bounds themselves are familiar from elementary school education. \begin{example}[Least Common Multiple, Greatest Common Divisor] For the ordered set of non-negative integers $(\N,\mid)$, the $\sup$ of $\{12,18,30\}$ is $180$, and the $\inf$ is $6$. Generally, the $\sup$ of a set $S \subset \N$ is the least common multiple of the elements of $S$, and the $\inf$ is the greatest common divisor. \end{example} \begin{example}[Union and Intersection] Considering the power set $\ca{P}(A)$ of a set $A$ (the set of all subsets of $A$) as an ordered set $(\ca{P}(A),\subset)$, for a subset $S \subset \ca{P}(A)$ (a set of subsets of $A$), the $\sup$ of $S$ is the union of the elements (subsets of $A$) of $S$, and the $\inf$ is the intersection of the elements (subsets of $A$) of $S$. \end{example} \begin{example}[Example in Real Numbers] For the subset of $\R$, $S = \{x \in \Q (\subset \R) \mid x^2 \leq 2\}$, the upper limit is $\sqrt{2}$ and the lower limit is $-\sqrt{2}$. On the other hand, for the subset of $\Q$, $S = \{x \in \Q \mid x^2 \leq 2\}$, there are no upper or lower limits. \end{example} \begin{remark}[Correspondence with Category Theory] For readers familiar with category theory, we explicitly note the correspondence between concepts in order set theory, described in Chapter 2, and concepts in category theory: \begin{align*} \text{Ordered Set}&\leftrightarrow\text{Category}\\ \text{Order-Preserving Map}&\leftrightarrow\text{Functor}\\ \text{Order of Order-Preserving Maps}&\leftrightarrow\text{Natural Transformation}\\ \text{Least Element, Greatest Element}&\leftrightarrow\text{Initial Object, Terminal Object}\\ \text{Supremum, Infimum}&\leftrightarrow\text{Colimit, Limit}\\ \end{align*} The category theory concepts on the right coincide exactly with the order set theory concepts on the left when only considering order sets as categories. \end{remark} \section{Definition of Kan Extension} In this chapter, we first describe the definition of a Kan extension. The $hg$ in the definition refers to the composition of mappings. \begin{definition}[Kan Extension]\label{def:kan_extension} For ordered sets $P, Q, R$ and order-preserving maps $f: P \to R, \ g: P \to Q$, a left Kan extension of $f$ along $g$ is defined as the smallest order-preserving map $h: Q \to R$ such that $f \leq hg$ \[ \begin{tikzcd} P \ar[rr,"f",""{name=U, below}] \ar[rd,"g"']&&R\\ &Q \ar[ur,"h"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] The left Kan extension of $f$ along $g$ is denoted as $\Lan_g f: Q \to R$. Similarly, a right Kan extension of $f$ along $g$ is defined as the largest order-preserving map $h: Q \to R$ such that $f \geq hg$ \[ \begin{tikzcd} P \ar[rr,"f",""{name=U, below}] \ar[rd,"g"']&&R\\ &Q \ar[ur,"h"'] \ar["\rotatebox{90}{$\leq$}",phantom, to=U]& \end{tikzcd} \] The right Kan extension of $f$ along $g$ is denoted as $\Ran_g f: Q \to R$. \end{definition} In informal terms, the left Kan extension $h$ is required to be as large as possible to satisfy $f \leq hg$, but among those that fulfill this requirement, it is defined to be the smallest. Dually, the right Kan extension $h$ is required to be as small as possible to satisfy $f \geq hg$, but among those that meet this requirement, it is the largest. Of course, this definition needs to be unraveled using concrete examples, but we will leave that to later chapters and first make a few remarks. Rewriting the definition, a left Kan extension of $f$ along $g$ is an order-preserving map $\Lan_g f: Q \to R$ that satisfies \[ \begin{tikzcd} P \ar[rr,"f",""{name=U, below}] \ar[rd,"g"']&&R\\ &Q \ar[ur,"\Lan_g f"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] and for any order-preserving map $h: Q \to R$ \[ \begin{tikzcd}[row sep=5pt] P \ar[rr,"f",""{name=U, below}] \ar[rdd,"g"']&&R && P \ar[rr,"f",""{name=V, below}] \ar[rdd,"g"']&&R\\ &&&\implies&&&\\ &Q \ar[uur,"h"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& && &Q \ar[uur, "\Lan_{g} f" description, bend left=20,""{name=a,below}] \ar[uur,""{name=b, below},bend right=50, "h"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=V]& \ar["\rotatebox{135}{$\geq$}",phantom, from=a, to=b] \end{tikzcd} \] Since Kan extensions are defined as the greatest or least elements, they are unique if they exist\footnote{In category theory, similar to other universal properties, they are unique up to a canonical isomorphism if they exist.}. Hence, definitions like "... is defined as the left Kan extension of ... along ..." can be used unambiguously as long as their existence is proven. Kan extensions do not necessarily exist. This will be exemplified later. On the positive side, one could say that they \textit{properly do not exist} when we wouldn't want them to. I believe this positive interpretation will be agreed upon in the next chapters through concrete examples. In the definition of Kan extensions, it is not required that $f$ becomes a true extension, i.e., $f = (\Lan_g f) \circ g$. As we will see later, Kan extensions generally do not become true extensions\footnote{Convenient sufficient conditions are known for when they become true extensions.}. In this sense, the inequality $f \leq (\Lan_g f) \circ g$ can be interpreted as representing an \textit{unavoidable error}. Positively speaking, even when a true extension does not exist, a \textit{Kan extension provides the best possible approximation of an extension}. Additionally, as is often the case in order set theory and category theory, it is worth noting that there are dually two types of extensions: left Kan extensions and right Kan extensions. We will start examining examples in the next section. \begin{remark}[Relation to Kan Extensions in Category Theory] The Kan extensions in order set theory are not merely analogous but are a special case of Kan extensions in category theory. \end{remark} \section{Simplified Examples} In this chapter, we will unravel definitions through simple and intuitive examples primarily using real numbers and rational numbers. We want to familiarize the reader with the ideas and properties of Kan extensions. It's good to verify whether something is a Kan extension, but don't be too anxious if it seems difficult. Kan extensions in chapters other than Chapter 8 can all be easily checked with the Kan extension formulas given in Chapter 6. \subsection*{Motivation Retrieval} \begin{example}[Extension of the Exponential Function] Let's confirm that the example of the exponential function introduced in Chapter 1 is indeed a Kan extension. In the definition of the Kan extension (Definition \ref{def:kan_extension}), $P$ is the ordered set $\Q$ of rational numbers, and $Q, R$ are $\R$. We extend $2^q:\Q \to \R$ along the embedding $\iota : \Q \to \R$. Consider an order-preserving map $h:\R\to \R$ such that, \[ \begin{tikzcd} \Q \ar[rr,"2^q",""{name=U, below}] \ar[rd,"\iota"']& & \R \\ &\R \ar[ru, "h"',dotted] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] (i.e., $\forall q \in \Q,\ 2^q \leq h(q)$). The smallest such $h$ is the left Kan extension, which explains the usual $2^r:\R\to \R$. Indeed, any order-preserving map $h:\R\to \R$ that satisfies $\forall q \in \Q,\ 2^q \leq h(q)$ must be at least $2^r:\R\to \R$. This can be demonstrated by considering, for example, when $r = \pi$ with $2^\pi \leq h(\pi)$. Consider a sequence of rational numbers converging to $\pi$ from below: $3, 3.1, 3.14, 3.141, 3.1415 \dots$. Then, \begin{align*} 2^{3}\leq h(3)&\leq h(\pi)\\ 2^{3.1}\leq h(3.1)&\leq h(\pi)\\ 2^{3.14}\leq h(3.14)&\leq h(\pi)\\ 2^{3.141}\leq h(3.141)&\leq h(\pi)\\ 2^{3.1415}\leq h(3.1415)&\leq h(\pi)\\ &\vdots \end{align*} From this sequence, we understand that $2^\pi \leq h(\pi)$. [Image: A visual representation of the sequence approaching $2^\pi$ and $h(\pi)$] This detailed discussion confirms that the usual $2^r:\R\to \R$ is a left Kan extension. \[ \begin{tikzcd} \Q \ar[rr,"2^q",""{name=U, below}] \ar[rd,"\iota"']& & \R \\ &\R \ar[ru, "2^r=\Lan_{\iota}2^q"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] Similarly, the right Kan extension is also $2^r$. In this case, the two dual extensions, left Kan extension, and right Kan extension, coincide. In Chapter 1, we explained that a natural extension as a map cannot be obtained. However, discussing extensions in the language of order sets and order-preserving maps (instead of sets and maps with equality $=$), which involves inequality $\leq$ (and in general, morphisms in categories), proved successful! \end{example} \subsection*{Mismatch of Left and Right Kan Extensions} As an example where the dual extensions do not coincide, many readers are already familiar with the floor and ceiling functions. \begin{example}[Floor and Ceiling Functions (Integer Approximation of Real Numbers)]\label{floor} This time, let's extend $\id{\Z}:\Z\to \Z$ along the embedding $\iota: \Z\to \R$. In other words, what is a natural way to obtain an integer from a real number? Or, what is a natural integer approximation of a real number? \[ \begin{tikzcd} \Z \ar[rr,"\id{\Z}",""{name=U, below}] \ar[rd,"\iota"']& & \Z \\ &\R \ar[ru, "h"',dotted] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] The smallest $h$, that is, the left Kan extension of $\id{\Z}$ along $\iota$, is the floor function $\floor{\ }$. Dually, the right Kan extension is the ceiling function $\ceil{\ }$. [Image: A visual representation of floor and ceiling functions for a real number, e.g., $e$] Thus, \textit{left and right Kan extensions do not always coincide}. \end{example} \begin{exercise}[Maximal Extension of Real-valued Functions] For a real number $r \in \R$, define the order-preserving map $s_r:\Q\to \R$ as \[ s_{r}(q)\coloneqq \begin{cases} 1 & (q \geq r)\\ 0 & (q < r) \end{cases} \] Consider the left and right Kan extensions $\Lan_{\iota}s_r,\Ran_{\iota}s_r$ of $s_r$ along the embedding $\iota:\Q\to \R$. \[ \begin{tikzcd}[row sep=8pt] \Q \ar[rr,"s_r",""{name=U, below}] \ar[rdd,"\iota"']&&\R & \Q \ar[rr,"s_r",""{name=V, below}] \ar[rdd,"\iota"']&&\R\\ &&&&&\\ &\R \ar[uur,"\Lan_{\iota} s_r"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& & &\R \ar[uur, "\Ran_{\iota} s_r"'] \ar["\rotatebox{90}{$\leq$}",phantom, to=V] \end{tikzcd} \] \begin{enumerate} \item Show that left and right Kan extensions exist. \item Determine the necessary and sufficient condition for $r \in \R$ such that the left and right Kan extensions coincide ($\Lan_{\iota}s_r=\Ran_{\iota}s_r$). \end{enumerate} \end{exercise} \subsection*{Non-Existence of Kan Extensions} Furthermore, it is not guaranteed that Kan extensions always exist. \begin{example}[No Natural Extension of a Mapping]\label{mapping_extension} In Chapter 1, we claimed that 'a natural extension of a mapping does not exist.' This intuitive fact can be formalized as follows: Consider a set $X$ and its subset $S$. We want to extend a map $f: S \to Y$ over $X$. We view sets as ordered sets with trivial ordering. The (left) Kan extension of $f$ along the embedding $\iota: S \to X$ \[ \begin{tikzcd} S \ar[rr,"f",""{name=U, below}] \ar[rd,"\iota"']& & Y \\ &X \ar[ru, "?"', dotted] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] does not exist, except in trivial cases ($S = X$ or $Y$ consists of a single point). \end{example} \begin{exercise}[No Natural Rational Approximation of Real Numbers] Following Example \ref{floor}, consider the Kan extension of $\id{\Q}:\Q\to \Q$ along the embedding $\iota: \Q\to \R$. In other words, what is a natural rational approximation of a real number? \[ \begin{tikzcd} \Q \ar[rr,"\id{\Q}",""{name=U, below}] \ar[rd,"\iota"']& & \Q \\ &\R \ar[ru, "?"',dotted] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] \begin{enumerate} \item For a positive integer $n \geq 1$, define $h_n:\R\to \Q$ as $h_n (x) \coloneqq \frac{\ceil{nx}}{n}$. Show that $h_n$ is an order-preserving map and satisfies \[ \begin{tikzcd} \Q \ar[rr,"\id{\Q}",""{name=U, below}] \ar[rd,"\iota"']& & \Q \\ &\R \ar[ru, "h_n"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] \item Show that the natural rational approximation of real numbers (the left Kan extension $\Lan_{\iota} \id{\Q}$ along $\iota$) does not exist. \end{enumerate} \end{exercise} \subsection*{Dependency on Order Structure} The definition of a Kan extension, naturally, is essentially dependent on the order structure. Here's a simple example illustrating how changing the order structure alters the Kan extension. \begin{example}[Dirichlet Function] Define the order-preserving map $\rm{c}_1 :\Q\to \Ri$ from $\Q$ to $\Ri\coloneqq \{x\in \R\mid 0\leq x \leq 1\}$ as $\rm{c}_1 (q)=1$, that is, a constant function to 1. In this case, the left Kan extension of $\rm{c}_1$ along the embedding $\iota:\Q\to \R$ \[ \begin{tikzcd} \Q \ar[rr,"\rm{c}_1",""{name=U, below}] \ar[rd,"\iota"']& & \Ri \\ &\R \ar[ru, "\Lan_{\iota} \rm{c}_1"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] is the constant function $(\Lan_{\iota} \rm{c}_1)(x)=1$ from $\R$ to $\Ri$. On the other hand, if the order on $\Ri$ remains normal, but the order on $\Q,\R$ is changed to trivial, then $\Lan_{\iota} \rm{c}_1$ becomes the Dirichlet function \[ (\Lan_{\iota} \rm{c}_1)(x)= \begin{cases} 1 & (x\in \Q)\\ 0 & (x \notin \Q) \end{cases} \]. \end{example} It might be confusing to mention right after saying the order structure is important, but in fact, in the Kan extension of ordered sets, the order on $P$ (the set on the domain side) is not essentially used\footnote{In the case of Kan extensions in categories, it is important. As we are considering order structures here, any diagram as a category is commutative, making the naturality of natural transformations trivial}. Here's an exercise to demonstrate this. \begin{exercise}[Independence from the Order on $P$] For the Kan extension in ordered sets \[ \begin{tikzcd} P \ar[rr,"f",""{name=U, below}] \ar[rd,"g"']&&R\\ &Q \ar[ur,"\Lan_g f"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] show that changing the order on $P$ within the range that $f,g$ remain order-preserving maps does not change $\Lan_g f$ being a left Kan extension. Particularly, $\Lan_g f$ remains a left Kan extension even with a trivial order on $P$. \end{exercise} \subsection*{Examples Where the Extension is Not Real} All the Kan extensions mentioned so far have been real extensions. In other words, the inequality $f \leq (\Lan_g f) \circ g$ representing unavoidable error has been an equality. Now, we will look at examples where Kan extensions are not real extensions. Moreover, we will see that the unavoidable error $f \leq (\Lan_g f) \circ g$ becomes a familiar inequality. \begin{example}[Quantifiers $\exists, \forall$]\label{quantifiers} Define the ordered set $\Omega$ as $\Omega=\{\true, \false\}$ with the inequality $\false \leq \true$. This can also be understood as an ordered set of truth values and logical implication $\Rightarrow$ ("if... then"). When a trivial order is imposed on a set $X$, all maps $X\to \Omega$ are order-preserving. Thus, order-preserving maps $X\to \Omega$ and "correspondences assigning $\true$ or $\false$ to each element" correspond one-to-one. With this perspective, we call an order-preserving map $X\to \Omega$ a proposition on $X$. For sets $X, Y$, a proposition on $X \times Y$ can be interpreted as a two-variable proposition. So, is there a natural way to reduce the number of variables in a proposition? That is, given a proposition $\phi: X \times Y \to \Omega$, does a Kan extension along the first component projection $\pi_1: X \times Y \to X$ exist? \[ \begin{tikzcd} X\times Y \ar[rr,"\phi",""{name=U, below}] \ar[rd,"\pi_1"']& & \Omega \\ &X \ar[ru, "?"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] In fact, \[x \mapsto \exists y \in Y, \ \phi(x,y)\] provides the left Kan extension. This left Kan extension is denoted as $\exists y \in Y, \ \phi(-,y)$. The expression $\exists y \in Y, \ \phi(x,y)$ means "there exists some $y \in Y$ such that $\phi(x,y)$ is true". The unavoidable error $\phi \leq (\exists y \in Y, \ \phi(-,y)) \circ \pi_1$ is the logical implication \[ \phi(x_0, y_0) \implies \exists y \in Y, \ \phi(x_0, y) \] for each $(x_0, y_0) \in X \times Y$. In layman's terms, "If the pair $(x_0, y_0)$ satisfies the condition $\phi$, then 'there exists some $y$ such that the pair $(x_0, y)$ satisfies the condition $\phi'$ (just take $y = y_0$!). This left Kan extension is a real extension when the truth of a two-variable proposition $\phi$ depends only on the first variable and not on the second variable. Dually, $x \mapsto \forall y \in Y, \ \phi(x,y)$ gives a right Kan extension, and the unavoidable error is \[ \forall y \in Y, \ \phi(x_0, y) \implies \phi(x_0, y_0) \] for each $(x_0, y_0) \in X \times Y$. \textit{Two natural methods to reduce the number of variables in a proposition are $\exists$ and $\forall$}. For more details on this example, refer to Section 9.5 of \cite{awodey} or Section 1.9 of \cite{SGL}. \end{example} $\sup$ and $\inf$, playing an essential role from Chapter 6 onwards, are also important examples of Kan extensions that are not real extensions, generally. \begin{example}[$\sup$ and $\inf$]\label{sup} Let $\1$ denote the ordered set with exactly one element. % There is exactly one (order-preserving) map from any ordered set $R$ to $\1$, which we denote as $!_R: R \to \1$. An (order-preserving) map from $\1$ to an (ordered) set $R$ corresponds one-to-one with elements of $R$. % Utilizing this, we describe (order-preserving) maps from $\1$ to $R$ using the corresponding element of $R$. For an ordered set $R$, its subset $S \subset R$, and $r \in R$, the fact that $r$ is the $\sup$ of $S$ is equivalent to the (order-preserving) map $\ceil{r}: \1 \to R$ corresponding to $r$ being a left Kan extension of the unique (order-preserving) map $!: S \to \1$ along the embedding $\iota: S \to R$ \[ \begin{tikzcd} S \ar[rr,"\iota",""{name=U, below}] \ar[rd,"!"']& & R \\ &\1 \ar[ru, "\ceil{r}"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \]. Dually, $\inf$ can be defined as a right Kan extension. Therefore, \textit{two natural ways to obtain elements from a subset of an ordered set are $\sup$ and $\inf$}. % As a result, this left Kan extension becomes a pointwise Kan extension. The unavoidable error for each $s \in S$ is $s \leq \sup S$ and $\inf S \leq s$. This Kan extension becomes a real extension only when $S$ has at most one element. \end{example} \begin{example}[Inverse Image] Consider the order-preserving map $f(-):\ca{P}(X)\to \ca{P}(Y)$ that takes the direct image of a mapping $f: X \to Y$. The order under consideration is based on the inclusion relation. \[ \begin{tikzcd} \ca{P}(X) \ar[rr,"\id{\ca{P}(X)}",""{name=U, below}] \ar[rd,"f(-)"']& & \ca{P}(X) \\ &\ca{P}(Y) \ar[ru, "f^{-1}"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] The order-preserving map $f^{-1}$ taking the inverse image is a left Kan extension of $\id{\ca{P}(X)}$ along $f(-)$. The unavoidable error for each subset $S \subset X$ is $S \subset f^{-1}(f(S))$, which is the inclusion relationship. In other words, elements of $X$ that are sent to the same destination by $f$ become indistinguishable. This left Kan extension becomes a real extension when $f$ is injective. \end{example} \section{Challenging Examples} For readers who have a bit of prior knowledge, I'll provide some specific examples. While Kan extensions in general categories truly show their strengths, we can also find examples within ordered sets. \subsection*{Topological Spaces} \begin{example}[Interior]\label{interior} Consider a topological space $X$, its power set $\ca{P}(X)$, and the set of all open sets of $X$, $\ca{O}(X)$. Both $\ca{P}(X)$ and $\ca{O}(X)$ are viewed as ordered sets under the inclusion relation. What is the left Kan extension of $\id{\ca{O}(X)}$ along the embedding $\iota$? In other words, what is the optimal approximation of a subset by open sets? \[ \begin{tikzcd} \ca{O}(X) \ar[rr,"\id{\ca{O}(X)}",""{name=U, below}] \ar[rd,"\iota"']& & \ca{O}(X) \\ &\ca{P}(X) \ar[ru, "\Int"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] As expected, the interior (interior kernel) $\Int: \ca{P}(X)\to \ca{O}(X)$ is the Kan extension we seek. \end{example} The right Kan extension will be left as an exercise. \begin{exercise}[Right Kan Extension to Open Set Families] In the context of Example \ref{interior}, show the following: \begin{enumerate} \item Demonstrate the existence of the right Kan extension. \item Show that $X$ being a $T_1$ space is a necessary and sufficient condition for the left and right Kan extensions to coincide. \end{enumerate} \end{exercise} %\cite{toy} discusses more general arguments. \subsection*{Set Operations} The examples of set operations introduced here are related to general theory and their connections to category theory, as described in \cite{toy}. % The following is one of the main topics in \cite{toy}. \begin{exercise}[Various Closure Operators] Consider a set $X$, its power set $\ca{P}(X)$, and a sub-order set $\ca{B}$ of $\ca{P}(X)$. Now, consider the right Kan extension of $\id{\ca{B}}$ along the embedding $\iota:\ca{B}\to \ca{P}(X)$\footnote{Its existence is not always guaranteed}. \[ \begin{tikzcd} \ca{B} \ar[rr,"\id{\ca{B}}",""{name=U, below}] \ar[rd,"\iota"']& & \ca{B} \\ &\ca{P}(X) \ar[ru, "f"', dotted] \ar["\rotatebox{90}{$\leq$}",phantom, to=U]& \end{tikzcd} \] \begin{enumerate} \item If $X$ is a linear space (group, monoid, lattice, ring, etc.), and $\ca{B}$ is the set of all sub-linear spaces (corresponding sub-algebras), show that generating a sub-linear space (corresponding sub-algebra) defines the right Kan extension. \item If $X$ is $\R^2$ and $\ca{B}$ is the set of all convex subsets, show that taking the convex hull operation defines the right Kan extension. \item If $X$ is a topological space and $\ca{B}$ is the set of all closed sets in $X$, show that the closure operator defines the right Kan extension. %\item The existence of right Kan extension is... \end{enumerate} \end{exercise} \begin{exercise}[Existential Quantifier and Direct Image] A subset $S \subset X$ of a set $X$ corresponds to a proposition $\chi_S: X \to \Omega$ on $X$ defined by \[\chi_S (x) = \text{true} \iff x \in S\]. % defined this way. $\chi_S$ is called the characteristic function of $S$. Consider the situation in Example \ref{quantifiers}, but with the map $\pi_1: X \times Y \to X$ replaced by a general map $g: X \to Y$. \begin{enumerate} \item Confirm that the left Kan extension in terms of corresponding subsets becomes the direct image. \[ \begin{tikzcd} X \ar[rr,"\chi_S",""{name=U, below}] \ar[rd,"g"']& & \Omega \\ &Y \ar[ru, "\chi_{g(S)}"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] \item Write down the subset corresponding to the right Kan extension\footnote{Referred to as 'dual image' on nLab \url{https://ncatlab.org/nlab/show/internal+logic}}. \[ \begin{tikzcd} X \ar[rr,"\chi_S",""{name=U, below}] \ar[rd,"g"']& & \Omega \\ &Y \ar[ru, "\chi_{g_!(S)}"'] \ar["\rotatebox{90}{$\leq$}",phantom, to=U]& \end{tikzcd} \] \end{enumerate} \end{exercise} \subsection*{Measure Theory} Some important definitions in measure theory can be described using the language of Kan extensions. \begin{example}[Integration over a Measure Space] Defining integration over a measure space, extending the integration of non-negative simple functions to non-negative measurable functions, was a crucial step. This extension problem is also an example of a Kan extension. For a measure space $(X, \ca{B}, \mu)$, consider the ordered set ${\rm{Mea}}_X$ of non-negative measurable functions and their size relations. The integral $\int d\mu : {\rm{Mea}}_X \to \Rc$ is the left Kan extension of the integral $\int d\mu : {\rm{Sim}}_X \to \Rc$ of non-negative simple functions along the embedding $\iota: {\rm{Sim}}_X \to {\rm{Mea}}_X$. \[ \begin{tikzcd} {\rm{Sim}}_X \ar[rr,"\int d\mu",""{name=U, below}] \ar[rd,"\iota"']& & \Rc \\ &{\rm{Mea}}_X \ar[ru, "\int d\mu"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] \end{example} When considering a Kan extension of an order-preserving map $f: P \to R$, we specify which $g: P \to Q$ to extend along. Particularly, we determine the domain $Q$ of the Kan extension $\Lan_{g}f: Q \to R$. Hence, extension problems aiming to "extend to the widest possible domain" may seem incompatible. However, \textit{using both left and right Kan extensions allows us to achieve the widest possible domain}. Specifically, the maximal expansion can be considered as limiting to the range where both left and right Kan extensions coincide\footnote{For those familiar with category theory, the completion of the measure $\mu$ can be said to be the equalizer of $\Lan_{\iota}\mu$ and $\Ran_{\iota}\mu$ in the category of categories $\Cat$ (though losing generality, the category of ordered sets $\Poset$ or the category of sets $\Set$ is also fine).}. While natural extension concepts are dual Kan extensions, if one desires a single extension, the idea is to take their common part. \begin{example}[Completion of Measure Spaces]\label{measure} Consider a measure space $(X, \ca{B}, \mu)$, where $\mu: \ca{B} \to \Rc$ is an order-preserving map. We want to extend $\mu$ to as broad a part of the power set $\ca{P}(X)$ of $X$ as possible. First, consider the left and right Kan extensions of $\mu$ along the embedding $\iota: \ca{B} \to \ca{P}(X)$. \[ \begin{tikzcd} \ca{B} \ar[rr,"\mu",""{name=U, below}] \ar[rd,"\iota"']& & \Rc \\ &\ca{P}(X) \ar[ru, "\Lan_{\iota}\mu",bend left=10]\ar[ru, "\Ran_{\iota}\mu"',bend right=10] & \end{tikzcd} \] Then, restrict $\Lan_{\iota}\mu$ and $\Ran_{\iota}\mu$ to the part $\bar{\ca{B}} \subset \ca{P}(X)$ where they coincide, and denote this restricted function as $\bar{\mu}: \bar{\ca{B}} \to \Rc$. \[ \begin{tikzcd} \ca{B} \ar[rr,"\mu"] \ar[rd,"\iota"']& & \Rc \\ &\ca{P}(X)\ar[phantom, ""{name=U, below}] \ar[ru, "\Lan_{\iota}\mu",bend left=10]\ar[ru,"\Ran_{\iota}\mu"' description, bend right=10] & \\ \bar{\ca{B}} \ar[ru,tail] \ar["\bar{\mu}"', rruu,bend right=40, ""{name=V, below}] && \ar["\rotatebox{130}{$\coloneqq$}", from=U ,to=V, phantom] \end{tikzcd} \] In this case, if $(X, \ca{B}, \mu)$ is finite $\mu(X) < \infty$\footnote{Even when the measure space is not finite, it mostly results in completion, but there is a discrepancy at $\infty$ (measuring too much). If $\bar{\mu}(S) = \infty$, then for any larger set $S \subset S'$, $\bar{\mu}(S') = \infty$. This seems rational, but the $\sigma$-additivity of $\bar{\ca{B}}$ may be lost.}, then $(X, \bar{\ca{B}}, \bar{\mu})$ is the completion of the measure space $(X, \ca{B}, \mu)$. %Thus, the 'maximal extension' of the measure is equivalent to its completion. \end{example} We will leave exercises to confirm this example in measure theory until Chapter 6 and beyond, when calculation formulas are obtained. For now, we set an exercise that can be easily confirmed from the definition alone. \begin{exercise}[Maximal Extension of Measure is Complete] Consider $(X, \bar{\ca{B}}, \bar{\mu})$ as defined in Example \ref{measure}. Demonstrate that for any $N \in \bar{\ca{B}}$ with $\bar{\mu}(N) = 0$, every subset $S \subset N$ satisfies $S \in \bar{\ca{B}}$ and $\bar{\mu}(S) = 0$. \end{exercise} \section{Kan Extension Formulas} All Kan extensions examples provided so far, including those in this document, are essentially constructed using the same method (as will be introduced shortly in Theorem \ref{OrderSetKanExtensionFormula}). To observe this, let's revisit the example of the exponential function: \[ \begin{tikzcd} \Q \ar[rr,"2^q",""{name=U, below}] \ar[rd,"\iota"']& & \R \\ &\R \ar[ru, "2^r=\Lan_{\iota}2^q"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] As recalled in Chapter 1, the natural extension (both left and right Kan extensions) $2^r$ was defined as the limit of the sequence $2^{q_1},2^{q_2},\dots$ converging to $r$, where $q_1,q_2,\dots \to r$. When $r=\pi$, this looks like: \[ \begin{tikzcd}[row sep=3pt, column sep =3pt] 3,\ 3.1,\ 3.14, \ 3.141, \ \dots &\to& \pi \\ &\rotatebox{-90}{$\rightsquigarrow$} &\\ 2^{3},\ 2^{3.1},\ 2^{3.14}, \ 2^{3.141}, \ \dots &\to& 2^\pi \end{tikzcd} \] Although this definition uses the concept of a limit, let's rephrase it in terms of ordered sets: \begin{align*} 2^\pi &\coloneqq \sup_{q\leq \pi} 2^q\\ (&= \sup \{2^q\in \R\mid q\in \Q \land q\leq \pi\}) \end{align*} Here $q$ ranges over all rational numbers less than or equal to $\pi$. Instead of choosing one sequence converging to $\pi$, we consider all rational numbers less than or equal to $\pi$. This method of construction can be generalized to ordered sets. \begin{theorem}[Kan Extension Formulas for Ordered Sets]\label{OrderSetKanExtensionFormula} Consider ordered sets $P,Q,R$ and order-preserving maps $f:P\to R$ and $g:P\to Q$. \[ \begin{tikzcd} P \ar[rr,"f",""{name=U, below}] \ar[rd,"g"']&&R\\ &Q %\ar[ur,"G"'] %\ar["\rotatebox{90}{$\geq$}",phantom, to=U] & \end{tikzcd} \] For any $q \in Q$, if $\displaystyle \sup_{g(p) \leq q} f(p) \ (\in R)$ exists, then \[q\mapsto \sup_{g(p) \leq q} f(p)\] provides the left Kan extension of $f$ along $g$. \[ \begin{tikzcd} P \ar[rr,"f",""{name=U, below}] \ar[rd,"g"']&&R\\ &Q \ar[ur," \displaystyle \sup_{g(p) \leq -} f(p)"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] \end{theorem} \begin{proof}\ % Proof content... \end{proof} \begin{exercise}[Right Kan Extension Formula] Dually, demonstrate that if the necessary $\inf$ exists, the right Kan extension can be computed using $\inf$. \end{exercise} Let's try to explain the Kan extension formula in layman's terms. Initially, in a situation where we consider (left) Kan extensions, we have the following scenario: \[ \begin{tikzcd} P \ar[rr,"f",""{name=U, below}] \ar[rd,"g"']&&R\\ &Q %\ar[ur,"G"'] %\ar["\rotatebox{90}{$\geq$}",phantom, to=U] & \end{tikzcd} \] We aim to extend a map from $Q$ to $R$. We want to receive an element $q$ from $Q$ and return an element from $R$. Naturally, we want to go through $P$, but considering the direction of $g$, it's not straightforward. Thus, the Kan extension formula takes an element from $Q$, uses elements from $P$ for \textgt{template matching}, and then sends it to $R$! Specifically, when receiving $q\in Q$, we construct the subset of $P$: \[\{p\in P\mid g(p)\leq q\}\subset P\] This is collecting elements of $P$ that are less than $q$ (via $g$), playing the role of the 'template' mentioned earlier. We then use this template to obtain an element in $R$. We do this by mapping the 'template' through $f$ to get: \[\{f(p)\mid p\in P, g(p)\leq q\} \subset R\] and then taking the supremum of this set. This process of template matching and replication across $Q, P, R$ is essentially what the Kan extension formula: \[q\mapsto \sup_{g(p) \leq q} f(p)\] is about! To put it more insistently, this formula employs the operation of taking the supremum ($\sup$) of elements below itself, which would typically reconstruct itself, but it does so while transitioning through ordered sets, thereby obtaining a natural extension. Consider the following trivial extension problem as an example to experience this concept. \begin{exercise}[Educational Overkill] For an ordered set $P$, verify using Theorem \ref{OrderSetKanExtensionFormula} that the left Kan extension of $\id{P}$ along $\id{P}$ is $\id{P}$. \[ \begin{tikzcd} P \ar[rr,"\id{P}",""{name=U, below}] \ar[rd,"\id{P}"']& & P \\ &P \ar[ru, "\id{P}"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] \end{exercise} The next exercise is one of the most important in this document (along with Exercise \ref{You}). Please do attempt it. \begin{exercise}[Examples So Far] All Kan extensions presented in this document can be calculated using this formula. Verify this with as many examples as possible. \end{exercise} You should have felt the power of the formula through this exercise. As we will discuss in Chapter 9, expanding the conversation to Kan extensions in category theory vastly increases the range of applications for this formula. \begin{definition}[Pointwise Kan Extension] Kan extensions computed using Theorem \ref{OrderSetKanExtensionFormula} are called pointwise Kan extensions. \end{definition} \begin{remark}[Kan Extensions Not Computable by the Formula] Not all left Kan extensions can be calculated using the formula. In the realm of ordered sets, there exist Kan extensions that are not pointwise. As introduced in Example \ref{CounterExample}, Kan extensions that are not pointwise do exist. However, there's no need for pessimism. As suggested by the fact that all examples thus far were pointwise Kan extensions, it is known through an experiential rule (not a mathematical statement) that \textgt{important Kan extensions are pointwise}. In Section 6.3 of \cite{context}, it is stated: \begin{quote} By the categorical community's consensus, the important Kan extensions are pointwise Kan extensions. \end{quote} In \cite{Benri}, what this document refers to as Kan extensions are called weak Kan extensions, and only the pointwise Kan extensions are termed Kan extensions, asserting that: \begin{quote} Our present choice of nomenclature is based on our failure to find a single instance where a weak Kan extension plays any mathematical role whatsoever. \end{quote} Readers are encouraged to verify the veracity of this experiential rule in their future studies. \end{remark} In the scenario of Theorem \ref{OrderSetKanExtensionFormula}, the more subsets an ordered set $R$ has that possess a $\sup$, the more likely it is for a left Kan extension to exist. An extreme case is that of a complete lattice. \begin{definition}[Complete Lattice]\label{CompleteLattice} An ordered set $P$ is a complete lattice if every subset of $P$ has a supremum\footnote{Interestingly, it is equivalent to every subset of $P$ having an infimum.}. \end{definition} \begin{corollary}[Existence Theorem for Kan Extensions]\label{ExistenceTheorem} If $R$ is a complete lattice, then for any order-preserving maps $f:P\to R, g:P\to Q$, a pointwise left Kan extension $\Lan_g f$ exists. \end{corollary} For the examples thus far, $\Omega,\ca{P}(X),\ca{O}(X),\Rc $ and the various families of closed sets in exercises (such as closed sets in topological spaces, subalgebras, convex sets, etc.) are complete lattices. $\R$ only lacks a supremum for empty sets\footnote{The supremum of an empty set is typically the least element.} and unbounded subsets. Ordered sets seen as sets with trivial order and $\Q$ have many subsets without a supremum\footnote{One-element sets viewed as ordered sets are an exception}, making it harder for Kan extensions to exist. As an exercise, the converse of Corollary \ref{ExistenceTheorem} is presented. \begin{exercise}[Converse of the Existence Theorem for Kan Extensions] Consider $R$ as an ordered set. Show that the following three conditions are equivalent (Hint: Example \ref{sup}): \begin{enumerate} \item $R$ is a complete lattice. \item For any order-preserving maps $f:P\to R, g:P\to Q$, a pointwise left Kan extension $\Lan_g f$ exists. \item For any order-preserving maps $f:P\to R, g:P\to Q$, a left Kan extension $\Lan_g f$ exists. \end{enumerate} \end{exercise} \section{Interesting Properties of the Computation Formula} This chapter presents interesting properties of Kan extensions, such as sufficient conditions for them to be true extensions, under the assumption of the computation formula from Chapter 6. Due to the theoretical nature of this chapter, it is sufficient to solve only those exercises that pique your interest. The purpose of this chapter also includes aiding in the study of Kan extensions in category theory. The properties introduced below are general theorems in category theory translated into the context of ordered sets. The proofs introduced in the form of exercises are similar to the general case. However, to keep in line with the spirit of this document, the categorical background is merely mentioned in passing (even though it is very important for an interesting, powerful, and intuitive understanding). Those who will study the corresponding theorems in category theory in the future are advised to read this to get familiar with the ideas in simpler cases. Those who have already studied them may seek a better understanding through simple examples. \begin{definition}[Embedding in Ordered Sets]\label{Embedding} An order-preserving map $f:P\to Q$ is an embedding if, for all $p, p' \in P$, \[p\leq p' \iff f(p)\leq f(p').\] \end{definition} The corresponding concept in category theory can be found in \cite{context}, Definition 1.5.7 (fully faithful functor). All order-preserving maps referred to as embeddings thus far in this document are embeddings in this sense. \begin{exercise}[Sufficient Condition for a True Extension]\label{TrueExtension} Suppose an order-preserving map $g:P\to Q$ is an embedding. Show that for any order-preserving map $f:P\to R$, the pointwise left Kan extension $\Lan_g f$ of $f$ along $g$ satisfies $f=(\Lan_g f) \circ g$. \[ \begin{tikzcd} P \ar[rr,"f",""{name=U, below}] \ar[rd,"g"']&&R\\ &Q \ar[ur,"\Lan_g f"'] \ar["\rotatebox{90}{$=$}",phantom, to=U]& \end{tikzcd} \] \textgt{Pointwise Kan extensions along embeddings are true extensions.} The corresponding theorem in category theory can be found in \cite{context}, Corollary 6.3.9. \end{exercise} % \section{Interesting Properties of the Computation Formula} Chapter 8 presents an example where pointwise property is necessary. \begin{exercise}[An Alternate Definition of Pointwise Property]\label{DifferentDefinition} Consider an order-preserving map $r\leq -:R\to \Omega$ for an element $r$ in an ordered set $R$. For the right Kan extension $\Ran_g f$ of $f:P\to R$ along $g:P\to Q$, the pointwise property of $\Ran_g f$ is equivalent to the following condition being a right Kan extension again for any $r\in R$: \[ \begin{tikzcd}[row sep=5pt] P \ar[rr,"f",""{name=U, below}] \ar[rdd,"g"']&&R \ar[r,"r\leq -"]&\Omega && P \ar[rr,"f",""{name=V, below}] \ar[rdd,"g"']&&R\ar[r,"r\leq -"]&\Omega\\ &&&&=&&&R\ar[ur,"r\leq -"']&\\ &Q \ar[uur,"\Ran_g f"'] \ar["\rotatebox{90}{$\leq$}",phantom, to=U]& &&& &Q \ar[ur,"\Ran_{g} f"'] \ar["\rotatebox{90}{$\leq$}",phantom, to=V]&& \end{tikzcd} \] The corresponding theorem in category theory is \cite{context}, Theorem 6.3.7. \end{exercise} This alternate definition is explicitly used to introduce sufficient conditions for pointwise property. \begin{exercise}[Minimum Element Implies Pointwise] Consider the right Kan extension \[ \begin{tikzcd} P \ar[rr,"f",""{name=U, below}] \ar[rd,"g"']&&R\\ &Q \ar[ur,"\Ran_g f"'] \ar["\rotatebox{90}{$\leq$}",phantom, to=U]& \end{tikzcd} \] Suppose $R$ has a minimum element $0_R$. Show that this right Kan extension $\Ran_g f$ is a pointwise Kan extension. Use Exercise \ref{DifferentDefinition}. Take any $r\in R$ and consider \[ \begin{tikzcd}[row sep=5pt] P \ar[rr,"f",""{name=U, below}] \ar[rdd,"g"']&&R \ar[r,"r\leq -"]&\Omega && P \ar[rr,"f",""{name=V, below}] \ar[rdd,"g"']&&R\ar[r,"r\leq -"]&\Omega\\ &&&&=&&&R\ar[ur,"r\leq -"']&\\ &Q \ar[uur,"\Ran_g f"'] \ar["\rotatebox{90}{$\leq$}",phantom, to=U]& &&& &Q \ar[ur,"\Ran_{g} f"'] \ar["\rotatebox{90}{$\leq$}",phantom, to=V]&& \end{tikzcd} \] To avoid confusion, write $r\leq -:R\to \Omega$ as $s_r:R\to \Omega$. Also, define an auxiliary order-preserving map $t_r:\Omega \to R$ as \begin{align*} t_r(\text{true}) &= r\\ t_r(\text{false}) &= 0_R \end{align*} \begin{enumerate} \item Show $t_r \circ s_r \leq \id{R}$ and $\id{\omega}\leq s_r\circ t_r$\footnote{This is called a Galois connection in order set theory, or adjunction in category theory}. \item Using the first part of 1, show that for any order-preserving map $h:Q\to \Omega$ with $hg \leq s_r \circ f$, we have $t_r h g \leq f$. \item From 2 and the definition of the right Kan extension $\Ran_g f$, demonstrate $t_r h \leq \Ran_g f$. \item From the second part of 1 and 3, conclude that $h\leq s_r \Ran_g f$. \item Finally, conclude from the above and Exercise \ref{DifferentDefinition} that $\Ran_g f$ is a pointwise right Kan extension. \end{enumerate} This exercise corresponds to solving Exercise 6.3.i. in \cite{context}, using Lemma 6.3.2. \end{exercise} Before the next two exercises, define the following order-preserving map: \begin{definition}[$\yo{P}:P\to \ca{D}(P)$] For an ordered set $P$, define the ordered set $\ca{D}(P)$ and the order-preserving map $\yo{P}:P\to \ca{D}(P)$ as follows: \begin{itemize} \item A subset $S\subset P$ is closed downwards if, for any $p\in S$, all elements of $P$ less than $p$ are also in $S$. \item Define $\ca{D}(P)$ as the ordered set of all downwards closed subsets of $P$. \item Define $\yo{P}:P\to \ca{D}(P)$ by \[\yo{P}(p) \coloneqq \{ p'\in P\mid p'\leq p\}.\] \end{itemize} The corresponding concept in category theory, including the fact that $\yo{P}$ is an embedding, can be found in \cite{context}, Corollary 2.2.8. \end{definition} \begin{exercise}[Universality of Power Sets]\label{PowerSet} Consider a set $X$ with a trivial order as an ordered set. The (order-preserving) map $\yo{X}:X\to \ca{D}(X)=\ca{P}(X)$ is given by $\yo{X}(x)= \{x\}$. $\ca{P}(X)$ is a complete lattice (see Remark \ref{CompleteLattice}). Let $L$ be a complete lattice, and for an (order-preserving) map $f:X\to L$, define the order-preserving map $\hat{f}:\ca{P}(X)\to L$ as the left Kan extension guaranteed by Theorem \ref{OrderSetKanExtensionComputationFormula}: \[ \begin{tikzcd} X \ar[rr,"f",""{name=U, below}] \ar[rd,"\yo{X}"']&&L\\ &\ca{P}(X) \ar[ur,"\hat{f}"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] \begin{enumerate} \item Show that $\hat{f}$ preserves all $\sup$\footnote{To preserve $\sup$ means that the $\sup$ of a subset is equal to the $\sup$ of its image}. \item Show that the correspondence $f\mapsto \hat{f}$ provides a one-to-one correspondence between (order-preserving) maps $X\to L$ and $\sup$-preserving order-preserving maps $\ca{P}(X)\to L$. Hence, \textgt{the power set is the universal completion of a set}. \item Define the order-preserving map $\check{f}:L\to \ca{P}(X)$ by $\check{f}(l)\coloneqq \{x\in X\mid f(x)\leq l\}$. Show that for any $S\in \ca{P}(X), l\in L$, \[ S\subset \check{f}(l) \iff \hat{f}(S)\leq l \] \footnote{This is known as a Galois connection in order set theory, or adjunction in category theory}. \item Generalize this exercise's trivially ordered set $X$ to a general ordered set $P$, and conclude that \textgt{$\ca{D}(P)$ is the universal completion of $P$}. \end{enumerate} The corresponding theorem in category theory is one of the most interesting theorems related to Kan extensions, known as Nerve and realization (see \url{https://ncatlab.org/nlab/show/nerve+and+realization} or Remark 6.5.9. in \cite{context}). \end{exercise} \begin{exercise}[Density]\label{Density} An order-preserving map $f:Q\to R$ is dense if $\id{R}$ is a \textgt{pointwise} left Kan extension along $f$ of $f$ itself. \[ \begin{tikzcd} Q \ar[rr,"f",""{name=U, below}] \ar[rd,"f"']& & R \\ &R \ar[ru, "\id{R}"'] \ar["\rotatebox{90}{$\geq$}",phantom, to=U]& \end{tikzcd} \] In plain language, this means that elements of $R$ can be reconstructed (using the computation formula) solely based on their relationships with elements of $Q$. \begin{enumerate} \item For an order-preserving map $f:Q\to R$, define an order-preserving map $\check{f}:R\to \ca{D}(Q)$ by $\check{f}(r)\coloneqq \{q\in Q\mid f(q)\leq r\}$\footnote{This is the same as in Exercise \ref{PowerSet} and is theoretically the restricted Yoneda embedding}. Show that $f$ being dense is equivalent to $\check{f}$ being an embedding. \item Show that for any ordered set $P$, $\yo{P}:P\to \ca{D}(P)$ is dense. \end{enumerate} The corresponding theorem in category theory is in \cite{context}, Theorem 6.5.8, or Chapter X Section 6 in \cite{CWM}. \end{exercise} For the case where pointwise property does not hold, Chapter 8 is recommended. The last exercise on density might not fully share the motivation with readers who just solved the exercise. Hence, a familiar example of density is provided below. \begin{example}[Density in Real Numbers] An embedding $\iota:S\to \R$ of a subset $S\subset \R$ being dense means that $S$ is (topologically) dense as a subset of $\R$, i.e., for any distinct real numbers $r < r'$, there exists some $s\in S$ such that $r< s