Ian Ray. 27th September 2026.

Updated in October 2026.

In this file we construct the truncated singleton basis for the powerset sup
lattice. We also observe that any small generated sup lattice is the retract of
the powerset on its basis. Using this retraction we show that with ฮฉ-resizing a
small generated sup lattice is itself small. We conclude this file by showing
if monotone functions on powersets have least prefixed points, then so does
every monotone endomap on a sup-lattice with a small basis.

\begin{code}

{-# OPTIONS --safe --without-K #-}

open import UF.FunExt
open import UF.PropTrunc
open import UF.Subsingletons

module OrderedTypes.PowersetSmallBasisSupLattice
        (pt : propositional-truncations-exist)
        (fe : Fun-Ext)
        (pe : Prop-Ext)
       where

private
 fe' : FunExt
 fe' ๐“ค ๐“ฅ = fe {๐“ค} {๐“ฅ}

open import MLTT.Spartan
open import UF.Embeddings
open import UF.Equiv
open import UF.Logic
open import UF.Powerset-MultiUniverse
open import UF.Retracts
open import UF.Size
open import UF.SmallnessProperties
open import UF.SubtypeClassifier
open import OrderedTypes.SupLattice pt fe
open import OrderedTypes.SupLattice-SmallBasis pt fe

open AllCombinators pt fe
open PropositionalTruncation pt hiding (_โˆจ_)
open import Locales.Frame pt fe hiding (โŸจ_โŸฉ ; join-of ; rel-syntax)
open import Slice.Family

\end{code}

We show that the powerset of any given small type A is itself a sup-lattice with
small basis. To do this we first need to define the truncated singleton
construction and show that it has the proper characterization of the singleton.

\begin{code}

module _ (A : ๐“ค ฬ‡) where

 open singleton-subsets
 open unions-of-small-families pt ๐“ค ๐“ค A
 open PropositionalSubsetInclusionNotation fe
 open Joins {๐“ค โบ} {๐“ค} {๐“Ÿ {๐“ค} A} _โІโ‚š_

 ๐“Ÿ-sup-lattice : Sup-Lattice (๐“ค โบ) ๐“ค ๐“ค
 ๐“Ÿ-sup-lattice
  = (๐“Ÿ {๐“ค} A , (_โІโ‚š_ , ๐“Ÿ-sup) , (๐“Ÿ-par-ord , ๐“Ÿ-suprema))
  module ๐“Ÿ-sup-lattice-data where
   ๐“Ÿ-sup : Fam ๐“ค (๐“Ÿ A) โ†’ ๐“Ÿ {๐“ค} A
   ๐“Ÿ-sup (S , s) a = โ‹ƒ s a
   ๐“Ÿ-par-ord : is-partial-order (๐“Ÿ A) _โІโ‚š_
   ๐“Ÿ-par-ord = ((โІ-refl , โІ-trans) , subset-extensionality pe fe)
   ๐“Ÿ-suprema : (S : Fam ๐“ค (๐“Ÿ {๐“ค} A)) โ†’ ((๐“Ÿ-sup S) is-lub-of S) holds
   ๐“Ÿ-suprema (S , s)
    = (โ‹ƒ-is-upperbound s , (ฮป ((U , O) : upper-bound (S , s))
                            โ†’ โ‹ƒ-is-lowerbound-of-upperbounds s U O))

\end{code}

Note: This generalizes the definition of ๐“Ÿ-lattice from the file FreeSupLattice.

\begin{code}
 
 โด_โตโ‚œแตฃ : A โ†’ ๐“Ÿ {๐“ค} A
 โด x โตโ‚œแตฃ = ฮป (y : A) โ†’ (โˆฅ x ๏ผ y โˆฅ , โˆฅโˆฅ-is-prop)

\end{code}

Note: The total space of โด_โตโ‚œแตฃ is not contractible. While this is somewhat
pathological we will see that โด_โตโ‚œแตฃ satisfies enough of the criteria of a
singleton for our purposes.

\begin{code}

 โˆˆ-โดโตโ‚œแตฃ : {x : A} โ†’ x โˆˆ โด x โตโ‚œแตฃ
 โˆˆ-โดโตโ‚œแตฃ {x} = โˆฃ refl โˆฃ

 โดโตโ‚œแตฃ-subset-characterization : {x : A} (S : ๐“Ÿ {๐“ฅ} A) โ†’ x โˆˆ S โ†” โด x โตโ‚œแตฃ โІ S
 โดโตโ‚œแตฃ-subset-characterization {๐“ฅ} {x} S = โฆ…โ‡’โฆ† , โฆ…โ‡โฆ†
  where
   โฆ…โ‡’โฆ† : x โˆˆ S โ†’ โด x โตโ‚œแตฃ โІ S
   โฆ…โ‡’โฆ† xโˆˆS y = โˆฅโˆฅ-rec (holds-is-prop (S y)) (ฮป p โ†’ transport (_โˆˆ S) p xโˆˆS)
   โฆ…โ‡โฆ† : โด x โตโ‚œแตฃ โІ S โ†’ x โˆˆ S
   โฆ…โ‡โฆ† ฮณ = ฮณ x โˆฃ refl โˆฃ

 subset-is-โ‹ƒ-of-โดโตโ‚œแตฃ : (S : ๐“Ÿ {๐“ค} A)
                     โ†’ โ‹ƒ (โ†“แดฎ-inclusion ๐“Ÿ-sup-lattice โด_โตโ‚œแตฃ S) ๏ผ S
 subset-is-โ‹ƒ-of-โดโตโ‚œแตฃ S = subset-extensionality pe fe I III
  where
   I : โ‹ƒ (โ†“แดฎ-inclusion ๐“Ÿ-sup-lattice โด_โตโ‚œแตฃ S) โІ S
   I x = โˆฅโˆฅ-rec (holds-is-prop (S x)) II
    where
     II : ฮฃ (ฮป i โ†’ โ†“แดฎ-inclusion ๐“Ÿ-sup-lattice โด_โตโ‚œแตฃ S i x holds) โ†’ x โˆˆ S
     II ((a , aโˆˆโ†“S) , โˆฅa๏ผxโˆฅ)
      = โˆฅโˆฅ-rec (holds-is-prop (S x))
               (ฮป (p : a ๏ผ x) โ†’ transport (_โˆˆ S) p (aโˆˆโ†“S a โˆˆ-โดโตโ‚œแตฃ)) โˆฅa๏ผxโˆฅ
   III : S โІ โ‹ƒ (โ†“แดฎ-inclusion ๐“Ÿ-sup-lattice โด_โตโ‚œแตฃ S)
   III x xโˆˆS
    = โˆฃ (x , lr-implication (โดโตโ‚œแตฃ-subset-characterization S) xโˆˆS) , โˆˆ-โดโตโ‚œแตฃ โˆฃ

 โดโตโ‚œแตฃ-is-basis : is-basis ๐“Ÿ-sup-lattice โด_โตโ‚œแตฃ
 โดโตโ‚œแตฃ-is-basis
  = record{โ‰ค-is-small = I ; โ†“-is-sup = II}
  where
   open ๐“Ÿ-sup-lattice-data
   I : (S : ๐“Ÿ {๐“ค} A) (a : A) โ†’ (โด a โตโ‚œแตฃ โІ S) is ๐“ค small
   I S a = ((โด a โตโ‚œแตฃ โІ S) , โ‰ƒ-refl (โด a โตโ‚œแตฃ โІ S))
   โ†“แดฎ-Fam : (S : ๐“Ÿ {๐“ค} A) โ†’ Fam ๐“ค (๐“Ÿ A)
   โ†“แดฎ-Fam S = (โ†“แดฎ ๐“Ÿ-sup-lattice โด_โตโ‚œแตฃ S , โ†“แดฎ-inclusion ๐“Ÿ-sup-lattice โด_โตโ‚œแตฃ S)
   II : (S : ๐“Ÿ {๐“ค} A) โ†’ (S is-lub-of (โ†“แดฎ-Fam S)) holds
   II S = transport (ฮป (- : ๐“Ÿ {๐“ค} A) โ†’ (- is-lub-of (โ†“แดฎ-Fam S)) holds)
           (subset-is-โ‹ƒ-of-โดโตโ‚œแตฃ S) (๐“Ÿ-suprema (โ†“แดฎ-Fam S))
               
\end{code}

We now observe that any sup lattice L with small basis B is a retract of ๐“Ÿ B.

           L --- โ†“แดฎ ---> ๐“Ÿ B --- โ‹ ---> L
            \                          ^
             \                        /
               -------- id ----------

\begin{code}

module sup-lattice-powerset-retract
         (L : Sup-Lattice ๐“ค ๐“ฃ ๐“ฅ)
         {B : ๐“ฅ ฬ‡} (ฮฒ : B โ†’ โŸจ L โŸฉ) (h : is-basis L ฮฒ)
       where

 open is-basis h

 โ†“-map : โŸจ L โŸฉ โ†’ ๐“Ÿ {๐“ฅ} B
 โ†“-map x b = ((b โ‰คแดฎ x) , โ‰คแดฎ-is-prop-valued)

 โ†“-monotone : (x y : โŸจ L โŸฉ)
            โ†’ (x โ‰คโŸจ L โŸฉ y) holds
            โ†’ โ†“-map x โІ โ†“-map y
 โ†“-monotone x y xโ‰คy b bโˆˆโ†“x = โ‰คแดฎ-โ‰ค-to-โ‰คแดฎ bโˆˆโ†“x xโ‰คy 

 โ‹-map : ๐“Ÿ {๐“ฅ} B โ†’ โŸจ L โŸฉ
 โ‹-map S = โ‹โŸจ L โŸฉ (๐•‹ S , ฮฒ โˆ˜ ๐•‹-to-carrier S)

 โ‹-monotone : (S T : ๐“Ÿ {๐“ฅ} B)
            โ†’ S โІ T
            โ†’ (โ‹-map S โ‰คโŸจ L โŸฉ โ‹-map T) holds
 โ‹-monotone S T SโІT = joins-are-monotone L ฮฒ S T SโІT

 โ‹โˆ˜โ†“โˆผid : โ‹-map โˆ˜ โ†“-map โˆผ id
 โ‹โˆ˜โ†“โˆผid x = is-supแดฎ' x โปยน

 sup-lattice-retract-of-powerset : retract โŸจ L โŸฉ of ๐“Ÿ {๐“ฅ} B
 sup-lattice-retract-of-powerset = (โ‹-map , โ†“-map , โ‹โˆ˜โ†“โˆผid)

\end{code}

We now show in the presence of ฮฉ-resizing that any small generated sup lattice
is also small.

\begin{code}

 sup-lattice-is-small : ฮฉ-resizing ๐“ฅ โ†’ โŸจ L โŸฉ is ๐“ฅ small
 sup-lattice-is-small omega-res
  = embedded-retract-is-small sup-lattice-retract-of-powerset
     (sections-into-sets-are-embeddings โ†“-map (โ‹-map , โ‹โˆ˜โ†“โˆผid)
      (powersets-are-sets fe pe))
     (ฮ -is-small fe' (B , โ‰ƒ-refl B) (ฮป (_ : B) โ†’ omega-res))

\end{code}

Now we will investigate the connection between least prefixed points of
monotone maps on small generated sup lattices and monotone operators on the
power set.

\begin{code}

module _ (๐“ค ๐“ฃ ๐“ฅ : Universe)
         (L : Sup-Lattice ๐“ค ๐“ฃ ๐“ฅ)
         {B : ๐“ฅ ฬ‡} (ฮฒ : B โ†’ โŸจ L โŸฉ) (h : is-basis L ฮฒ)
       where

 open is-basis h

 record monotone-map-has-least-pre-fixed-point
  (f : โŸจ L โŸฉ โ†’ โŸจ L โŸฉ) (f-mono : is-monotone-endomap L f) : ๐“ค โŠ” ๐“ฃ ฬ‡ where
  field
   point : โŸจ L โŸฉ
   pre-fixed : (f point โ‰คโŸจ L โŸฉ point) holds
   least-pre-fixed : (q : โŸจ L โŸฉ) โ†’ (f q โ‰คโŸจ L โŸฉ q) holds โ†’ (point โ‰คโŸจ L โŸฉ q) holds

 monotone-map-LPFP : ๐“ค โŠ” ๐“ฃ ฬ‡
 monotone-map-LPFP = (f : โŸจ L โŸฉ โ†’ โŸจ L โŸฉ) (f-mono : is-monotone-endomap L f)
                   โ†’ monotone-map-has-least-pre-fixed-point f f-mono

module _ (๐“ค : Universe) (A : ๐“ค ฬ‡) where

 monotone-operator-LPFP : (๐“ค โบ) ฬ‡
 monotone-operator-LPFP
  = (f : ๐“Ÿ {๐“ค} A โ†’ ๐“Ÿ {๐“ค} A) (f-mono : is-monotone-endomap (๐“Ÿ-sup-lattice A) f)
  โ†’ monotone-map-has-least-pre-fixed-point
     (๐“ค โบ) ๐“ค ๐“ค (๐“Ÿ-sup-lattice A) (โด_โตโ‚œแตฃ A) (โดโตโ‚œแตฃ-is-basis A) f f-mono

\end{code}

Clearly monotone-map-LPFP ๐“คโบ ๐“ค ๐“ค implies monotone-operator-LPFP ๐“ค.

\begin{code}

monotone-map-implies-monotone-operator-LPFP
 : (A : ๐“ค ฬ‡)
 โ†’ monotone-map-LPFP (๐“ค โบ) ๐“ค ๐“ค (๐“Ÿ-sup-lattice A) (โด_โตโ‚œแตฃ A) (โดโตโ‚œแตฃ-is-basis A)
 โ†’ monotone-operator-LPFP ๐“ค A
monotone-map-implies-monotone-operator-LPFP A mon-map-LPFP = mon-map-LPFP

\end{code}

We also have that monotone-operator-LPFP ๐“ฅ implies monotone-map-LPFP ๐“ค ๐“ฃ ๐“ฅ.

\begin{code}

monotone-operator-implies-monotone-map-LPFP
 : (L : Sup-Lattice ๐“ค ๐“ฃ ๐“ฅ)
   {B : ๐“ฅ ฬ‡} (ฮฒ : B โ†’ โŸจ L โŸฉ) (h : is-basis L ฮฒ)
 โ†’ monotone-operator-LPFP ๐“ฅ B
 โ†’ monotone-map-LPFP ๐“ค ๐“ฃ ๐“ฅ L ฮฒ h
monotone-operator-implies-monotone-map-LPFP
 {๐“ค} {๐“ฃ} {๐“ฅ} L {B} ฮฒ h mon-op-LPFP f f-mono
  = record{point = p ; pre-fixed = fpโ‰คp ; least-pre-fixed = pโ‰คany}
 where
  open sup-lattice-powerset-retract L ฮฒ h
  open is-basis h
  open equational-reasoning-โ‰ค L
  mon-op : ๐“Ÿ {๐“ฅ} B โ†’ ๐“Ÿ {๐“ฅ} B
  mon-op = โ†“-map โˆ˜ f โˆ˜ โ‹-map
  mon-op-is-monotone : is-monotone-endomap (๐“Ÿ-sup-lattice B) mon-op
  mon-op-is-monotone
   = โˆ˜-is-monotone (๐“Ÿ-sup-lattice B) L (๐“Ÿ-sup-lattice B)
       โ‹-map (โ†“-map โˆ˜ f) โ‹-monotone
       (โˆ˜-is-monotone L L (๐“Ÿ-sup-lattice B) f โ†“-map f-mono โ†“-monotone)
  S : ๐“Ÿ {๐“ฅ} B
  S = monotone-map-has-least-pre-fixed-point.point
       (mon-op-LPFP mon-op mon-op-is-monotone)
  mon-opSโІS : mon-op S โІ S
  mon-opSโІS = monotone-map-has-least-pre-fixed-point.pre-fixed
               (mon-op-LPFP mon-op mon-op-is-monotone)
  SโІany : (T : ๐“Ÿ {๐“ฅ} B) โ†’ (mon-op T โІ T) โ†’ S โІ T
  SโІany = monotone-map-has-least-pre-fixed-point.least-pre-fixed
           (mon-op-LPFP mon-op mon-op-is-monotone)
  p : โŸจ L โŸฉ
  p = โ‹-map S
  fpโ‰คp : (f p โ‰คโŸจ L โŸฉ p) holds
  fpโ‰คp = f p                โ‰ค[ ๏ผ-to-โ‰ค L (โ‹โˆ˜โ†“โˆผid (f p) โปยน) ]
         โ‹-map (mon-op S)   โ‰ค[ โ‹-monotone (mon-op S) S mon-opSโІS ]
         p                  โ–ฃ
  pโ‰คany : (q : โŸจ L โŸฉ) โ†’ (f q โ‰คโŸจ L โŸฉ q) holds โ†’ (p โ‰คโŸจ L โŸฉ q) holds
  pโ‰คany q fqโ‰คq = โ‹-map S          โ‰ค[ โ‹-monotone S (โ†“-map q) II ]
                 โ‹-map (โ†“-map q)  โ‰ค[ ๏ผ-to-โ‰ค L (โ‹โˆ˜โ†“โˆผid q) ]
                 q                โ–ฃ
   where
    I : mon-op (โ†“-map q) โІ โ†“-map q
    I = โІ-trans (mon-op (โ†“-map q)) (โ†“-map (f q)) (โ†“-map q)
         (prโ‚ (โІ-refl-consequence (mon-op (โ†“-map q)) (โ†“-map (f q))
                (ap (โ†“-map โˆ˜ f) (โ‹โˆ˜โ†“โˆผid q))))
         (โ†“-monotone (f q) q fqโ‰คq)
    II : S โІ โ†“-map q
    II = SโІany (โ†“-map q) I 

\end{code}

We close the file by stating a corollary of the previous two results where we
fix a single universe level and give an equivalence between two statements
about least prefixed points. The following are equivalent

 (i) Given a type A : ๐“ค, every monotone map f : ๐“Ÿ A โ†’ ๐“Ÿ A has a least
     prefixed point.

 (ii) Given a sup lattice L : ๐“ค โบ with ๐“ค-basis (B , ฮฒ), every monotone
      map f : L โ†’ L has a least prefixed point.

\begin{code}

module _ (๐“ค : Universe) where

 least-prefixed-point-equivalence
  : ((A : ๐“ค ฬ‡) โ†’ monotone-operator-LPFP ๐“ค A)
  โ†” ((L : Sup-Lattice (๐“ค โบ) ๐“ค ๐“ค) {B : ๐“ค ฬ‡} (ฮฒ : B โ†’ โŸจ L โŸฉ) (h : is-basis L ฮฒ)
     โ†’ monotone-map-LPFP (๐“ค โบ) ๐“ค ๐“ค L ฮฒ h)
 least-prefixed-point-equivalence = (I , II)
  where
   I : ((A : ๐“ค ฬ‡) โ†’ monotone-operator-LPFP ๐“ค A)
     โ†’ ((L : Sup-Lattice (๐“ค โบ) ๐“ค ๐“ค) {B : ๐“ค ฬ‡} (ฮฒ : B โ†’ โŸจ L โŸฉ) (h : is-basis L ฮฒ)
        โ†’ monotone-map-LPFP (๐“ค โบ) ๐“ค ๐“ค L ฮฒ h)
   I mono-op-LPFP L {B} ฮฒ h 
    = monotone-operator-implies-monotone-map-LPFP L ฮฒ h (mono-op-LPFP B) 
   II : ((L : Sup-Lattice (๐“ค โบ) ๐“ค ๐“ค) {B : ๐“ค ฬ‡} (ฮฒ : B โ†’ โŸจ L โŸฉ) (h : is-basis L ฮฒ)
        โ†’ monotone-map-LPFP (๐“ค โบ) ๐“ค ๐“ค L ฮฒ h)
      โ†’ ((A : ๐“ค ฬ‡) โ†’ monotone-operator-LPFP ๐“ค A)
   II mono-map-LPFP A
    = monotone-map-implies-monotone-operator-LPFP A
       (mono-map-LPFP (๐“Ÿ-sup-lattice A) (โด_โตโ‚œแตฃ A) (โดโตโ‚œแตฃ-is-basis A)) 

\end{code}