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}